Abstract
Given a primal-dual pair of linear programs, it is well known that if their optimal values are viewed as lying on the extended real line, then the duality gap is zero, unless both problems are infeasible, in which case the optimal values are +∞ and −∞. In contrast, for optimization problems over nonpolyhedral convex cones, a nonzero duality gap can exist when either the primal or the dual is feasible.
For a pair of dual conic convex programs, we provide simple conditions on the ``constraint matrices'' and cone under which the duality gap is zero for every choice of linear objective function and constraint right-hand side. We refer to this property as ``universal duality''. Our conditions possess the following properties: (i) they are necessary and sufficient, in the sense that if (and only if) they do not hold, the duality gap is nonzero for some linear objective function and constraint right-hand side; (ii) they are metrically and topologically generic; and (iii) they can be verified by solving a single conic convex program. We relate to universal duality the fact that the feasible sets of a primal convex program and its dual cannot both be bounded, unless they are both empty. Finally we illustrate our theory on a class of semidefinite programs that appear in control theory applications.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Absil, P.-A., Mahony, R., Sepulchre, R.: Riemannian geometry of Grassmann manifolds with a view on algorithmic computation. Acta Appl. Math. 80 (2), 199–220 (2004)
Alizadeh, F., Haeberly, J.-P.A., Overton, M.L.: Complementarity and nondegeneracy in semidefinite programming. Math. Programming Mathematical Programming 77 (2 Ser. B), 111–128 (1997)
Berman, A.: Cones, Matrices and Mathematical Programming. Springer-Verlag, Berlin, 1973. Lecture Notes in Economics and Mathematical Systems Vol. 79
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge, University Press, 2004
Duffin, R.J.: Clark's Theorem on linear programs holds for convex programs. Proc. Nat. Acad. Sci. U.S.A., 75 (4), 1624–1626 (1978)
Edelman, A., Arias T.A., Smith S.T. The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20 (2), 303–353 (1998)
Ewald, G.: Combinatorial Convexity and Algebraic Geometry, volume 168 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1996
Halmos, P.R.: Measure Theory. D. Van Nostrand Company Inc., 1950
Luo, Z.-Q., Sturm, J.F., Zhang S.: Conic convex programming and self-dual embedding. Optim. Methods Softw. 14 (3), 169–218 (2000)
Mangasarian, O.L.: Nonlinear Programming, volume 10 of Classics in Applied Mathematics, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1994 Reprint of the 1969 original
Pataki, G.: On the closedness of the linear image of a closed convex cone. Research Report TR-02-3, Department of Operations Research, University of North Carolina, Chapel Hill, 2003; Math. Oper. Res., to appear
Pataki, G., Tunçel, L.: On the generic properties of convex optimization problems in conic form. Math. Programming. 89 (3 Ser. A), 449–457 (2001)
Renegar, J.: A Mathematical View of Interior-Point Methods in Convex Optimization. MPS/SIAM Series on Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
Rockafellar, R.T.: Convex Analysis. Princeton Landmarks in Mathematics. Princeton University Press, Princeton, NJ, 1997 Reprint of the 1970 original
Rogers, C.A.: Hausdorff Measures. Cambridge University Press, London, 1970
Royden, H.L.: Real Analysis (second edition). The Macmillan Co., New York, 1968
Schneider, R.: Convex Bodies: the Brunn-Minkowski Theory, Volume 44 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1993
Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, New York, 1986.
Smirnov, S.: Functional Analysis lecture notes. http://www.math.kth.se/~stas/fa00/part1.ps, 2000
Todd, M.: Semidefinite optimization. Acta Numerica, 10, 515–560 (2001)
Vandenberghe, L., Balakrishnan, V.: Semidefinite programming duality and linear system theory: connections and implications for computation. In: Proc. IEEE Conference on Decision and Control, Phoneix, AZ, 1999, pp. 989–994
Vandenberghe, L., Balakrishnan, V., Walliny, R., Hanssony, A., Roh, T.: Interior-point algorithms for semidefinite programming problems derived from the KYP lemma. In: A. Garulli and D. Henrion, editors, Positive Polynomials in Control, Lecture Notes in Control and Information Sciences. Vol. 312, pp. 195–238. Springer, 2005
Zalgaller, V.A.: k-dimensional directions singular for a convex body F in R n. Zap. Naučn. Sem. Leningrad. Otdel. Mat. Inst. Steklov., 27, 67–72, 1972. English translation: J. Soviet Math. 3 (1975) 437–441
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by a fellowship at the University of Maryland, in addition to NSF grants DEMO-9813057, DMI0422931, CUR0204084, and DoE grant DEFG0204ER25655. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation or those of the US Department of Energy.
Rights and permissions
About this article
Cite this article
Schurr, S., Tits, A. & O'Leary, D. Universal duality in conic convex optimization. Math. Program. 109, 69–88 (2007). https://doi.org/10.1007/s10107-005-0690-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-005-0690-4