Optimization over structured subsets of positive semidefinite matrices via column generation
Optimization over structured subsets of positive semidefinite matrices via column generation
复制标题
通过列生成对半正定矩阵的结构化子集进行优化
DOI：
10.1016/j.disopt.2016.04.004
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
G. Hall
中科院分区：
文献类型：
--
作者：
Amir Ali Ahmadi;S. Dash;G. Hall
利用线性规划和二阶锥规划，给出了构造正半定矩阵锥的内逼近的算法。从Ahmadi和Majumdar最近提出的初始线性代数近似开始，我们描述了一个迭代过程，通过这个过程，我们的近似在每一步都得到改进。这是使用大规模线性规划中的列生成思想来完成的。然后，我们将这些技术应用于近似平方和锥的非凸多项式优化设置，以及对离散优化问题的合成锥。
We develop algorithms to construct inner approximations of the cone of positive semidefinite matrices via linear programming and second order cone programming. Starting with an initial linear algebraic approximation suggested recently by Ahmadi and Majumdar, we describe an iterative process through which our approximation is improved at every step. This is done using ideas from column generation in large-scale linear programming. We then apply these techniques to approximate the sum of squares cone in a nonconvex polynomial optimization setting, and the copositive cone for a discrete optimization problem.