Abstract
A strong duality which states that the optimal values of the primal convex problem and its Lagrangian dual problem are equal (i.e. zero duality gap) and the dual problem attains its maximum is a corner stone in convex optimization. In particular it plays a major role in the numerical solution as well as the application of convex semidefinite optimization. The strong duality requires a technical condition known as a constraint qualification (CQ). Several CQs which are sufficient for strong duality have been given in the literature. In this note we present new necessary and sufficient CQs for the strong duality in convex semidefinite optimization. These CQs are shown to be sharper forms of the strong conical hull intersection property (CHIP) of the intersecting sets of constraints which has played a critical role in other areas of convex optimization such as constrained approximation and error bounds.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Balakrishnan V. and Vandenberghe L. (2003). Semidefinite programming duality and linear time-invariant systems. IEEE Trans. Autom. Control 48: 30–41
Borwein J.M. and Lewis A.S. (1992). Partially finite convex programming, part I: Quasi relative interiors and duality theory. Math. Progr. 57: 15–48
Boyd, S., El Ghaoui, L., Feron, E., Balakrishnan, V.: Linear matrix inequalities in systems and control theory. In: SIAM Stud. Appl. Math., vol. 15. SIAM, Philadelphia (1994)
Boyd S. and Vandenberghe L. (2004). Convex Optimization. Cambridge University Press, Cambridge
Burachik R.S. and Jeyakumar V. (2005). A simple closure condition for the normal cone intersection formula. Proc. Am. Math. Soc. 133: 1741–1748
Burachik R.S. and Jeyakumar V. (2005). A new geometric condition for Fenchel’s duality in infinite dimensional spaces. Math. Program. Ser. B 104: 229–233
Burachik R.S., Jeyakumar V. and Wu Z.Y. (2006). Necessary and sufficient conditions for stable conjugate duality. Nonlin. Anal. 64: 1998–2006
Deutsch F. (1998). The role of conical hull intersection property in convex optimization and approximation. In: Chui, C.K. and Schumaker, L.L. (eds) Approximation Theory, vol. IX, pp. Vanderbilt University Press, Nashville
Deutsch F., Li W. and Swetits J. (1999). Fenchel duality and the strong conical hull intersection property. J. Optim. Theory Appl. 102: 681–695
Guignard M. (1969). Generalized Kuhn-Tucker conditions for mathematical programming problems in a Banach space. SIAM J. Control 7: 232–241
Helmberg C. (2002). Semidefinite programming. Eur. J. Oper. Res. 137: 461–482
Hiriart-Urruty J-B. and Lemarechal C. (1993). Convex Analysis and Minimization Algorithms vols. I, II. Springer, Heidelberg
Jeyakumar V. (2006). The strong conical hull intersection property for convex programming. Math. Progr. Ser. A 106: 81–92
Jeyakumar V. and Nealon M. (2000). Complete characterizations of optimality for convex semidefinite programming. Can. Math. Soc. Conf. Proc 27: 165–173
Jeyakumar V. and Wolkowicz H. (1992). Generalizations of Slater’s constraint qualification for infinite convex programs. Math. Progr. 57: 85–102
Jeyakumar V., Lee G.M. and Dinh N. (2003). New sequential Lagrange multiplier conditions characterizing optimality without constraint qualification for convex programs. SIAM J. Optim. 14: 534–547
De Oliveira M.C. (2004). Investigating duality on stability conditions. Syst. Control Lett. 52: 1–6
Ramana M.V. (1997). An exact duality theory for semidefinite programming and its complexity implications. Math. Progr. 77: 129–162
Ramana M.V., Tunçcel L. and Wolkowicz H. (1997). Strong duality for semidefinite programming. SIAM J. Optim. 7: 644–662
Shapiro, A.: On duality theory of conic linear problems, semi-infinite programming (Alicante, 1999). In: Nonconvex Optim. Appl. vol. 57, pp. 135–165. Kluwer, Dordrecht (2001)
Todd M.J. (2001). Semidefinite optimization. Acta Numer. 10: 515–560
Vandenberghe L. and Boyd S. (1996). Semidefinite programming. SIAM Rev. 38: 49–95
Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of semidefinite programming. In: International Series in Operations Research and Management Science, vol. 27. Kluwer, Dordrecht (2000)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research was partially supported by the Australian Research Council. The author is grateful to the referees for their helpful comments
Rights and permissions
About this article
Cite this article
Jeyakumar, V. A note on strong duality in convex semidefinite optimization: necessary and sufficient conditions. Optimization Letters 2, 15–25 (2008). https://doi.org/10.1007/s11590-006-0038-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-006-0038-x