Duality of Linear Conic Problems

Alexander Shapiro (ashapiroisye.gatech.edu)
Arkadi Nemirovski (nemirovsie.technion.ac.il)

Abstract: It is well known that the optimal values of a linear programming problem and its dual are equal to each other if at least one of these problems is feasible. It is also well known that for linear conic problems this property of "no duality gap" may not hold. It is then natural to ask whether there exist some other convex closed cones, apart from polyhedral, for which the "no duality gap" property holds. We show that the answer to this question is negative. We then discuss the question of a finite duality gap, when both the primal and dual problems are feasible, and pose the problem of characterizing linear conic problems without a finite duality gap.

Keywords:

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Other )

Citation: Preprint, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA

Download: [PDF]

Entry Submitted: 12/10/2003
Entry Accepted: 12/10/2003
Entry Last Modified: 12/10/2003

Modify/Update this entry