(522c) A Level-Based Quadratic Outer Approximation Algorithm for Convex MINLP

Jan Kronqvist*, David E. Bernal**, Ignacio E. Grossmann**

*Chemical Engineering, Åbo Akademi University, Turku Finland, jan.kronqvist@abo.fi

**Chemical Engineering, Carnegie Mellon University, Pittsburgh PA

Mixed-integer Nonlinear programming (MINLP) deals with optimization problems containing both continuous and integer variables as well as linear and nonlinear functions. The integer variables make it possible to incorporate logic relations and discrete quantities in the optimization problem. The ability to incorporate logic decisions and nonlinear functions make it possible to accurately model complex systems. Therefore, there is a large number of applications in engineering and other fields, e.g., see [1] and [2]. An MINLP problem is usually regarded as convex, if an integer relaxation results in a convex nonlinear programming (NLP) problem [3]. There are several techniques for solving convex MINLP problems available, for example, the extended cutting plane (ECP) algorithm [4], extended supporting hyperplane (ESH) algorithm [5], outer approximation (OA) [6], generalized Benders decomposition (GDB) [7], and branch and bound techniques [8]. However, solving convex MINLP instances may still be a difficult task, as shown in a recent benchmark on convex MINLP solvers in [8].

OA can be considered as a decomposition technique, where the optimal solution is obtained by solving a sequence of mixed-integer linear programming (MILP) and convex NLP subproblems. A linear approximation of the MINLP problem is constructed and improved in each iteration in order to predict a non-decreasing sequence of lower bounds (assuming minimization problem). In each iteration, the integer variables are chosen as the minimizer of the linear approximation, and values for the continuous variables are obtained by solving a convex NLP problem where the integer variables are fixed. This problem yields an upper bound. When applied to a difficult MINLP problems, the normal OA technique may require a substantial number of iterations to obtain the optimal solution and verify optimality; i.e. converging the corresponding lower and upper bounds within a small tolerance.

Here we present a different approach for obtaining trial solutions, within an OA framework. The main idea is to use a different technique for obtaining trial values to the integer variables, and using these integer solutions in an OA algorithm. By utilizing second order derivatives of the nonlinear functions, we should be able to construct a better approximation of the MINLP problem, and thus, obtain better trial solutions. Instead of choosing the integer variables as the minimizer of a linear approximation, we propose to use a second order approximation of the Lagrangean function combined with the outer approximation cuts to obtain trial values for the integer variables.

In order to guarantee convergence, we cannot simply replace the linear objective of the MILP subproblems with a quadratic approximation of the Lagragean. However, by using ideas from the level method [9] we are able to guarantee convergence by introducing linear constraints that impose a specific improvement of the linearized objective function. These linear constraints restrict the search space into a specific level set of the linearized objective. Trial values for the integer variables are therefore obtained by minimizing a quadratic approximation the Lagrangean function such that all linear constraints and obtained cuts are satisfied. Thus, the algorithm uses second order information for obtaining trial solutions for the integer variables. Therefore, the algorithm should be able to find the optimal integer combination in fewer iterations. However, each iteration also becomes more computationally demanding compared to normal OA since it also requires the solution of a mixed-integer quadratic programming problem.

The level-based quadratic outer approximation algorithm will be presented in detail, including its theoretical properties. Furthermore, we present numerical comparisons against other convex MINLP techniques.

[1] Biegler, L. T., Grossmann, I. E., 2004. Retrospective on optimization. Computers & Chemical Engineering 28 (8), 1169–1192.

[2] Floudas, C. A., 2000. Deterministic Global Optimization, vol. 37 of Nonconvex Optimization and its Applications.

[3] Lee, J., Leyffer, S. (Eds.), 2011. Mixed Integer Nonlinear Programming. Vol. 154. Springer Science & Business Media.

[4] Westerlund, T., Petterson, F., 1995. An extended cutting plane method for solving convex MINLP problems. Computers and Chemical Engineering 19, S131–S136.

[5] Kronqvist, J., Lundell, A., Westerlund, T., 2015. The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming. Journal of Global Optimization 64 (2), 249–272.

[6] Duran, M. A., Grossmann, I. E., 1986. An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Mathematical Programming 36 (3), 307–339.

[7] Geoffrion, A.M.: Generalized Benders decomposition. J. Optim. Theory Appl. 10(4), 237–260 (1972)

[8] Dakin, R.J.: A tree-search algorithm for mixed integer programming problems. Comput. J. 8(3), 250–255 (1965)

 [9] Lemarechal, C., Nemirovskii, A., Nesterov, Y.: New variants of bundle methods. Mathematical programming 69(1-3), 111-147 (1995)