NE/SQP: A robust algorithm for the nonlinear complementarity problem.

*(English)*Zbl 0808.90123From the authors’ summary: ‘We present a new iterative method for solving the nonlinear complementarity problem. This method, which we call NE/SQP (for Nonsmooth Equations/Successive Quadratic Programming), is a damped Gauss-Newton algorithm applied to solve a certain nonsmooth-equation formulation of the complementarity problem; it is intended to overcome a major deficiency of several previous methods of this type. Unlike these earlier algorithms whose convergence critically depends on a solvability assumptions on the subproblems, the NE/SQP method involves solving a sequence of nonnegatively constrained convex quadratic programs of the least-squares type; the latter programs are always solvable and their solution can be obtained by a host of efficient quadratic programming subroutines. Hence, the new method is a robust procedure which, not only is very easy to describe and simple to implement, but also has the potential advantage of being capable of solving problems of very large size. Besides the desirable feature of robustness and ease of implementation, the NE/SQP method retains two fundamental attractions of a typical member in the Gauss-Newton family of algorithms; namely, it is globally and locally quadratically convergent. Besides presenting the detailed description of the NE/SQP method and the associated convergence theory, we also report the numerical results of an extensive computational study which is aimed at demonstrating the practical efficiency of the method for solving a wide variety of realistic nonlinear complementarity problems’.

Reviewer: M.A.Noor (Riyadh)

##### MSC:

90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |

90C20 | Quadratic programming |

49J40 | Variational inequalities |

##### Software:

QPSOL
PDF
BibTeX
XML
Cite

\textit{J.-S. Pang} and \textit{S. A. Gabriel}, Math. Program. 60, No. 3 (A), 295--337 (1993; Zbl 0808.90123)

Full Text:
DOI

**OpenURL**

##### References:

[1] | H.Z. Aashtiani, ”The multi-modal traffic assignment problem,” Ph.D. thesis, Sloan School of Management, Massachusetts Institute of Technology (Cambridge, MA, 1979). |

[2] | H.Z. Aashtiani and T.L. Magnanti, ”Equilibria on a congested transportation network,”SIAM Journal on Algebraic and Discrete Methods 2 (1981) 213–226. · Zbl 0501.90033 |

[3] | B.H. Ahn,Comutation of Market Equilibria for Policy Analysis: The Project Independence Evaluation System (PIES)Approach (Garland, New York, 1979). |

[4] | D.P. Bertsekas and E.M. Gafni, ”Projection methods for variational inequalities with application to the traffic assignment problem,”Mathematical Programming Study 17 (1982) 139–159. · Zbl 0478.90071 |

[5] | J.V. Burke, ”Methods for solving generalized inequalities with applications to nonlinear programming,” Ph.D. thesis, Department of Mathematics, University of Illinois (Urbana-Champaign, IL, 1984). |

[6] | J.V. Burke and S.P. Han, ”A Gauss–Newton approach to solving generalized inequalities,”Mathematics of Operations Research 11 (1986) 632–643. · Zbl 0623.90072 |

[7] | J.V. Burke and S.P. Han, ”A robust sequential quadratic programming method,”Mathematical Programming 43 (1989) 277–303. · Zbl 0683.90070 |

[8] | S.C. Choi, W. DeSarbo and P.T. Harker, ”Product positioning under price competition,”Management Science 36 (1990) 175–199. · Zbl 0703.90054 |

[9] | F.H. Clarke,Optimization and Nonsmooth Analysis (Wiley-Interscience, New York, 1983). · Zbl 0582.49001 |

[10] | R.C. Cottle, J.S. Pang and R.E. Stone,The Linear Complementarity Problem (Academic Press, Boston, MA, 1992). · Zbl 0757.90078 |

[11] | G.B. Dantzig and A.S. Manne, ”A complementarity algorithm for an optimal capital path with invariant proportions,”Journal of Economic Theory 9 (1974) 312–323. |

