Second-order Cone Programming : Algorithms and Applications

大二阶锥规划：算法与应用。Donald Goldfarb和Garud iyengar。摘要。二阶锥规划（SOCPs）是一种凸优化问题，其中线性函数在仿射线性流形与二阶（洛伦兹）锥的笛卡尔积的交点上进行优化。线性规划（lp）、凸二次规划（qp）和二次约束凸二次规划都可以表示为socp，许多不属于这三个问题类别的其他问题也可以表示为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.