Second-order Cone Programming : Algorithms and Applications

大型二阶锥规划：算法与应用。 作者声明：by Donald Goldfarb，Garud Iyengar.二阶锥规划（Second-order cone programmes，SOCPs）是凸优化问题，其中线性函数在仿射线性流形与二阶（洛伦兹）锥的笛卡尔积的交集上进行优化。 线性规划（LP）、凸二次规划（QP）和二次约束凸二次规划都可以用SOCP表示，许多其他问题也可以不属于这三个问题类别。另一方面，由于二阶锥约束等价于线性矩阵不等式，半定规划（SDP）包括SOCP作为特殊情况。 从计算上讲，SOCP福尔斯介于LP或QP和SDP之间。内点方法在多项式时间内解决了所有这些问题。尽管求解SOCP所需的计算工作量大于求解LP或QP所需的计算工作量，但它基本上小于求解类似大小和结构的SDP所需的计算工作量。然而，在许多方面，SOCP比LP或QP更接近SDP，因为其可行集是非多面体的。该研究主要集中在几个方面的SOCPs，包括发展的数值稳定算法的SOCPs，利用稀疏的数据，基于SOCPs的近似算法的研究，硬组合优化问题，研究的计算方面的切割生成方法的混合0-1 SOCPs和SOCPs在稳健的金融优化的应用。SOCP是一种优秀的模型，适用于从工程、控制和金融到鲁棒组合优化的广泛领域。SOCP的广泛适用性和高效，数值稳定的算法来解决它们的需要，使他们的研究值得。

Large Second-order Cone Programming: Algorithms and Applications.PI. Donald Goldfarb and Garud Iyengar.Abstract. Second-order cone programs (SOCPs) are convex optimization problems in which a linear function is optimized over the intersection of an affine linear manifold with the Cartesian product of second-order (Lorentz) cones. Linear programs (LPs), convex quadratic programs (QPs), and quadratically constrained convex quadratic programs can all be formulated as SOCPs, as can many other problems that do not fall into these three problem classes. On the other hand, since a second-order cone constraint is equivalent to a linear matrix inequality, semidefinite programs (SDPs) include SOCPs as a special case. Computationally speaking, an SOCP falls between an LP or a QP and an SDP. Interior point methods solve all of these problems in polynomial time. Although, the computational effort required to solve an SOCP is greater than that required to solve an LP or a QP, it is substantially less than that required to solve an SDP of similar size and structure. However, in many ways, an SOCP is closer to an SDP than an LP or QP since its feasible set is non-polyhedral. The proposed research focuses on several aspects of SOCPs, including the development of numerically stable algorithms for SOCPs that take advantage of sparsity in the data, the study of SOCP-based approximation algorithms for hard combinatorial optimization problems, the study of computational aspects of cut generation methods for mixed 0-1 SOCPs and the applications of SOCPs in robust financial optimization. SOCPs are excellent models for applications that arise in a broad range of fields from engineering, control, and finance, to robust and combinatorial optimization. The wide applicability of SOCPs and the need for efficient, numerically stable algorithms to solve them makes their study worthwhile.