A two-step matrix splitting method for the mixed linear complementarity problem

In this paper, on the base of the methodology of the new modulus-based matrix splitting method in [Optim. Lett., (2022) 16:1427-1443], we establish a two-step matrix splitting (TMS) method for solving the mixed linear complementarity problem (MLCP). Two sufficient conditions to ensure the convergence of the proposed method are presented. Numerical examples are provided to illustrate the feasibility and efficiency of the proposed method.     

An interior point potential reduction algorithm for the linear complementarity problem

The linear complementarity problem (LCP) can be viewed as the problem of minimizingx ^T y subject toy=Mx+q andx, y?0. We are interested in finding a point withx ^T y <ε for a givenε > 0. The algorithm proceeds by iteratively reducing the potential function $$f(x,y) = \rho \ln x^T y - \Sigma \ln x_j y_j ,$$ where, for example,ρ=2n. The direction of movement in the original space can be viewed as follows. First, apply alinear scaling transformation to make the coordinates of the current point all equal to 1. Take a gradient step in the transformed space using the gradient of the transformed potential function, where the step size is either predetermined by the algorithm or decided by line search to minimize the value of the potential. Finally, map the point back to the original space. A bound on the worst-case performance of the algorithm depends on the parameterλ ^*=λ^*(M, ε), which is defined as the minimum of the smallest eigenvalue of a matrix of the form $$(I + Y^{ - 1} MX)(I + M^T Y^{ - 2} MX)^{ - 1} (I + XM^T Y^{ - 1} )$$ whereX andY vary over the nonnegative diagonal matrices such thate ^T XYe ?ε andX _jj Y _jj?n ². IfM is a P-matrix,λ ^* is positive and the algorithm solves the problem in polynomial time in terms of the input size, |log ε|, and 1/λ ^*. It is also shown that whenM is positive semi-definite, the choice ofρ = 2n+ \(\sqrt {2n} \) yields a polynomial-time algorithm. This covers the convex quadratic minimization problem.     

Accelerated modulus-based matrix splitting iteration methods for linear complementarity problem

For the large sparse linear complementarity problem, a class of accelerated modulus-based matrix splitting iteration methods is established by reformulating it as a general implicit fixed-point equation, which covers the known modulus-based matrix splitting iteration methods. The convergence conditions are presented when the system matrix is either a positive definite matrix or an H ₊-matrix. Numerical experiments further show that the proposed methods are efficient and accelerate the convergence performance of the modulus-based matrix splitting iteration methods with less iteration steps and CPU time.     

A neural network for the linear complementarity problem

An artificial neural network is proposed in this paper for solving the linear complementarity problem. The new neural network is based on a reformulation of the linear complementarity problem into the unconstrained minimization problem. Our new neural network can be easily implemented on a circuit. On the theoretical aspect, we analyze the existence of the equilibrium points for our neural network. In addition, we prove that if the equilibrium point exists for the neural network, then any such equilibrium point is both asymptotically and bounded (Lagrange) stable for any initial state. Furthermore, linear programming and certain quadratical programming problems (not necessarily convex) can be also solved by the neural network. Simulation results on several problems including a nonconvex one are also reported.     

An existence theorem for the complementarity problem

LetC be a pointed, solid, closed and convex cone in then-dimensional Euclidean spaceE ⁿ ,C* its polar cone,M:C→E ⁿ a map, andq a vector inE ⁿ . The complementarity problem (q|M) overC is that of finding a solution to the system $$(q|M) x \varepsilon C, M(x) + q \varepsilon C{^*} , \left\langle {x, M(x) + q} \right\rangle = 0.$$ It is shown that, ifM is continuous and positively homogeneous of some degree onC, and if (q|M) has a unique solution (namely,x=0) forq=0 and for someq=q ₀ ∈ intC*, then it has a solution for allq ∈E ⁿ .     

A modified homogeneous potential reduction algorithm for solving the monotone semidefinite linear complementarity problem

In this paper, we study the performance of the Semidefinite Linear Complementarity Problem (SDLCP) for symmetric matrices that is equipped with a continuously differentiable potential function. A practical homogeneous self-dual potential reduction algorithm based on this potential function is prescribed, and we establish a computational basis for interior point methods with the use of HKM directions towards the central trajectory for the monotone SDLCP. Our computational implementation maintains a global linear polynomial time convergence, while achieving strong practical performance in comparison with existing solution methods.     

A new polynomial time method for a linear complementarity problem

The purpose of this paper is to present a new polynomial time method for a linear complementarity problem with a positive semi-definite matrix. The method follows a sequence of points. If we generate the sequence on a path, we can construct a path following method, and if we generate the sequence based on a potential function, we can construct a potential reduction method. The method has the advantage that it requires at most iterations for any initial feasible point whose components lie between 2^–O(L) and 2^O(L).Research was supported in part by Grant-in-Aids for Encouragement of Young Scientists (63730014) and for General Scientific Research (63490010) of The Ministry of Education, Science and Culture.     

A parallel algorithm for solving the linear complementarity problem

The concept of multitasking mathematical programs is discussed, and an application of multitasking to the multiple-cost-row linear programming problem is considered. Based on this, an algorithm for solving the Linear Complementarity Problem (LCP) in parallel is presented. A variety of computational results are presented using this multitasking approach on the CRAY X-MP/48. These results were obtained for randomly generated LCP's where thenxn dense matrixM has no special properties (hence, the problem is NP-hard). based on these results, an average time performance ofO(n ⁴) is observed.     

A variable dimension algorithm for the linear complementarity problem

A variable dimension algorithm is presented for the linear complementarity problems – Mz = q; s,z 0; s _i z _i = 0 fori = 1,2, ,n. The algorithm solves a sequence of subproblems of different dimensions, the sequence being possibly nonmonotonic in the dimension of the subproblem solved. Every subproblem is the linear complementarity problem defined by a leading principal minor of the matrixM. Index-theoretic arguments characterize the points at which nonmonotonic behavior occurs.     

A modulus-based formulation for the vertical linear complementarity problem

Numerical Algorithms - We introduce a modulus-based formulation for vertical linear complementarity problems (VLCPs) with an arbitrary number ? of matrices. This formulation can be used to...     

A support submatrix for the generalized linear complementarity problem

We provide an algorithm that selects, in a polynomial time, a representative submatrix whose appropriately defined LCP solution solves the GLCP. An algorithm based on support submatrices is also presented.     

Basic-set algorithm for a generalized linear complementarity problem

In this paper, the authors develop a new direct method for the solution of a BLCP, that is, a linear complementarity problem (LCP) with upper bounds, when its matrix is a symmetric or an unsymmetricP-matrix. The convergence of the algorithm is established by extending Murty's principal pivoting method to an LCP which is equivalent to the BLCP. Computational experience with large-scale BLCPs shows that the basic-set method can solve efficiently large-scale BLCPs with a symmetric or an unsymmetricP-matrix.     

Perturbation results for the linear complementarity problem

This paper presents several results concerning the perturbation of the solution vector to an linear complementarity LCP(q,M) as a function of changes in the input data (q,M).     

A continuation method for linear complementarity problems with P 0 matrix

In this article, we propose a new continuation method for solving the linear complementarity problem (LCP). The method solves one system of linear equations and carries out only a one-line search at each iteration. The continuation method is based on a modified smoothing function. The existence and continuity of a smooth path for solving the LCP with a P ₀ matrix are discussed. We investigate the boundedness of the iteration sequence generated by our continuation method under the assumption that the solution set of the LCP is nonempty and bounded. It is shown to converge to an LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution under suitable assumption. In addition, some numerical results are also reported in this article.     

On the monotone convergence of matrix multisplitting relaxation methods for the linear complementarity problem

The monotone convergence of the parallel matrix multisplittingrelaxation method for linear complementarity problems (see Bai,Z. Z. and Evans, D. J. 1997 Int. J. Comput. Math 63, 309-326)is discussed, and the corresponding comparison theorem aboutthe monotone convergence rate of this method is thoroughly established.     

Continuous linear complementarity problem

We investigate a form of linear complementarity problem posed over a space of measures onX, where the matrix which occurs in the finite-dimensional linear complementarity problem is replaced by a continuous functionM(x, y),x,yX. We give a number of conditions which ensure the existence of solutions, and we discuss the extension of Lemke's algorithm to this problem.     

A method for solving the general parametric linear complementarity problem

This paper presents a solution method for the general (mixed integer) parametric linear complementarity problem pLCP(q(θ),M), where the matrix M has a general structure and integrality restriction can be enforced on the solution. Based on the equivalence between the linear complementarity problem and mixed integer feasibility problem, we propose a mixed integer programming formulation with an objective of finding the minimum 1-norm solution for the original linear complementarity problem. The parametric linear complementarity problem is then formulated as multiparametric mixed integer programming problem, which is solved using a multiparametric programming algorithm. The proposed method is illustrated through a number of examples.     

A new resolution method for the parametric linear complementarity problem

An original method is presented to solve the parametric linear complementarity problem. To solve such a problem requires to identify the values taken by the solution of a linear complementarity problem where some of its right-hand side terms vary in a prescribed domain. This class of problems allows, among others, to deal with linear market equilibrium problems with varying prices: it allows to identify how does the equilibrium point varies when the prices vary over a set of given values. This method is illustrated through an application related to the institution of ecological taxes on the Western European natural gas market.     

A dual exact penalty formulation for the linear complementarity problem

We consider a dual exact penalty formulation for the monotone linear complementarity problem. Tihonov regularization is then used to reduce the solution of the problem to the solution of a sequence of positive-definite, symmetric quadratic programs. A modified form of an SOR method due to Mangasarian is proposed to solve these quadratic programs. We also indicate how to obtain approximate solutions to predefined tolerance by solving a single quadratic program, in special cases.This research was sponsored by US Army Contract DAAG29-80-C-0041, by National Science Foundation Grants DCR-8420963 and MCS-8102684, and AFSOR Grant AFSOR-ISSA-85-0880.     

A parametric linear complementarity problem involving derivatives

The problem considered in this paper is given by the conditions:w = q + tp + Mz, w 0, 0,w ^T = 0, where a dot denotes the derivative with respect to the scalar parametert 0. In this problem,q, p aren-vectors withq 0 andM is an byn P-matrix. This problem arises in a certain basic problem in the field of structural mechanics. The main result in this paper is the existence and uniqueness theorem of a solution to this problem. The existence proof is constructive providing a computational method of obtaining the solution asymptotically.This research is in part supported by the National Science Foundation under Grant No. ENG77-11136.