On the Upper Semi-continuity of the Solution Map to the Vertical Implicit Homogeneous Complementarity Problem of Type <Emphasis Type="Italic">R</Emphasis><Subscript>0</Subscript>

In this paper, we introduce a class of vertical implicit complementarity problems and give a necessary and sufficient condition for the upper semi-continuity of the solution map to the vertical implicit homogeneous complementarity problem of type R₀. This work is supported by the Basic and Applied Research Projection of Sichuan Province (05JY029-009-1).     

On the Equivalence of Extended Generalized Complementarity and Generalized Least-Element Problems

In this paper, we derive some equivalences of generalized nonlinear programs, generalized least-element problems, and extended generalized complementarity problems under certain regularity and growth conditions. We also generalize the notion of a Z-map for point-to-set maps. Our results extend recent results by Schaible and Yao (Ref. 1).     

A Regularization Newton Method for Solving Nonlinear Complementarity Problems

In this paper we construct a regularization Newton method for solving the nonlinear complementarity problem (NCP(F )) and analyze its convergence properties under the assumption that F is a P ₀ -function. We prove that every accumulation point of the sequence of iterates is a solution of NCP(F ) and that the sequence of iterates is bounded if the solution set of NCP(F ) is nonempty and bounded. Moreover, if F is a monotone and Lipschitz continuous function, we prove that the sequence of iterates is bounded if and only if the solution set of NCP(F ) is nonempty by setting , where is a parameter. If NCP(F) has a locally unique solution and satisfies a nonsingularity condition, then the convergence rate is superlinear (quadratic) without strict complementarity conditions. At each step, we only solve a linear system of equations. Numerical results are provided and further applications to other problems are discussed. Accepted 25 March 1998     

Projected Splitting Methods for Vertical Linear Complementarity Problems

Journal of Optimization Theory and Applications - In this paper, we generalize the projected Jacobi and the projected Gauss–Seidel methods to vertical linear complementarity problems (VLCPs)...     

Generalized Equilibrium Problems and Generalized Complementarity Problems

From a general minimax inequality or an abstract lopsided saddle-point theorem, we deduce general Karamardian-type equilibrium theorems and generalized complementarity theorems. Our new results extend a number of well-known earlier works of many authors.     

垂直线性互补问题的一步全局线性和局部二次收敛光滑Newton法

基于凝聚函数,提出一个求解垂直线性互补问题的光滑Newton法.该算法具有以下优点:(i)每次迭代仅需解一个线性系统和实施一次线性搜索;(ⅱ)算法对垂直分块P0矩阵的线性互补问题有定义且迭代序列的每个聚点都是它的解.而且,对垂直分块P₀+R₀矩阵的线性互补问题,算法产生的迭代序列有界且其任一聚点都是它的解;(ⅲ)在无严格互补条件下证得算法即具有全局线性收敛性又具有局部二次收敛性.许多已存在的求解此问题的光滑Newton法都不具有性质(ⅲ).     

On the convergence of iterative methods for symmetric linear complementarity problems

We prove convergence of the whole sequence generated by any of a large class of iterative algorithms for the symmetric linear complementarity problem (LCP), under the only hypothesis that a quadratic form associated with the LCP is bounded below on the nonnegative orthant. This hypothesis holds when the matrix is strictly copositive, and also when the matrix is copositive plus and the LCP is feasible. The proof is based upon the linear convergence rate of the sequence of functional values of the quadratic form. As a by-product, we obtain a decomposition result for copositive plus matrices. Finally, we prove that the distance from the generated sequence to the solution set (and the sequence itself, if its limit is a locally unique solution) have a linear rate of R-convergence.Research for this work was partially supported by CNPq grant No. 301280/86.     

Smoothing Newton method for NCP with the identification of degenerate indices

We present a new smoothing Newton method for nonlinear complementarity problems (NCP(F)) by using an NCP function to reformulate the problem to its equivalent form. Compared with most current smoothing methods, our method contains an estimating technique based on the active-set strategy. This technique focuses on the identification of the degenerate set for a solution x^∗ of the NCP(F). The proposed method has the global convergence, each accumulation point is a solution of the problem. The introduction of the active-set strategy effectively reduces the scale of the problem. Under some regularity assumption, the degenerate set can be identified correctly near the solution and local superlinear convergence is obtained as well.     

A Note on Backward Error Analysis for Generalized Linear Complementarity Problems

This note extends the classical Oettli–Prager theorem to generalized linear complementarity problems.     

Convergence analysis of nonsmooth equations for the general nonlinear complementarity problem

