2
$\begingroup$

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.

$\endgroup$

2 Answers 2

5
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ >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? $\endgroup$
    – user15459
    May 29, 2011 at 23:40
  • $\begingroup$ Great answer, I would like to add that the gradient method might converge to some local solution but global optimality is not ensured. $\endgroup$
    – mikitov
    Oct 13, 2011 at 12:58
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The question was specifically about non-convex sets, so it's not clear how these references are helpful. $\endgroup$ Jun 26, 2013 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.