[12] | B.C. Eaves, ”Thoughts on computing market equilibrium with SLCP,” in: D. Talman and G. van der Laan, eds.,The Computation and Modelling of Economic Equilibria (North-Holland, Amsterdam, 1987) pp. 1–18. |

[13] | M. Ferris and S. Lucidi, ”Globally convergent methods for nonlinear equations,” manuscript, Computer Sciences Department, University of Wisconsin (Madison, WI, 1991). · Zbl 0803.65070 |

[14] | R. Fletcher, ”Numerical experiments with an exactL 1 penalty function method,” in: O.L. Mangasarian, R.R. Meyer and S.M. Robinson, eds.,Nonlinear Programming 4 (Academic Press, New York, 1981) pp. 99–129. |

[15] | M. Frank and P. Wolfe, ”An algorithm for quadratic programming,”Naval Research Logistics Quarterly 3 (1956) 95–110. |

[16] | T.L. Friesz, R.L. Tobin, T.E. Smith and P.T. Harker, ”A nonlinear complementarity formulation and solution procedure for the general derived demand network equilibrium problem,”Journal of Regional Sciences 23 (1983) 337–359. |

[17] | M. Fukushima, ”Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,”Mathematical Programming 53 (1992) 99–110. · Zbl 0756.90081 |

[18] | S.A. Gabriel, ”Algorithms for the nonlinear complementarity problem: NE/SQP and extensions,” Ph.D. thesis, Department of Mathematical Sciences, The Johns Hopkins University (Baltimore, MD, 1992). |

[19] | S.A. Gabriel and J.S. Pang, ”An inexact NE/SQP method for solving the nonlinear complementarity problem,” manuscript, Department of Mathematical Sciences, The Johns Hopkins University (Baltimore, MD, 1992). · Zbl 0794.90071 |

[20] | P.E. Gill, W. Murray, M.S. Saunders and M.H. Wright, ”User’s guide for QPSOL (Version 3.2): A FORTRAN package for quadratic programming, ”Technical Report SOL 84-6, Systems Optimization Laboratory, Department of Operations Research, Stanford University (Stanford, CA, 1984). |

[21] | M. El Hallabi and R.A. Tapia, ”A global convergence theory for arbitrary norm trust-region methods for nonlinear equations,” Technical Report TR87-25, Department of Mathematical Sciences, Rice University (Houston, TX, 1989). |

[22] | S.P. Han, J.S. Pang and N. Rangaraj, ”Globally convergent Newton methods for nonsmooth equations,” to appear in:Mathematics of Operations Research (1992). · Zbl 0777.90057 |

[23] | T. Hansen and T.C. Koopmans, ”On the definition and computation of a capital stock invariant under optimization,”Journal of Economic Theory 5 (1972) 487–523. · Zbl 0266.90018 |

[24] | P.T. Harker, ”Dispersed spatial price equilibrium,”Environment and Planning A 20 (1988) 353–368. |

[25] | P.T. Harker, ”Accelerating the convergence of the diagonalization and projection algorithms for finite-dimensional variational inequalities,”Mathematical Programming 41 (1988) 25–59. · Zbl 0825.49019 |

[26] | P.T. Harker and J.S. Pang, ”Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications,”Mathematical Programming 48 (1990) 161–220. · Zbl 0734.90098 |

[27] | P.T. Harker and B. Xiao, ”Newton’s method for the nonlinear complementarity problem: a B-differentiable equation approach,”Mathematical Programming 48 (1990) 339–357. · Zbl 0724.90071 |

[28] | R.H.W. Hoppe and H.D. Mittelmann, ”A multi-grid continuation method for parameter-dependent variational inequalities,”Journal of Computational and Applied Mathematics 26 (1989) 35–46. · Zbl 0671.65047 |

[29] | W.W. Hogan, ”Energy policy models for project independence,”Computers and Operations Research 2 (1975) 251–271. |

[30] | C.M. Ip and J. Kyparisis, ”Local convergence of quasi-Newton methods for B-differentiable equations,”Mathematical Programming 56 (1992) 71–89. · Zbl 0761.90088 |

