A Comparative Study of SQP-Type Algorithms for Nonlinear and
Nonconvex Mixed-Integer Optimization
O. Exler,
T. Lehmann,
K. Schittkowski, submitted for publication
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
neighbored 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.pdf
(Acrobat Reader)