Solving constrained optimization problem: projected gradient vs. dual?

Question

I recently got to know about projected gradient descent and have a question. My understanding is that when you have constrained optimization problem, you use the duality to solve an easier dual problem, which also gives an answer to the original problem. Is the projected gradient descent just another method for solving constrained optimization problems? If so, when do people use the projected gradient descent instead of duality and vice versa?

Answer 1

Essentially yes, projected gradient descent is another method for solving constrained optimization problems. It's only useful when the projection operation is easy or has a closed form, for example, box constraints or linear constraint sets.

Besides directly solving constrained problems with simple constraint sets, it can be used on the dual with good results on some problems. For instance, there are many problems where the primal is unconstrained but involves non-smooth terms. By taking the dual the non-smooth terms can be (often) converted to simple constraints, leaving the rest of the problem differentiable. Projected gradient descent can then be used. Examples of this include L1 norm regularized problems; I particularly like this application of the technique.

Answer 2

AaronDefazio had a very good answer:

It's only useful when the projection operation is easy or has a closed form, for example, box constraints or linear constraint sets.

I am just adding some details and an example of this statement.

Note that, 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. AaronDefazio mentioned box constraint and linear constraint set. I will use an even simpler example, sphere constraint to demonstrate (Sphere constraint is L2, and box constraint is L1).

$$ \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 (gray dashed line), the intersection with the circle is the projection.

The whole point of this example is trying to show finding the projection is easy and intuitive in this case, and it has a closed form solution. On the other hand, if we have a very complicated $C$, solving $\underset{x \in C}{\text{arg min}} \|x-x^*\|$ will be not this trivial. In such case, we may not use projected gradient descent.