Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming
Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming
复制标题
二次曲线线性规划中的精确对偶和不可行性和弱不可行性的短证明
DOI：
10.1007/s10107-017-1136-5
复制
发表时间：
2015
影响因子：
2.7
通讯作者：
G. Pataki
中科院分区：
文献类型：
--
作者：
Minghui Liu;G. Pataki
在圆锥线性编程中，与线性编程相反，Lagrange Dual不是一个确切的二元组合：它可能无法达到其最佳值，或者可能存在正面双重性差距。始终证明是不可行的）。 ，klep and Schweighofer对我们的一些保险证书的上下文概括了线性方程式的行echelon形式：它们由一个小的，琐碎的子系统组成。我们获得了一些基本的几何推论：封闭式凸锥的线性图像的精确表征，并且我们的感染证书的精确表征提供了算法，以生成所有属于几个重要类的圆锥体所有使用这些算法的自然级别的不可行的SDP，我们可以通过确切的算术来验证我们实例的不可行的公共领域库研究法规。
In conic linear programming—in contrast to linear programming—the Lagrange dual is not an exact dual: it may not attain its optimal value, or there may be a positive duality gap. The corresponding Farkas’ lemma is also not exact (it does not always prove infeasibility). We describe exact duals, and certificates of infeasibility and weak infeasibility for conic LPs which are nearly as simple as the Lagrange dual, but do not rely on any constraint qualification. Some of our exact duals generalize the SDP duals of Ramana, and Klep and Schweighofer to the context of general conic LPs. Some of our infeasibility certificates generalize the row echelon form of a linear system of equations: they consist of a small, trivially infeasible subsystem obtained by elementary row operations. We prove analogous results for weakly infeasible systems. We obtain some fundamental geometric corollaries: an exact characterization of when the linear image of a closed convex cone is closed, and an exact characterization of nice cones. Our infeasibility certificates provide algorithms to generate all infeasible conic LPs over several important classes of cones; and all weakly infeasible SDPs in a natural class. Using these algorithms we generate a public domain library of infeasible and weakly infeasible SDPs. The status of our instances can be verified by inspection in exact arithmetic, but they turn out to be challenging for commercial and research codes.