### Joint DOS/ACO Seminar - The reflex algorithm - Convex optimization by random reflection

- Series
- Other Talks
- Time
- Wednesday, March 17, 2010 - 13:30 for 1 hour (actually 50 minutes)
- Location
- ISyE Executive Classroom
- Speaker
- Merrick Furst – College of Computing, Georgia Tech

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.