# Optimization with weaker oracle than projection

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

## 1 Answer

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.

• 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. – yon Aug 31 '19 at 13:19