Skip to main content
3 of 5
deleted 201 characters in body
Haitao Du
  • 37.3k
  • 25
  • 148
  • 244

The problem is valid and can be solved by Projected Gradient Descent, where we project the solution to L2 ball constraint. Check my answer here for details.

In Projected Gradient Decent, the projection step is another optimization problem.In this problem, we want to find a point in $C$ (constraint set), this point is closest to a given point $x^*$. Which is $$ \underset{x \in C}{\text{arg min}} \|x-x^*\| $$

In certain cases, this optimization problem is easy to solve and have closed from for example, box constraint or L2 ball.

$$ \underset{x \in C}{\text{arg min}} \|x-x^*\|=\left\{ \begin{array}{ll} x^* & \|x^*\| \leq r \\ r \frac {x^*} {\|x\|} & \text{otherwise} \\ \end{array} \right. $$

The equation tells, if the point is inside of the constraint domain, then the projection is the point itself.

And I will demonstrate the $r \frac {x^*} {\|x\|}$ case graphically, check the points (labeled with numbers) in blue track and red track, the relationship is easy: connect the blue dots with the center of the circle, the intersection with the circle is the projection.

The following figure gives how it works visually: where the red trace is projected gradient decent trace.

enter image description here

Haitao Du
  • 37.3k
  • 25
  • 148
  • 244