How is the minimization part done in projected gradient descent?

Question

It says to do:

$$y_{k+1}=x_k-t^{(k)}\partial f(x^{(k)})$$

where $x_{k+1}=\min_{z \in \chi} \|x-z\|$

So is one supposed to solve the $x_{k+1}$ using some other minimization method? Or what is one supposed to do?

Typically depends on the problem (i.e. what the set $\chi$ is). For example, if $\chi$ is the $\ell2$ unit ball, then the projection subproblem has a closed-form solution. For very complicated sets, you might not be able to do it practically. — David M., Feb 02 '19 at 02:41

score 0 · Answer 1 · answered Jun 05 '19 at 08:03

You probably meant: $$ y_{k+1}=x_k-t^{(k)}\partial f(x^{(k)}) $$

where $x_{k+1}=\min_{z \in \chi} \|y_{k+1}-z\|$.

How to project will depend on your set $\chi$. Some projections are easy to enforce. For instance if you have to satisfy $ ||Fx||_2^2 = P $, you will have to normalize the power of your solution $x_{k+1}$ such that the conatraint above is respected.

How is the minimization part done in projected gradient descent?

1 Answers1