×

zbMATH — the first resource for mathematics

A class of smoothing functions for nonlinear and mixed complementarity problems. (English) Zbl 0859.90112
Summary: We propose a class of parametric smooth functions that approximate the fundamental plus function, \((x)_+=\max\{0,x\}\), by twice integrating a probability density function. This leads to class of smooth parametric nonlinear equation approximations of nonlinear and mixed complementarity problems (NCPs and MCPs). For any solvable NCP or MCP, existence of an arbitrarily accurate solution to the smooth nonlinear equation as well as the NCP or MCP, is established for sufficiently large value of a smoothing parameter \(\alpha\). Newton-based algorithms are proposed for the smooth problem. For strongly monotone NCPs, global convergence and local quadratic convergence are established. For solvable monotone NCPs, each accumulation point of the proposed algorithms solves the smooth problem. Exact solutions of our smooth nonlinear equation for various values of the parameter \(\alpha\), generate an interior path, which is different from the central path for interior point methods. Computational results for 52 test problems compare favorably with those for another Newton-based method. The smooth technique is capable of solving efficiently the test problems solved by Dirkse and Ferris, Harker and Xiao and Pang and Gabriel.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] D.P. Bertsekas, ”Projected Newton methods for optimization problems with simple constraints”, SIAM Journal on Control and Optimization, vol. 20, pp. 221–246, 1982. · Zbl 0507.49018 · doi:10.1137/0320018
[2] B. Chen and P.T. Harker, ”A non-interior-point continuation method for linear complementarity problems”, SIAM Journal on Matrix Analysis and Applications, vol. 14, pp. 1168–1190, 1993. · Zbl 0788.65073 · doi:10.1137/0614081
[3] C. Chen and O.L. Mangasarian, ”Smoothing methods for convex inequalities and linear complementarity problems”, Technical Report 1191, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, 53706, November 1993. (To appear in Mathematical Programming, vol. 71, 1995.) · Zbl 0855.90124
[4] R.W. Cottle, F. Giannessi, and J.-L. Lions, Variational Inequalities and Complementarity Problems, John Wiley & Sons: New York, 1980.
[5] J.E. Dennis and R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall: Englewood Cliffs, N.J., 1983. · Zbl 0579.65058
[6] S.P. Dirkse and M.C. Ferris, ”The path solver: A non-monotone stabilization scheme for mixed complementarity problems”, Optimization Methods and Software, vol. 5, pp. 123–156, 1995. · doi:10.1080/10556789508805606
[7] S.P. Dirkse and M.C. Ferris, ”MCPLIB: A collection of nonlinear mixed complementarity problems”, Optimization Methods and Software, vol. 5, pp. 319–345, 1995. · doi:10.1080/10556789508805619
[8] S.P. Dirkse, M.C. Ferris, P.V. Preckel, and T. Rutherford, ”The GAMS callable program library for variational and complementarity solvers”, Manuscript, University of Wisconsin, 1993.
[9] M.S. Gowda, ”On the extended linear complementarity problem”, Technical Report, Department of Mathematics & Statistics, University of Maryland Baltimore Country, Baltimore, Maryland, 1994, Mathematical Programming, to appear. · Zbl 0831.90112
[10] P.T. Harker and J.-S. Pang, ”Finite-dimensional variational inequality and nonlinear complementarty problems: A survey of theory, algorithms and applications”, Mathematical Programming, vol. 48, pp. 161–220, 1990. · Zbl 0734.90098 · doi:10.1007/BF01582255
[11] P.T. Harker and B. Xiao, ”Newton’s method for the nonlinear complementarity problem: A B-differentiable equation approach”, Mathematical Programming, vol. 48, pp. 339–357, 1990. · Zbl 0724.90071 · doi:10.1007/BF01582262
[12] J. Hertz, A. Krogh, and R.G. Palmer, Introduction to the Theory of Neural Computation, Addison-Wesley: Redwood City, California, 1991.
[13] J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms I, Springer-Verlag: Berlin, 1993.
[14] N.H. Josephy, ”Newton’s method for generalized equations”, Technical Summary Report 1965, Mathematics Research Center, University of Wisconsin, Madison, Wisconsin, 1979.
[15] C. Kanzow, ”Some tools allowing interior-point methods to become noninterior”, Technical Report, Institute of Applied Mathematics, University of Hamburg, Germany, 1994.
[16] M. Kojima and N. Megiddo, ”The relation between the path of centers and smale’s regularization of the linear programming problem”, Linear Algebra and Its Applications, vol. 152, pp. 135–139, 1991. · Zbl 0727.65053 · doi:10.1016/0024-3795(91)90271-W
[17] M. Kojima, S. Mizuno, and A. Yoshise, ”A polynomial-time algorithms for a class of linear complementarity problems”, Mathematical Programming, vol. 44, pp. 1–27, 1989. · Zbl 0676.90087 · doi:10.1007/BF01587074
[18] J. Kreimer and R.Y. Rubinstein, ”Nondifferentiable optimization via smooth approximation: General analytical approach”, Annals of Operations Research, vol. 39, pp. 97–119, 1992. · Zbl 0769.49014 · doi:10.1007/BF02060937
[19] K. Madsen and H.B. Nielsen, ”A finite smoothing algorithm for linear l 1 estimation”, SIAM on Optimization, vol. 3, no. 2, pp. 223–235, May 1993. · Zbl 0781.65115 · doi:10.1137/0803010
[20] O.L. Mangasarian, ”Mathematical programming in neural networks”, ORSA Journal on Computing, vol. 5, no. 4, pp. 349–360, 1993. · Zbl 0789.90053 · doi:10.1287/ijoc.5.4.349
[21] O.L. Mangasarian and J.-S. Pang, ”The extended linear complementarity problems”, SIAM Journal on Matrix Analysis and Applications, vol. 16, pp. 359–368, 1995. · Zbl 0835.90103 · doi:10.1137/S0895479893262734
[22] Jorge J. Moré, ”Global methods for nonlinear complementarity problems”, Technical Report Preprint MCS-P429–0494, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, Illinois, 1994. · Zbl 0868.90127
[23] B.A. Murtagh and M.A. Saunders, ”MINOS 5.0 user’s guide”, Technical Report SOL 83.20, Stanford University, December 1983.
[24] K.G. Murty, Linear Complementarity, Linear and Nonlinear Programming, Helderman-Verlag: Berlin, 1988. · Zbl 0634.90037
[25] J.M. Ortega, Numerical Analysis, A Second Course, Academic Press, 1972. · Zbl 0248.65001
[26] J.-S. Pang, ”Newton’s method for B-differentiable equations”, Mathematics of Operations Research, vol. 15, pp. 331–341, 1990. · Zbl 0716.90090 · doi:10.1287/moor.15.2.311
[27] J.-S. Pang, ”A B-differentiable equation based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems”, Mathematical Programming, vol. 51, pp. 101–131, 1991. · Zbl 0733.90063 · doi:10.1007/BF01586928
[28] J.-S. Pang and S.A. Gabriel, ”NE/SQP: A robust algorthm for the nonlinear complementarity problem”, Mathematical Programming, vol. 60, pp. 295–337, 1993. · Zbl 0808.90123 · doi:10.1007/BF01580617
[29] M.C. Pinar and S.A. Zenios ”On smoothing exact penalty functions for convex constrained optimization”, SIAM Journal on Optimization, vol. 4, pp. 486–511, 1994. · Zbl 0819.90072 · doi:10.1137/0804027
[30] D. Ralph, ”Global convergence of damped Newton’s method for nonsmooth equations via the path search”, Mathematics of Operations Research, vol. 19, pp. 352–389, 1994. · Zbl 0819.90102 · doi:10.1287/moor.19.2.352
[31] J. Ren, ”Computable error bounds in mathematical programming”, Technical Report 1173, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin 53706, August 1993.
[32] S.M. Robinson, ”Generalized equations and their solution: Part I: Basic theory”, Mathematical Programming Study, vol. 10, pp. 128–140, 1979. · Zbl 0404.90093 · doi:10.1007/BFb0120850
[33] S.M. Robinson, ”Strongly regular generalized equations”, Mathematics of Operations Research, vol. 5, pp. 43–62, 1980. · Zbl 0437.90094 · doi:10.1287/moor.5.1.43
[34] S.M. Robinson, ”Newton’s method for a class of nonsmooth functions”, Working Paper, Department of Industrial Engineering, University of Wisconsin, Madison, Wisconsin, 1988.
[35] T.F. Rutherford, ”MILES: A mixed inequality and nonlinear equation solver”, Working Paper, Department of Economics, University of Colorado, Boulder, 1993.
[36] S. Smale, ”Algorithms for solving equations”, In Proceedings of the International Congress of Mathematicians, pp. 172–195, Ameri. Math. Soc., Providence, 1987. · Zbl 0665.65058
[37] B. Xiao, ”Global Newtons methods for nonlinear programs and variational inequalities”, Technical Report, Ph.D. Thesis, Department of Decision Sciences, The Wharton School, University of Pennsylvania, Philadelphia, PA, 1990.
[38] Y. Ye, ”A fully polynomial-time approximation algorithm for computing a stationary point of the general linear complementarity problem”, Mathematics of Operations Research, vol. 18, pp. 334–345, 1993. · Zbl 0791.90060 · doi:10.1287/moor.18.2.334
[39] I. Zang, ”A smoothing-out technique for min-max optimization”, Mathematical Programming, vol. 19, pp. 61–77, 1980. · Zbl 0468.90064 · doi:10.1007/BF01581628
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.