A Comparative Study of SQP-Type Algorithms for Nonlinear and
Nonconvex Mixed-Integer Optimization
O. Exler,
T. Lehmann,
K. Schittkowski, Mathematical Programming Computation, Vol. 4, 383-412 (2012)
Abstract:
We present numerical results of a comparative study of codes for nonlinear and
nonconvex mixed-integer optimization. The underlying algorithms are based on
sequential quadratic programming (SQP) with stabilization by trust-regions,
linear outer approximations, and branch-and-bound techniques. The mixed-integer
quadratic programming subproblems are solved by a branch-and-cut algorithm.
Second order information is updated by a quasi-Newton update formula (BFGS)
applied to the Lagrange function for continuous, but also for integer variables.
We do not require that the model functions can be evaluated at fractional values
of the integer variables. Thus, partial derivatives with respect to integer
variables are replaced by descent directions obtained from function values at
neighboring grid points, and the number of simulations or function evaluations,
respectively, is our main performance criterion to measure the efficiency of a
code. Numerical results are presented for a set of 100 academic mixed-integer
test problems. Since not all of our test examples are convex, we reach the
best-known solutions in about 90 % of the test runs, but at least feasible
solutions in the other cases. The average number of function evaluations of the
new mixed-integer SQP code is between 240 and 500
including those needed for one- or two-sided approximations of partial
derivatives or descent directions, respectively. In addition, we present
numerical results for a set of 55 test problems with some practical background
in petroleum engineering.
To download the report, click here:
minlp_comp_study.pdf
(Acrobat Reader)