Smooth Methods For Two Kinds Of General Linear Complementarity Problems

Some new algorithms for general linear complementarity problems are studied in this paper.The non-smoothness is an intrinsic difficulty for numerical methods for complementarity problems (CPs). In recent years, there are two main strategies frequently used in the literature for solving CPs: One way is first to reformulate CPs as a system of nonsmooth equations, then directly solve the non-smooth problem by applying a generalized Newton method; An other way is first to reformulate CPs as a system of nonlinear smooth equations with smoothing parameters, then use the classical Newton method. Their common property is to reformulate CPs as a system of determined (nonsmooth or smooth with smoothing parameters) equations, then construct a (generalized) Newton-type algorithm. Distinct from those methods, this paper's main idea is to reformulate CPs as an unconstrained minimization problem with the form of least squares of a system of overdetermined equations being equivalent to the CPs. This method not only reformulates CPs as a smooth minimization problem, but also avoids the inconvenience of adjusting parameters. To some extent, it widens the numerical methods for studying CPs. This paper focuses on studying general linear complementarities problems as follows:Vertical Linear Complementarity Problem (VLCP). For VLCP, a smooth merit function with good coercive property is first constructed, then a damped Newton algorithm is presented for solving VLCP. The algorithm has following properties:(i) Although the merit function has the form of least squares of a system of overdetermined equations, in the Newton equation of our algorithm, only the coefficient matrix of the system of overdetermined equations is used instead of its product as in Guass-Newton method for solving the least squares problems (LSPs). That is, our Newton method is more like that for the system of nonlinear equations rather than that for LSPs.(ii) The global convergence is obtained for VLCP with vertical block P₀ + R₀ matrix;(iii) The local quadratic convergence rate is proved under the condition that the solution is BD-regular;(iv) Although there is only a Newton equation in our algorithm, the finite convergence property can be shown if matrix is vertical block P— matrix (without the hypotheses of strict complementarity).Numerical results show that the algorithm is feasible and effective. In particular, the numerical experiments on many different initial points indicate the algorithm is more adaptable.A kind of General Linear Complementarity Problem (GLCP). For GLCP, similarly, the merit function is constructed as in VLCP. Instead of Newton-type method, a kind of conjugate gradient algorithm with an inexact line search is implemented for solving the unconstrained minimization problem. Global convergence of the method is proved. Numerical results show that the method is stable and high efficient. Especially, it is suitable for large-scale problems.