A method for solving a general multi-valued complementarity problem

We propose an extended version of Chandrasekaran’s method for general complementarity problems with multi-valued weakly off-diagonally antitone costmappings. It allows one either to construct a sequence converging to a solution or to recognize that the problem has no solutions. We also propose versions of Jacobi’s methods for multi-valued inclusions subject to one- and two-side constraints.     

GAUSSIAN PIVOTING METHOD FORSOLVING LINEAR COMPLEMENTARITY PROBLEM

In this paper, a new direct algorithm for solving linear complementarity problem with Z-matrix is proposed. The algorithm exhibits either a solution or its nonexistence after at most n steps (where n is the dimension of the problem) and the computational complexity is at most 1/3n^2 O(n^2)     

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 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.     

On the gradient-projection method for solving the nonsymmetric linear complementarity problem

The Levitin-Poljak gradient-projection method is applied to solve the linear complementarity problem with a nonsymmetric matrixM, which is either a positive-semidefinite matrix or aP-matrix. Further-more, if the quadratic functionx ^T(Mx + q) is pseudoconvex on the feasible region {x R ⁿ |Mx + q 0,x0}, then the gradient-projection method generates a sequence converging to a solution, provided that the problem has a solution. For the case when the matrixM is aP-matrix and the solution is nondegenerate, the gradient-projection method is finite.This work is based on the author's PhD Dissertation, which was supported by NSF Grant No. MCS-79-01066 at the University of Wisconsin, Madison, Wisconsin.The author would like to thank Professor O. L. Mangasarian for his guidance of the dissertation.     

A new modified one-step smoothing Newton method for solving the general mixed complementarity problem

In last decades, there has been much effort on the solution and the analysis of the mixed complementarity problem (MCP) by reformulating MCP as an unconstrained minimization involving an MCP function. In this paper, we propose a new modified one-step smoothing Newton method for solving general (not necessarily P₀) mixed complementarity problems based on well-known Chen-Harker-Kanzow-Smale smooth function. Under suitable assumptions, global convergence and locally superlinear convergence of the algorithm are established.     

Parallel pivotal algorithm for solving the linear complementarity problem

We propose a parallel implementation of the classical Lemke's algorithm for solving the linear complementarity problem. The algorithm is designed for a loosely coupled network of computers which is characterized by relatively high communication costs. We provide an accurate prediction of speedup based on a simple operation count. The algorithm produces speedup nearp, wherep is the number of processors, when tested on large problems as demonstrated by computational results on the CRYSTAL token-ring multicomputer and the Sequent Balance 21000 multiprocessor.This material is based on research supported by National Science Foundation Grants DCR-84-20963 and DCR-850-21228 and by Air Force Office of Scientific Research Grants AFSOR-86-0172 and AFSOR-86-0255 while the author was at the University of Wisconsin, Madison, Wisconsin.     

Monotone solutions of the parametric linear complementarity problem

The parametric linear complementarity problem under study here is given by the conditionsq + αp + Mz ≥ 0,α ≥ 0,z ≥ 0,z ^T (q + αp + Mz) = 0 whereq is nonnegative. This paper answers three questions including the following one raised by G. Maier: What are the necessary and sufficient conditions onM guaranteeing that for every nonnegative starting pointq and every directionp the components of the solution to the parametric linear complementarity problem are nondecreasing functions of the parameterα?     

A two-stage successive overrelaxation algorithm for solving the symmetric linear complementarity problem

We propose a two-stage successive overrelaxation method (TSOR) algorithm for solving the symmetric linear complementarity problem. After the first SOR preprocessing stage this algorithm concentrates on updating a certain prescribed subset of variables which is determined by exploiting the complementarity property. We demonstrate that this algorithm successfully solves problems with up to ten thousand variables.This material is based on research supported by National Science Foundation Grants DCR-8420963 and DCR-8521228 and Air Force Office of Scientific Research Grants AFSOR-86-0172 and AFSOR-86-0255 while the author was at the Computer Sciences Department at the University of Wisconsin-Madison, USA.     

On the parametric linear complementarity problem: A generalized solution procedure

This paper presents a solution procedure for the parametric linear complementarity problemIw–Mz=q+sp,w ^T z=0,w0, andz0, whereM is a positive semidefinite matrix or aP-matrix. This procedure is different from existing ones in the way it handles initialization. By exploiting special relationships between the vectorsq andp, it can reduce computational effort. Sinceq is an arbitrary vector, the procedure can be used for the ordinary linear complementarity problem. In that case, it produces pivots exactly analogous to those of Lemke's algorithm.This paper is based on the author's doctoral dissertation at Johns Hopkins University, 1977. The author wishes to thank her advisors, Professors C. S. ReVelle and D. J. Elzinga. During the last year of her graduate studies, the author held an AAUW-IBM dissertation fellowship.     

New multiplier method for solving linear complementarity problems

A new multiplier method for solving the linear complementarity problem LCP(q, M) is proposed. By introducing a Lagrangian of LCP(q, M), a new smooth merit function ϑ(x, λ) for LCP(q, M) is constructed. Based on it, a simple damped Newton-type algorithm with multiplier self-adjusting step is presented. When M is a P-matrix, the sequence {ϑ(x ^k, λ ^k)} (where {(x ^k, λ ^k)} is generated by the algorithm) is globally linearly convergent to zero and convergent in a finite number of iterations if the solution is degenerate. Numerical results suggest that the method is highly efficient and promising. Selected from Numerical Mathematics (A Journal of Chinese Universities), 2004, 26(2): 162–171     

非对称线性互补问题的并行二级多分裂迭代法

提出了求解非对称线性互补问题的并行二级多分裂迭代算法,并证明了该算法的收敛性,最后通过数值实验验证了算法的有效性和可行性.     

A problem expanding parametric programming method for solving the job shop scheduling problem

A new zero-one integer programming model for the job shop scheduling problem with minimum makespan criterion is presented. The algorithm consists of two parts: (a) a branch and bound parametric linear programming code for solving the job shop problem with fixed completion time; (b) a problem expanding algorithm for finding the optimal completion time. Computational experience for problems having up to thirty-six operations is presented. The largest problem solved was limited by memory space, not computation time. Efforts are under way to improve the efficiency of the algorithm and to reduce its memory requirements.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie-Mellon University, under Contract No. N00014-82-K-0329 NR 047-048 with the U.S. Office of Naval Research. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

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 smoothing Levenberg-Marquardt algorithm for solving a class of stochastic linear complementarity problem

In this paper, it is considered for a class of stochastic linear complementarity problems (SLCPs) with finitely many elements. A smoothing Levenberg-Marquardt algorithm is proposed for solving the SLCP. Under suitable conditions, the global convergence and local quadratic convergence of the proposed algorithm is given. Some numerical results are reported in this paper, which confirms the good theoretical properties of the proposed algorithm.