This paper deals with a general nonlinear complementarity problem, where the underlying functions are assumed to be continuous. Based on a nonlinear complementarity function, it is transformed into a system of nonsmooth equations. Then, two kinds of approximate Newton methods for the nonsmooth equations are developed and their convergence are proved. Finally, numerical tests are also listed.     

On the Convergence Regions of Generalized Accelerated Overrelaxation Method for Linear Complementarity Problems

In this paper, we use a generalized Accelerated Overrelaxation (GAOR) method and analyze the convergence of this method for solving linear complementarity problems. Furthermore, we improve on the convergence region of this method with acknowledgement of the maximum norm. A numerical example is also given, to illustrate the efficiency of our results.     

A branch and bound algorithm for globally solving a class of nonconvex programming problems

A branch and bound algorithm is proposed for globally solving a class of nonconvex programming problems (NP). For minimizing the problem, linear lower bounding functions (LLBFs) of objective function and constraint functions are constructed, then a relaxation linear programming is obtained which is solved by the simplex method and which provides the lower bound of the optimal value. The proposed algorithm is convergent to the global minimum through the successive refinement of linear relaxation of the feasible region and the solutions of a series of linear programming problems. And finally the numerical experiment is reported to show the feasibility and effectiveness of the proposed algorithm.     

Solvability of Newton equations in smoothing-type algorithms for the SOCCP

In this paper, we first investigate the invertibility of a class of matrices. Based on the obtained results, we then discuss the solvability of Newton equations appearing in the smoothing-type algorithm for solving the second-order cone complementarity problem (SOCCP). A condition ensuring the solvability of such a system of Newton equations is given. In addition, our results also show that the assumption that the Jacobian matrix of the function involved in the SOCCP is a P₀-matrix is not enough for ensuring the solvability of such a system of Newton equations, which is different from the one of smoothing-type algorithms for solving many traditional optimization problems in ℜⁿ.     

A globally and superlinearly convergent trust region method for LC 1 optimization problems

Abstract. A new trust region algorithm for solving convex LC1 optimization problem is present-ed. It is proved that the algorithm is globally convergent and the rate of convergence is superlin-ear under some reasonable assumptions.     

A family of derivative-free conjugate gradient methods for large-scale nonlinear systems of equations

In this paper, we propose a family of derivative-free conjugate gradient methods for large-scale nonlinear systems of equations. They come from two modified conjugate gradient methods [W.Y. Cheng, A two term PRP based descent Method, Numer. Funct. Anal. Optim. 28 (2007) 1217–1230; L. Zhang, W.J. Zhou, D.H. Li, A descent modified Polak–Ribiére–Polyak conjugate gradient method and its global convergence, IMA J. Numer. Anal. 26 (2006) 629–640] recently proposed for unconstrained optimization problems. Under appropriate conditions, the global convergence of the proposed method is established. Preliminary numerical results show that the proposed method is promising.     

Cyclic orders: Equivalence and duality

Cyclic orders of graphs and their equivalence have been promoted by Bessy and Thomassé’s recent proof of Gallai’s conjecture. We explore this notion further: we prove that two cyclic orders are equivalent if and only if the winding number of every circuit is the same in the two. The proof is short and provides a good characterization and a polynomial algorithm for deciding whether two orders are equivalent. We then derive short proofs of Gallai’s conjecture and a theorem “polar to” the main result of Bessy and Thomassé, using the duality theorem of linear programming, total unimodularity, and the new result on the equivalence of cyclic orders.     

Positive semidefinite matrix completions on chordal graphs and constraint nondegeneracy in semidefinite programming

Let G=(V,E) be a graph. In matrix completion theory, it is known that the following two conditions are equivalent: (i) G is a chordal graph; (ii) Every G-partial positive semidefinite matrix has a positive semidefinite matrix completion. In this paper, we relate these two conditions to constraint nondegeneracy condition in semidefinite programming and prove that they are each equivalent to (iii) For any G-partial positive definite matrix that has a positive semidefinite completion, constraint nondegeneracy is satisfied at each of its positive semidefinite matrix completions.     

On strong Z-matrices

A strong Z-matrix is a Z-matrix with negative off-diagonal entries and nonnegative diagonal entries. In this article, for a nonsingular strong Z-matrix, we indicate a way to ascertain whether such a matrix has the Lipschitzian property or not.     

Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.     

Cone complementarity problems with finite solution sets

We introduce the notion of a complementary cone and a nondegenerate linear transformation and characterize the finiteness of the solution set of a linear complementarity problem over a closed convex cone in a finite dimensional real inner product space. In addition to the above, other geometrical properties of complementary cones have been explored.