×

zbMATH — the first resource for mathematics

Outer-approximation algorithms for nonsmooth convex MINLP problems. (English) Zbl 1401.90133
Summary: In this work, we combine outer-approximation (OA) and bundle method algorithms for dealing with mixed-integer non-linear programming (MINLP) problems with nonsmooth convex objective and constraint functions. As the convergence analysis of OA methods relies strongly on the differentiability of the involved functions, OA algorithms may fail to solve general nonsmooth convex MINLP problems. In order to obtain OA algorithms that are convergent regardless the structure of the convex functions, we solve the underlying OA’s nonlinear subproblems by a specialized bundle method that provides necessary information to cut off previously visited (non-optimal) integer points. This property is crucial for proving (finite) convergence of OA algorithms. We illustrate the numerical performance of the given proposal on a class of hybrid robust and chance-constrained problems that involve a random variable with finite support.

MSC:
90C11 Mixed integer programming
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Belotti, P; Kirches, C; Leyffer, S; Linderoth, J; Luedtke, J; Mahajan, A, Mixed-integer nonlinear optimization, Acta Numer, 22, 1-131, (2013) · Zbl 1291.65172
[2] Bonami, P; Biegler, LT; Conn, AR; Cornuéjols, G; Grossmann, IE; Laird, CD; Lee, J; Lodi, A; Margot, F; Sawaya, N; Wächter, A, An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim, 5, 2, 186-204, (2008) · Zbl 1151.90028
[3] Bonvin, G; Demassey, S; Le Pape, C; Maïzi, N; Mazauric, V; Samperio, A, A convex mathematical program for pump scheduling in a class of branched water networks, Appl Energy, 185, 1702-1711, (2017)
[4] de Oliveira, W, Regularized optimization methods for convex MINLP problems, TOP, 24, 3, 665-692, (2016) · Zbl 1358.90086
[5] Dubost, L; Gonzalez, R; Lemaréchal, C, A primal-proximal heuristic applied to the French unit-commitment problem, Math Program, 104, 1, 129-151, (2005) · Zbl 1077.90083
[6] Eronen, VP; Mäkelä, MM; Westerlund, T, On the generalization of ECP and OA methods to nonsmooth convex MINLP problems, Optimization, 63, 7, 1057-1073, (2014) · Zbl 1295.90022
[7] Grossmann, IE, Review of nonlinear mixed-integer and disjunctive programming techniques, Optim Eng, 3, 3, 227-252, (2002) · Zbl 1035.90050
[8] Hemmecke, R; Köppe, M; Lee, J; Weismantel, R; Jünger, M; Liebling, TM; Naddef, D; Nemhauser, GL; Pulleyblank, WR; Reinelt, G; Rinaldi, G; Wolsey, LA, 50 years of integer programming 1958–2008: from the early years to the state-of-the-art, Nonlinear integer programming, 561-618, (2010), Springer, Berlin
[9] van Ackooij, W; Frangioni, A; de Oliveira, W, Inexact stabilized benders’ decomposition approaches with application to chance-constrained problems with finite support, Comput Optim Appl, 65, 637-669, (2016) · Zbl 1357.90104
[10] Wei, Z; Ali, MM, Convex mixed integer nonlinear programming problems and an outer approximation algorithm, J Global Optim, 63, 2, 213-227, (2015) · Zbl 1327.90144
[11] Westerlund, T; Pörn, R, Solving pseudo-convex mixed integer optimization problems by cutting plane techniques, Optim Eng, 3, 3, 253-280, (2002) · Zbl 1035.90051
[12] van Ackooij, W, A comparison of four approaches from stochastic programming for large-scale unit-commitment, EURO J Comput Optim, 5, 119-147, (2017) · Zbl 1361.90044
[13] Kelley, JE Jr, The cutting-plane method for solving convex programs, J Soc Indus Appl Math, 8, 4, 703-712, (1960) · Zbl 0098.12104
[14] Benders, JF, Partitioning procedures for solving mixed variables programming problems, Numer Math, 4, 238-252, (1962) · Zbl 0109.38302
[15] Geoffrion, AM, Generalized benders’ decomposition, J Optim Theory Appl, 10, 237-260, (1972) · Zbl 0229.90024
[16] 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
[17] Fletcher, R; Leyffer, S, Solving mixed integer nonlinear programs by outer approximation, Math Program, 66, 1-3, 327-349, (1994) · Zbl 0833.90088
[18] Quesseda, I; Grossamann, IE, An LP/NLP based branch and bound algorithm for convex MINLP optimization problem, Comput Chem Eng, 16, 937-947, (1992)
[19] Bagirov, A; Karmitsa, N; Mäkelä, MM, Introduction to nonsmooth optimization: theory, practice and software, (2014), Springer International Publishing, Switzerland · Zbl 1312.90053
[20] Bonnans, JF; Gilbert, JCh; Lemaréchal, C; Sagastizábal, C, Numerical optimization. Theoretical and practical aspects, (2006), Universitext, Springer-Verlag, Berlin
[21] Westerlund, T; Petterson, F, An extended cutting plane method for solving convex MINLP problems, Comput Chem Eng, 19, 131-136, (1995)
[22] Hiriart-Urruty, JB; Lemaréchal, C, Convex analysis and minimization algorithms II, 306, (1996), Springer-Verlag, Berlin Heidelberg
[23] Lemaréchal, C, An algorithm for minimizing convex functions, Inform Process, 1974, 552-556, (1974)
[24] de Oliveira, W; Sagastizábal, C; Lemaréchal, C, Convex proximal bundle methods in depth: a unified analysis for inexact oracles, Math Program, 148, 241-277, (2014) · Zbl 1327.90321
[25] de Oliveira, W; Solodov, M, A doubly stabilized bundle method for nonsmooth convex optimization, Math Program, 156, 1, 125-159, (2016) · Zbl 1346.90675
[26] Frangioni, A, Generalized bundle methods, SIAM J Optim, 13, 1, 117-156, (2002) · Zbl 1041.90037
[27] Kiwiel, KC, A proximal bundle method with approximate subgradient linearizations, SIAM J Optim, 16, 4, 1007-1023, (2006) · Zbl 1104.65055
[28] van Ackooij, W; Sagastizábal, C, Constrained bundle methods for upper inexact oracles with application to joint chance constrained energy problems, SIAM J Optim, 24, 2, 733-765, (2014) · Zbl 1297.49057
[29] Ruszczyński, A, Nonlinear optimization, (2006), Princeton University Press, Princeton (NJ)
[30] Kiwiel, KC, Exact penalty functions in proximal bundle methods for constrained convex nondifferentiable minimization, Math Program, 52, 1, 285-302, (1991) · Zbl 0754.90045
[31] Hiriart-Urruty, JB; Lemaréchal, C, Convex analysis and minimization algorithms I, 305, (1996), Springer-Verlag, Berlin Heidelberg
[32] Rockafellar, RT; Wets, RJ-B, Variational analysis, 317, (2009), Springer Verlag, Berlin Heidelberg
[33] van Ackooij, W; de Oliveira, W, Level bundle methods for constrained convex optimization with various oracles, Comput Optim Appl, 57, 555-597, (2014) · Zbl 1329.90109
[34] Zaourar, S; Malick, J, Quadratic stabilization of benders decomposition, (2014), INRIA - Grenoble
[35] González, GT; Heitsch, H; Henrion, R, A joint model of probabilistic/robust constraints for gas transport management in stationary networks, Comput Manage Sci, 14, 443-460, (2017) · Zbl 1397.90092
[36] Bertsimas, D; Brown, DB; Caramanis, C, Theory and applications of robust optimization, SIAM Rev, 53, 3, 464-501, (2011) · Zbl 1233.90259
[37] Gurobi Optimization. Gurobi optimizer reference manual, (2016)
[38] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math Program, 91, 201-213, (2002) · Zbl 1049.90004
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.