Numerical algebraic geometry and semidefinite programming

Dataset

Description

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.

Attributes

Attribute NameValues
Creator
  • Jonathan Hauenstein

  • Alan Liddell

  • Yi Zhang

Publisher
  • Jonathan Hauenstein

Departments and Units
Record Visibility and Access Public
Content License
  • All rights reserved

Digital Object Identifier

doi:10.7274/R0D798G4

This DOI is the best way to cite this dataset.


Files

Please Note: You may encounter a delay before a download begins. Large or infrequently accessed files can take several minutes to retrieve from our archival storage system.