Second-order cone programming
Second-order cone programming
复制标题
DOI：
10.1007/s10107-002-0339-5
复制
发表时间：
2003-01-01
影响因子：
2.7
通讯作者：
Goldfarb, D
中科院分区：
文献类型：
--
作者：
Alizadeh, F;Goldfarb, D
二阶锥规划 (SOCP) 问题是凸优化问题，其中线性函数在仿射线性流形与二阶 (洛伦兹) 锥的笛卡尔积的交点上最小化。线性规划、凸二次规划和二次约束凸二次规划都可以表述为 SOCP 问题，许多其他不属于这三类的问题也可以表述为 SOCP 问题。后面这些问题对从工程、控制和金融到鲁棒优化和组合优化等广泛领域的应用进行了建模。另一方面，半定规划 (SDP)——即仿射集和正半定矩阵锥体的交集的优化问题——包括 SOCP 作为一个特例。因此，SOCP 介于线性 (LP) 和二次 (QP) 规划以及 SDP 之间。与 LP、QP 和 SDP 问题一样，SOCP 问题可以通过内点法在多项式时间内求解。这些方法解决 SOCP 问题所需的每次迭代计算量大于解决 LP 和 QP 问题所需的计算量，但小于解决类似大小和结构的 SDP 所需的计算量。由于 SOCP 问题的可行解集不像 LP 和 QP 问题那样是多面体，因此如何为 SOCP 开发单纯形或类单纯形方法并不明显。虽然 SOCP 问题可以作为 SDP 问题来解决，但出于数值基础和计算复杂性考虑，这样做并不可取。例如，Vandenberghe 和 Boyd [VB96] 的调查论文中作为 SDP 示例提出的许多问题实际上可以表述为 SOCP，并且应该这样解决。在下面的第 2、3 节中，我们给出了其中四个示例的 SOCP 公式：凸二次约束二次规划 (QCQP) 问题、涉及分数二次函数的问题
Second-order cone programming (SOCP) problems are convex optimization problems in which a linear function is minimized over the intersection of an affine linear manifold with the Cartesian product of second-order (Lorentz) cones. Linear programs, convex quadratic programs and quadratically constrained convex quadratic programs can all be formulated as SOCP problems, as can many other problems that do not fall into these three categories. These latter problems model applications from a broad range of fields from engineering, control and finance to robust optimization and combinatorial optimization. On the other hand semidefinite programming (SDP)—that is the optimization problem over the intersection of an affine set and the cone of positive semidefinite matrices—includes SOCP as a special case. Therefore, SOCP falls between linear (LP) and quadratic (QP) programming and SDP. Like LP, QP and SDP problems, SOCP problems can be solved in polynomial time by interior point methods. The computational effort per iteration required by these methods to solve SOCP problems is greater than that required to solve LP and QP problems but less than that required to solve SDP’s of similar size and structure. Because the set of feasible solutions for an SOCP problem is not polyhedral as it is for LP and QP problems, it is not readily apparent how to develop a simplex or simplex-like method for SOCP. While SOCP problems can be solved as SDP problems, doing so is not advisable both on numerical grounds and computational complexity concerns. For instance, many of the problems presented in the survey paper of Vandenberghe and Boyd [VB96] as examples of SDPs can in fact be formulated as SOCPs and should be solved as such. In § 2, 3 below we give SOCP formulations for four of these examples: the convex quadratically constrained quadratic programming (QCQP) problem, problems involving fractional quadratic functions