Strong Duality for Semidefinite Programming
Strong Duality for Semidefinite Programming
复制标题
DOI：
10.1137/s1052623495288350
复制
发表时间：
1997-03
期刊：
影响因子：
--
通讯作者：
M. Ramana;L. Tunçel;Henry Wolkowicz
中科院分区：
文献类型：
--
作者：
M. Ramana;L. Tunçel;Henry Wolkowicz
众所周知，线性规划的对偶理论是强大而优雅的，它落后于单纯形法和内点法等算法。然而，用于非线性规划的标准拉格朗日函数需要约束限定以避免对偶间隙。半定线性规划(SDP)是线性规划的一种推广，它用矩阵变量的半定约束代替非负性约束。它在系统、控制理论和组合优化等领域有着广泛的应用。然而，SDP的拉格朗日对偶可能存在对偶缺口。讨论了半定规划中各种对偶之间的关系，给出了半定规划中强对偶的统一处理。这些二元性保证了强烈的二元性，即零对偶性差距和双重成就。这篇论文的动机是由Ramana最近的一篇论文所激发的，其中介绍了这些对偶之一。
It is well known that the duality theory for linear programming (LP) is powerful and elegant and lies behind algorithms such as simplex and interior-point methods. However, the standard Lagrangian for nonlinear programs requires constraint qualifications to avoid duality gaps. Semidefinite linear programming (SDP) is a generalization of LP where the nonnegativity constraints are replaced by a semidefiniteness constraint on the matrix variables. There are many applications, e.g., in systems and control theory and combinatorial optimization. However, the Lagrangian dual for SDP can have a duality gap. We discuss the relationships among various duals and give a unified treatment for strong duality in semidefinite programming. These duals guarantee strong duality, i.e., a zero duality gap and dual attainment. This paper is motivated by the recent paper by Ramana where one of these duals is introduced.