# zbMATH — the first resource for mathematics

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
##### Software:
AlphaECP; SHOT; MINLP
Full Text:
##### References:
  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  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  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  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  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  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)  Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001  Oliveira, W, Regularized optimization methods for convex MINLP problems, TOP, 24, 665-692, (2016) · Zbl 1358.90086  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  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  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  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  Fletcher, R; Leyffer, S, Solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 327-349, (1994) · Zbl 0833.90088  Fletcher, R; Leyffer, S, Numerical experience with lower bounds for MIQP branch-and-bound, SIAM J. Optim., 8, 604-616, (1998) · Zbl 0912.90225  Geoffrion, AM, Generalized benders decomposition, J. Optim. Theory Appl., 10, 237-260, (1973) · Zbl 0229.90024  Grossmann, IE, Review of nonlinear mixed-integer and disjunctive programming techniques, Optim. Eng., 3, 227-252, (2002) · Zbl 1035.90050  Jain, V; Grossmann, I, Cyclic scheduling of continuous parallel-process units with decaying performance, AIChE J., 44, 1623-1636, (1999)  Kelley, JE, The cutting plane method for solving convex programs, J. SIAM, 8, 703-712, (1960) · Zbl 0098.12104  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  Lee, J., Leyffer, S.: Mixed Integer Nonlinear Programming. Springer, New York (2012) · Zbl 1230.90005  Leyffer, S, Integrating SQP and branch-and-bound for mixed integer nonlinear programming, Comput. Optim. Appl., 18, 295-309, (2001) · Zbl 1009.90074  Lundell, A; Skjäl, A; Westerlund, T, A reformulation framework for global optimization, J. Glob. Optim., 57, 115-141, (2013) · Zbl 1277.90102  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  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  Nestorov, Y., Nemirowskii, A.: Interior-point polynomial algorithms in convex programming. In: SIAM Studies in Applied Mathematics, vol. 13. Philadelphia (1994) · Zbl 1311.90083  Pörn, R.: Mixed-Integer Non-Linear Programming: Convexification Techniques and Algorithm Development. Ph.D. Thesis, Åbo Akademi University (2000) · Zbl 1295.90022  Quesada, I; Grossmann, IE, An LP/NLP based branch-and-bound algorithm for convex MINLP optimization problems, Comput. Chem. Eng., 16, 937-947, (1999)  Roberts, A.W., Varberg, D.E.: Convex Functions. Academic Press, New York, London (1973) · Zbl 0271.26009  Rockafellar, R.T.: Convex Analysis. Princeton Landmarks in Mathematics and Physics. Princeton University Press, Princeton (1997)  Ryoo, HS; Sahinidis, NV, A branch-and-reduce approach to global optimization, J. Glob. Optim., 8, 107-138, (1996) · Zbl 0856.90103  Veinott, AF, The supporting hyperplane method for unimodal programming, Oper. Res., 15, 147-152, (1967) · Zbl 0147.38604  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  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  Westerlund, T; Pettersson, F, An extended cutting plane method for solving convex MINLP problems, Comput. Chem. Eng., 19, 131-136, (1995)  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. 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.