×

Operator splitting for a homogeneous embedding of the linear complementarity problem. (English) Zbl 1479.90202

Authors’ abstract: We present a first-order quadratic cone programming algorithm that can scale to very large problem sizes and produce modest accuracy solutions quickly. Our algorithm returns primal-dual optimal solutions when available or certificates of infeasibility otherwise. It is derived by applying Douglas-Rachford splitting to a homogeneous embedding of the linear complementarity problem, which is a general set membership problem that includes quadratic cone programs (QCPs) as a special case. Each iteration of our procedure requires projecting onto a convex cone and solving a linear system with a fixed coefficient matrix. If a sequence of related problems are solved, then the procedure can easily be warm-started and make use of factorization caching of the linear system. We demonstrate on a range of public and synthetic datasets that for feasible problems our approach tends to be somewhat faster than applying operator splitting directly to the QCP, and in cases of infeasibility our approach can be significantly faster than alternative approaches based on diverging iterates. The algorithm we describe has been implemented in C and is available open-source in the solver SCS v3.0.
Reviewer: Bing Tan (Chengdu)

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C20 Quadratic programming
65K05 Numerical mathematical programming methods
65K10 Numerical optimization and variational techniques
90C05 Linear programming
90C06 Large-scale problems in mathematical programming
90C22 Semidefinite programming
90C25 Convex programming
90C30 Nonlinear programming
90C46 Optimality conditions and duality in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] A. Ali, E. Wong, and J. Z. Kolter, A semismooth Newton method for fast, generic convex programming, in Proceedings of the International Conference on Machine Learning, PMLR, 2017, pp. 70-79.
[2] E. D. Andersen and Y. Ye, On a homogeneous algorithm for the monotone complementarity problem, Math. Program., 84 (1999), pp. 375-399. · Zbl 0972.90078
[3] D. Applegate, M. Díaz, H. Lu, and M. Lubin, Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming, preprint, https://arxiv.org/abs/2102.04592, 2021.
[4] G. Banjac, On the minimal displacement vector of the Douglas-Rachford operator, Oper. Res. Lett., 49 (2021), pp. 197-200. · Zbl 07331252
[5] G. Banjac, P. Goulart, B. Stellato, and S. Boyd, Infeasibility detection in the alternating direction method of multipliers for convex optimization, J. Optim. Theory Appl., 183 (2019), pp. 490-519. · Zbl 1429.90050
[6] G. Banjac and J. Lygeros, On the asymptotic behavior of the Douglas-Rachford and proximal-point algorithms for convex optimization, Optim. Lett., (2021), pp. 1-14.
[7] H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed., CMS Books Math. 408, Springer, New York, 2017. · Zbl 1359.26003
[8] B. Borchers, SDPLIB 1.2, a library of semidefinite programming test problems, Optim. Methods Softw., 11 (1999), pp. 683-690. · Zbl 0973.90522
[9] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Machine Learning, 3 (2011), pp. 1-122. · Zbl 1229.90122
[10] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, UK, 2004. · Zbl 1058.90049
[11] S. P. Boyd, M. T. Mueller, B. O’Donoghue, and Y. Wang, Performance bounds and suboptimal policies for multi-period investment, Found. Trends Optim., 1 (2014), pp. 1-69.
[12] K. Bredies and H. Sun, Preconditioned Douglas-Rachford splitting methods for convex-concave saddle-point problems, SIAM J. Numer. Anal., 53 (2015), pp. 421-444. · Zbl 1314.65084
[13] E. F. Camacho and C. B. Alba, Model Predictive Control, Springer, New York, 2013.
[14] E. Chu, B. O’Donoghue, N. Parikh, and S. Boyd, A Primal-Dual Operator Splitting Method for Conic Optimization, Tech. report, Stanford University, 2013.
[15] R. W. Cottle, J.-S. Pang, and R. E. Stone, The Linear Complementarity Problem, Classics in Appl. Math. 60, SIAM, Philadelphia, 1992. · Zbl 0757.90078
[16] D. Davis and W. Yin, Convergence rate analysis of several splitting schemes, in Splitting Methods in Communication, Imaging, Science, and Engineering, Springer, New York, 2016, pp. 115-163. · Zbl 1372.65168
[17] T. A. Davis, Direct Methods for Sparse Linear Systems, Fundam. Algorithms 2, SIAM, Philadelphia, 2006.
[18] S. Diamond and S. Boyd, CVXPY: A Python-Embedded Modeling Language for Convex Optimization. http://web.stanford.edu/ boyd/papers/cvxpy_paper.html, 2015. · Zbl 1360.90008
[19] E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), pp. 201-213. · Zbl 1049.90004
[20] J. Douglas and H. H. Rachford, On the numerical solution of heat conduction problems in two and three space variables, Trans. Amer. Math. Soc., 82 (1956), pp. 421-439. · Zbl 0070.35401
[21] I. Dunning, J. Huchette, and M. Lubin, JuMP: A modeling language for mathematical optimization, SIAM Rev., 59 (2017), pp. 295-320, https://doi.org/10.1137/15M1020575. · Zbl 1368.90002
[22] B. C. Eaves, The linear complementarity problem, Management Sci., 17 (1971), pp. 612-634. · Zbl 0228.15004
[23] J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), pp. 293-318. · Zbl 0765.90073
[24] C. Fougner and S. Boyd, Parameter selection and preconditioning for a graph form solver, in Emerging Applications of Control and Systems Theory, Springer, New York, 2018, pp. 41-61. · Zbl 1407.93126
[25] D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, Stud. Math. Appl. 15, Elsevier, Amsterdam, 1983, pp. 299-331.
[26] M. Garstka, M. Cannon, and P. Goulart, COSMO: A conic operator splitting method for large convex problems, in Proceedings of the European Control Conference, 2019, https://doi.org/10.23919/ECC.2019.8796161.
[27] D. M. Gay, Electronic mail distribution of linear programming test problems, Mathematical Programming Society COAL Newsletter, 13 (1985), pp. 10-12.
[28] P. Giselsson and S. Boyd, Linear convergence and metric selection for Douglas-Rachford splitting and ADMM, IEEE Trans. Automat. Control, 62 (2016), pp. 532-544. · Zbl 1364.90256
[29] A. J. Goldman and A. W. Tucker, Theory of linear programming, Linear Inequalities and Related Systems, 38 (1956), pp. 53-97. · Zbl 0072.37601
[30] T. Goldstein, B. O’Donoghue, S. Setzer, and R. Baraniuk, Fast alternating direction optimization methods, SIAM J. Imaging Sci., 7 (2014), pp. 1588-1623. · Zbl 1314.49019
[31] M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming, version 2.0 beta, http://cvxr.com/cvx, Sept. 2013.
[32] B. He and X. Yuan, On the convergence rate of douglas-rachford operator splitting method, Math. Program., 153 (2015), pp. 715-722. · Zbl 1327.90211
[33] B. Hermans, A. Themelis, and P. Patrinos, QPALM: A Newton-type proximal augmented Lagrangian method for quadratic programs, in Proceedings of the 58th IEEE Conference on Decision and Control, IEEE, 2019, pp. 4325-4330.
[34] P. Jain, P. Netrapalli, and S. Sanghavi, Low-rank matrix completion using alternating minimization, in Proceedings of the 45th Annual ACM Symposium on Theory of Computing, 2013, pp. 665-674. · Zbl 1293.65073
[35] V. Koltchinskii, K. Lounici, and A. B. Tsybakov, Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion, Ann. Statist., 39 (2011), pp. 2302-2329. · Zbl 1231.62097
[36] E. L. Lawler and D. E. Wood, Branch-and-bound methods: A survey, Oper. Res., 14 (1966), pp. 699-719. · Zbl 0143.42501
[37] P.-L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16 (1979), pp. 964-979. · Zbl 0426.65050
[38] Y. Liu, E. K. Ryu, and W. Yin, A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs, Math. Program., 177 (2019), pp. 225-253. · Zbl 07089030
[39] J. Löfberg, YALMIP: A toolbox for modeling and optimization in MATLAB, in Proceedings of the IEEE International Symposium on Computed Aided Control Systems Design, 2004, pp. 294-289.
[40] B. F. Lourenço, M. Muramatsu, and T. Tsuchiya, Weak infeasibility in second order cone programming, Optim. Lett., 10 (2016), pp. 1743-1755. · Zbl 1391.90578
[41] B. F. Lourenço, M. Muramatsu, and T. Tsuchiya, Solving SDP completely with an interior point oracle, Optim. Methods Softw., 36 (2021), pp. 425-471. · Zbl 1470.90066
[42] Z.-Q. Luo, J. Sturm, and S. Zhang, Duality Results for Conic Convex Programming, Econometric Institute Research Papers EI 9719/A, https://EconPapers.repec.org/RePEc:ems:eureir:1412, 1997.
[43] H. M. Markowitz, Foundations of portfolio theory, J. Finance, 46 (1991), pp. 469-477.
[44] I. Maros and C. Mészáros, A repository of convex quadratic programming problems, Optim. Methods Softw., 11 (1999), pp. 671-681. · Zbl 0973.90520
[45] C. Meszaros, The practical behavior of the homogeneous self-dual formulations in interior point methods, CEJOR Cent. Eur. J. Oper. Res., 23 (2015), pp. 913-924. · Zbl 1339.90333
[46] G. J. Minty, On the maximal domain of a “monotone” function, Michigan Math. J., 8 (1961), pp. 135-137. · Zbl 0102.37503
[47] G. J. Minty, Monotone (nonlinear) operators in Hilbert space, Duke Math. J., 29 (1962), pp. 341-346. · Zbl 0111.31202
[48] W. M. Moursi and L. Vandenberghe, Douglas-Rachford splitting for the sum of a Lipschitz continuous and a strongly monotone operator, J. Optim. Theory Appl., 183 (2019), pp. 179-198. · Zbl 07112082
[49] K. G. Murty and F.-T. Yu, Linear Complementarity, Linear and Nonlinear Programming, Vol. 3, Heldermann, Berlin, 1988.
[50] V. Nair, S. Bartunov, F. Gimeno, I. von Glehn, P. Lichocki, I. Lobov, B. O’Donoghue, N. Sonnerat, C. Tjandraatmadja, P. Wang, et al., Solving Mixed Integer Programs Using Neural Networks, preprint, https://arxiv.org/abs/2012.13349, 2020.
[51] A. Nemirovski, Advances in convex optimization: conic programming, in Proceedings of the International Congress of Mathematicians, Vol. 1, 2007, pp. 413-444. · Zbl 1135.90379
[52] Y. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming, Stud. Appl. Numer. Math. 13, SIAM, Philadelphia, 1994. · Zbl 0824.90112
[53] W. S. Noble, What is a support vector machine?, Nature Biotechnology, 24 (2006), pp. 1565-1567.
[54] J. Nocedal and S. Wright, Numerical Optimization, Springer, New York, 2006. · Zbl 1104.65059
[55] J. Nocedal and S. J. Wright, Sequential quadratic programming, in Numerical Optimization, Springer, New York, 2006, pp. 529-562.
[56] B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd, Conic optimization via operator splitting and homogeneous self-dual embedding, J. Optim. Theory Appl., 169 (2016), pp. 1042-1068, http://stanford.edu/ boyd/papers/scs.html. · Zbl 1342.90136
[57] B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd, SCS: Splitting Conic Solver, Version 2.1.0. https://github.com/cvxgrp/scs, 2017.
[58] B. O’Donoghue and C. J. Maddison, Hamiltonian descent for composite objectives, in Advances in Neural Information Processing Systems, 2019, pp. 14443-14453.
[59] B. O’Donoghue, G. Stathopoulos, and S. Boyd, A splitting method for optimal control, IEEE Trans. Control Systems Technology, 21 (2013), pp. 2432-2442.
[60] N. Parikh and S. Boyd, Proximal algorithms, Found. Trends Optim., 1 (2014), pp. 127-239.
[61] D. W. Peaceman and H. H. Rachford, Jr., The numerical solution of parabolic and elliptic differential equations, J. SIAM, 3 (1955), pp. 28-41. · Zbl 0067.35801
[62] F. Permenter, H. A. Friberg, and E. D. Andersen, Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach, SIAM J. Optim., 27 (2017), pp. 1257-1282. · Zbl 1368.90123
[63] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970. · Zbl 0193.18401
[64] R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14 (1976), pp. 877-898. · Zbl 0358.90053
[65] E. K. Ryu and S. Boyd, Primer on monotone operator methods, Appl. Comput. Math., 15 (2016), pp. 3-43. · Zbl 1342.47066
[66] P. Sopasakis, K. Menounou, and P. Patrinos, SuperSCS: Fast and accurate large-scale conic optimization, in Proceedings of the 18th European Control Conference, IEEE, 2019, pp. 1500-1505.
[67] G. Stathopoulos, H. A. Shukla, A. Szuecs, Y. Pu, and C. Jones, Operator splitting methods in control, Found. Trends Systems Control, 3 (2016), pp. 249-362.
[68] B. Stellato, G. Banjac, P. Goulart, A. Bemporad, and S. Boyd, OSQP: An operator splitting solver for quadratic programs, Math. Program. Comput., 12 (2020), pp. 637-672, https://doi.org/10.1007/s12532-020-00179-2. · Zbl 1452.90236
[69] A. Themelis and P. Patrinos, SuperMann: A superlinearly convergent algorithm for finding fixed points of nonexpansive operators, IEEE Trans. Automat. Control, 64 (2019), pp. 4875-4890. · Zbl 1482.49019
[70] R. Tibshirani, Regression shrinkage and selection via the lasso, J. R. Stat. Soc. Ser. B Stat. Methodol., 58 (1996), pp. 267-288. · Zbl 0850.62538
[71] J. W. Tolle, Sequential quadratic programming, Acta Numer. 4, (1995), pp. 1-51. · Zbl 0828.65060
[72] P. Tseng, A modified forward-backward splitting method for maximal monotone mappings, SIAM J. Control Optim., 38 (2000), pp. 431-446. · Zbl 0997.90062
[73] M. Udell, K. Mohan, D. Zeng, J. Hong, S. Diamond, and S. Boyd, Convex optimization in Julia, in Proceedings of the SC14 Workshop on High Performance Technical Computing in Dynamic Languages, 2014.
[74] R. J. Vanderbei, Symmetric quasidefinite matrices, SIAM J. Optim., 5 (1995), pp. 100-113. · Zbl 0822.65017
[75] Z. Wen, D. Goldfarb, and W. Yin, Alternating direction augmented Lagrangian methods for semidefinite programming, Math. Program. Comput., 2 (2010), pp. 203-230. · Zbl 1206.90088
[76] Y. Ye, On homogeneous and self-dual algorithms for LCP, Math. Program., 76 (1997), pp. 211-221. · Zbl 0881.90116
[77] Y. Ye, M. J. Todd, and S. Mizuno, An o \(( \sqrt{nL} )\)-iteration homogeneous and self-dual linear programming algorithm, Math. Oper. Res., 19 (1994), pp. 53-67. · Zbl 0799.90087
[78] J. Zhang, B. O’Donoghue, and S. Boyd, Globally convergent type-I Anderson acceleration for non-smooth fixed-point iterations, SIAM J. Optim., 30 (2020), pp. 3170-3197. · Zbl 07284421
[79] Y. Zheng, G. Fantuzzi, A. Papachristodoulou, P. Goulart, and A. Wynn, Chordal decomposition in operator-splitting methods for sparse semidefinite programs, Math. Program., 180 (2020), pp. 489-532. · Zbl 1434.90126
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.