MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Projected gradient descent for non-convex optimization problems

Hi All,

My question is in regards to the minimization of a convex function where the feasible set of solutions is non-convex. Can projected gradient descent (PGD) be used here to obtain a stationary solution?

By PGD, I am referring to the process of stepping in the negative direction of the gradient and then projecting the current solution unto the feasible set. Let's assume that the projector unto the non-convex set exists and is unique.

-

First, I'm assuming that your nonconvex feasible set $D$ is a subset of some larger convex set $C$ on which the objective function $f(x)$ is defined. It doesn't really make sense to talk about $f(x)$ being convex without its being defined on some convex set.

Also, to specify the projected (sub)gradient algorithm more precisely, you have to give a step size selection rule. For example, you might use

$x_{k+1} = x_{k}= -\alpha_{k} \nabla f(x_{k})$

where $\alpha_{k}=1/k$.

There are proofs of convergence for the projected subgradient descent method on convex feasible sets for various step size rules.

In general this doesn't work on a nonconvex feasible set. The proof of convergence on a convex feasible set constructs a sequence of solutions which converges to an optimal solution, Although there certainly will be such a sequence in $C$, it might not exist in $D$.

For example, let

$f(x)=|x|$.

Let $D$ be the set $\{ -1,2 \}$. If we start at $x_1=2$, then the projected subgradient algorithm with the step size rule above produces the sequence $x_{2}=2$, $x_{3}=2$, $\ldots$, which doesn't converge to the the minimum at $x=-1$.

-
 Thanks Brian for the comments! – Bernard Mar 29 2011 at 5:26 Great answer, I would like to add that the gradient method might converge to some local solution but global optimality is not ensured. – mikitov Oct 13 2011 at 12:58

There are proofs of convergence for the projected subgradient descent method on convex feasible sets for various step size rules.

Do you have reference for this proof?

-

This is a very good reference and has proofs for various step-size rules.

Nonlinear programming,Bertsekas, D.P.,1999 Chapter 2: gradient methods over a convex set.

You can also check "Optimization: algorithms and consistent approximations" By Elijah Polak.

-