|
The elegant results for strong duality and strict complementarity for linear
programming, LP, can fail for cone programming over nonpolyhedral cones. One can
have: unattained optimal values; nonzero duality gaps; and no primal-dual optimal
pair that satisfies strict complementarity.
We take a fresh look at known and new results for duality, optimality, constraint
qualifications, and complementarity, for linear cone optimization problems in
finite dimensions. These results include: weakest and universal constraint
qualifications, CQs; duality and characterizations of optimality that hold without
any CQ; geometry of nice and devious cones; the geometric relationships between
zero duality gaps, complementarity, and the facial structure of cones; and, the
connection between theory and empirical evidence for lack of a CQ and failure of
strict complementarity.
One theme is the notion of minimal representation of the cone and the constraints
in order to regularize the problem and avoid both the theoretical and numerical
difficulties that arise due to (near) loss of a CQ. We include a discussion on
obtaining these representations efficiently. A parallel theme is the loss of
strict complementarity and the corresponding theoretical and numerical
difficulties that arise; a discussion on avoiding these difficulties is
included. We then discuss the surprising connections between the duality theory
and complementarity.
Our emphasis is on results that deal with Semidefinite Programming, SDP.
Joint work with Simon Schurr and Levent Tuncel.
|