×

Solving mathematical programs with complementary constraints as nonlinear programs. (English) Zbl 1074.90044

Summary: We consider solving mathematical programs with complementarity constraints (MPCCs) as nonlinear programs (NLPs) using standard NLP solvers. This approach is appealing because it allows existing off-the-shelf NLP solvers to tackle large instances of MPCCs. Numerical experience on MacMPEC, a large collection of MPCC test problems is presented. Our experience indicates that sequential quadratic programming (SQP) methods are very well suited for solving MPCCs and at present outperform interior-point solvers both in terms of speed and reliability. All NLP solvers also compare very favorably to special MPCC solvers on tests published in the literature.

MSC:

90C30 Nonlinear programming
49M37 Numerical methods based on nonlinear programming
65K05 Numerical mathematical programming methods
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C55 Methods of successive quadratic programming type
90C51 Interior-point methods

Software:

SNOPT; AMPL; COPS; MacMPEC
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1137/S0036144595285963 · Zbl 0891.90158 · doi:10.1137/S0036144595285963
[2] Luo Z.-Q., Mathematical Programs with Equilibrium Constraints (1996)
[3] Outrata J., Nonsmooth Approach to Optimization Problems with Equilibrium Constraints (1998) · doi:10.1007/978-1-4757-2825-5
[4] Leyffer S. (2000) MacMPEC: AMPL collection of MPECs Webpagehttp://www.mcs.anl.gov/leyffer/MacMPEC/
[5] DOI: 10.1080/02331939508844048 · doi:10.1080/02331939508844048
[6] DOI: 10.1287/moor.25.1.1.15213 · Zbl 1073.90557 · doi:10.1287/moor.25.1.1.15213
[7] Fletcher R. Leyffer S. Ralph D. Scholtes S. (2002) Local convergence of SQP methods for mathematical programs with equilibrium constraints Numerical Analysis Report NA/209 Department of Mathematics, University of Dundee Dundee UK May 2002 · Zbl 1112.90098
[8] Anitescu M., On Solving Mathematical Programs with Complementarity Constraints as Nonlinear Programs (2000)
[9] Gill P.E. Murray W. Saunders M.A. (1997) SNOPT: An SQP algorithm for large-scale constrained optimization Report NA 97-2 Dept. of Mathematics, University of California San Diego November 1997
[10] DOI: 10.1007/BF01580720 · Zbl 0655.90060 · doi:10.1007/BF01580720
[11] DOI: 10.1007/BF02592099 · Zbl 0848.90109 · doi:10.1007/BF02592099
[12] Ferris M.C. Kanzow C. (1999) Complementarity and related problems: A survey Mathematical Programming Technical Report 98-17 University of Wisconsin August 1999
[13] Ferris M.C., Structural Engineering and Mechanics 6 pp 857– (1998)
[14] DOI: 10.1007/s101070050048 · Zbl 0959.65079 · doi:10.1007/s101070050048
[15] DOI: 10.1137/S1052623497332329 · Zbl 0955.90134 · doi:10.1137/S1052623497332329
[16] DOI: 10.1023/A:1018359900133 · Zbl 0904.90153 · doi:10.1023/A:1018359900133
[17] Leyffer S. (2002) The penalty interior point method fails to converge Numerical Analysis Report NA/208 Department of Mathematics, University of Dundee Dundee UK February 2002. Revised Sept. 2003 · Zbl 1134.90051
[18] Dirkse S.P., Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods (1999)
[19] Dirkse S.P. Ferris M.C. Meeraus A. (2002) Mathematical programs with equilibrium Constraints: Automatic reformulation and solution via constraint optimization Technical Report NA-02/11 Oxford University Computing Laboratory July 2002 · Zbl 1203.91142
[20] DOI: 10.1007/s101070100244 · Zbl 1049.90088 · doi:10.1007/s101070100244
[21] Fourer R., AMPL: A Modelling Language for Mathematical Programming (2003)
[22] Leyffer S. (2003) Complementarity constraints as nonlinear equations: Theory and numerical experience Technical report Argonne National Laboratory 2003
[23] DOI: 10.1137/S105262349833338X · Zbl 0997.90087 · doi:10.1137/S105262349833338X
[24] DOI: 10.1145/200979.201043 · Zbl 0886.65058 · doi:10.1145/200979.201043
[25] DOI: 10.1023/A:1008632215341 · Zbl 0883.90116 · doi:10.1023/A:1008632215341
[26] DOI: 10.1109/99.714603 · Zbl 05092192 · doi:10.1109/99.714603
[27] Fletcher R. Leyffer S. Toint Ph.L. (1998) On the global convergence of an SLP-filter algorithm Numerical Analysis Report NA/183 University of Dundee UK August 1998
[28] DOI: 10.1137/S1052623497325107 · Zbl 0957.65057 · doi:10.1137/S1052623497325107
[29] Vanderbei R.J., COAP 13 pp 231– (1999)
[30] Raghunathan A. Biegler L.T. (2002) Barrier methods for mathematical programs with complementarity constraints (MPCCs) Technical report Carnegie Mellon University, Department of Chemical Engineering Pittsburgh PA December 2002
[31] Benson H. Shanno D.F. Vanderbei R.V.D. (2002) Interior-point methods for nonconvex nonlinear programming: Complementarity constraints Technical Report ORFE 02-02 Princeton University, Operations Research and Financial Engineering · Zbl 1022.90017
[32] Dolan E.D., Benchmarking Optimization Software with Cops (2000)
[33] Dirkse S.P., Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods pp pp. 127–148– (1999)
[34] DOI: 10.1007/BF02592205 · Zbl 0870.90092 · doi:10.1007/BF02592205
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.