An alternating direction method for second-order conic programming. (English) Zbl 1348.90518
Summary: An alternating direction dual augmented Lagrangian method for second-order cone programming (SOCP) problems is proposed. In the algorithm, at each iteration it first minimizes the dual augmented Lagrangian function with respect to the dual variables, and then with respect to the dual slack variables while keeping the other two variables fixed, and then finally it updates the Lagrange multipliers. Convergence result is given. Numerical results demonstrate that our method is fast and efficient, especially for the large-scale second-order cone programming.
Keywords:
second-order cone programming; dual augmented Lagrangian method; alternating direction method; primal-dual interior point methodReferences:
| [1] | Lobo, M. S.; Vandenberghe, L.; Boyd, S.; Lebret, H., Application of second order cone programming, Linear Algebra and Its Applications, 284, 193-228 (1998) · Zbl 0946.90050 |
| [2] | Lebret, H.; Boyd, S., Antenna array pattern synthesis via convex optimization, IEEE Transactions on Signal Processing, 45, 526-532 (1997) |
| [3] | Lu, W. S.; Hinamoto, T., Optimal design of IIR digital filters with robust stability using conic-quadratic-programming updates, IEEE Transactions on Signal Processing, 51, 1581-1592 (2003) · Zbl 1369.94217 |
| [4] | Luo, Z. Q., Applications of convex optimization in signal processing and digital communication, Mathematical Programming, 97B, 177-207 (2003) · Zbl 1035.90059 |
| [5] | Rika, Ita; Fujie, T.; Suyama, K.; Hirabayashi, R., Design methods of FIR filters with signed power of two coefficients using a new linear programming relaxation with triangle inequalities, International Journal of Innovative Computing, Information and Control, 2, 441-448 (2006) |
| [6] | Monteiro, R. D.C.; Takashi, Tsuchiya, Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions, Mathematical Programming, 88, 61-83 (2000) · Zbl 0967.65077 |
| [7] | Alizadeh, F.; Goldfarb, D., Second-order cone programming, Mathematical Programming, 95, 3-51 (2003) · Zbl 1153.90522 |
| [8] | Kuo, Yuju; Mittelmann, Hans D., Interior point methods for second-order cone programming and OR applications, Computational Optimization and Application, 28, 255-285 (2004) · Zbl 1084.90046 |
| [9] | Cai, Z.; Toh, K-C., Solving SOCP via a reduced augmented system, SIAM Journal on Optimization, 17, 711-737 (2006) · Zbl 1128.90045 |
| [11] | Chen, X. D.; Sun, D.; Sun, J., Complementarity functions and numerical experiments for second-order cone complementarity problems, Computational Optimization and Applications, 25, 39-56 (2003) · Zbl 1038.90084 |
| [12] | Fukushima, M.; Luo, Z. Q.; Tseng, P., Smoothing functions for second-order cone complementarity problems, SIAM Journal on Optimization, 12, 436-460 (2002) · Zbl 0995.90094 |
| [13] | Chen, J. S.; Tseng, P., An unconstrained smooth minimization reformulation of the second-order cone complementarity problems, Mathematical Programming, 104, 293-327 (2005) · Zbl 1093.90063 |
| [14] | Kanzow, C.; Ferenczi, I.; Fukushima, M., On the local convergence of semismooth Newton methods for linear and nonlinear second-order cone programs without strict complementarity, SIAM Journal on Optimization, 20, 297-320 (2009) · Zbl 1190.90239 |
| [15] | Gabay, D., Applications of the method of multipliers to variational inequalities, (Fortin, M.; Glowinski, R., Augmented Lagrangian methodsapplications to the numerical solution of boundary-value problem (1983), North-Holland: North-Holland Amsterdam), 299-331 · Zbl 0525.65045 |
| [16] | Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Computers and Mathematics with Applications, 2, 17-40 (1976) · Zbl 0352.65034 |
| [17] | He, B.; Liao, L.-Z.; Han, D.; Yang, H., A new inexact alternating directions method for monotone variational inequalities, Mathematical Programming, 92, 103-118 (2002) · Zbl 1009.90108 |
| [18] | 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, 337-356 (2000) · Zbl 0997.49008 |
| [19] | Ye, C.; Yuan, X., A descent method for structured monotone variational inequalities, Optimization Methods and Software, 22, 329-338 (2007) · Zbl 1196.90118 |
| [21] | Chen, G.; Teboulle, M., A proximal-based decomposition method for convex minimization problems, Mathematical Programming, 64, 81-101 (1994) · Zbl 0823.90097 |
| [22] | Eckstein, J.; Bertsekas, D. P., On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming, 55, 293-318 (1992) · Zbl 0765.90073 |
| [23] | Kiwiel, K. C.; Rosa, C. H.; Ruszczyński, A., Proximal decomposition via alternating linearization, SIAM Journal on Optimization, 9, 668-689 (1999) · Zbl 0958.65068 |
| [24] | Kontogiorgis, S.; Meyer, R. R., A variable-penalty alternating directions method for convex optimization, Mathematical Programming, 83, 29-53 (1998) · Zbl 0920.90118 |
| [25] | Malick, J.; Povh, J.; Rendl, F.; Wiegele, A., Regularization methods for semidefinite programming, SIAM Journal on Optimization, 20, 336-356 (2009) · Zbl 1187.90219 |
| [26] | Tseng, P., Alternating projection-proximal methods for convex programming and variational inequalities, SIAM Journal on Optimization, 7, 951-965 (1997) · Zbl 0914.90218 |
| [27] | Wang, Y.; Yang, J.; Yin, W.; Zhang, Y., A new alternating minimization algorithm for total variation image reconstruction, SIAM Journal on Imaging Sciences, 1, 248-272 (2008) · Zbl 1187.68665 |
| [28] | Yang, J.; Zhang, Y.; Yin, W., An efficient tvl1 algorithm for deblurring multichannel images corrupted by impulsive noise, SIAM Journal on Scientific Computing, 31, 2842-2865 (2008) · Zbl 1195.68110 |
| [29] | Yu, Z., Solving semidefinite programming problems via alternating direction methods, Journal of Computational and Applied Mathematics, 193, 437-445 (2006) · Zbl 1098.65069 |
| [30] | Wen, Z.; Goldfarb, D.; Yin, W., Alternating direction augmented Lagrangian methods for semidefinite programming, Mathematical Programming Computation, 2, 203-230 (2010) · Zbl 1206.90088 |
| [33] | Outrata, Jiřì V.; Sun, Defeng, On the coderivative of the projection operator onto the second-order cone, Set-Valued and Variational Analysis, 16, 999-1014 (2008) · Zbl 1161.49011 |
| [34] | Kong, Lingchen; Tuncel, Levent; Xiu, Naihua, Clarke generalized Jacobian of the projection onto symmetric cones, Set-Valued and Variational Analysis, 17, 135-151 (2009) · Zbl 1168.49043 |
| [35] | Sun, Jie; Zhang, Su, A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs, European Journal of Operational Research, 207, 1210-1220 (2010) · Zbl 1229.90119 |
| [36] | Sturm, J. F., Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optimization Methods and Software, 11-12, 625-653 (1999) · Zbl 0973.90526 |
| [38] | Ye, Y.; Todd, M. J.; Mizuno, S., An \(O(\sqrt{n} L)\)-iteration homogeneous and self-dual linear programming algorithm, Mathematics of Operations Research, 19, 53-67 (1994) · Zbl 0799.90087 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
