American Institute of Mathematical Sciences

Advanced
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

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 & 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.  Google Scholar

[2]

J. Bonnans and A. Shapiro, "Perturbation Analysis of Optimization Problems," Springer, New York, 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-530. 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-236.  Google Scholar

[6]

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

[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. Google Scholar

[8]

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

[9]

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

[10]

R. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, New Jersey, 1970.  Google Scholar

[11]

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

[12]

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

[13]

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

[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.  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-32.  Google Scholar

[2]

J. Bonnans and A. Shapiro, "Perturbation Analysis of Optimization Problems," Springer, New York, 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-530. 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-236.  Google Scholar

[6]

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

[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. Google Scholar

[8]

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

[9]

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

[10]

R. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, New Jersey, 1970.  Google Scholar

[11]

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

[12]

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

[13]

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

[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.  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, 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]

Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & 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 & 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 & 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 & Optimization, 2014, 4 (1) : 9-23. doi: 10.3934/naco.2014.4.9
[11]

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
[12]

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
[13]

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
[14]

Tone-Yau Huang, Tamaki Tanaka. Optimality and duality for complex multi-objective programming. Numerical Algebra, Control & Optimization, 2022, 12 (1) : 121-134. doi: 10.3934/naco.2021055
[15]

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
[16]

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
[17]

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
[18]

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
[19]

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
[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

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (57)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy