Projected Gradient Algorithm

Projected Gradient AlgorithmAndersen AngMath ematique et recherche op erationnelleUMONS, draft: August 2, 2017 Last update : October 23, 2020 Overview1 Constrained and unconstrained problem2 Understanding the geometry of projection3 PGD is a special case of proximal gradient4 Theorem 1. An inequality of PGD with constant stepsize5 Theorem 2. PGD converges at orderO(1 k)on Lipschitz function6 Summary2 / 22 Constrained 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 / 22 Solving 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 ...

Loading..

Tags:

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

Information

Related search queries