×

zbMATH — the first resource for mathematics

Infeasibility detection in the alternating direction method of multipliers for convex optimization. (English) Zbl 1429.90050
Summary: The alternating direction method of multipliers is a powerful operator splitting technique for solving structured optimization problems. For convex optimization problems, it is well known that the algorithm generates iterates that converge to a solution, provided that it exists. If a solution does not exist, then the iterates diverge. Nevertheless, we show that they yield conclusive information regarding problem infeasibility for optimization problems with linear or quadratic objective functions and conic constraints, which includes quadratic, second-order cone, and semidefinite programs. In particular, we show that in the limit the iterates either satisfy a set of first-order optimality conditions or produce a certificate of either primal or dual infeasibility. Based on these results, we propose termination criteria for detecting primal and dual infeasibility.

MSC:
90C25 Convex programming
90C20 Quadratic programming
90C06 Large-scale problems in mathematical programming
90C22 Semidefinite programming
68Q25 Analysis of algorithms and problem complexity
Software:
SDPLIB; SCS; UNLocBoX; OSQP
PDF BibTeX Cite
Full Text: DOI
References:
[1] Parikh, N.; Boyd, S., Proximal algorithms, Found. Trends Optim., 1, 123-231, (2013)
[2] Bauschke, HH; Borwein, JM, On projection algorithms for solving convex feasibility problems, SIAM Rev., 38, 367-426, (1996) · Zbl 0865.47039
[3] Bauschke, HH; Combettes, PL; Luke, DR, Finding best approximation pairs relative to two closed convex sets in Hilbert spaces, J. Approx. Theory, 127, 178-192, (2004) · Zbl 1050.46021
[4] Boley, D., Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs, SIAM J. Optim., 23, 2183-2207, (2013) · Zbl 1288.65086
[5] O’Donoghue, B.; Chu, E.; Parikh, N.; Boyd, S., Conic optimization via operator splitting and homogeneous self-dual embedding, J. Optim. Theory Appl., 169, 1042-1068, (2016) · Zbl 1342.90136
[6] Zheng, Y.; Fantuzzi, G.; Papachristodoulou, A.; Goulart, P.; Wynn, A., Chordal decomposition in operator-splitting methods for sparse semidefinite programs, Math. Program., (2019)
[7] O’Donoghue, B.; Stathopoulos, G.; Boyd, S., A splitting method for optimal control, IEEE Trans. Control Syst. Technol., 21, 2432-2442, (2013)
[8] Jerez, J.; Goulart, P.; Richter, S.; Constantinides, G.; Kerrigan, E.; Morari, M., Embedded online optimization for model predictive control at megahertz rates, IEEE Trans. Autom. Control, 59, 3238-3251, (2014) · Zbl 1360.93235
[9] Banjac, G., Stellato, B., Moehle, N., Goulart, P., Bemporad, A., Boyd, S.: Embedded code generation using the OSQP solver. In: IEEE Conference on Decision and Control (CDC), pp. 1906-1911 (2017). https://doi.org/10.1109/CDC.2017.8263928
[10] Beck, A.; Teboulle, M., Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Trans. Image Process., 18, 2419-2434, (2009) · Zbl 1371.94049
[11] Combettes, PL; Wajs, VR, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4, 1168-1200, (2005) · Zbl 1179.94031
[12] Combettes, PL; Pesquet, JC, Proximal splitting methods in signal processing, Springer Optim. Appl., 49, 185-212, (2011) · Zbl 1242.90160
[13] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1-122, (2011) · Zbl 1229.90122
[14] Stathopoulos, G.; Shukla, H.; Szucs, A.; Pu, Y.; Jones, C., Operator splitting methods in control, Found. Trends Syst. Control, 3, 249-362, (2016)
[15] Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011). https://doi.org/10.1007/978-1-4419-9467-7 · Zbl 1218.47001
[16] Ghadimi, E.; Teixeira, A.; Shames, I.; Johansson, M., Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems, IEEE Trans. Autom. Control, 60, 644-658, (2015) · Zbl 1360.90182
[17] Giselsson, P.; Boyd, S., Linear convergence and metric selection for Douglas-Rachford splitting and ADMM, IEEE Trans. Autom. Control, 62, 532-544, (2017) · Zbl 1364.90256
[18] Banjac, G.; Goulart, P., Tight global linear convergence rate bounds for operator splitting methods, IEEE Trans. Autom. Control, 63, 4126-4139, (2018) · Zbl 1423.90175
[19] Naik, V.V., Bemporad, A.: Embedded mixed-integer quadratic optimization using accelerated dual gradient projection. In: IFAC World Congress, pp. 10,723-10,728 (2017). https://doi.org/10.1016/j.ifacol.2017.08.2235
[20] Eckstein, J.; Bertsekas, DP, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 293-318, (1992) · Zbl 0765.90073
[21] Bauschke, HH; Dao, MN; Moursi, WM, The Douglas-Rachford algorithm in the affine-convex case, Oper. Res. Lett., 44, 379-382, (2016) · Zbl 1408.90231
[22] Bauschke, HH; Moursi, WM, The Douglas-Rachford algorithm for two (not necessarily intersecting) affine subspaces, SIAM J. Optim., 26, 968-985, (2016) · Zbl 1341.47064
[23] Bauschke, HH; Moursi, WM, On the Douglas-Rachford algorithm, Math. Program., 164, 263-284, (2017) · Zbl 06751028
[24] Moursi, W.M.: The Douglas-Rachford operator in the possibly inconsistent case: static properties and dynamic behaviour. Ph.D. thesis, University of British Columbia (2016). https://doi.org/10.14288/1.0340501
[25] Raghunathan, A.U., Di Cairano, S.: Infeasibility detection in alternating direction method of multipliers for convex quadratic programs. In: IEEE Conference on Decision and Control (CDC), pp. 5819-5824 (2014). https://doi.org/10.1109/CDC.2014.7040300
[26] Toh, KC, An inexact primal-dual path following algorithm for convex quadratic SDP, Math. Program., 112, 221-254, (2008) · Zbl 1136.90027
[27] Henrion, D., Malick, J.: Projection Methods in Conic Optimization, pp. 565-600. Springer, New York (2012). https://doi.org/10.1007/978-1-4614-0769-0_20 · Zbl 1334.90105
[28] Stellato, B., Banjac, G., Goulart, P., Bemporad, A., Boyd, S.: OSQP: an operator splitting solver for quadratic programs. arXiv:1711.08013 (2018)
[29] Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Grundlehren der mathematischen Wissenschaften. Springer, New York (1998). https://doi.org/10.1007/978-3-642-02431-3 · Zbl 0888.49001
[30] Lourenço, BF; Muramatsu, M.; Tsuchiya, T., Weak infeasibility in second order cone programming, Optim. Lett., 10, 1743-1755, (2016) · Zbl 1391.90578
[31] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[32] Boyd, S., Vandenberghe, L.: Convex Optim. Cambridge University Press, Cambridge (2004). https://doi.org/10.1017/CBO9780511804441 · Zbl 1058.90049
[33] Gabay, D., Applications of the method of multipliers to variational inequalities, Stud. Math. Appl., 15, 299-331, (1983)
[34] Giselsson, P., Fält, M., Boyd, S.: Line search for averaged operator iteration. In: IEEE Conference on Decision and Control (CDC), pp. 1015-1022 (2016). https://doi.org/10.1109/CDC.2016.7798401
[35] Lions, P.; Mercier, B., Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16, 964-979, (1979) · Zbl 0426.65050
[36] Pazy, A., Asymptotic behavior of contractions in Hilbert space, Isr. J. Math., 9, 235-240, (1971) · Zbl 0225.54032
[37] Baillon, JB; Bruck, RE; Reich, S., On the asymptotic behavior of nonexpansive mappings and semigroups in Banach spaces, Houst. J. Math., 4, 1-9, (1978) · Zbl 0396.47033
[38] Borchers, B., SDPLIB 1.2, a library of semidefinite programming test problems, Optim. Methods Softw., 11, 683-690, (1999) · Zbl 0973.90522
[39] Ramana, MV, An exact duality theory for semidefinite programming and its complexity implications, Math. Program., 77, 129-162, (1997) · Zbl 0890.90144
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.