# accelerate convex optimization by proximal projection

I am using level method to solve non-smooth convex programming problem (where the objective function is given by an oracle from another program ): http://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf chapter 8.2.1

Basically, every iteration a projection of a point into a polytope is needed to be done, and I am using Gurobi (Quadratic programming) to achieve this. However, as my problem dimension could be rather high, say n=5000, an exact projection is slow (takes roughly 20s where as the oracle can be fast taking only 0.5s to compute) and 5000 iterations is needed. I am wondering whether there is way walking around this difficulty, since only a good projection is needed and exact projection is not needed. Thank you.

• can't you just stop your quadratic optimisations early? Jan 23, 2015 at 10:07
• possible crosspost Mar 12, 2015 at 3:19

For example there is quite general theory in "Incremental subgradients for constrained convex optimization: a unified framework and new methods", Elias Salomão Helou Neto, Álvaro Rodolfo De Pierro, SIAM Journal on Optimization 20 (3), 1547-1572 where "subgradient projections" are used. To use this, you can desribe your feasible set by inequalites of the form $g(x)\leq 0$ with convex (not necessarily smooth) functions $g$ and do "subgradient steps" for the functions $g$ if the constraint is not fulfilled. Note that you can have a number of these constraints and treat them sequentially/incrementally. So if you have a polytope as constraint, you can iteratively use subgradient projections (or even projections) onto the hyperplanes defining the polytope.