×

zbMATH — the first resource for mathematics

Smoothing methods for convex inequalities and linear complementarity problems. (English) Zbl 0855.90124
Summary: A smooth approximation \(p(x, \alpha)\) to the plus function \(\max\{x,0\}\) is obtained by integrating the sigmoid function \(1/(1+ e^{- \alpha x})\), commonly used in neural networks. By means of this approximation, linear and convex inequalities are converted into smooth, convex unconstrained minimization problems, the solution of which approximates the solution of the original problem to a high degree of accuracy for \(\alpha\) sufficiently large. In the special case when a Slater constraint qualification is satisfied, an exact solution can be obtained for finite \(\alpha\). Speedup over MINOS 5.4 was as high as 1142 times for linear inequalities of size \(2000\times 1000\), and 580 times for convex inequalities with 400 variables. Linear complementarity problems are converted into a system of smooth nonlinear equations and are solved by a quadratically convergent Newton method. For monotone LCPs with as many as 10 000 variables, the proposed approach was as much as 63 times faster than Lemke’s method.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
Software:
MINOS; MCPLIB; PATH Solver; tn
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R.W. Cottle, J.-S. Pang and R.E. Stone,The Linear Complementarity Problem (Academic Press, New York, 1992). · Zbl 0757.90078
[2] R. De Leone and M.A. Tork Roth, ”Massively parallel solution of quadratic programs via successive overrelaxation,”Concurrency: Practice and Experience 5 (1993) 623–634.
[3] J.E. Dennis and R.B. Schnabel,Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Prentice-Hall, Englewood Cliffs, NJ, 1983). · Zbl 0579.65058
[4] S.P. Dirkse and M.C. Ferris, ”The path solver: A non-monotone stabilization scheme for mixed complementarity problems,” Technical Report 1179, Computer Sciences Department, University of Wisconsin, Madison, WI, 1993.
[5] A.J. Hoffman, ”On approximate solutions of systems of linear inequalities,”Journal of Research of the National Bureau of Standards 49 (1952) 263–265.
[6] M. Kojima, S. Mizuno and A. Yoshise, ”A polynomial-time algorithm for a class of linear complementarity problems,”Mathematical Programming 44 (1) (1989) 1–26. · Zbl 0676.90087
[7] K. Madsen and H.B. Nielsen, ”A finite smoothing algorithm for linearl 1 estimation,”SIAM Journal on Optimization 3 (2) (1993) 223–235. · Zbl 0781.65115
[8] O.L. Mangasarian, ”A condition number for linear inequalities and linear programs,” in: G. Bamberg and O. Opitz, eds.,Proceedings of 6. Symposium über Operations Research, Augsburg, 1981 (Atheneum/Hain/Scriptor/Hanstein, Königstein, 1981) pp. 3–15. · Zbl 0505.90042
[9] O.L. Mangasarian, ”A condition number for differentiable convex inequalities,”Mathematics of Operations Research 10 (2) (1985) 175–179. · Zbl 0565.90059
[10] O.L. Mangasarian, ”Mathematical programming in neural networks,”ORSA Journal on Computing 5 (4) (1993) 349–360. · Zbl 0789.90053
[11] O.L. Mangasarian, ”Error bounds for inconsistent linear inequalities and programs,”Operations Research Letters 15 (1994) 187–192. · Zbl 0814.90082
[12] O.L. Mangasarian and J. Ren, ”New improved error bounds for the linear complementarity problem,”Mathematical Programming 66 (2) (1994) 241–255. · Zbl 0829.90124
[13] T.S. Motzkin and I.J. Schoenberg, ”The relaxation method for linear inequalities,”Canadian Journal of Mathematics 6 (1954) 393–404. · Zbl 0055.35002
[14] B.A. Murtagh and M.A. Saunders, ”MINOS 5.0 user’s guide,” Technical Report SOL 83.20, Stanford University, Stanford, CA, 1983.
[15] S.G. Nash, ”Newton-type minimization via the Lanczos method,”SIAM Journal of Numerical Analysis 21 (1984) 770–778. · Zbl 0558.65041
[16] J. Nocedal, ”Theory of algorithms for unconstrained optimization,”Acta Numerica (1992) 199–242. · Zbl 0766.65051
[17] M.C. Pinar and S.A. Zenios, ”On smoothing exact penalty functions for convex constrained optimization,”SIAM Journal on Optimization 4 (1994) 486–511. · Zbl 0819.90072
[18] J. Ren, ”Computable error bounds in mathematical programming,” Technical Report 1173, Computer Sciences Department, University of Wisconsin, Madison, WI, 1993.
[19] S.M. Robinson, ”Application of error bounds for convex programming in a linear space,”SIAM Journal on Control and Optimization 13 (1975) 271–273. · Zbl 0297.90072
[20] R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970). · Zbl 0193.18401
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.