Convex Optimization · Problem 9.25

Equality constrained minimization — Boyd & Vandenberghe

Mathematics — Optimization · smoothed-fit-given-data

Problem

Smoothed fit to given data. Consider the problem minimizef(x)=∑i=1nψ(xi−yi)+λ∑i=1n−1(xi+1−xi)2\text{minimize} \quad f(x) = \sum_{i=1}^n \psi(x_i - y_i) + \lambda \sum_{i=1}^{n-1} (x_{i+1} - x_i)^2 where λ>0\lambda > 0 is smoothing parameter, ψ\psi is a convex penalty function, and x∈Rnx \in \mathbf{R}^n is the variable. We can interpret xx as a smoothed fit to the vector yy. ((a)) What is the structure in the Hessian of ff? ((b)) Extend to the problem of making a smooth fit to two-dimensional data, i.e., minimizing the function ∑i,j=1nψ(xij−yij)+λ(∑i=1n−1∑j=1n(xi+1,j−xij)2+∑i=1n∑j=1n−1(xi,j+1−xij)2),\sum_{i,j=1}^n \psi(x_{ij} - y_{ij}) + \lambda \left( \sum_{i=1}^{n-1} \sum_{j=1}^n (x_{i+1,j} - x_{ij})^2 + \sum_{i=1}^n \sum_{j=1}^{n-1} (x_{i,j+1} - x_{ij})^2 \right), with variable X∈Rn×nX \in \mathbf{R}^{n \times n}, where Y∈Rn×nY \in \mathbf{R}^{n \times n} and λ>0\lambda > 0 are given.

Browse the problem library