[31] | P.C. Jones, ”Computing an optimal invariant capital stock,”SIAM Journal on Algebraic and Discrete Methods 3 (1982) 145–150. · Zbl 0492.90078 |

[32] | N.H. Josephy, ”A Newton method for the PIES energy model,” MRC Technical Summary Report #1971, Mathematics Research Center, University of Wisconsin (Madison, WI, 1979). |

[33] | M. Kojima, ”Computational methods for solving the nonlinear complementarity problem”Keio Engineering Reports 27 (1974) 1–41. · Zbl 0406.90071 |

[34] | M. Kojima and S. Shindo, ”Extensions of Newton and quasi-Newton methods to systems of PC1 equations,”Journal of Operations Research Society of Japan 29 (1986) 352–374. · Zbl 0611.65032 |

[35] | M.M. Kostreva, ”Elasto-hydrodynamic lubrication: a nonlinear complementarity problem,”International Journal for Numerical Methods in Fluids 4 (1984) 377–397. · Zbl 0551.76007 |

[36] | Y.Y. Lin and J.S. Pang, ”Iterative methods for large convex quadratic programs: a survey,”SIAM Journal on Control and Optimization 25 (1987) 383–411. · Zbl 0624.90083 |

[37] | L. Mathiesen, ”Computational experience in solving equilibrium models by a sequence of linear complementarity problems,”Operations Research 33 (1985) 1225–1250. · Zbl 0583.90097 |

[38] | L. Mathiesen, ”An algorithm based on a sequence of linear complementarity problems applied to a Walrasian equilibrium model: an example,”Mathematical Programming 37 (1987) 1–18. · Zbl 0613.90098 |

[39] | E. Miersemann and H.D. Mittelmann, ”Continuation for parameterized variational inequalities,”Journal of Computational and Applied Mathematics 26 (1989) 23–34. · Zbl 0672.65040 |

[40] | F.H. Murphy, H.D. Sherali and A.L. Soyster, ”A mathematical programming approach for determining oligopolistic market equilibrium,”Mathematical Programming 24 (1982) 92–106. · Zbl 0486.90015 |

[41] | K.P. Oh, ”The numerical solution of dynamically loaded elastohydrodynamic contact as a nonlinear complementarity problem,”Transactions of the ASME 106 (1984) 88–95. |

[42] | K.P. Oh, ”The formulation of the mixed lubrication problem as a generalized nonlinear complementarity problem,”Transactions of the ASME 108 (1986) 598–604. |

[43] | J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Euqations in Several Variables (Academic Press, New York, 1970). · Zbl 0241.65046 |

[44] | J.S. Pang, ”Newton’s method for B-differentiable equations,”Mathematics of Operations Research 15 (1990) 311–341. · Zbl 0716.90090 |

[45] | J.S. Pang, ”A B-differentiable equation based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems,”Mathematical Programming 51 (1991) 101–131. · Zbl 0733.90063 |

[46] | J.S. Pang, ”Convergence of splitting and Newton methods for complementarity problems: An application of some sensitivity results,”Mathematical Programming 58 (1993) 149–160. · Zbl 0784.90089 |

[47] | J.S. Pang, S.P. Han and N. Rangaraj, ”Minimization of locally Lipschitzian functions,”SIAM Journal on Optimization 1 (1991) 57–82. · Zbl 0752.90070 |

[48] | J.S. Pang and L. Qi, ”Nonsmooth equations: motivation and algorithms,” to appear in:SIAM Journal on Optimization. · Zbl 0784.90082 |

[49] | J.S. Pang and Z.P. Wang, ”Embedding methods for variational inequality and nonlinear complementarity problems,” manuscript, Department of Mathematical Sciences, The Johns Hopkins University (Baltimore, MD, 1990). |

[50] | J.S. Pang and C.S. Yu, ”Linearized simplicial decomposition methods for computing traffic equilibria on networks,”Networks 14 (1984) 427–438. · Zbl 0545.90037 |

[51] | K. Park, ”Newton’s method for nonsmooth equations and constrained optimization,” manuscript, Department of Industrial Engineering, University of Wisconsin (Madison, WI, 1989). |

