Using regularization and second order information in outer approximation for convex MINLP. (English) Zbl 1461.65168
Summary: In this paper, we present two new methods for solving convex mixed-integer nonlinear programming problems based on the outer approximation method. The first method is inspired by the level method and uses a regularization technique to reduce the step size when choosing new integer combinations. The second method combines ideas from both the level method and the sequential quadratic programming technique and uses a second order approximation of the Lagrangean when choosing the new integer combinations. The main idea behind the methods is to choose the integer combination more carefully at each iteration, in order to obtain the optimal solution in fewer iterations compared to the original outer approximation method. We prove rigorously that both methods will find and verify the optimal solution in a finite number of iterations. Furthermore, we present a numerical comparison of the methods based on 109 test problems to illustrate their advantages.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C11 | Mixed integer programming |
| 90C30 | Nonlinear programming |
| 90C55 | Methods of successive quadratic programming type |
References:
| [1] | Bagirov, A.; Karmitsa, N.; Mäkelä, Mm, Introduction to Nonsmooth Optimization: Theory, Practice and Software (2014), Berlin: Springer, Berlin · Zbl 1312.90053 |
| [2] | 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 · doi:10.1017/S0962492913000032 |
| [3] | Biegler, Lt; Grossmann, Ie, Retrospective on optimization, Comput. Chem. Eng., 28, 8, 1169-1192 (2004) · doi:10.1016/j.compchemeng.2003.11.003 |
| [4] | 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, Discr. Optim., 5, 2, 186-204 (2008) · Zbl 1151.90028 · doi:10.1016/j.disopt.2006.10.011 |
| [5] | Bonami, P.; Cornuéjols, G.; Lodi, A.; Margot, F., A feasibility pump for mixed integer nonlinear programs, Math. Program., 119, 2, 331-352 (2009) · Zbl 1163.90013 · doi:10.1007/s10107-008-0212-2 |
| [6] | Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1058.90049 |
| [7] | Currie, J.; Wilson, Di; Sahinidis, N.; Pinto, J., OPTI: lowering the barrier between open source optimizers and the industrial MATLAB user, Foundations of Computer-Aided Process Operations (2012), Georgia: Savannah, Georgia |
| [8] | Dakin, Rj, A tree-search algorithm for mixed integer programming problems, Comput. J., 8, 3, 250-255 (1965) · Zbl 0154.42004 · doi:10.1093/comjnl/8.3.250 |
| [9] | Dolan, Ed; Moré, Jj, Benchmarking optimization software with performance profiles, Math. Program. Ser. B, 91, 2, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263 |
| [10] | 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 |
| [11] | Den Hertog, D.; Kaliski, J.; Roos, C.; Terlaky, T., A logarithmic barrier cutting plane method for convex programming, Ann. Oper. Res., 58, 2, 67-98 (1995) · Zbl 0836.90126 · doi:10.1007/BF02032162 |
| [12] | De Oliveira, W., Regularized optimization methods for convex MINLP problems, TOP, 24, 3, 665-692 (2016) · Zbl 1358.90086 · doi:10.1007/s11750-016-0413-4 |
| [13] | Fletcher, R.; Leyffer, S., Solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 1, 327-349 (1994) · Zbl 0833.90088 · doi:10.1007/BF01581153 |
| [14] | Floudas, Christodoulos A., Deterministic Global Optimization (2000), Boston, MA: Springer US, Boston, MA · Zbl 0980.49027 |
| [15] | GAMSWorld: mixed-integer nonlinear programming library. http://www.gamsworld.org/minlp/minlplib2/html/ (2016). Accessed 24 Nov 2016 |
| [16] | Geoffrion, Am, Generalized Benders decomposition, J. Optim. Theory Appl., 10, 4, 237-260 (1972) · Zbl 0229.90024 · doi:10.1007/BF00934810 |
| [17] | Gershgorin, Sa, Uber die Abgrenzung der Eigenwerte einer Matrix, Bulletin de l’Académie des Sciences de l’URSS. Classe des sciences mathématiques et na, 6, 749-754 (1931) · Zbl 0003.00102 |
| [18] | Grossmann, I.E., Viswanathan, J., Vecchietti, A., Raman, R., Kalvelagen, E.: GAMS/DICOPT: A Discrete Continuous Optimization Package (2002) |
| [19] | Gurobi Optimization, I.: Gurobi optimizer reference manual. http://www.gurobi.com (2016) |
| [20] | V12.6: User’s Manual for CPLEX, Int. Bus. Mach. Corp., 12, 1, 481 (2009) |
| [21] | Kelley, Je Jr, The cutting-plane method for solving convex programs, J. Soc. Ind. Appl. Math., 8, 4, 703-712 (1960) · Zbl 0098.12104 · doi:10.1137/0108053 |
| [22] | Kiwiel, Kc, Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities, Math. Program., 69, 1-3, 89-109 (1995) · Zbl 0857.90101 |
| [23] | Kronqvist, J.; Lundell, A.; Westerlund, T., The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming, J. Glob. Optim., 64, 2, 249-272 (2016) · Zbl 1339.90247 · doi:10.1007/s10898-015-0322-3 |
| [24] | Kronqvist, J.; Lundell, A.; Westerlund, T., Reformulations for utilizing separability when solving convex MINLP problems, J. Glob. Optim., 71, 3, 571-592 (2018) · Zbl 1402.90098 · doi:10.1007/s10898-018-0616-3 |
| [25] | Lee, J.; Leyffer, S., Mixed Integer Nonlinear Programming (2011), Berlin: Springer, Berlin |
| [26] | Lemaréchal, C.; Nemirovskii, A.; Nesterov, Y., New variants of bundle methods, Math. Program., 69, 1-3, 111-147 (1995) · Zbl 0857.90102 · doi:10.1007/BF01585555 |
| [27] | Nesterov, Y., Introductory Lectures on Convex Optimization: A Basic Course (2004), Berlin: Springer, Berlin · Zbl 1086.90045 |
| [28] | Quesada, I.; Grossmann, Ie, An LP/NLP based branch and bound algorithm for convex MINLP optimization problems, Comput. Chem. Eng., 16, 10-11, 937-947 (1992) · doi:10.1016/0098-1354(92)80028-8 |
| [29] | Slater, M., et al.: Lagrange multipliers revisited. Technical report, Cowles Foundation for Research in Economics, Yale University (1959) |
| [30] | Trespalacios, F.; Grossmann, Ie, Review of mixed-integer nonlinear and generalized disjunctive programming methods, Chem. Ing. Tech., 86, 7, 991-1012 (2014) · doi:10.1002/cite.201400037 |
| [31] | Viswanathan, J.; Grossmann, Ie, A combined penalty function and outer-approximation method for MINLP optimization, Comput. Chem. Eng., 14, 7, 769-782 (1990) · doi:10.1016/0098-1354(90)87085-4 |
| [32] | Wächter, A.; Biegler, Lt, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, 25-57 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y |
| [33] | Wei, Z.; Ali, Mm, Outer approximation algorithm for one class of convex mixed-integer nonlinear programming problems with partial differentiability, J. Optim. Theory Appl., 167, 2, 644-652 (2015) · Zbl 1327.90145 · doi:10.1007/s10957-015-0715-y |
| [34] | Westerlund, T.; Petterson, F., An extended cutting plane method for solving convex MINLP problems, Comput. Chem. Eng., 19, S131-S136 (1995) · doi:10.1016/0098-1354(95)00164-W |
| [35] | 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 · doi:10.1023/A:1021091110342 |
| [36] | Wolfe, P., A duality theorem for non-linear programming, Q. Appl. Math., 19, 3, 239-244 (1961) · Zbl 0109.38406 · doi:10.1090/qam/135625 |
| [37] | Zaourar, S., Malick, J.: Quadratic stabilization of Benders decomposition. https://hal.archives-ouvertes.fr/hal-01181273 (2014). Working paper or preprint · Zbl 1291.90300 |
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.
