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