accelerate convex optimization by proximal projection

Question

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.

Answer 1

There is abundant literature about stuff like this but it can be hard to find the framework that is best suited for your case.

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.

This is just one possibility and it is not clear if this would be useful in your contexts (e.g., if the number of linear constraints is very large, convergence may be slow; but on the other hand, if the iteration become very quick you still may have some speedup).