##
Duality And Self-Duality
For Conic Convex Programming

###
Zhi-Quan Luo, Jos Sturm, Shuzhong Zhang

This paper considers the problem of minimizing a linear function
over the intersection of an affine space with a closed convex cone.
In the first half of the paper,
we give a detailed study of duality properties of
this problem and present examples to illustrate these properties.
In particular, we introduce the notions of weak/strong
feasibility or infeasibility for a general primal-dual pair of conic convex
programs, and then establish various
relations between these notions and the duality properties of the problem.
In the second half of the paper, we propose a self-dual
embedding with the following properties: Any weakly centered
sequence converging to a complementary pair either induces a
sequence converging to a certificate of strong infeasibility, or
induces a sequence of primal-dual pairs for which the amount
of constraint violation converges to zero, and the corresponding
objective values are in the limit not worse than the optimal
objective value(s). In case of strong duality, these objective values in
fact converge to the optimal value of the original problem. When
the problem is neither strongly infeasible nor endowed
with a complementary pair, we completely specify the asymptotic
behavior of an indicator in relation to the status of the
original problem, namely whether the problem (1) is weakly
infeasible, (2) is feasible but with a positive duality gap,
(3) has no duality gap nor complementary solution pair.

Report 9620/A, Econometric Institute, Erasmus University Rotterdam.

Contact: sturm@opres.few.eur.nl