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

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[2]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[3]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311
[4]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451
[5]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Recent progresses in the theory of nonlinear nonlocal problems. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : i-i. doi: 10.3934/dcdss.2020446
[6]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349
[7]

John Leventides, Costas Poulios, Georgios Alkis Tsiatsios, Maria Livada, Stavros Tsipras, Konstantinos Lefcaditis, Panagiota Sargenti, Aleka Sargenti. Systems theory and analysis of the implementation of non pharmaceutical policies for the mitigation of the COVID-19 pandemic. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021004

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences