Duality formulations in semidefinite programming

Previous Article
A new exact penalty function method for continuous inequality constrained optimization problems
JIMO Home
This Issue
Next Article
Adaptive control of nonlinear systems using fuzzy systems

October 2010, 6(4): 881-893. doi: 10.3934/jimo.2010.6.881

Duality formulations in semidefinite programming

Qinghong Zhang ^1, , Gang Chen ^2, and Ting Zhang ^2,

1.	Department of Mathematics and Computer Science, Northern Michigan University, Marquette, MI 49855, United States
2.	Department of Mathematics, Nantong Vacational College, Nantong 226007, China, China

Received October 2009 Revised June 2010 Published September 2010

Abstract
Related Papers

In this paper, duals for standard semidefinite programming problems from both the primal and dual sides are studied. Explicit expressions of the minimal cones and their dual cones are obtained under closeness assumptions of certain sets. As a result, duality formulations resulting from regularizations for both primal and dual problems can be expressed explicitly in terms of equality and inequality constraints involving three vector and matrix variables under such assumptions. It is proved in this paper that these newly developed duals can be cast as the Extended Lagrange-Slater Dual (ELSD) and the Extended Lagrange-Slater Dual of the Dual (ELSDD) with one reduction step. Therefore, the duals formulated in this paper guarantee strong duality, i.e., a zero duality gap and dual attainment.

Keywords: duality theory, Extended Lagrange-Slater Dual., Semidefinite programming.

Mathematics Subject Classification: Primary: 90C22, 90C46; Secondary: 90C2.

Citation: Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial and Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881

References:

[1]	G. Barker and D. Carlson, Cones of diagonally dominant matrices, Pacific J. Math., 57 (1975), 15-32.
[2]	J. Bonnans and A. Shapiro, "Perturbation Analysis of Optimization Problems," Springer, New York, 2000.
[3]	J. Borwein and H. Wolkowicz, Facial reduction for a cone-convex programming problem, J. Austral. Math. Soc. Ser. A, 30 (1980/1981), 369-380.
[4]	J. Borwein and H. Wolkowicz, Regularizing the abstract convex program, J. Math. Anal. Appl., 83 (1981), 495-530. doi: 10.1016/0022-247X(81)90138-4.
[5]	E. de Klerk, C. Roos and T. Terlaky, Infeasible start semidefinite programming algorithms via self-dual embeddings, Fields Inst. Commun., 18 (1998), 215-236.
[6]	K. Kortanek and Q. Zhang, Perfect duality in semi-infinite and semidefinite programming, Math. Program., Ser. A, 91 (2001), 127-144.
[7]	Z. Luo, J. Sturm and S. Zhang, "Duality Results for Conic Convex Programming," Technical Report, Econometric Institute Report No. 9719/A, Econometric Institute, Erasumus University, Rotterdam, The Netherlands, April 1997.
[8]	M. Ramana, An exact duality theory for semidefinite programming and its complexity implications, Math. Program., Ser. B, 77 (1997), 129-162.
[9]	M. Ramana, L. Tunçel and H. Wolkowicz, Strong duality for semidefinite programming, SIAM J. Optim., 7 (1997), 641-662.
[10]	R. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, New Jersey, 1970.
[11]	J. Sturm, "Primal-Dual Interior Point Approach to Semidefinite Programming," Ph.D thesis, Erasmus University, 1997.
[12]	M. Todd, Semidefinite optimization, Acta. Numer., 10 (2001), 515-560. doi: 10.1017/S0962492901000071.
[13]	L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Review, 38 (1996), 49-95. doi: 10.1137/1038003.
[14]	H. Wolkowicz, Some applications of optimization in matrix theory, Linear Algebra Appl., 40 (1981), 101-118. doi: 10.1016/0024-3795(81)90143-9.
[15]	Q. Zhang, Embedding methods for semidefinite programming, submitted for publication.

show all references

References:

