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

Duality formulations in semidefinite programming

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

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.
Citation: Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & 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. Google Scholar

[2]

J. Bonnans and A. Shapiro, "Perturbation Analysis of Optimization Problems,", Springer, (2000). Google Scholar

[3]

J. Borwein and H. Wolkowicz, Facial reduction for a cone-convex programming problem,, J. Austral. Math. Soc. Ser. A, 30 (): 369. Google Scholar

[4]

J. Borwein and H. Wolkowicz, Regularizing the abstract convex program,, J. Math. Anal. Appl., 83 (1981), 495. doi: 10.1016/0022-247X(81)90138-4. Google Scholar

[5]

E. de Klerk, C. Roos and T. Terlaky, Infeasible start semidefinite programming algorithms via self-dual embeddings,, Fields Inst. Commun., 18 (1998), 215. Google Scholar

[6]

K. Kortanek and Q. Zhang, Perfect duality in semi-infinite and semidefinite programming,, Math. Program., 91 (2001), 127. Google Scholar

[7]

Z. Luo, J. Sturm and S. Zhang, "Duality Results for Conic Convex Programming,", Technical Report, (9719). Google Scholar

[8]

M. Ramana, An exact duality theory for semidefinite programming and its complexity implications,, Math. Program., 77 (1997), 129. Google Scholar

[9]

M. Ramana, L. Tunçel and H. Wolkowicz, Strong duality for semidefinite programming,, SIAM J. Optim., 7 (1997), 641. Google Scholar

[10]

R. Rockafellar, "Convex Analysis,", Princeton University Press, (1970). Google Scholar

[11]

J. Sturm, "Primal-Dual Interior Point Approach to Semidefinite Programming,", Ph.D thesis, (1997). Google Scholar

[12]

M. Todd, Semidefinite optimization,, Acta. Numer., 10 (2001), 515. doi: 10.1017/S0962492901000071. Google Scholar

[13]

L. Vandenberghe and S. Boyd, Semidefinite programming,, SIAM Review, 38 (1996), 49. doi: 10.1137/1038003. Google Scholar

[14]

H. Wolkowicz, Some applications of optimization in matrix theory,, Linear Algebra Appl., 40 (1981), 101. doi: 10.1016/0024-3795(81)90143-9. Google Scholar

[15]

Q. Zhang, Embedding methods for semidefinite programming,, submitted for publication., (). Google Scholar

show all references

References:
[1]

G. Barker and D. Carlson, Cones of diagonally dominant matrices,, Pacific J. Math., 57 (1975), 15. Google Scholar

[2]

J. Bonnans and A. Shapiro, "Perturbation Analysis of Optimization Problems,", Springer, (2000). Google Scholar

[3]

J. Borwein and H. Wolkowicz, Facial reduction for a cone-convex programming problem,, J. Austral. Math. Soc. Ser. A, 30 (): 369. Google Scholar

[4]

J. Borwein and H. Wolkowicz, Regularizing the abstract convex program,, J. Math. Anal. Appl., 83 (1981), 495. doi: 10.1016/0022-247X(81)90138-4. Google Scholar

[5]

E. de Klerk, C. Roos and T. Terlaky, Infeasible start semidefinite programming algorithms via self-dual embeddings,, Fields Inst. Commun., 18 (1998), 215. Google Scholar

[6]

K. Kortanek and Q. Zhang, Perfect duality in semi-infinite and semidefinite programming,, Math. Program., 91 (2001), 127. Google Scholar

[7]

Z. Luo, J. Sturm and S. Zhang, "Duality Results for Conic Convex Programming,", Technical Report, (9719). Google Scholar

[8]

M. Ramana, An exact duality theory for semidefinite programming and its complexity implications,, Math. Program., 77 (1997), 129. Google Scholar

[9]

M. Ramana, L. Tunçel and H. Wolkowicz, Strong duality for semidefinite programming,, SIAM J. Optim., 7 (1997), 641. Google Scholar

[10]

R. Rockafellar, "Convex Analysis,", Princeton University Press, (1970). Google Scholar

[11]

J. Sturm, "Primal-Dual Interior Point Approach to Semidefinite Programming,", Ph.D thesis, (1997). Google Scholar

[12]

M. Todd, Semidefinite optimization,, Acta. Numer., 10 (2001), 515. doi: 10.1017/S0962492901000071. Google Scholar

[13]

L. Vandenberghe and S. Boyd, Semidefinite programming,, SIAM Review, 38 (1996), 49. doi: 10.1137/1038003. Google Scholar

[14]

H. Wolkowicz, Some applications of optimization in matrix theory,, Linear Algebra Appl., 40 (1981), 101. doi: 10.1016/0024-3795(81)90143-9. Google Scholar

[15]

Q. Zhang, Embedding methods for semidefinite programming,, submitted for publication., (). Google Scholar

[1]

Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial & 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 & 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 & Continuous Dynamical Systems - A, 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 & Management Optimization, 2005, 1 (1) : 33-38. doi: 10.3934/jimo.2005.1.33

[5]

Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187

[6]

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

[7]

Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019015

[8]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193

[9]

Yuying Zhou, Gang Li. The Toland-Fenchel-Lagrange duality of DC programs for composite convex functions. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 9-23. doi: 10.3934/naco.2014.4.9

[10]

Andrzej Nowakowski, Jan Sokolowski. On dual dynamic programming in shape control. Communications on Pure & Applied Analysis, 2012, 11 (6) : 2473-2485. doi: 10.3934/cpaa.2012.11.2473

[11]

Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003

[12]

Xinmin Yang. On second order symmetric duality in nondifferentiable multiobjective programming. Journal of Industrial & Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697

[13]

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

[14]

Cristian Dobre. Mathematical properties of the regular *-representation of matrix $*$-algebras with applications to semidefinite programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 367-378. doi: 10.3934/naco.2013.3.367

[15]

Xinmin Yang, Jin Yang, Heung Wing Joseph Lee. Strong duality theorem for multiobjective higher order nondifferentiable symmetric dual programs. Journal of Industrial & Management Optimization, 2013, 9 (3) : 525-530. doi: 10.3934/jimo.2013.9.525

[16]

Xinmin Yang, Xiaoqi Yang, Kok Lay Teo. Higher-order symmetric duality in multiobjective programming with invexity. Journal of Industrial & Management Optimization, 2008, 4 (2) : 385-391. doi: 10.3934/jimo.2008.4.385

[17]

Xinmin Yang, Xiaoqi Yang. A note on mixed type converse duality in multiobjective programming problems. Journal of Industrial & Management Optimization, 2010, 6 (3) : 497-500. doi: 10.3934/jimo.2010.6.497

[18]

Yuhua Sun, Laisheng Wang. Optimality conditions and duality in nondifferentiable interval-valued programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 131-142. doi: 10.3934/jimo.2013.9.131

[19]

Xian-Jun Long, Jing Quan. Optimality conditions and duality for minimax fractional programming involving nonsmooth generalized univexity. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 361-370. doi: 10.3934/naco.2011.1.361

[20]

Deepak Singh, Bilal Ahmad Dar, Do Sang Kim. Sufficiency and duality in non-smooth interval valued programming problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 647-665. doi: 10.3934/jimo.2018063

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (8)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]