Convex Optimization Research Notebook

Proof Sketch: Outer Approximation Acceleration of Averaged Projections


A simple but potentially powerful acceleration scheme: perform averaged projections and then solve a small QP in which you project the averaged iterate onto the intersection of the halfspaces that the projection nets you. It is not difficult to show that this algorithm converges to an optimal solution. Below is a proof sketch.