×

A trust region SQP algorithm for mixed-integer nonlinear programming. (English) Zbl 1152.90551

Summary: We propose a modified sequential quadratic programming method for solving mixed-integer nonlinear programming problems. Under the assumption that integer variables have a smooth influence on the model functions, i.e., that function values do not change drastically when in- or decrementing an integer value, successive quadratic approximations are applied. The algorithm is stabilized by a trust region method with Yuan’s second order corrections. It is not assumed that the mixed-integer program is relaxable or, in other words, function values are evaluated only at integer points. The Hessian of the Lagrangian function is approximated by a quasi-Newton update formula subject to the continuous and integer variables. Numerical results are presented for a set of 80 mixed-integer test problems taken from the literature. The surprising result is that the number of function evaluations, the most important performance criterion in practice, is less than the number of function calls needed for solving the corresponding relaxed problem without integer variables.

MSC:

90C20 Quadratic programming
90C11 Mixed integer programming
90C30 Nonlinear programming

Software:

QL; MISQP; AlphaECP; NLPQLP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Audet, C.; Dennis, J. E., Pattern search algorithm for mixed variable programming, SIAM J. Optim., 11, 573-594 (2001) · Zbl 1035.90048 · doi:10.1137/S1052623499352024
[2] Borchers, B.; Mitchell, J. E., An improved branch and bound algorithm for mixed integer nonlnear programming, Comput. Oper. Res., 21, 4, 359-367 (1994) · Zbl 0797.90069 · doi:10.1016/0305-0548(94)90024-8
[3] Bünner, M. J.; Schittkowski, K.; van de Braak, G., Optimal design of electronic components by mixed-integer nonlinear programming, Optim. Eng., 5, 271-294 (2004) · Zbl 1151.90503 · doi:10.1023/B:OPTE.0000038887.72677.3e
[4] Burke, J. V., A robust trust region method for constrained nonlinear programming problems, SIAM J. Optim., 2, 325-347 (1992) · Zbl 0770.90062 · doi:10.1137/0802016
[5] Byrd, R.; Schnabel, R. B.; Schultz, G. A., A trust region algorithm for nonlinearly constrained optimization, SIAM J. Numer. Anal., 24, 1152-1170 (1987) · Zbl 0631.65068 · doi:10.1137/0724076
[6] Celis, M.R.: A trust region strategy for nonlinear equality constrained optimization. Ph.D. Thesis, Department of Mathematics. Rice University (1983)
[7] Conn, A. R.; Gould, I. M.; Toint, P. L., Trust-Region Methods (2000), Philadelphia: SIAM, Philadelphia · Zbl 0958.65071
[8] Duran, M.; Grossmann, I. E., An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Mathe. Program., 36, 307-339 (1986) · Zbl 0619.90052 · doi:10.1007/BF02592064
[9] Exler, O., Schittkowksi, K.: MISQP: a Fortran implementation of a trust region SQP algorithm for mixed-integer nonlinear programming—user’s guide, version 2.1, Report, Department of Computer Science, University of Bayreuth (2006). http://www.uni-bayreuth.de/departments/math/ kschittkowski/MISQP.pdf
[10] Fletcher, R., Practical Methods of Optimization, vol. 2, Constrained Optimization (1981), Chichester: Wiley, Chichester · Zbl 0474.65043
[11] Fletcher, R.; Watson, G. A., Second order correction for nondifferentiable optimization, Numerical Analysis., 85-114 (1982), Berlin Heidelberg New York: Springer, Berlin Heidelberg New York · Zbl 0476.65048 · doi:10.1007/BFb0093151
[12] 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
[13] Floudas, C. A., Nonlinear and Mixed-Integer Optimization (1995), New York, Oxford: Oxford University Press, New York, Oxford · Zbl 0886.90106
[14] Floudas, C.A., Pardalos, P.M., Adjiman, C.S., Esposito, W.R., Gumus, Z.H., Harding S.T., Klepeis, J.L., Meyer, C.A., Schweiger, C.A.: Handbook of Test Problems in Local and Global Optimization. Kluwer (1999) · Zbl 0943.90001
[15] Gill, P. E.; Murray, W.; Wright, M., Practical Optimization (1981), New York: Academic, New York · Zbl 0503.90062
[16] Grossmann, I. E.; Kravanja, Z.; Conn, A. R.; Biegler, L. T.; Coleman, T. F.; Santosa, F. N., Mixed-integer nonlinear programming: A survey of algorithms and applications, Large-Scale Optimization with Applications, Part II: Optimal Design and Control. (1997), Berlin Heidelberg New York: Springer, Berlin Heidelberg New York · Zbl 0884.65058
[17] Gupta, O. K.; Ravindran, V., Branch and bound experiments in convex nonlinear integer programming, Manag. Sci., 31, 1533-1546 (1985) · Zbl 0591.90065 · doi:10.1287/mnsc.31.12.1533
[18] 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
[19] Li, H.-L.; Chou, C.-T., A global approach for nonlinear mixed discrete programming in design optimization, Eng. Optim., 22, 109-122 (1994)
[20] Moré, J. J.; Bachem, A.; Grötschel, M.; Korte, B., Recent developments in algorithms and software for trust region methods, Mathematical Programming: The State of the Art., 258-287 (1983), Berlin Hedelberg New York: Springer, Berlin Hedelberg New York · Zbl 0546.90077
[21] Powell, M. J.D., On the global convergence of trust region algorithms for unconstrained minimization, Math. Program., 29, 297-303 (1984) · Zbl 0569.90069 · doi:10.1007/BF02591998
[22] Powell, M. J.D.; Yuan, Y., A trust region algorithm for equality constrained optimization, Math. Program., 49, 189-211 (1991) · Zbl 0816.90121 · doi:10.1007/BF01588787
[23] Schittkowski, K.: QL: A Fortran code for convex quadratic programming—user’s guide, version 2.11. Report, Department of Mathematics, University of Bayreuth (2003) http://www.uni-bayreuth.de/departments/math/ kschittkowski/QL.pdf
[24] Spickenreuther, T.: Entwicklung eines allgemeinen Branch & Bound Ansatzes zur gemischt-ganzzahligen Optimierung. Diploma Thesis, Department of Mathematics, University of Bayreuth (2005)
[25] Stoer, J.: Foundations of recursive quadratic programming methods for solving nonlinear programs. In: Schittkowski, K. (ed.) Computational Mathematical Programming, vol. 15. NATO ASI Series, Series F: Computer and Systems Sciences. Springer, Berlin Heidelberg New York (1985) · Zbl 0581.90067
[26] Toint, P. L., A nonmonotone trust-region algorithm for nonlinear optimization subject to convex constraints, Math. Program., 77, 69-94 (1997) · Zbl 0891.90153
[27] Westerlund, P., 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
[28] Yuan, Y.-X., An example of only linearly convergence of trust region algorithms for nonsmooth optimization, IMA J. Numer. Anal., 4, 327-335 (1984) · Zbl 0555.65037 · doi:10.1093/imanum/4.3.327
[29] Yuan, Y.-X., On the superlinear convergence of a trust region algorithm for nonsmooth optimization, Math. Program., 31, 269-285 (1985) · Zbl 0577.90066 · doi:10.1007/BF02591949
[30] Yuan, Y.-X., On the convergence of a new trust region algorithm, Numer. Math., 70, 515-539 (1995) · Zbl 0828.65062 · doi:10.1007/s002110050133
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.