[1]	G. Barker and D. Carlson, Cones of diagonally dominant matrices, Pacific J. Math., 57 (1975), 15-32.
[2]	J. Bonnans and A. Shapiro, "Perturbation Analysis of Optimization Problems," Springer, New York, 2000.
[3]	J. Borwein and H. Wolkowicz, Facial reduction for a cone-convex programming problem, J. Austral. Math. Soc. Ser. A, 30 (1980/1981), 369-380.
[4]	J. Borwein and H. Wolkowicz, Regularizing the abstract convex program, J. Math. Anal. Appl., 83 (1981), 495-530. doi: 10.1016/0022-247X(81)90138-4.
[5]	E. de Klerk, C. Roos and T. Terlaky, Infeasible start semidefinite programming algorithms via self-dual embeddings, Fields Inst. Commun., 18 (1998), 215-236.
[6]	K. Kortanek and Q. Zhang, Perfect duality in semi-infinite and semidefinite programming, Math. Program., Ser. A, 91 (2001), 127-144.
[7]	Z. Luo, J. Sturm and S. Zhang, "Duality Results for Conic Convex Programming," Technical Report, Econometric Institute Report No. 9719/A, Econometric Institute, Erasumus University, Rotterdam, The Netherlands, April 1997.
[8]	M. Ramana, An exact duality theory for semidefinite programming and its complexity implications, Math. Program., Ser. B, 77 (1997), 129-162.
[9]	M. Ramana, L. Tunçel and H. Wolkowicz, Strong duality for semidefinite programming, SIAM J. Optim., 7 (1997), 641-662.
[10]	R. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, New Jersey, 1970.
[11]	J. Sturm, "Primal-Dual Interior Point Approach to Semidefinite Programming," Ph.D thesis, Erasmus University, 1997.
[12]	M. Todd, Semidefinite optimization, Acta. Numer., 10 (2001), 515-560. doi: 10.1017/S0962492901000071.
[13]	L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Review, 38 (1996), 49-95. doi: 10.1137/1038003.
[14]	H. Wolkowicz, Some applications of optimization in matrix theory, Linear Algebra Appl., 40 (1981), 101-118. doi: 10.1016/0024-3795(81)90143-9.
[15]	Q. Zhang, Embedding methods for semidefinite programming, submitted for publication.

[1]	Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial and Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723
[2]	Cheng Lu, Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Industrial and Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779
[3]	Annamaria Barbagallo, Rosalba Di Vincenzo, Stéphane Pia. On strong Lagrange duality for weighted traffic equilibrium problem. Discrete and Continuous Dynamical Systems, 2011, 31 (4) : 1097-1113. doi: 10.3934/dcds.2011.31.1097
[4]	Regina Sandra Burachik, Alex Rubinov. On the absence of duality gap for Lagrange-type functions. Journal of Industrial and Management Optimization, 2005, 1 (1) : 33-38. doi: 10.3934/jimo.2005.1.33
[5]	Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1527-1538. doi: 10.3934/jimo.2019015
[6]	Daniel Heinlein, Ferdinand Ihringer. New and updated semidefinite programming bounds for subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 613-630. doi: 10.3934/amc.2020034
[7]	Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187
[8]	Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127-145. doi: 10.3934/amc.2013.7.127
[9]	Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[10]	Yuying Zhou, Gang Li. The Toland-Fenchel-Lagrange duality of DC programs for composite convex functions. Numerical Algebra, Control and Optimization, 2014, 4 (1) : 9-23. doi: 10.3934/naco.2014.4.9
[11]	Takeshi Fukao, Nobuyuki Kenmochi. Abstract theory of variational inequalities and Lagrange multipliers. Conference Publications, 2013, 2013 (special) : 237-246. doi: 10.3934/proc.2013.2013.237
[12]	Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003
[13]	Xinmin Yang. On second order symmetric duality in nondifferentiable multiobjective programming. Journal of Industrial and Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697
[14]	Tone-Yau Huang, Tamaki Tanaka. Optimality and duality for complex multi-objective programming. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 121-134. doi: 10.3934/naco.2021055
[15]	Andrzej Nowakowski, Jan Sokolowski. On dual dynamic programming in shape control. Communications on Pure and Applied Analysis, 2012, 11 (6) : 2473-2485. doi: 10.3934/cpaa.2012.11.2473
[16]	Cristian Dobre. Mathematical properties of the regular -representation of matrix $$-algebras with applications to semidefinite programming. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 367-378. doi: 10.3934/naco.2013.3.367
[17]	Xinmin Yang, Jin Yang, Heung Wing Joseph Lee. Strong duality theorem for multiobjective higher order nondifferentiable symmetric dual programs. Journal of Industrial and Management Optimization, 2013, 9 (3) : 525-530. doi: 10.3934/jimo.2013.9.525
[18]	Gang Li, Yinghong Xu, Zhenhua Qin. Optimality conditions of fenchel-lagrange duality and farkas-type results for composite dc infinite programs. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1275-1293. doi: 10.3934/jimo.2021019
[19]	Xinmin Yang, Xiaoqi Yang, Kok Lay Teo. Higher-order symmetric duality in multiobjective programming with invexity. Journal of Industrial and Management Optimization, 2008, 4 (2) : 385-391. doi: 10.3934/jimo.2008.4.385
[20]	Xinmin Yang, Xiaoqi Yang. A note on mixed type converse duality in multiobjective programming problems. Journal of Industrial and Management Optimization, 2010, 6 (3) : 497-500. doi: 10.3934/jimo.2010.6.497

2021 Impact Factor: 1.411

Tools

Metrics

Other articles
by authors

on AIMS
Qinghong Zhang Gang Chen Ting Zhang
on Google Scholar
Qinghong Zhang Gang Chen Ting Zhang

[Back to Top]