Georgia Institute of Technology College of Sciences

Santosh Vempala and I have been exploring an intriguing newapproach to convex optimization. Intuition about first-order interiorpoint methods tells us that a main impediment to quickly finding aninside track to optimal is that a convex body's boundary can get inone's way in so many directions from so many places. If the surface ofa convex body is made to be perfectly reflecting then from everyinterior vantage point it essentially disappears. Wondering about whatthis might mean for designing a new type of first-order interior pointmethod, a preliminary analysis offers a surprising and suggestiveresult. Scale a convex body a sufficient amount in the direction ofoptimization. Mirror its surface and look directly upwards fromanywhere. Then, in the distance, you will see a point that is as closeas desired to optimal. We wouldn't recommend a direct implementation,since it doesn't work in practice. However, by trial and error we havedeveloped a new algorithm for convex optimization, which we arecalling Reflex. Reflex alternates greedy random reflecting steps, thatcan get stuck in narrow reflecting corridors, with simply-biasedrandom reflecting steps that escape. We have early experimentalexperience using a first implementation of Reflex, implemented inMatlab, solving LP's (can be faster than Matlab's linprog), SDP's(dense with several thousand variables), quadratic cone problems, andsome standard NETLIB problems.