Georgia Institute of Technology College of Sciences

Santosh Vempala and I have been exploring an intriguing new approach to convex optimization. Intuition about first-order interior point methods tells us that a main impediment to quickly finding an inside track to optimal is that a convex body's boundary can get in one's way in so many directions from so many places. If the surface of a convex body is made to be perfectly reflecting then from every interior vantage point it essentially disappears. Wondering about what this might mean for designing a new type of first-order interior point method, a preliminary analysis offers a surprising and suggestive result. Scale a convex body a sufficient amount in the direction of optimization. Mirror its surface and look directly upwards from anywhere. Then, in the distance, you will see a point that is as close as desired to optimal. We wouldn't recommend a direct implementation, since it doesn't work in practice. However, by trial and error we have developed a new algorithm for convex optimization, which we are calling Reflex. Reflex alternates greedy random reflecting steps, that can get stuck in narrow reflecting corridors, with simply-biased random reflecting steps that escape. We have early experimental experience using a first implementation of Reflex, implemented in Matlab, solving LP's (can be faster than Matlab's linprog), SDP's (dense with several thousand variables), quadratic cone problems, and some standard NETLIB problems.