- Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming Minghui Liu(minghuillive.unc.edu) Gabor Pataki(gaborunc.edu) Abstract: We describe simple and exact duals, and certificates of infeasibility and weak infeasibility in conic linear programming which do not rely on any constraint qualification, and retain most of the simplicity of the Lagrange dual. In particular, some of our infeasibility certificates generalize the row echelon form of a linear system of equations, and the easy'' proofs -- as sufficiency of a certificate to prove infeasibility -- are trivial. \\ For many cones of interest, we provide an algorithm to generate {\em all} infeasible conic LP instances. For semidefinite programs we provide an algorithm to generate {\em all} weakly infeasible instances in a natural class. \\ As a byproduct, we obtain some fundamental geometric corollaries: an exact characterization of when the linear image of a closed convex cone is closed; an exact characterization of nice cones; and bounds on the number of constraints that can be dropped from, or added to a (weakly) infeasible conic LP while keeping it (weakly) infeasible. \\ We generate a public domain library of infeasible and weakly infeasible semidefinite programs. The status of our instances is easy to verify by inspection in exact arithmetic, but they turn out to be challenging for commercial and research codes. Keywords: Conic linear programming; semidefinite programming; exact duals; certificates of infeasibility and weak infeasibility Category 1: Linear, Cone and Semidefinite Programming Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Category 3: Convex and Nonsmooth Optimization Citation: Download: [PDF]Entry Submitted: 06/10/2015Entry Accepted: 06/10/2015Entry Last Modified: 06/10/2015Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.