A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms
A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms
复制标题
奇异SDP正则化的极限分析及其对不可行内点算法的影响
DOI：
10.1007/s10107-022-01891-8
复制
发表时间：
2022
影响因子：
2.7
通讯作者：
Okuno Takayuki
中科院分区：
文献类型：
--
作者：
Tsuchiya Takashi;Lourenco Bruno F.;Muramatsu Masakazu;Okuno Takayuki
我们考虑半定规划的原始对偶对，并假设它们是奇异的，即，原始和对偶都是弱可行或弱不可行的。在这种情况下，强对偶可能会崩溃，原始对偶和对偶可能会有一个非零的对偶间隙。然而，有任意的小扰动的问题数据，这将使他们强烈可行，从而零的对偶差距。在本文中，我们进行了渐近分析的最佳值的正则化的扰动被驱动到零。具体来说，我们固定两个正定矩阵，和，说，（通常是单位矩阵），并通过将其相关的仿射空间分别移动和来正则化原始和对偶问题，以恢复这两个问题的内部可行性，其中和是正数。然后我们分析了正则化问题的最优值的行为时，扰动减少到零保持之间的比率和常数。我们的分析的一个关键特征是，没有进一步的假设，如紧凑性或约束条件。结果表明，扰动问题的最优值收敛到原问题的原始最优值和对偶最优值之间的一个值。此外，极限最优值从原始最优值“单调地”变化到对偶最优值，作为函数，如果我们parametrizeand让。最后，分析导致我们相对令人惊讶的后果，一些代表性的不可行的邻近点算法SDP生成序列收敛到一个数之间的原始和对偶最优值，即使在存在一个非零的对偶间隙。虽然这个结果在这一点上是更多的理论兴趣，它可能是一些价值的发展不可行的邻域点算法，可以处理奇异问题。
We consider primal-dual pairs of semidefinite programs and assume that they are singular, i.e., both primal and dual are either weakly feasible or weakly infeasible. Under such circumstances, strong duality may break down and the primal and dual might have a nonzero duality gap. Nevertheless, there are arbitrary small perturbations to the problem data which would make them strongly feasible thus zeroing the duality gap. In this paper, we conduct an asymptotic analysis of the optimal value as the perturbation for regularization is driven to zero. Specifically, we fix two positive definite matrices,and, say, (typically the identity matrices), and regularize the primal and dual problems by shifting their associated affine space byand, respectively, to recover interior feasibility of both problems, whereandare positive numbers. Then we analyze the behavior of the optimal value of the regularized problem when the perturbation is reduced to zero keeping the ratio betweenandconstant. A key feature of our analysis is that no further assumptions such as compactness or constraint qualifications are ever made. It will be shown that the optimal value of the perturbed problem converges to a value between the primal and dual optimal values of the original problems. Furthermore, the limiting optimal value changes “monotonically” from the primal optimal value to the dual optimal value as a function of, if we parametrizeasand let. Finally, the analysis leads us to the relatively surprising consequence that some representative infeasible interior-point algorithms for SDP generate sequences converging to a number between the primal and dual optimal values, even in the presence of a nonzero duality gap. Though this result is more of theoretical interest at this point, it might be of some value in the development of infeasible interior-point algorithms that can handle singular problems.
登录
查看更多内容
DOI：
10.1137/s1052623495288350
发表时间：
1997-03
期刊：
SIAM J. Optim.
影响因子：
--
作者：
M. Ramana;L. Tunçel;Henry Wolkowicz
通讯作者：
M. Ramana;L. Tunçel;Henry Wolkowicz
影响因子：
2.2
作者：
Gally, Tristan;Pfetsch, Marc E.;Ulbrich, Stefan
通讯作者：
Ulbrich, Stefan
Sieve-SDP：一种简单的面部缩减算法，用于预处理半定程序
影响因子：
6.3
作者：
Zhu, Yuzixuan;Pataki, Gábor;Tran-Dinh, Quoc
通讯作者：
Tran-Dinh, Quoc
影响因子：
2.7
作者：
Bruno F. Lourenço
通讯作者：
Bruno F. Lourenço
半定线性互补问题引起的不可行内点路径分析
影响因子：
2.7
作者：
M. Preiß;J. Stoer
通讯作者：
J. Stoer