Projected Gradient Algorithm

← Back to document page

Projected Gradient AlgorithmAndersen AngMath ematique et recherche op erationnelleUMONS, draft: August 2, 2017Last update : October 23, 2020Overview1Constrained and unconstrained problem2Understanding the geometry of projection3PGD is a special case of proximal gradient4Theorem 1. An inequality of PGD with constant stepsize5Theorem 2. PGD converges at orderO(1 k)on Lipschitz function6Summary2 / 22Constrained and unconstrained problemIFor unconstrained minimization problemminx Rnf(x),anyxinRncan be a constrained minimization problem with a given setQ Rnminx Qf(x),not anyxcan be a solution, the solution has to be inside the example of constrained minimization problem:minx Rn Ax b x 2 1can be expressed asmin x 2 1 Ax b / 22Solving unconstrained problem by Gradient descentIGradient Descent(GD) is a standard (easy and simple) way to solveunconstrainedoptimization from an initial pointx0 Rn, GD iterates the followingequation until a stopping condition is met:xk+1=xk k f(xk),where fis the Gradient off, the parameter 0is the step size,andkis the iteration.

Oct 23, 2020 · Q(:) is a function from Rnto Rn, and itself is an optimization problem: P Q(x 0) = argmin x2Q 1 2 kx x 0k2 2: I PGD is an \economic" algorithm if the problem is easy to solve. This is not true for general Qand there are lots of constraint sets that are very di cult to project onto. I If Qis a convex set, the optimization problem has a unique ...

  Projected, Algorithm, Optimization, Convex, Derating, Projected gradient algorithm