Facial Reduction Algorithms for Conic Optimization Problems
Facial Reduction Algorithms for Conic Optimization Problems
复制标题
DOI：
10.1007/s10957-012-0219-y
复制
发表时间：
2012-11
影响因子：
1.9
通讯作者：
Hayato Waki;M. Muramatsu
中科院分区：
文献类型：
--
作者：
Hayato Waki;M. Muramatsu
众所周知，在二次优化问题中，可能会出现正对偶间隙，并且求解这样的问题在数值上是困难的或不稳定的。针对这种情况，我们提出了一种面部约简算法来寻找具有零对偶间隙且最优值等于原始原始或对偶问题之一的原始-对偶优化问题对。圆锥展开法也被称为寻找这种原始对偶对的方法，在本文中，我们阐明了我们的面部还原算法与圆锥展开法之间的关系。我们的分析表明，虽然它们可以被视为彼此对偶，但我们的人脸约简算法能够产生包括可行区域在内的更精细的锥体人脸序列。给出了该算法收敛性的一个简单证明。通过对图划分问题的数值实验，我们还观察到我们的人脸约简算法具有实际影响；我们的人脸约简算法实际上提高了这些问题的数值稳定性。
In the conic optimization problems, it is well-known that a positive duality gap may occur, and that solving such a problem is numerically difficult or unstable. For such a case, we propose a facial reduction algorithm to find a primal–dual pair of conic optimization problems having the zero duality gap and the optimal value equal to one of the original primal or dual problems. The conic expansion approach is also known as a method to find such a primal–dual pair, and in this paper we clarify the relationship between our facial reduction algorithm and the conic expansion approach. Our analysis shows that, although they can be regarded as dual to each other, our facial reduction algorithm has ability to produce a finer sequence of faces of the cone including the feasible region. A simple proof of the convergence of our facial reduction algorithm for the conic optimization is presented. We also observe that our facial reduction algorithm has a practical impact by showing numerical experiments for graph partition problems; our facial reduction algorithm in fact enhances the numerical stability in those problems.