[52] | M.J.D. Powell, ”A hybrid method for nonlinear equations,” in: P. Rabinowitz, ed.,Numerical Methods for Nonlinear Algebraic Equations (Gordon and Breach, London, 1970) pp. 90–93. · Zbl 0277.65028 |

[53] | P.V. Preckel, ”Alternative algorithms for computing economic equilibria,”Mathematical Programming Study 23 (1985) 163–172. · Zbl 0574.90092 |

[54] | L. Qi, ”Convergence analysis of some algorithms for solving nonsmooth equations,” manuscript, School of Mathematics, The University of New South Wales (Kensington, NSW, 1991). |

[55] | L. Qi and J. Sun, ”A nonsmooth version of Newton’s method and an interior point algorithm for convex programming,” manuscript, School of Mathematics, The University of New South Wales (Kensington, NSW, 1991). |

[56] | D. Ralph, ”Global convergence of damped Newton’s method for nonsmooth equations, via the path search,” manuscript, Computer Sciences Department, Cornell University (Ithaca, New York, 1991). |

[57] | A. Reinoza, ”Solving generalized equations via homotopies,”Mathematical Programming 31 (1985) 307–320. · Zbl 0613.65068 |

[58] | S.M. Robinson, ”Strongly regular generalized equations,”Mathematics of Operations Research 5 (1980) 43–62. · Zbl 0437.90094 |

[59] | S.M. Robinson, ”Newton’s method for a class of nonsmooth functions,” manuscript, Department of Industrial Engineering, University of Wisconson (Madison, WI, 1988). |

[60] | S.M. Robinson, ”Mathematical foundation of embedding methods for nonsmooth equations,”Mathematical Programing 48 (1990) 221–230. · Zbl 0728.90084 |

[61] | T.F. Rutherford, ”A modelling system for applied general equilibrium analysis,” Discussion Paper No. 836, Cowles Foundation for Research in Economics, Yale University (New Haven, CT, 1987). |

[62] | T.F. Rutherford, ”Implementational issues and computational performance solving applied general equilibrium models with SLCP,” Discussion Paper No. 837, Cowles Foundation for Research in Economics, Yale University (New Haven, CT, 1987). |

[63] | P.A. Samuelson, ”Spatial price equilibrium and linear programming,”American Economic Review 42 (1952) 283–303. |

[64] | H. Scarf,The Computation of Economic Equilibria (Yale University Press, New Haven, CT, 1973). · Zbl 0311.90009 |

[65] | M.J. Smith, ”The existence, uniqueness and stability of traffic equilibria,”Transportation Research 13B (1979) 295–304. |

[66] | J.C. Stone, ”Sequential optimization and complementarity techniques for computing economic equilibria,”Mathematical Programming Study 23 (1985) 173–191. · Zbl 0574.90093 |

[67] | J.C. Stone, ”Formulation and solution of economic equilibrium problems,” Technical Report SOL 88-7, Systems Optimization Laboratory, Department of Operations Research, Stanford University (Stanford, CA, 1987). |

[68] | K. Taji, M. Fukushima, and T. Ibaraki, ”A globally convergent Newton method for solving monotone variational inequalities,” Technical Report #91006, Department of Applied Mathematics and Physics, Kyoto University (Kyoto, Japan, 1991). · Zbl 0792.49007 |

[69] | R.L. Tobin, ”Variable dimension spatial price equilibrium algorithm,”Mathematical Programming 40 (1988) 33–51. · Zbl 0645.90095 |

[70] | R.L. Tobin, ”A method for the analysis of equilibrium multipart prices in oligopolistic markets,” manuscript, GTE Laboratories Incorporated (Waltham, MA, 1990). · Zbl 0795.90007 |

[71] | B. Xiao, ”Global Newton methods for nonlinear programs and variational inequalities: a B-differentiable equation approach,” Ph.D. thesis, Department of Decision Sciences, The Wharton School, University of Pennsylvania (Philadelphia, PA, 1990). |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.