Simplicial approximation of solutions to the nonlinear complementarity problem with lower and upper bounds.(English)Zbl 0633.90082
Ideas of a simplicial variable dimension restart algorithm to approximate zero points on \(R^ n\) developed by the authors and of a linear complementarity problem pivoting algorithm are combined to an algorithm for solving the nonlinear complementarity problem with lower and upper bounds. The algorithm can be considered as a modification of the 2n-ray zero point finding algorithm on \(R^ n\). It appears that for the new algorithm the number of linear programming pivot steps is typically less than for the 2n-ray algorithm applied to an equivalent zero point problem. This is caused by the fact that the algorithm utilizes the complementarity conditions on the variables.
MSC:
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 65K05 | Numerical mathematical programming methods |
Keywords:
simplicial algorithm;triangulation;simplicial variable dimension restart algorithm;linear complementarity;nonlinear complementarity;lower and upper boundsCite
References:
| [1] | E.L. Allgower and K. Georg, ”Simplicial and continuation methods for approximating fixed points and solutions to systems of equations,”SIAM Review 22 (1980) 28–85. ·Zbl 0432.65027 ·doi:10.1137/1022003 |
| [2] | S.N. Chow, J. Mallet-Paret and J.A. Yorke, ”Finding zeroes of maps: homotopy methods that are constructive with probability one,”Mathematics of Computation 32 (1978) 887–899. ·Zbl 0398.65029 ·doi:10.1090/S0025-5718-1978-0492046-9 |
| [3] | B.C. Eaves, ”On the basic theory of complementarity,”Mathematical Programming 1 (1971) 68–75. ·Zbl 0227.90044 ·doi:10.1007/BF01584073 |
| [4] | M.L. Fisher and F.J. Gould, ”A simplicial algorithm for the nonlinear complementarity problem,”Mathematical Programming 6 (1974) 281–300. ·Zbl 0291.90058 ·doi:10.1007/BF01580246 |
| [5] | C.B. Garcia, ”The complementarity problem and its applications,” Ph.D. Thesis, Rensselaer Polytechnic Institute, Troy, NY (1973). ·Zbl 0284.90048 |
| [6] | G.J. Habetler and K.M. Kostreva, ”On a direct algorithm for nonlinear complementarity problems,”SIAM Journal of Control and Optimization 16 (1978) 504–511. ·Zbl 0392.90083 ·doi:10.1137/0316033 |
| [7] | M. Kojima, ”Computational methods for solving the nonlinear complementarity problem”, Keio Engineering Reports 27, Keio University, Yokohama, Japan (1974). ·Zbl 0406.90071 |
| [8] | M. Kojima and R. Saigal, ”On the number of solutions to a class of complementarity problems,”Mathematical Programming 21 (1981) 190–203. ·Zbl 0461.90066 ·doi:10.1007/BF01584240 |
| [9] | M. Kojima and Y. Yamamoto, ”Variable dimension algorithms: Basic theory, interpretations and extensions of some existing methods,”Mathematical Programming 24 (1982) 177–215. ·Zbl 0509.90070 ·doi:10.1007/BF01585103 |
| [10] | M. Kojima and Y. Yamamoto, ”A unified approach to the implementation of several restart fixed point algorithms and a new variable dimension algorithm,”Mathematical Programming 28 (1984) 288–328. ·Zbl 0539.65036 ·doi:10.1007/BF02612336 |
| [11] | G. van der Laan and A.J.J. Talman, ”A restart algorithm for computing fixed points without an extra dimension,”Mathematical Programming 17 (1979) 74–84. ·Zbl 0411.90061 ·doi:10.1007/BF01588226 |
| [12] | G. van der Laan and A.J.J. Talman, ”A class of simplicial restart fixed point algorithms without an extra dimension,”Mathematical Programming 20 (1981) 33–48. ·Zbl 0441.90112 ·doi:10.1007/BF01589331 |
| [13] | G. van der Laan and A.J.J. Talman, ”Simplicial algorithms for finding stationary points, a unifying description,”Journal of Optimization Theory and Applications 50 (1986) 165–182. ·Zbl 0571.90075 ·doi:10.1007/BF00938483 |
| [14] | H.J. Lüthi, ”A simplicial approximation of a solution for the nonlinear complementarity problem,”Mathematical Programming 9 (1975) 278–293. ·Zbl 0358.90058 ·doi:10.1007/BF01681351 |
| [15] | O.L. Mangasarian, ”Equivalence of the complementarity problem to a system of nonlinear equations,”SIAM Journal of Applied Mathematics 31 (1976) 89–92. ·Zbl 0339.90051 ·doi:10.1137/0131009 |
| [16] | O.H. Merrill, ”Applications and extensionof an algorithm that computes fixed points of certain upper semi-continuous point-to-set mappings” Ph.D. Thesis, University of Michigan, Ann Arbor, Mich. (1972). |
| [17] | J.J. Moré, ”Coercivity conditions in nonlinear complementarity algorithms”,SIAM Review 16 (1974) 1–15. ·doi:10.1137/1016001 |
| [18] | R. Saigal, ”A homotopy for solving large, sparse and structured fixed point problems”,Mathematics of Operations Research 8 (1983) 557–578. ·Zbl 0532.65039 ·doi:10.1287/moor.8.4.557 |
| [19] | A.J.J. Talman, ”Variable dimension fixed point algorithms and triangulations,” Mathematical Centre Tracts, 128 (Mathematisch Centrum, Amsterdam, 1980). ·Zbl 0464.90047 |
| [20] | A.J.J. Talman and L. Van der Heyden, ”Algorithms for the linear complementarity problem which allow an arbitrary starting point,” in: B.C. Eaves et al., eds.Homotopy Methods and Global Convergence (Plenum Press, New York, 1983) pp. 267–286. ·Zbl 0542.65034 |
| [21] | M.J. Todd, ”Improving the convergence of fixed point algorithms”,Mathematical Programming Study 7 (1978) 151–169. ·Zbl 0399.65034 |
| [22] | M.J. Todd, ”Global and local convergence and monotonicity results for a recent variable dimension simplicial algorithm,” in W. Forster, ed.,Numerical Solution of Highly Nonlinear Problems (North-Holland, Amsterdam, 1980) pp. 43–69. ·Zbl 0449.65021 |
| [23] | L.T. Watson, ”Solving the nonlinear complementarity problem by a homotopy method,”SIAM Journal of Control and Optimization 17 (1979) 36–46. ·Zbl 0407.90083 ·doi:10.1137/0317004 |
| [24] | A.H. Wright, ”The octahedral algorithm, a new simplicial fixed point algorithm”,Mathematical Programming 21 (1981) 47–9. ·Zbl 0475.65029 ·doi:10.1007/BF01584229 |
| [25] | Y. Yamamoto, ”A new variable dimension algorithm for the fixed point problem”,Mathematical Programming 25 (1983) 329–342. ·Zbl 0495.90071 ·doi:10.1007/BF02594783 |
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.
