On finite termination of an iterative method for linear complementarity problems.

*(English)*Zbl 0855.90125Summary: Based on a well-known reformulation of the linear complementarity problem (LCP) as a nondifferentiable system of nonlinear equations, a Newton-type method will be described for the solution of LCPs. Under certain assumptions, it will be shown that this method has a finite termination property, i.e., if an iterate is sufficiently close to a solution of LCP, the method finds this solution in one step. This result will be applied to a recently proposed algorithm by Harker and Pang in order to prove that their algorithm also has the finite termination property.

##### MSC:

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

##### Keywords:

nonsmooth equations; generalized Jacobians; linear complementarity; nondifferentiable system of nonlinear equations; Newton-type method##### Software:

PATH Solver
PDF
BibTeX
XML
Cite

\textit{A. Fischer} and \textit{C. Kanzow}, Math. Program. 74, No. 3 (A), 279--292 (1996; Zbl 0855.90125)

Full Text:
DOI

##### References:

[1] | B. Chen and P.T. Harker, A non-interior-continuation method for linear complementarity problems,SIAM Journal on Matrix Analysis and Applications 14 (1993) 1168–1190. · Zbl 0788.65073 |

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

[3] | R.W. Cottle, J.-S. Pang and R.E. Stone,The Linear Complementary Problem (Academic Press, New York, 1992). · Zbl 0757.90078 |

[4] | S.P. Dirkse and M.C. Ferris, The PATH solver: a nonmonotone stabilization scheme for mixed complementarity problemsOptimization Methods and Software 5 (1995) 123–156. |

[5] | F. Facchinei and J. Soares, A new merit function for nonlinear complementary problems and a related algorithm. Technical Report 15.94, Dipartimento di Informatica e Sistemistica. Universita di Roma ”La Sapienza”, Rome, Italy, 1994. To appear inSIAM Journal on Optimization. · Zbl 0873.90096 |

[6] | M.C. Ferris and S. Lucidi, Globally convergent methods for nonlinear equations,Journal of Optimization Theory and Applications 81 (1994) 53–71. · Zbl 0803.65070 |

[7] | A. Fischer, A special Newton-type optimization method,Optimization 24 (1992) 269–284. · Zbl 0814.65063 |

[8] | A. Fischer, A Newton-type method for positive semidefinite linear complementarity problems,Journal of Optimization Theory and Applications 86 (1995) 585–608. · Zbl 0839.90121 |

[9] | A. Fischer, On the superlinear convergence of a Newton-type method for LCP under weak conditions.Optimization Methods and Software 6 (1995) 83. |

[10] | L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for Newton’s method,SIAM Journal on Numerical Analysis 23 (1986) 707–716. · Zbl 0616.65067 |

[11] | P.T. Harker,Lectures on Computation of Equilibria with Equation-Based Methods, CORE Lecture Series, CORE Foundation, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, 1993. |

[12] | P.T. Harker and J.-S. Pang, A damped Newton method for the linear complementarity problem, in: E.L. Allgower and K. Georg, eds.,Computational Solution of Nonlinear Systems of Equations, Lectures on Applied Mathematics 26 (Amer. Mathematical Soc., Providence, RI, 1990) 265–284. · Zbl 0699.65054 |

[13] | 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 |

[14] | J.J. Júdice, Algorithms for linear complementarity problems, in: E. Spedicato, ed.,Algorithms for Continuous Optimization. The State of the Art (Kluwer Academic Publishers, Dordrecht, 1994) 435–474. |

[15] | C. Kanzow, Some equation-based methods for the nonlinear complementarity problem,Optimization Methods and Software 3 (1994) 327–340. |

[16] | C. Kanzow, Global convergence properties of some iterative methods for linear complementarity problems,SIAM Journal on Optimization 6 (1996) 326–341. · Zbl 0847.90132 |

[17] | C. Kanzow, Some noninterior continuation methods for linear complementarity problems, Preprint 79, Institute of Applied Mathematics, University of Hamburg (Hamburg, Germany, 1994) (revised 1995). To appears inSIAM Journal on Matrix Analysis and Applications. |

[18] | C. Kanzow and H. Kleinmichel, A class of Newton-type methods for equality and inequality constrained optimization,Optimization Methods and Software 5 (1995) 173–198. |

[19] | M. Kojima, N. Meggido, T. Noma and A. Yoshise,A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science 538 (Springer, Berlin, 1991). · Zbl 0745.90069 |

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

[21] | B. Kummer. Newton’s method for non-differentiable functions. in: J. Guddat et al., eds.,Mathematical Research. Advances in Mathematical Optimization (Akademie-Verlag, Berlin, 1988) 114–125. · Zbl 0662.65050 |

[22] | O.L. Mangasarian, Equivalence of the complementarity problem to a system of nonlinear equations,SIAM Journal on Applied Mathematics 31 (1976) 89–92. · Zbl 0339.90051 |

[23] | K.G. Murty,Linear Complementarity, Linear and Nonlinear Programming, Sigma Series in Applied Mathematics 3, (Heldermann Verlag, Berlin, 1988). · Zbl 0634.90037 |

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

[25] | 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 |

[26] | L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations.Mathematics of Operations Research 18 (1993) 227–244. · Zbl 0776.65037 |

[27] | L. Qi and J. Sun, A nonsmooth version of Newton’s method,Mathematical Programming 58 (1993) 353–367. · Zbl 0780.90090 |

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

[29] | P.K. Subramanian, Gauss-Newton methods for the complementarity problem,Journal of Optimization Theory and Applications 77 (1993) 467–482. · Zbl 0792.90082 |

[30] | P. Tseng, Growth behaviour of a class of merit functions for the nonlinear complementarity problem,Journal of Optimization Theory and Applications 89 (1996) 17–37. · Zbl 0866.90127 |

[31] | L.T. Watson, Solving the nonlinear complementarity problem by a homotopy method,SIAM Journal on Control and Optimization 17 (1979) 36–46. · Zbl 0407.90083 |

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.