Characterizing Bad Semidefinite Programs: Normal Forms and Short Proofs
Characterizing Bad Semidefinite Programs: Normal Forms and Short Proofs
复制标题
DOI：
10.1137/17m1140844
复制
发表时间：
2017-09
期刊：
影响因子：
--
通讯作者：
G. Pataki
中科院分区：
文献类型：
--
作者：
G. Pataki
半定规划（SDP）--过去几十年中最有用和最通用的优化问题之一--通常是病态的：原始问题和对偶问题的最优值可能不同，并且可能无法达到。这种SDPs在理论上是有趣的，而且往往不可能解决;然而，文献中的病理性SDPs看起来惊人地相似。基于我们最近的工作，我们用某些排除矩阵来描述病态半定系统，这些矩阵在所有已发表的例子中很容易被发现。我们的主要工具是半定系统的标准（规范）形式，这使得它们的病态行为易于验证。范式是以一种令人惊讶的简单方式构造的，主要使用从高斯消去法继承的基本行操作。证明是基本的，可以遵循的读者在先进的本科水平。作为一个副产品，我们展示了如何将任何线性映射作用于对称矩阵转化为规范形式，这使我们能够快速检查下的映射的半定锥的图像是否是封闭的。因此，我们可以向读者介绍凸分析中的一个基本问题：闭凸集的线性图像可能不是闭的，并且通常可以用简单的条件来验证闭性或缺乏闭性。
Semidefinite programs (SDPs) -- some of the most useful and versatile optimization problems of the last few decades -- are often pathological: the optimal values of the primal and dual problems may differ and may not be attained. Such SDPs are both theoretically interesting and often impossible to solve; yet, the pathological SDPs in the literature look strikingly similar. Based on our recent work \cite{Pataki:17} we characterize pathological semidefinite systems by certain {\em excluded matrices}, which are easy to spot in all published examples. Our main tool is a normal (canonical) form of semidefinite systems, which makes their pathological behavior easy to verify. The normal form is constructed in a surprisingly simple fashion, using mostly elementary row operations inherited from Gaussian elimination. The proofs are elementary and can be followed by a reader at the advanced undergraduate level. As a byproduct, we show how to transform any linear map acting on symmetric matrices into a normal form, which allows us to quickly check whether the image of the semidefinite cone under the map is closed. We can thus introduce readers to a fundamental issue in convex analysis: the linear image of a closed convex set may not be closed, and often simple conditions are available to verify the closedness, or lack of it.