Standard interior point methods in semidefinite programming track a solution path for a homotopy defined by a system of polynomial equations. By viewing this in the context of numerical algebraic geometry, we are able to employ techniques to handle various cases which can arise. Adaptive precision path tracking techniques can help navigate around ill-conditioned areas. When the optimizer is singular with respect to the first-order optimality conditions, endgames can be used to efficiently and accurately compute the optimizer. When the optimal value is not achievable, the solution path diverges to infinity with current software implementations needing to decide when to truncate the tracking of such a path. By using projective space, this path always has finite length so that the endpoint can be accurately computed using endgames. With these numerical algebraic geometric methods, we describe feasibility tests and a solving approach for both primal and dual problems, and employ them on various examples.
Numerical algebraic geometry and semidefinite programmingDataset
|Departments and Units|
|Record Visibility and Access||Public|
Digital Object Identifier
This DOI is the best way to cite this dataset.