Global Linear and Quadratic One-step Smoothing Newton Method for P 0-LCP

We propose a new smoothing Newton method for solving the P ₀-matrix linear complementarity problem (P ₀-LCP) based on CHKS smoothing function. Our algorithm solves only one linear system of equations and performs only one line search per iteration. It is shown to converge to a P ₀-LCP solution globally linearly and locally quadratically without the strict complementarity assumption at the solution. To the best of author's knowledge, this is the first one-step smoothing Newton method to possess both global linear and local quadratic convergence. Preliminary numerical results indicate that the proposed algorithm is promising.     

Ky Fan's N-matrices and linear complementarity problems

We consider the linear complementarity problem (LCP),w=Az + q, w0,z0,w ^T z=0, when all the off-diagonal entries ofA are nonpositive (the class of Z-matrices), all the proper principal minors ofA are positive and the determinant ofA is negative (the class of almost P-matrices). We shall call this the class of F-matrices. We show that ifA is a Z-matrix, thenA is an F-matrix if and only if LCP(q, A) has exactly two solutions for anyq0,q0, and has at most two solutions for any otherq. Research supported by AFOSR-89-0512.     

A finite characterization ofK-matrices in dimensions less than four

The class of realn × n matricesM, known asK-matrices, for which the linear complementarity problemw – Mz = q, w 0, z 0, w ^T z =0 has a solution wheneverw – Mz =q, w 0, z 0 has a solution is characterized for dimensionsn <4. The characterization is finite and practical. Several necessary conditions, sufficient conditions, and counterexamples pertaining toK-matrices are also given. A finite characterization of completelyK-matrices (K-matrices all of whose principal submatrices are alsoK-matrices) is proved for dimensions <4.Partially supported by NSF Grant MCS-8207217.Research partially supported by NSF Grant No. ECS-8401081.     

A short proof of finiteness of Murty's principal pivoting algorithm

We give a short proof of the finiteness of Murty's principal pivoting algorithm for solving the linear complementarity problemy = Mz + q, y ^T z = 0,y 0,z 0 withP-matrixM.     

On co-positive,semi-monotoneQ-matrices

In this paper we consider not necessarily symmetric co-positive as well as semi-monotoneQ-matrices and give a set of sufficient conditions for such matrices to beR ₀-matrices. We give several examples to show the sharpness of our results. Construction of these examples is based on the following elementary proposition: IfA is a square matrix of ordern whose first two rows are identical and bothA ₁₁ andA ₂₂ areQ-matrices whereA _ii stands for the principal submatrix ofA obtained by deleting rowi and columni fromA, thenA is aQ-matrix.Dedicated to our colleague and friend B. Ramachandran on his sixtieth birthday.Corresponding author.     

Degeneracy in linear complementarity problems: a survey

Given a square matrixM of ordern and a vectorq ⁿ , the linear complementarity problem is the problem of either finding aw ⁿ and az ⁿ such thatw–Mz=q,w0,z0 andw ^T z=0 or showing that no such (w, z) exists. This problem is denoted asLCP(q, M). We say that a solution (w, z) toLCP(q, M) is degenerate if the number of positive coordinates in (w, z) is less thann. As in linear programming, degeneracy may cause cycling in an adjacent vertex following methods like Lemke's algorithm. Moreover, ifLCP(0,M) has a nontrivial solution, a condition related to degeneracy, then unless certain other conditions are satisfied, the algorithm may not be able to decide about the solvability of the givenLCP(q, M). In this paper we review the literature on the implications of degeneracy to the linear complementarity theory.     

A note on solvability of a class of linear complementarity problems

We give a characterization of unique solvability of an infinite family of linear complementarity problems of a special form by means of a finite subset of this family.     

The global linear and local quadratic convergence of a non-interior continuation algorithm for the LCP

^** Email: zhenghaihuang{at}yahoo.com.cn; huangzhenghai{at}hotmail.com In this paper, we propose a non-interior continuation algorithmfor solving the P₀-matrix linear complementarity problem (LCP),which is conceptually simpler than most existing non-interiorcontinuation algorithms in the sense that the proposed algorithmonly needs to solve at most one linear system of equations ateach iteration. We show that the proposed algorithm is globallyconvergent under a common assumption. In particular, we showthat the proposed algorithm is globally linearly and locallyquadratically convergent under some assumptions which are weakerthan those required in many existing non-interior continuationalgorithms. It should be pointed out that the assumptions usedin our analysis of both global linear and local quadratic convergencedo not imply the uniqueness of the solution to the LCP concerned.To the best of our knowledge, such a convergence result hasnot been reported in the literature.     

The non-interior continuation methods for solving theP0 function nonlinear complementarity problem

In this paper, we propose a new smooth function that possesses a property not satisfied by the existing smooth functions. Based on this smooth function, we discuss the existence and continuity of the smoothing path for solving theP ₀ function nonlinear complementarity problem ( NCP). Using the characteristics of the new smooth function, we investigate the boundedness of the iteration sequence generated by the non-interior continuation methods for solving theP ₀ function NCP under the assumption that the solution set of the NCP is nonempty and bounded. We show that the assumption that the solution set of the NCP is nonempty and bounded is weaker than those required by a few existing continuation methods for solving the NCP     

