Optimization Online


Exact duality in semidefinite programming based on elementary reformulations

Minghui Liu (minghuil***at***live.unc.edu)
Gabor Pataki (gabor***at***unc.edu)

Abstract: In semidefinite programming (SDP), unlike in linear programming, Farkas' lemma may fail to prove infeasibility. Here we obtain an exact, short certificate of infeasibility in SDP by an elementary approach: we reformulate any equality constrained semidefinite system using only elementary row operations, and rotations. When the system is infeasible, the infeasibility of the reformulated system is trivial to verify by inspection. \\ For feasible systems we obtain a similar reformulation, which trivially has strong duality with its Lagrange dual for all objective functions. As a corollary, we obtain algorithms to systematically generate the data of all infeasible semidefinite programs (SDPs), and the data of all feasible SDPs whose maximum rank feasible solution has a prescribed rank.

Keywords: semidefinite programming; duality; infeasibility certificates; strong duality

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Convex and Nonsmooth Optimization

Category 3: Nonlinear Optimization


Download: [PDF]

Entry Submitted: 06/05/2014
Entry Accepted: 06/05/2014
Entry Last Modified: 12/08/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society