zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Stable zero duality gaps in convex programming: complete dual characterisations with applications to semidefinite programs. (English) Zbl 1208.90134
Summary: The zero duality gap that underpins the duality theory is one of the central ingredients in optimisation. In convex programming, it means that the optimal values of a given convex program and its associated dual program are equal. It allows, in particular, the development of efficient numerical schemes. However, the zero duality gap property does not always hold even for finite-dimensional problems and it frequently fails for problems with non-polyhedral constraints such as the ones in semidefinite programming problems. Over the years, various criteria have been developed ensuring zero duality gaps for convex programming problems. In the present work, we take a broader view of the zero duality gap property by allowing it to hold for each choice of linear perturbation of the objective function of the given problem. Globalising the property in this way permits us to obtain complete geometric dual characterisations of a stable zero duality gap in terms of epigraphs and conjugate functions. For convex semidefinite programs, we establish necessary and sufficient dual conditions for stable zero duality gaps, as well as for a universal zero duality gap in the sense that the zero duality gap property holds for each choice of constraint right-hand side and convex objective function. Zero duality gap results for second-order cone programming problems are also given. Our approach makes use of elegant conjugate analysis and Fenchel’s duality.

90C25Convex programming
90C46Optimality conditions, duality
90C34Semi-infinite programming
Full Text: DOI
[1] Auslender, A.; Teboulle, M.: Asymptotic cones and functions in optimisation and variational inequalities, Springer monogr. Math. (2003) · Zbl 1017.49001
[2] Auslender, A.: Existence of optimal solutions and duality results under weak conditions, Math. program. Ser. A 88, 45-59 (2000) · Zbl 0980.90063 · doi:10.1007/s101070000138
[3] Bonnans, J. F.; Shapiro, A.: Perturbation analysis of optimization problems, (2000) · Zbl 0966.49001
[4] Ban, L.; Song, W.: Duality gap of the conic convex constrained optimisation problems in normed spaces, Math. program. Ser. A 119, 195-214 (2009) · Zbl 1172.90012 · doi:10.1007/s10107-008-0207-z
[5] Burachik, R. S.; Jeyakumar, V.: A new geometric condition for Fenchel’s duality in infinite dimensional spaces, Math. program. Ser. B 104, No. 2 -- 3, 229-233 (2005) · Zbl 1093.90077 · doi:10.1007/s10107-005-0614-3
[6] Burachik, R. S.; Jeyakumar, V.; Wu, Z. Y.: Necessary and sufficient conditions for stable conjugate duality, J. nonlinear anal. Ser. A 64, 1998-2006 (2006) · Zbl 1091.49031 · doi:10.1016/j.na.2005.07.034
[7] Canovas, M. J.; Klatte, D.; Lopez, M. A.; Parra, J.: Metric regularity in convex semi-infinite optimisation under canonical perturbations, SIAM J. Optim. 18, 717-732 (2007) · Zbl 1211.90256 · doi:10.1137/060658345
[8] Goberna, M. A.; Gomez, S.; Guerra, F.; Todorov, M. I.: Sensitivity analysis in linear semi-infinite programming: perturbing cost and right-hand-side coefficients, European J. Oper. res. 181, 1069-1085 (2007) · Zbl 1121.90121 · doi:10.1016/j.ejor.2005.06.075
[9] Jeyakumar, V.: A note on strong duality in convex semidefinite optimization: necessary and sufficient conditions, Optim. lett. 2, 15-25 (2008) · Zbl 1147.90038 · doi:10.1007/s11590-006-0038-x
[10] Jeyakumar, V.: Constraint qualifications characterizing Lagrangian duality in convex optimization, J. optim. Theory appl. 136, 31-41 (2008) · Zbl 1194.90069 · doi:10.1007/s10957-007-9294-x
[11] Jeyakumar, V.; Lee, G. M.: Complete characterizations of stable farkas’ lemma and cone-convex programming duality, Math. program. Ser. A 114, 335-347 (2008) · Zbl 1145.90074 · doi:10.1007/s10107-007-0104-x
[12] Jeyakumar, V.; Wolkowicz, H.: Zero duality gaps in infinite dimensional programming, J. optim. Theory appl. 67, 87-108 (1990) · Zbl 0687.90077 · doi:10.1007/BF00939737
[13] Jeyakumar, V.; Li, G.: New dual constraint qualifications characterizing zero duality gaps of convex programs and semidefinite programs, Nonlinear anal. (2009) · Zbl 1239.90084
[14] G. Li, V. Jeyakumar, No duality gaps for convex programs with separable inequality constraints, School of Mathematics Preprint, 2008, Math. Oper. Res., submitted for publication
[15] Li, C.; Ng, K. F.; Pong, T. K.: The SECQ, linear regularity and the strong CHIP for infinite system of closed convex sets in normed linear spaces, SIAM J. Optim. 18, 643-665 (2007) · Zbl 1151.90054 · doi:10.1137/060652087
[16] Pataki, G.: On the closedness of the linear image of a closed convex cone, Math. oper. Res. 32, No. 2, 395-412 (2008) · Zbl 05279730
[17] Ramana, M. V.; Tunçel, L.; Wolkowicz, H.: Strong duality for semidefinite programming, SIAM J. Optim. 7, 644-662 (1997) · Zbl 0891.90129 · doi:10.1137/S1052623495288350
[18] Rockafellar, T.: Conjugate duality and optimization, (1974) · Zbl 0296.90036
[19] Schurr, S. P.; Tits, A. L.; O’leary, P.: Universal duality in conic convex optimization, Math. program. Ser. A 109, 69-88 (2007) · Zbl 1167.90023 · doi:10.1007/s10107-005-0690-4
[20] Tseng, P.: Some convex programs without a duality gap, Math. program. Ser. B 116, 553-573 (2009) · Zbl 1176.90464 · doi:10.1007/s10107-007-0110-z
[21] Shapiro, A.: On duality theory of convex semi-infinite programming, Optimization 54, 535-543 (2005) · Zbl 1147.90403 · doi:10.1080/02331930500342823
[22] Wolkowicz, H.; Saigal, R.; Vandenberghe, L.: Handbook of semidefinite programming, Internat. ser. Oper. res. Management sci. 27 (2000) · Zbl 0951.90001
[23] Zalinescu, C.: Convex analysis in general vector spaces, (2002)