Numerical algebraic geometry and semidefinite programming

作     者：Hauenstein, Jonathan D. Liddell, Jr Alan C. McPherson, Sanesha Zhang, Yi 

作者机构：Univ Notre Dame Dept Appl & Computat Math & Stat Notre Dame IN 46556 USA Vidrio Technol Ashburn VA USA North Carolina Cent Univ Dept Math & Phys Durham NC USA Univ North Carolina Greensboro Dept Math & Stat Greensboro NC USA 

出 版 物：《RESULTS IN APPLIED MATHEMATICS》 (Result. Appl. Math.)

年 卷 期：2021年第11卷

核心收录：

基　　金：Office of Naval Research [N00014-16-1-2722] National Science Foundation [ACI-1460032, CCF-1812746] Sloan Research Fellowship [BR2014-110 TR14] 

主　　题：Numerical algebraic geometry Semidefinite programming Infeasible Facial reduction Homotopy continuation Projective space 

摘      要：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. (C) 2021 The Author(s). Published by Elsevier B.V.