×

On solving generalized convex MINLP problems using supporting hyperplane techniques. (English) Zbl 1397.90286

Summary: Solution methods for convex mixed integer nonlinear programming (MINLP) problems have, usually, proven convergence properties if the functions involved are differentiable and convex. For other classes of convex MINLP problems fewer results have been given. Classical differential calculus can, though, be generalized to more general classes of functions than differentiable, via subdifferentials and subgradients. In addition, more general than convex functions can be included in a convex problem if the functions involved are defined from convex level sets, instead of being defined as convex functions only. The notion generalized convex, used in the heading of this paper, refers to such additional properties. The generalization for the differentiability is made by using subgradients of Clarke’s subdifferential. Thus, all the functions in the problem are assumed to be locally Lipschitz continuous. The generalization of the functions is done by considering quasiconvex functions. Thus, instead of differentiable convex functions, nondifferentiable \(f^\circ\)-quasiconvex functions can be included in the actual problem formulation and a supporting hyperplane approach is given for the solution of the considered MINLP problem. Convergence to a global minimum is proved for the algorithm, when minimizing an \(f^\circ\)-pseudoconvex function, subject to \(f^\circ\)-pseudoconvex constraints. With some additional conditions, the proof is also valid for \(f^\circ\)-quasiconvex functions, which sums up the properties of the method, treated in the paper. The main contribution in this paper is the generalization of the Extended Supporting Hyperplane method in [V.-P. Eronen et al., ibid. 69, No. 2, 443–459 (2017; Zbl 1373.90082)] to also solve problems with \(f^\circ\)-pseudoconvex objective function.

MSC:

90C11 Mixed integer programming
90C25 Convex programming

Citations:

Zbl 1373.90082

Software:

MINLP; AlphaECP; SHOT
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Androulakis, I; Maranas, C; Floudas, CA, \(α \)BB: A global optimization method for general constrained nonconvex problems, J. Glob. Optim., 7, 337-363, (1995) · Zbl 0846.90087 · doi:10.1007/BF01099647
[2] Bagirov, A., Mäkelä, M.M., Karmitsa, N.: Introduction to Nonsmooth Optimization: Theory Practice and Software. Springer International Publishing, Cham, Heidelberg (2014) · Zbl 1312.90053 · doi:10.1007/978-3-319-08114-4
[3] Bonami, P; Kilinc, M; Linderoth, J; Lee, J (ed.); Leyffer, S (ed.), Algorithms and software for convex mixed-integer nonlinear programs, 1-39, (2012), New York · Zbl 1242.90121
[4] Bussieck, M.R., Vigerske, S.: MINLP solver software. In: Wiley Encyclopedia of Operations Research and Management Science. Wiley (2011). https://doi.org/10.1002/9780470400531.eorms0527
[5] Cambini, A., Martein, L.: Generalized convexity and optimization—theory and applications. In: Lecture Notes in Economics and Mathematical Systems. Springer, Berlin (2009) · Zbl 1157.49001
[6] Castillo, I; Westerlund, J; Emet, S; Westerlund, T, Optimization of block layout design problems with unequal areas: a comparison of MILP and MINLP optimization methods, Comput. Chem. Eng., 30, 54-69, (2005) · doi:10.1016/j.compchemeng.2005.07.012
[7] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001
[8] Oliveira, W, Regularized optimization methods for convex MINLP problems, TOP, 24, 665-692, (2016) · Zbl 1358.90086 · doi:10.1007/s11750-016-0413-4
[9] Duran, MA; Grossmann, IE, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 307-339, (1986) · Zbl 0619.90052 · doi:10.1007/BF02592064
[10] Eronen, V-P; Mäkelä, MM; Westerlund, T, On the generalization of ECP and OA methods to nonsmooth MINLP problems, Optimization, 63, 1057-1073, (2014) · Zbl 1295.90022 · doi:10.1080/02331934.2012.712118
[11] Eronen, V-P; Mäkelä, MM; Westerlund, T, Extended cutting plane method for a class of nonsmooth nonconvex MINLP problems, Optimization, 64, 641-661, (2015) · Zbl 1311.90083
[12] Eronen, V-P; Kronqvist, J; Westerlund, T; Mäkelä, MM; Karmitsa, N, Method for solving generalized convex nonsmooth mixed-integer nonlinear programming problems, J. Glob. Optim., 69, 443-459, (2017) · Zbl 1373.90082 · doi:10.1007/s10898-017-0528-7
[13] Fletcher, R; Leyffer, S, Solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 327-349, (1994) · Zbl 0833.90088 · doi:10.1007/BF01581153
[14] Fletcher, R; Leyffer, S, Numerical experience with lower bounds for MIQP branch-and-bound, SIAM J. Optim., 8, 604-616, (1998) · Zbl 0912.90225 · doi:10.1137/S1052623494268455
[15] Geoffrion, AM, Generalized benders decomposition, J. Optim. Theory Appl., 10, 237-260, (1973) · Zbl 0229.90024 · doi:10.1007/BF00934810
[16] Grossmann, IE, Review of nonlinear mixed-integer and disjunctive programming techniques, Optim. Eng., 3, 227-252, (2002) · Zbl 1035.90050 · doi:10.1023/A:1021039126272
[17] Jain, V; Grossmann, I, Cyclic scheduling of continuous parallel-process units with decaying performance, AIChE J., 44, 1623-1636, (1999)
[18] Kelley, JE, The cutting plane method for solving convex programs, J. SIAM, 8, 703-712, (1960) · Zbl 0098.12104
[19] Kronqvist, J; Lundell, A; Westerlund, T, The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming, J. Glob. Optim., 64, 249-272, (2016) · Zbl 1339.90247 · doi:10.1007/s10898-015-0322-3
[20] Lee, J., Leyffer, S.: Mixed Integer Nonlinear Programming. Springer, New York (2012) · Zbl 1230.90005 · doi:10.1007/978-1-4614-1927-3
[21] Leyffer, S, Integrating SQP and branch-and-bound for mixed integer nonlinear programming, Comput. Optim. Appl., 18, 295-309, (2001) · Zbl 1009.90074 · doi:10.1023/A:1011241421041
[22] Lundell, A; Skjäl, A; Westerlund, T, A reformulation framework for global optimization, J. Glob. Optim., 57, 115-141, (2013) · Zbl 1277.90102 · doi:10.1007/s10898-012-9877-4
[23] Meyer, CA; Floudas, CA, Convex underestimation of twice continuously differential functions by piecewise quadratic perturbations: spline \(α \)BB underestimators, J. Glob. Optim., 32, 221-258, (2005) · Zbl 1080.90059 · doi:10.1007/s10898-004-2704-9
[24] Mäkelä, M.M., Neittaanmäki, P.: Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control. World Scientific Publishing Co., Singapore (1992) · Zbl 0757.49017 · doi:10.1142/1493
[25] Nestorov, Y., Nemirowskii, A.: Interior-point polynomial algorithms in convex programming. In: SIAM Studies in Applied Mathematics, vol. 13. Philadelphia (1994) · Zbl 1311.90083
[26] Pörn, R.: Mixed-Integer Non-Linear Programming: Convexification Techniques and Algorithm Development. Ph.D. Thesis, Åbo Akademi University (2000) · Zbl 1295.90022
[27] Quesada, I; Grossmann, IE, An LP/NLP based branch-and-bound algorithm for convex MINLP optimization problems, Comput. Chem. Eng., 16, 937-947, (1999) · doi:10.1016/0098-1354(92)80028-8
[28] Roberts, A.W., Varberg, D.E.: Convex Functions. Academic Press, New York, London (1973) · Zbl 0271.26009
[29] Rockafellar, R.T.: Convex Analysis. Princeton Landmarks in Mathematics and Physics. Princeton University Press, Princeton (1997)
[30] Ryoo, HS; Sahinidis, NV, A branch-and-reduce approach to global optimization, J. Glob. Optim., 8, 107-138, (1996) · Zbl 0856.90103 · doi:10.1007/BF00138689
[31] Veinott, AF, The supporting hyperplane method for unimodal programming, Oper. Res., 15, 147-152, (1967) · Zbl 0147.38604 · doi:10.1287/opre.15.1.147
[32] Westerlund, T; Skrifvars, H; Harjunkoski, I; Pörn, R, An extended cutting plane method for solving a class of non-convex MINLP problems, Comput. Chem. Eng., 22, 357-365, (1998) · Zbl 0955.90095 · doi:10.1016/S0098-1354(97)00000-8
[33] Westerlund, T; Pörn, R, Solving pseudo-convex mixed integer optimization problems by cutting plane techniques, Optim. Eng., 3, 253-280, (2002) · Zbl 1035.90051 · doi:10.1023/A:1021091110342
[34] 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
[35] Westerlund, T.: User’s guide for GAECP, version 5.537. An Interactive Solver for Generalized Convex MINLP-Problems Using Cutting Plane and Supporting Hyperplane Techniques. Åbo Akademi University. www.abo.fi/ twesterl/GAECPDocumentation.pdf (2017) · Zbl 0846.90087
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.