Projected gradient method

From Glossary

Jump to: navigation, search

A feasible direction is obtained for the region LaTeX: \textstyle \left \{x: Ax=b \right \} by projecting the gradient of the objective function to the null space of LaTeX: \textstyle A: d = P \nabla f(x), where LaTeX: \textstyle P = \begin{bmatrix}I - A^T[AA^T]^{-1} & A \end{bmatrix} (note LaTeX: A[Py] = 0 for all LaTeX: y, so LaTeX: \textstyle \left \{Py \right \} is the null space of LaTeX: A). Thus, LaTeX: x + ad is feasible for all feasible LaTeX: x and all LaTeX: a > 0 (since LaTeX: Ad=0). Further, if LaTeX: \textstyle P \nabla f(x) \ne 0, LaTeX: f(x+ad) = f(x) + a \nabla f(x)' P \nabla f(x) > f(x) for LaTeX: \textstyle a > 0, so the objective value improves each iteration until its projected gradient is null. At that point where LaTeX: \textstyle P \nabla f(x)=0, x satisfies first-order conditions.

Personal tools