Distributed primal outer approximation algorithm for sparse convex programming with separable structures. (English) Zbl 1530.90077
Summary: This paper presents the distributed primal outer approximation (DiPOA) algorithm for solving sparse convex programming (SCP) problems with separable structures, efficiently, and in a decentralized manner. The DiPOA algorithm development consists of embedding the recently proposed relaxed hybrid alternating direction method of multipliers (RH-ADMM) algorithm into the outer approximation (OA) algorithm. We also propose two main improvements to control the quality and the number of cutting planes that approximate nonlinear functions. In particular, the RH-ADMM algorithm acts as a distributed numerical engine inside the DiPOA algorithm. DiPOA takes advantage of the multi-core architecture of modern processors to speed up optimization algorithms. The proposed distributed algorithm makes practical the solution of SCP in learning and control problems from the application side. This paper concludes with a performance analysis of DiPOA for the distributed sparse logistic regression and quadratically constrained optimization problems. Finally, the paper concludes with a numerical comparison with state-of-the-art optimization solvers.
MSC:
| 90C25 | Convex programming |
| 90C11 | Mixed integer programming |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
Keywords:
outer approximation; sparse convex programming; distributed optimization; message passing interfaceReferences:
| [1] | Aguilera, RP; Urrutia, G.; Delgado, RA; Dolz, D.; Agüero, JC, Quadratic model predictive control including input cardinality constraints, IEEE Trans. Autom. Control, 62, 6, 3068-3075 (2017) · Zbl 1369.93328 · doi:10.1109/TAC.2017.2674185 |
| [2] | Aytug, H., Feature selection for support vector machines using generalized benders decomposition, Eur. J. Oper. Res., 244, 1, 210-218 (2015) · Zbl 1347.62105 · doi:10.1016/j.ejor.2015.01.006 |
| [3] | Bai, Y.; Liang, R.; Yang, Z., Splitting augmented Lagrangian method for optimization problems with a cardinality constraint and semicontinuous variables, Optim. Methods Softw., 31, 5, 1089-1109 (2016) · Zbl 1355.90053 · doi:10.1080/10556788.2016.1196206 |
| [4] | Bernal, DE; Vigerske, S.; Trespalacios, F.; Grossmann, IE, Improving the performance of DICOPT in convex MINLP problems using a feasibility pump, Optim. Methods Softw., 35, 1, 171-190 (2020) · Zbl 1425.90070 · doi:10.1080/10556788.2019.1641498 |
| [5] | Bertsimas, D.; Cory-Wright, R., A scalable algorithm for sparse portfolio selection, INFORMS J. Comput. (2022) · Zbl 07552219 · doi:10.1287/ijoc.2021.1127 |
| [6] | Bertsimas, D., Dunn, J.: Machine learning under a modern optimization lens. Dyn. Ideas LLC (2019) |
| [7] | Bertsimas, D.; King, A., Best subset selection via a modern optimization lens, Ann. Stat., 44, 2, 813-852 (2016) · Zbl 1335.62115 · doi:10.1214/15-AOS1388 |
| [8] | Bertsimas, D.; King, A., Logistic regression: From art to science, Stat. Sci., 32, 3, 367-384 (2017) · Zbl 1442.62166 · doi:10.1214/16-STS602 |
| [9] | Bertsimas, D.; Mundru, N., Sparse convex regression, INFORMS J. Comput., 33, 1, 262-279 (2021) · Zbl 07362315 · doi:10.1287/ijoc.2020.0954 |
| [10] | Bertsimas, D., Pauphilet, J., Parys, B.V.: Sparse classification: a scalable discrete optimization perspective. Mach. Learn. 110(October) (2021). doi:10.1007/s10994-021-06085-5 · Zbl 07465779 |
| [11] | Bertsimas, D.; Shioda, R., Algorithm for cardinality-constrained quadratic optimization, Comput. Optim. Appl., 43, 1, 1-22 (2009) · Zbl 1178.90262 · doi:10.1007/s10589-007-9126-9 |
| [12] | Bienstock, D., Computational study of a family of mixed-integer quadratic programming problems, Math. Program., 74, 2, 121-140 (1996) · Zbl 0855.90090 · doi:10.1007/BF02592208 |
| [13] | Blumensath, T., Compressed sensing with nonlinear observations and related nonlinear optimization problems, IEEE Trans. Inf. Theory, 59, 6, 3466-3474 (2013) · Zbl 1364.94111 · doi:10.1109/TIT.2013.2245716 |
| [14] | Blumensath, T.; Davies, ME, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal., 27, 3, 265-274 (2009) · Zbl 1174.94008 · doi:10.1016/j.acha.2009.04.002 |
| [15] | Bourguignon, S.; Ninin, J.; Carfantan, H.; Mongeau, M., Exact sparse approximation problems via mixed-integer programming: Formulations and computational performance, IEEE Trans. Signal Process., 64, 6, 1405-1419 (2015) · Zbl 1412.94020 · doi:10.1109/TSP.2015.2496367 |
| [16] | Boyd, S.; Boyd, SP; Vandenberghe, L., Convex Optimization (2004), Cambridge: Cambridge university press, Cambridge · Zbl 1058.90049 · doi:10.1017/CBO9780511804441 |
| [17] | Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J., et al.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends® in Machine Learning 3(1), 1-122 (2011). doi:10.1561/2200000016 · Zbl 1229.90122 |
| [18] | Candès, EJ, The restricted isometry property and its implications for compressed sensing, C.R. Math., 346, 9-10, 589-592 (2008) · Zbl 1153.94002 · doi:10.1016/j.crma.2008.03.014 |
| [19] | Duran, MA; Grossmann, IE, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 3, 307-339 (1986) · Zbl 0619.90052 · doi:10.1007/BF02592064 |
| [20] | Fletcher, R.; Ley, S., Solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 327-349 (1994) · Zbl 0833.90088 · doi:10.1007/BF01581153 |
| [21] | Geoffrion, AM, Generalized benders decomposition, J. Optim. Theory Appl., 10, 4, 237-260 (1972) · Zbl 0229.90024 · doi:10.1007/BF00934810 |
| [22] | Gropp, W.; Lusk, E.; Skjellum, A., Using MPI: Portable Parallel Programming with the Message-Passing Interface (2014), Cambridge: MIT Press, Cambridge |
| [23] | Grossmann, I., Review of nonlinear mixed-integer and disjunctive programming techniques, Optim. Eng., 3, 3, 227-252 (2002) · Zbl 1035.90050 · doi:10.1023/A:1021039126272 |
| [24] | Gurobi Optimization, L.: Gurobi optimizer reference manual (2020). http://www.gurobi.com |
| [25] | Hastie, T.; Tibshirani, R.; Tibshirani, R., Best subset, forward stepwise or lasso? Analysis and recommendations based on extensive comparisons, Stat. Sci., 35, 4, 579-592 (2020) · Zbl 07307187 · doi:10.1214/19-STS733 |
| [26] | Hijazi, H.; Bonami, P.; Cornuéjols, G.; Ouorou, A., Mixed-integer nonlinear programs featuring on/off constraints, Comput. Optim. Appl., 52, 2, 537-558 (2012) · Zbl 1250.90058 · doi:10.1007/s10589-011-9424-0 |
| [27] | James, G.; Witten, D.; Hastie, T.; Tibshirani, R., An Introduction to Statistical Learning (2013), Berlin: Springer, Berlin · Zbl 1281.62147 · doi:10.1007/978-1-4614-7138-7 |
| [28] | Kamiya, S., Miyashiro, R., Takano, Y.: Feature subset selection for the multinomial logit model via mixed-integer optimization. In: the 22nd International Conference on Artificial Intelligence and Statistics, pp. 1254-1263. PMLR (2019) |
| [29] | Kronqvist, J.; Bernal, DE; Grossmann, IE, Using regularization and second order information in outer approximation for convex MINLP, Math. Program., 180, 1-2, 285-310 (2020) · Zbl 1461.65168 · doi:10.1007/s10107-018-1356-3 |
| [30] | Kronqvist, J.; Bernal, DE; Lundell, A.; Grossmann, IE, review and comparison of solvers for convex MINLP, Optim. Eng., 20, 2, 397-455 (2019) · doi:10.1007/s11081-018-9411-8 |
| [31] | Kronqvist, J.; Lundell, A.; Westerlund, T., The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming, J. Global Optim., 64, 2, 249-272 (2016) · Zbl 1339.90247 · doi:10.1007/s10898-015-0322-3 |
| [32] | Kronqvist, J.; Lundell, A.; Westerlund, T., Reformulations for utilizing separability when solving convex MINLP problems, J. Global Optim., 71, 3, 571-592 (2018) · Zbl 1402.90098 · doi:10.1007/s10898-018-0616-3 |
| [33] | Lundell, A., Kronqvist, J.: Integration of polyhedral outer approximation algorithms with MIP solvers through callbacks and lazy constraints. In: AIP Conference Proceedings 2070(March) (2019). doi:10.1063/1.5089979 |
| [34] | Ma, M.; Nikolakopoulos, AN; Giannakis, GB, Hybrid admm: a unifying and fast approach to decentralized optimization, EURASIP J. Adv. Signal Process., 2018, 1, 1-17 (2018) · doi:10.1186/s13634-018-0589-x |
| [35] | Murray, A.; Faulwasser, T.; Hagenmeyer, V.; Villanueva, ME; Houska, B., Partially distributed outer approximation, J. Global Optim., 80, 523-550 (2021) · Zbl 1473.90094 · doi:10.1007/s10898-021-01015-0 |
| [36] | Muts, P.; Nowak, I.; Hendrix, EM, The decomposition-based outer approximation algorithm for convex mixed-integer nonlinear programming, J. Global Optim., 77, 75-96 (2020) · Zbl 1441.90100 · doi:10.1007/s10898-020-00888-x |
| [37] | Nedić, A.; Liu, J., Distributed optimization for control, Ann. Rev. Control Robot. Autonom. Syst., 1, 77-103 (2018) · doi:10.1146/annurev-control-060117-105131 |
| [38] | Nedić, A.; Olshevsky, A., Distributed optimization over time-varying directed graphs, IEEE Trans. Autom. Control, 60, 3, 601-615 (2015) · Zbl 1360.90262 · doi:10.1109/TAC.2014.2364096 |
| [39] | Notarstefano, G., Notarnicola, I., Camisa, A., et al.: Distributed optimization for smart cyber-physical networks. Found. Trends® Syst. Control 7(3), 253-383 (2019). doi:10.1561/2600000020 |
| [40] | Olama, A.; Bastianello, N.; Mendes, PR; Camponogara, E., Relaxed hybrid consensus ADMM for distributed convex optimisation with coupling constraints, IET Control Theory Appl., 13, 17, 2828-2837 (2019) · doi:10.1049/iet-cta.2018.6260 |
| [41] | Ryu, EK; Boyd, S., Primer on monotone operator methods, Appl. Comput. Math, 15, 1, 3-43 (2016) · Zbl 1342.47066 |
| [42] | Sant’Anna, LR; de Oliveira, AD; Filomena, TP; Caldeira, JF, Solving the index tracking problem based on a convex reformulation for cointegration, Financ. Res. Lett., 37 (2020) · doi:10.1016/j.frl.2019.101356 |
| [43] | Su, L.; Tang, L.; Bernal, DE; Grossmann, IE, Improved quadratic cuts for convex mixed-integer nonlinear programs, Comput. Chem. Eng., 109, 77-95 (2018) · doi:10.1016/j.compchemeng.2017.10.011 |
| [44] | Su, L.; Tang, L.; Grossmann, IE, Computational strategies for improved MINLP algorithms, Comput. Chem. Eng., 75, 40-48 (2015) · doi:10.1016/j.compchemeng.2015.01.015 |
| [45] | Sun, X.; Zheng, X.; Li, D., Recent advances in mathematical programming with semi-continuous variables and cardinality constraint, J. Oper. Res. Soc. China, 1, 1, 55-77 (2013) · Zbl 1277.90001 · doi:10.1007/s40305-013-0004-0 |
| [46] | Tibshirani, R., Regression shrinkage and selection via the lasso, J. R. Stat. Soc.: Ser. B (Methodol.), 58, 1, 267-288 (1996) · Zbl 0850.62538 · doi:10.1111/j.2517-6161.1996.tb02080.x |
| [47] | Tillmann, A.M., Bienstock, D., Lodi, A., Schwartz, A.: Cardinality minimization, constraints, and regularization: a survey. arXiv preprint arXiv:2106.09606 (2021) |
| [48] | Wang, F.; Cao, L., A new algorithm for quadratic integer programming problems with cardinality constraint, Jpn. J. Ind. Appl. Math., 37, 449-460 (2020) · Zbl 1442.90134 · doi:10.1007/s13160-019-00403-0 |
| [49] | Westerlund, T.; Pettersson, F., An extended cutting plane method for solving convex MINLP problems, Comput. Chem. Eng., 19, 131-136 (1995) · doi:10.1016/0098-1354(95)87027-X |
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.
