Numerical algebraic geometry and semidefinite programming

Abstract

Standard interior point methods in semidefinite programming can be viewed as tracking a solution path for a homotopy defined by a system of bilinear equations. By considering this in the context of numerical algebraic geometry, we employ numerical algebraic geometric techniques such as adaptive precision path tracking, endgames, and projective space to accurately solve semidefinite programs. We develop feasibility tests for both primal and dual problems which can distinguish between the four feasibility types of semidefinite programs. Finally, we couple our feasibility tests with facial reduction to develop a solving approach that can handle every scenario arising in semidefinite programming, including problems with nonzero duality gap. Various examples are used to demonstrate the new methods with comparisons to commonly used semidefinite programming software.

Keywords

• Numerical algebraic geometry
• Semidefinite programming
• Infeasible
• Facial reduction
• Homotopy continuation
• Projective space