Convex Optimization · Problem 10.2

Interior-point methods — Boyd & Vandenberghe

Mathematics — Optimization · projected-gradient-method

Problem

Projected gradient method. In this problem we explore an extension of the gradient method to equality constrained minimization problems. Suppose ff is convex and differentiable, and x∈dom fx \in \mathbf{dom}\, f satisfies Ax=bAx = b, where A∈Rp×nA \in \mathbf{R}^{p \times n} with rank A=p<n\mathbf{rank}\, A = p < n. The Euclidean projection of the negative gradient −∇f(x)-\nabla f(x) on N(A)\mathcal{N}(A) is given by Δxpg=argmin⁡Au=0∥−∇f(x)−u∥2.\Delta x_{\text{pg}} = \operatorname*{argmin}_{Au=0} \|-\nabla f(x) - u\|_2. ((a)) Let (v,w)(v, w) be the unique solution of [IATA0][vw]=[−∇f(x)0].\begin{bmatrix} I & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = \begin{bmatrix} -\nabla f(x) \\ 0 \end{bmatrix}. Show that v=Δxpgv = \Delta x_{\text{pg}} and w=argmin⁡y∥∇f(x)+ATy∥2w = \operatorname*{argmin}_y \|\nabla f(x) + A^T y\|_2. ((b)) What is the relation between the projected negative gradient Δxpg\Delta x_{\text{pg}} and the negative gradient of the reduced problem (10.5), assuming FTF=IF^T F = I? ((c)) The projected gradient method for solving an equality constrained minimization problem uses the step Δxpg\Delta x_{\text{pg}}, and a backtracking line search on ff. Use the results of part (b) to give some conditions under which the projected gradient method converges to the optimal solution, when started from a point x(0)∈dom fx^{(0)} \in \mathbf{dom}\, f with Ax(0)=bAx^{(0)} = b.

Related theory

Browse the problem library