Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

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

share|improve this answer
    
Thanks Brian for the comments! –  Bernard Mar 29 '11 at 5:26
    
>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? –  user15459 May 29 '11 at 23:40
    
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 '11 at 12:58
add comment

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.

share|improve this answer
    
The question was specifically about non-convex sets, so it's not clear how these references are helpful. –  Christian Clason Jun 26 '13 at 16:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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