Convex Optimization · Problem 6.7

Statistical estimation — Boyd & Vandenberghe

Mathematics — Optimization · bi-criterion-euclidean-norms-svd

Problem

Bi-criterion optimization with Euclidean norms. We consider the bi-criterion optimization problem minimize (w.r.t. R+2)(∥Ax−b∥22, ∥x∥22),\text{minimize (w.r.t. } \mathbf{R}^2_+) \quad (\|Ax - b\|_2^2,\, \|x\|_2^2), where A∈Rm×nA \in \mathbf{R}^{m \times n} has rank rr, and b∈Rmb \in \mathbf{R}^m. Show how to find the solution of each of the following problems from the singular value decomposition of AA, A=U diag(σ)VT=∑i=1rσiuiviTA = U\,\mathbf{diag}(\sigma)V^T = \sum_{i=1}^r \sigma_i u_i v_i^T (see \S A.5.4). (a) Tikhonov regularization: minimize ∥Ax−b∥22+δ∥x∥22\|Ax - b\|_2^2 + \delta\|x\|_2^2. (b) Minimize ∥Ax−b∥22\|Ax - b\|_2^2 subject to ∥x∥22=γ\|x\|_2^2 = \gamma. (c) Maximize ∥Ax−b∥22\|Ax - b\|_2^2 subject to ∥x∥22=γ\|x\|_2^2 = \gamma. Here δ\delta and γ\gamma are positive parameters. Your results provide efficient methods for computing the optimal trade-off curve and the set of achievable values of the bi-criterion problem.

Related theory

Browse the problem library