×
Jiao, Hong-Wei; Huang, Ya-Kui; Chen, Jing

A novel approach for solving semidefinite programs. (English) Zbl 1442.90139

J. Appl. Math. 2014, Article ID 613205, 9 p. (2014).
Summary: A novel linearizing alternating direction augmented Lagrangian approach is proposed for effectively solving semidefinite programs (SDP). For every iteration, by fixing the other variables, the proposed approach alternatively optimizes the dual variables and the dual slack variables; then the primal variables, that is, Lagrange multipliers, are updated. In addition, the proposed approach renews all the variables in closed forms without solving any system of linear equations. Global convergence of the proposed approach is proved under mild conditions, and two numerical problems are given to demonstrate the effectiveness of the presented approach.

MSC:

90C22 Semidefinite programming
65K05 Numerical mathematical programming methods

Software:

BiqMac; 2EBD-HPE; Biq Mac
PDF BibTeX XML Cite
\textit{H.-W. Jiao} et al., J. Appl. Math. 2014, Article ID 613205, 9 p. (2014; Zbl 1442.90139)
Full Text: DOI

References:

[1] Alizadeh, F., Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM Journal on Optimization, 5, 1, 13-51 (1995) · Zbl 0833.90087
[2] Boyd, S.; El Ghaoui, L.; Feron, E.; Balakrishnan, V., Linear Matrix Inequalities in System and Control Theory (1994), Philadelphia, Pa, USA: SIAM, Philadelphia, Pa, USA · Zbl 0816.93004
[3] Fujie, T.; Kojima, M., Semidefinite programming relaxation for nonconvex quadratic programs, Journal of Global Optimization, 10, 4, 367-380 (1997) · Zbl 0881.90101
[4] Alfakih, A. Y.; Khandani, A.; Wolkowicz, H., Solving Euclidean distance matrix completion problems via semidefinite programming, Computational Optimization and Applications, 12, 1-3, 13-30 (1999) · Zbl 1040.90537
[5] Anjos, M.; Lasserre, J. B., Handbook on Semidefinite, Conic and Polynomial Optimization (2012), New York, NY, USA: Springer, New York, NY, USA · Zbl 1235.90002
[6] Nesterov, Y.; Nemirovskii, A., Interior-Point Polynomial Algorithms in Convex Programming. Interior-Point Polynomial Algorithms in Convex Programming, SIAM Studies in Applied Mathematics (1994), Philadelphia, Pa, USA: SIAM, Philadelphia, Pa, USA · Zbl 0824.90112
[7] Monteiro, R. D. C., Primal-dual path-following algorithms for semidefinite programming, SIAM Journal on Optimization, 7, 3, 663-678 (1997) · Zbl 0913.65051
[8] Helmberg, C.; Rendl, F.; Vanderbei, R. J.; Wolkowicz, H., An interior-point method for semidefinite programming, SIAM Journal on Optimization, 6, 2, 342-361 (1996) · Zbl 0853.65066
[9] Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM Review, 38, 1, 49-95 (1996) · Zbl 0845.65023
[10] Toh, K.; Kojima, M., Solving some large scale semidefinite programs via the conjugate residual method, SIAM Journal on Optimization, 12, 3, 669-691 (2002) · Zbl 1008.90043
[11] Toh, K., Solving large scale semidefinite programs via an iterative solver on the augmented systems, SIAM Journal on Optimization, 14, 3, 670-698 (2003) · Zbl 1071.90026
[12] Povh, J.; Rendl, F.; Wiegele, A., A boundary point method to solve semidefinite programs, Computing, 78, 3, 277-286 (2006) · Zbl 1275.90055
[13] Malick, J.; Povh, J.; Rendl, F.; Wiegele, A., Regularization methods for semidefinite programming, SIAM Journal on Optimization, 20, 1, 336-356 (2009) · Zbl 1187.90219
[14] Huang, A.; Xu, C., A trust region method for solving semidefinite programs, Computational Optimization and Applications, 55, 1, 49-71 (2013) · Zbl 1273.90146
[15] Zhao, X.; Sun, D.; Toh, K., A Newton-CG augmented Lagrangian method for semidefinite programming, SIAM Journal on Optimization, 20, 4, 1737-1765 (2010) · Zbl 1213.90175
[16] Wen, Z.; Goldfarb, D.; Yin, W., Alternating direction augmented Lagrangian methods for semidefinite programming, Mathematical Programming Computation, 2, 3-4, 203-230 (2010) · Zbl 1206.90088
[17] Wen, Z.; Goldfarb, D.; Ma, S.; Scheinberg, K., Row by row methods for semidefinite programming (2009), Department of IEOR, Columbia University
[18] Xu, Y.; Sun, W.; Qi, L., A feasible direction method for the semidefinite program with box constraints, Applied Mathematics Letters, 24, 11, 1874-1881 (2011) · Zbl 1231.65108
[19] Zhadan, V. G.; Orlov, A. A., Dual interior point methods for linear semidefinite programming problems, Computational Mathematics and Mathematical Physics, 51, 12, 2031-2051 (2011) · Zbl 1249.90194
[20] Lin, H., An inexact spectral bundle method for convex quadratic semidefinite programming, Computational Optimization and Applications, 53, 1, 45-89 (2011) · Zbl 1282.90120
[21] Sun, J.; Zhang, S., A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs, European Journal of Operational Research, 207, 3, 1210-1220 (2010) · Zbl 1229.90119
[22] Auslender, A.; Ramírez, C. H., Penalty and barrier methods for convex semidefinite programming, Mathematical Methods of Operations Research, 63, 2, 195-219 (2006) · Zbl 1137.90639
[23] Zhang, S.; Ang, J.; Sun, J., An alternating direction method for solving convex nonlinear semidefinite programming problems, Optimization, 62, 4, 527-543 (2013) · Zbl 1282.65073
[24] Huang, X. X.; Yang, X. Q.; Teo, K. L., Lower-order penalization approach to nonlinear semidefinite programming, Journal of Optimization Theory and Applications, 132, 1, 1-20 (2007) · Zbl 1156.90010
[25] Aroztegui, M.; Herskovits, J.; Roche, J. R.; Bazn, E., A feasible direction interior point algorithm for nonlinear semidefinite programming, Structural and Multidisciplinary Optimization, 132, 1, 1-20 (2007)
[26] Yang, L.; Yu, B., A homotopy method for nonlinear semidefinite programming, Computational Optimization and Applications, 56, 1, 81-96 (2013) · Zbl 1298.90067
[27] Kanzow, C.; Nagel, C.; Kato, H.; Fukushima, M., Successive linearization methods for nonlinear semidefinite programs, Computational Optimization and Applications, 31, 3, 251-273 (2005) · Zbl 1122.90058
[28] Yamashita, H.; Yabe, H.; Harada, K., A primal-dual interior point method for nonlinear semidefinite programming, Mathematical Programming, 135, 1-2, 89-121 (2012) · Zbl 1273.90150
[29] Lu, Z.; Nemirovski, A.; Monteiro, R. D. C., Large-scale semidefinite programming via a saddle point mirror-prox algorithm, Mathematical Programming, 109, 2-3, 211-237 (2006) · Zbl 1148.90009
[30] Monteiro, R. D. C.; Ortiz, C.; Svaiter, B. F., A first-order block-decomposition method for solving two-easy-block structured semidefinite programs, Mathematical Programming Computation, 6, 2, 103-150 (2014) · Zbl 1342.49045
[31] Chen, J. H.; Yang, T. B.; Zhu, S. H., Efficient low-rank stochastic gradient descent methods for solving semidefinite programs, Proceedings of the 17th International Conference on Artificial Intelligence and Statistics
[32] Wang, G. Q.; Bai, Y. Q., A new primal-dual path-following interior-point algorithm for semidefinite optimization, Journal of Mathematical Analysis and Applications, 353, 1, 339-349 (2009) · Zbl 1172.90011
[33] Yu, Z., Solving semidefinite programming problems via alternating direction methods, Journal of Computational and Applied Mathematics, 193, 2, 437-445 (2006) · Zbl 1098.65069
[34] Xu, M. H.; Wu, T., A class of linearized proximal alternating direction methods, Journal of Optimization Theory and Applications, 151, 2, 321-337 (2011) · Zbl 1242.90168
[35] Tseng, P., Alternating projection-proximal methods for convex programming and variational inequalities, SIAM Journal on Optimization, 7, 4, 951-965 (1997) · Zbl 0914.90218
[36] Kiwiel, K. C.; Rosa, C. H.; Ruszczynski, A., Proximal decomposition via alternating linearization, SIAM Journal on Optimization, 9, 3, 668-689 (1999) · Zbl 0958.65068
[37] He, B. S.; Yang, H.; Wang, S. L., Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities, Journal of Optimization Theory and Applications, 106, 2, 337-356 (2000) · Zbl 0997.49008
[38] Barzilai, J.; Borwein, J. M., Two-point step size gradient methods, IMA Journal of Numerical Analysis, 8, 1, 141-148 (1988) · Zbl 0638.65055
[39] Eisenblätter, A.; Grötschel, M. A., Frequency planning and ramifications of coloring, Discussiones Mathematicae. Graph Theory, 22, 1, 51-88 (2002) · Zbl 1055.05147
[40] Burer, S.; Monteiro, R. D. C.; Zhang, Y., A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs, Mathematical Programming, 95, 2, 359-379 (2003) · Zbl 1030.90076
[41] Wiegele, A., Biq Mac Library—a collection of Max-Cut and quadratic 0-1 programming instances of medium size (2007)
[42] Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Mathematical Programming, 91, 2, 201-213 (2002) · Zbl 1049.90004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.