Error Bounds for R0-Type and Monotone Nonlinear Complementarity Problems

The paper generalizes the Mangasarian–Ren (Ref. 1) error bounds forlinear complementarity problems (LCPs) to nonlinear complementarity problems(NCPs). This is done by extending the concept of R ₀-matrixto several R ₀-type functions, which include a subset ofmonotone functions as a special case. Both local and global error bounds areobtained for R ₀-type NCPs and some monotone NCPs.     

A smoothing Newton method for NCPs with the P0-property

In this paper, we first investigate a two-parametric class of smoothing functions which contains the penalized smoothing Fischer-Burmeister function and the penalized smoothing CHKS function as special cases. Then we present a smoothing Newton method for the nonlinear complementarity problem based on the class of smoothing functions. Issues such as line search rule, boundedness of the level set, global and quadratic convergence are studied. In particular, we give a line search rule containing the common used Armijo-type line search rule as a special case. Also without requiring strict complementarity assumption at the P₀-NCP solution or the nonemptyness and boundedness of the solution set, the proposed algorithm is proved to be globally convergent. Preliminary numerical results show the efficiency of the algorithm and provide efficient domains of the two parameters for the complementarity problems.     

态R_0代数

本文研究了R_0代数上有关态算子的问题.利用MV-代数上内态的引入方法引入了态算子,定义了态R_0代数,它是R_0代数的一般化.给出了一些非平凡态R_0代数的例子并讨论了态R_0代数的一些基本性质.在此基础上给出了态滤子和态局部R_0代数的概念,并利用态滤子刻画了态局部R_0代数.推广了局部R_0代数的相关理论.     

R 0-algebras and weak dually residuated lattice ordered semigroups

We introduce the notion of weak dually residuated lattice ordered semi-groups (WDRL-semigroups) and investigate the relation between R ₀-algebras and WDRL-semigroups. We prove that the category of R ₀-algebras is equivalent to the category of some bounded WDRL-semigroups. Moreover, the connection between WDRL-semigroups and DRL-semigroups is studied.     

局部R0-代数

文提出了局部R₀-代数的概念,并给出了相应的等价条件,即(i)R₀-代数L是局部的,(ii) ?x∈L,ord(x)<∞或ord(-x)<∞,(iii)每一个真滤子是primary.另外,我们又证明了任一R₀-代数是局部R₀-代数的子直积.     

On the Rate of Local Convergence of High-Order-Infeasible-Path-Following Algorithms for P*-Linear Complementarity Problems

A simple and unified analysis is provided on the rate of local convergence for a class of high-order-infeasible-path-following algorithms for the P_*-linear complementarity problem (P_*-LCP). It is shown that the rate of local convergence of a -order algorithm with a centering step is + 1 if there is a strictly complementary solution and ( + 1)/2 otherwise. For the -order algorithm without the centering step the corresponding rates are and /2, respectively. The algorithm without a centering step does not follow the fixed traditional central path. Instead, at each iteration, it follows a new analytic path connecting the current iterate with an optimal solution to generate the next iterate. An advantage of this algorithm is that it does not restrict iterates in a sequence of contracting neighborhoods of the central path.     

OnQ-matrices

Recently, Jeter and Pye gave an example to show that Pang's conjecture, thatL ₁ Q , is false. We show in this article that the above conjecture is true for symmetric matrices. Specifically, we show that a symmetric copositive matrix is inQ if and only if it is strictly copositive.     

On the modulus algorithm for the linear complementarity problem

Concerning three subclasses of P-matrices the modulus algorithm and the projected successive overrelaxation (PSOR) method solving the linear complementarity problem are compared to each other with respect to convergence. It is shown that the modulus algorithm is convergent for all three subclasses whereas the convergence of the PSOR method is only guaranteed for two of them.     

On weak generalized positive subdefinite matrices and the linear complementarity problem

In this article, we present a weaker version of the class of generalized positive subdefinite matrices introduced by Crouzeix and Komlósi [J.P. Crouzeix and S. Komlósi, The Linear Complementarity Problem and the Class of Generalized Positive Subdefinite Matrices, Applied Optimization, Vol. 59, Kluwer, Dordrecht, 2001, pp. 45–63], which is new in the literature, and obtain some properties of weak generalized positive subdefinite (WGPSBD) matrices. We show that this weaker class of matrices is also captured by row-sufficient matrices introduced by Cottle et al. [R.W. Cottle, J.S. Pang, and V. Venkateswaran, Sufficient matrices and the linear complementarity problem, Linear Algebra Appl. 114/115 (1989), pp. 231–249] and show that for WGPSBD matrices under appropriate assumptions, the solution set of a linear complementarity problem is the same as the set of Karush–Kuhn–Tucker-stationary points of the corresponding quadratic programming problem. This further extends the results obtained in an earlier paper by Neogy and Das [S.K. Neogy and A.K. Das, Some properties of generalized positive subdenite matrices, SIAM J. Matrix Anal. Appl. 27 (2006), pp. 988–995].