Solving SDP completely with an interior point oracle
Solving SDP completely with an interior point oracle
复制标题
DOI：
10.1080/10556788.2020.1850720
复制
发表时间：
2015-07
影响因子：
2.2
通讯作者：
Bruno F. Lourenço;M. Muramatsu;T. Tsuchiya
中科院分区：
文献类型：
--
作者：
Bruno F. Lourenço;M. Muramatsu;T. Tsuchiya
我们假设存在一个预言机，它可以解决任何同时满足原始和对偶强可行性（即斯莱特条件）的半定规划（SDP）问题。我们注意到，即使在应用某些正则化方案之后，这样的预言机也可能无法直接求解一般的SDP。在这项工作中，我们填补了这一空白，并展示了如何使用这样的预言“完全解决”任意SDP。例如，完全求解需要区分弱/强可行性/不可行性，并检测何时达到最优值。我们将使用几种工具，包括面部缩小的变体，确保所有辅助问题都能满足所有方面的强大可行性。然而，我们的主要技术创新是对双重面归约的分析，这是将面归约应用两次的过程：首先应用于原始问题，然后再一次应用于第一次运行期间获得的正则化问题的对偶。虽然我们的讨论集中在半定规划，大多数的结果证明一般凸锥。
We suppose the existence of an oracle which solves any semidefinite programming (SDP) problem satisfying strong feasibility (i.e. Slater's condition) simultaneously at its primal and dual sides. We note that such an oracle might not be able to directly solve general SDPs even after certain regularization schemes are applied. In this work we fill this gap and show how to use such an oracle to ‘completely solve’ an arbitrary SDP. Completely solving entails, for example, distinguishing between weak/strong feasibility/infeasibility and detecting when the optimal value is attained or not. We will employ several tools, including a variant of facial reduction where all auxiliary problems are ensured to satisfy strong feasibility at all sides. Our main technical innovation, however, is an analysis of double facial reduction, which is the process of applying facial reduction twice: first to the original problem and then once more to the dual of the regularized problem obtained during the first run. Although our discussion is focused on semidefinite programming, the majority of the results are proved for general convex cones.