论文标题
半限定，线性和二次编程的中央曲线程度
The degree of the central curve in semidefinite, linear, and quadratic programming
论文作者
论文摘要
Zariski闭合中心路径，内部点算法在凸优化问题（例如线性，二次和半决赛程序）中跟踪的Zariski闭合是一个代数曲线。已经研究了有关这些内点算法的复杂性的该曲线的程度，对于线性程序，该曲线是由De Loera，Sturmfels和Vinzant在2012年计算的。我们显示，通用半限制程序的中心曲线程度等于最大的线性浓度模型的可能性。完全四边形空间的交点理论的新结果表明，这是半多项式的半多项矩阵，其程度等于约束数量。除了其程度外，我们还探索了同一曲线的算术属。我们还计算了具有不同技术的通用线性程序的中央曲线程度，这些技术扩展到通用二次程序的相同程度。
The Zariski closure of the central path which interior point algorithms track in convex optimization problems such as linear, quadratic, and semidefinite programs is an algebraic curve. The degree of this curve has been studied in relation to the complexity of these interior point algorithms, and for linear programs it was computed by De Loera, Sturmfels, and Vinzant in 2012. We show that the degree of the central curve for generic semidefinite programs is equal to the maximum likelihood degree of linear concentration models. New results from the intersection theory of the space of complete quadrics imply that this is a polynomial in the size of semidefinite matrices with degree equal to the number of constraints. Besides its degree we explore the arithmetic genus of the same curve. We also compute the degree of the central curve for generic linear programs with different techniques which extend to bounding the same degree for generic quadratic programs.
