Second-order Cone Programming : Algorithms and Applications

二阶圆锥规划：算法与应用

• 批准号: 0104282
• 负责人: Donald Goldfarb
• 金额: $ 24万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-01 至 2005-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0104282&HistoricalAwards=false
• 关键词: Second; order; Cone; Programming; Algorithms

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.

大型二阶锥规划：算法与应用。 作者声明：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，因为其可行集是非多面体的。拟议的研究重点关注SOCP的几个方面，包括开发利用数据稀疏性的SOCP数值稳定算法、研究基于SOCP的硬组合优化问题近似算法、研究混合0-1 SOCP的切割生成方法的计算方面以及SOCP在鲁棒金融优化中的应用。SOCP是一种优秀的模型，适用于从工程、控制和金融到鲁棒组合优化的广泛领域。SOCP的广泛适用性和高效，数值稳定的算法来解决它们的需要，使他们的研究值得。