5
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Aug 31, 2019 at 13:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .