I'm looking to solve the optimization problem $$ min_{x \in C} ~ f(x), $$ where $C \subset R^n$ is a closed, convex, bounded set and $f : R^n \to R$ a Lipschitz differentiable (nonconvex) function.

In my problem, $C$ is the solution set of a difficult convex optimization problem, so the projection onto $C$ and also a linear minimization oracle are intractable to compute in closed-form, thus projected gradient or Frank-Wolfe methods are not applicable.

However, I can efficiently compute a separating hyperplane between a point $\bar x$ and the set $C$. My question is whether iterations of the type

$$ \bar x^{t+1} = x^t - \alpha_t \nabla f(x^t), $$ $$ x^{t+1} = \text{proj}_H(\bar x^{t+1}), $$ have been analyzed in literature or have hope of converging to a stationary point. Here $\{ \alpha_t \}$ is a suitable vanishing step-size sequence, and $proj_H$ the projection onto a separating half-space to the set $C$ at point $\bar x^{t+1}$.


I would guess that the method is going to converge (weakly), even with constant stepsizes. Off the top of my head I don't know a precise reference. The method is close in spirit to the "hybrid projection proximal point method" by Solodov and Svaiter, but you have a gradient step instead of a proximal step.

  • $\begingroup$ Thanks for the reference! Similar to that work, my separating hyper-plane H to the solution set is obtained with a proximal point step. The difference is the additional gradient step. I suspect that with constant step-sizes the method is not guaranteed to converge, since even when initialized at a stationary point, the gradient step might move away from that point and the projection onto the separating hyperplane does not necessarily go back to the right location. $\endgroup$ – yon Aug 31 '19 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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