Conic Cutting Surface Algorithms
Conic Cuts, John E. Mitchell, Vasile L. Basescu · 2006
The problem of finding a feasible point in a fully dimensional set in a finite dimensional Hilbert space is analyzed. An analytic center cutting surface algorithm is developed that adds conic cuts. The algorithm generalizes similar LP, SDP, and SOCP approaches. It is shown that the algorithm is fully polynomial, with the complexity dependent on a condition number of the cuts. The algorithm is refined by modifying the cuts, which allows the derivation of a complexity result that does not depend on this condition number. Mitchell http://www.rpi.edu/~mitchj Conic Cutting Surface Algorithms Outline Conic Cuts Selective Orthonormalization Conclusions Convex feasibility problem Cutting planes Restarting Convergence Convex feasibility problem Given a set Y , find a point y ∈ Y or determine that Y is empty. Assumptions: I Y is a convex, bounded set contained in I Rm, containing a ball B(., ) of radius . I If ȳ 6∈ Y , a separation oracle returns a conic inequality G∗y + s = h, s ∈ K0 satisfied by all y ∈ Y and violated by ȳ . K0 is a full-dimensional self-scaled cone in IRp. I Assume the cone K0 has a self-concordant barrier function f0(K0). Mitchell http://www.rpi.edu/~mitchj Conic Cutting Surface Algorithms Outline Conic Cuts Selective Orthonormalization Conclusions Convex feasibility problem Cutting planes Restarting Convergence Convex feasibility problem