-

 

 

 




Optimization Online





 

Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming

Minghui Liu(minghuil***at***live.unc.edu)
Gabor Pataki(gabor***at***unc.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/2015
Entry Accepted: 06/10/2015
Entry Last Modified: 06/10/2015

Modify/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
Mathematical Optimization Society