×

zbMATH — the first resource for mathematics

On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions. (English) Zbl 1342.90130
Summary: In this paper, we establish the convergence properties for a majorized alternating direction method of multipliers for linearly constrained convex optimization problems, whose objectives contain coupled functions. Our convergence analysis relies on the generalized Mean-Value Theorem, which plays an important role to properly control the cross terms due to the presence of coupled objective functions. Our results, in particular, show that directly applying two-block alternating direction method of multipliers with a large step length of the golden ratio to the linearly constrained convex optimization problem with a quadratically coupled objective function is convergent under mild conditions. We also provide several iteration complexity results for the algorithm.

MSC:
90C25 Convex programming
68Q25 Analysis of algorithms and problem complexity
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Gabay, D.: Applications of the method of multipliers to variational inequalities. In: Fortin M., Glowinski R. (eds.) Augmented Lagrangian Methods: Applications to the Solution of Boundary Problems, pp. 299-331. North-Holland, Amsterdam (1983)
[2] Gabay, D; Mercier, B, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2, 17-40, (1976) · Zbl 0352.65034
[3] Glowinski, R.: Lectures on Numerical Methods for Non-linear Variational Problems, Tata Institute of Fundamental Research Lectures on Mathematics and Physics, Notes by Vijayasundaram, G and Adimurthi, M, vol. 65. Springer, Berlin (1980) · Zbl 0456.65035
[4] Glowinski, R; Marroco, A, Approximation by finite elements of order one and solution by penalization-duality of a class of nonlinear Dirichlet problems, Revue française d’automatique, informatique, recherche opérationnelle. Analyse numérique, 9, 41-76, (1975) · Zbl 0368.65053
[5] Eckstein, J., Bertsekas, D.P.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(1), 293-318 (1992) · Zbl 0765.90073
[6] Eckstein, J., Yao, W.: Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives. Pac. J. Optim. 11(4), 619-644 (2014) · Zbl 1330.90074
[7] Hong, M., Chang, T.H., Wang, X., Razaviyayn, M., Ma, S., Luo, Z.Q.: A block successive upper bound minimization method of multipliers for linearly constrained convex optimization. arXiv preprint arXiv:1401.7079 (2014) · Zbl 1320.90060
[8] Chen, C., He, B., Ye, Y., Yuan, X.: The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math. Program. 155(1), 57-79 (2016) · Zbl 1332.90193
[9] Clarke, F.H.: Optimization and Nonsmooth Analysis, vol. 5. SIAM, Philadelphia (1990) · Zbl 0696.49002
[10] Hiriart-Urruty, J.B., Strodiot, J.J., Nguyen, V.H.: Generalized hessian matrix and second-order optimality conditions for problems with \(C^{1, 1}\) data. Appl. Math. Optim. 11(1), 43-56 (1984) · Zbl 0542.49011
[11] Li, M., Sun, D., Toh, K.C.: A majorized admm with indefinite proximal terms for linearly constrained convex composite optimization. SIAM J. Optim. (to appear) · Zbl 1338.90305
[12] He, B; Yuan, X, On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers, Numerische Mathematik, 130, 567-577, (2012) · Zbl 1320.90060
[13] Deng, W., Lai, M., Peng, Z., Yin, W.: Parallel multi-block admm with o(1/k) convergence. arXiv preprint arXiv:1312.3040 (2013)
[14] Davis, D., Yin, W.: Convergence rate analysis of several splitting schemes. arXiv preprint arXiv:1406.4834 (2014) · Zbl 1372.65168
[15] Li, X., Sun, D., Toh, K.C.: A schur complement based semi-proximal admm for convex quadratic conic programming and extensions. Math. Program. 155(1), 333-373 (2016) · Zbl 1342.90134
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.