Search

The P-property of the linear transformation in second-order cone linear complementarity problems (SOCLCP) plays an important role in checking the globally uniquely solvable (GUS) property due to the work of Gowda et al. However, it is not easy to verify the P-property of the linear transformation, in general. In this paper, we provide matrix characterizations for checking the P-property, which is a new approach different from those in the literature. This is a do-able manipulation, which helps verifications of the P-property and globally uniquely solvable (GUS) property in second-order cone linear complementarity problems. Moreover, using an equivalence relation to the second-order cone linear complementarity problem, we study some sufficient and necessary conditions for the unique solution of the absolute value equations associated with second-order cone (SOCAVE).

In this paper, we investigate a class of differential linear stochastic complementarity system consisting of an ordinary differential equation and a stochastic complementarity problem. The existence of solutions for such system is obtained under two cases of the coefficient matrix of the linear stochastic complementarity problem: P-matrix and positive semi-definite matrix. As for the first case, the sample average approximate method and time-stepping method are adopted to get the numerical solutions. Furthermore, a regularization approximation is introduced to the second case to ensure the uniqueness of solutions. The corresponding convergence analysis is conducted, and numerical examples are presented to illustrate the convergence results we derived. Finally, we provide numerical results which come from applications involving dynamic traffic flow problems to support our theorems.

In this paper, for solving horizontal linear complementarity problems, a two-step modulus-based matrix splitting iteration method is established. The convergence analysis of the proposed method is presented, including the case of accelerated overrelaxation splitting. Numerical examples are reported to show the efficiency of the proposed method.

In this paper, we present some novel observations for the semidefinite linear complementarity problems, abbreviated as SDLCPs. Based on these new results, we establish the modulus-based matrix splitting iteration methods, which are obtained by reformulating equivalently SDLCP as an implicit fixed-point matrix equation. The convergence of the proposed modulus-based matrix splitting iteration methods has been analyzed. Numerical experiments have shown that the modulus-based iteration methods are effective for solving SDLCPs.

In (2013) [18] , Garcia-Esnaola and Pena presented error bounds for the linear complementarity problems of Σ-SDD and Σ 1 -SSD matrices respectively. These bounds all involve a parameter on an open interval. It is shown in this paper that the infimum of these error bounds as a function of the parameter exists, and then is determined. Numerical examples are given to verify the theoretical results.

In this paper, we study the mathematical program with equilibrium constraints (MPEC) formulated as a mathematical program with a parametric generalized equation involving the regular normal cone. We derive a new necessary optimality condition which is sharper than the usual M-stationary condition and is applicable even when no constraint qualifications hold for the corresponding mathematical program with complementarity constraints (MPCC) reformulation.

Inthis paper, we study the global uniqueness and solvability of tensor complementarity problems for $\mathcal {H}_{+}$-tensors. We obtain a sufficient condition of the global uniqueness and solvability of tensor complementarity problems for $\mathcal {H}_{+}$-tensors. We present nonlinear dynamical system models for solving the tensor complementarity problem (TCP). We prove that the presented dynamical system models are stable in the sense of Lyapunov stability theory for considering three classes of structured tensors. The computer simulation results further substantiate that the considered dynamical system can be used to solve the TCP.

Linear complementarity problem (LCP) presents many nice properties when the associated matrix belongs to some special matrix classes, especially H-matrices. In this paper, we put forward a new subclass of H-matrices, called S-QN matrices, which is the proper generalization of the QN matrices. We have proved that for a given S-QN matrix A, there exists a diagonal scaling matrix W such that AW is a QN matrix. Then, we present two kinds of error bounds for LCP of S-QN matrices. The Error Bound I generalizes the error bound for LCP of QN matrices. The Error Bound II overcomes the limitation that the Error Bound I cannot be used. Numerical examples illustrate that the Error Bound I is better than other previous bounds for H-matrices in some cases. Moreover, in some special cases, the Error Bound II can improve considerably the Error Bound I.

Garcia-Esnaola and Pena (Numer. Algor. 67, 655–667, 2014) presented an error bound involving a parameter for linear complementarity problems of Nekrasov matrices. This bound is not effective in some cases because it tends to infinity when the involved parameter tends to zero. In this paper, the optimal value of this error bound is determined completely by using the monotonicity of functions of this parameter. Numerical examples are given to verify the corresponding results.

In this paper, we extend modulus-based matrix splitting iteration methods to horizontal linear complementarity problems. We consider both standard and accelerated methods and analyze their convergence. In this context, we also generalize existing results on modulus-based matrix splitting iteration methods for (non-horizontal) linear complementarity problems. Lastly, we analyze the proposed methods by numerical experiments involving both symmetric and non-symmetric matrices.

In this paper, a class of two-step modulus-based matrix splitting (TMMS) iteration methods are proposed to solve the implicit complementarity problems. It is proved that the TMMS iteration methods are convergent under certain conditions when the system matrix is either a positive definite matrix or an H+-matrix. Two numerical examples are given to illustrate the effectiveness of the new proposed iteration methods. Numerical results show that the new proposed TMMS iteration methods have better performance than the existing modulus-based relaxation iteration methods for solving the implicit complementarity problems.

In this paper, we present a preconditioned general two-step modulus-based iteration method to solve a class of linear complementarity problems. Its convergence theory is proved when the system matrix A is an H+-matrix by using classical and new results from the theory of splitting. Numerical experiments show that the proposed methods are superior to the existing methods in actual implementation.

In this paper, a modified modulus-based matrix splitting iteration method is established for solving a class of implicit complementarity problems. The global convergence conditions are given when the system matrix is a positive definite matrix or an H+-matrix, respectively. In addition, some numerical examples show that the proposed method is efficient.

In this paper, a class of modulus-based matrix splitting iteration methods for the quasi-complementarity problems is presented. The convergence analysis of the proposed methods is discussed. Numerical experiments show that the proposed methods are efficient.

In this paper, we generalize modulus-based matrix splitting methods to a class of horizontal nonlinear complementarity problems (HNCPs). First, we write the HNCP as an implicit fixed-point equation and we introduce the proposed solution procedures. We then prove the convergence of the methods under some assumptions. We also comment on how the proposed methods and convergence theorems generalize existing results on (standard) linear and nonlinear complementarity problems and on horizontal linear complementarity problems. Finally, numerical experiments are solved to demonstrate the efficiency of the procedures. In this context, the effects of the splitting, of the dimension of the matrices, and of the nonlinear term of the problem are analyzed.

In this paper we consider the class of mathematical programs with complementarity constraints (MPCC). Under an appropriate constraint qualification of Mangasarian–Fromovitz type we present a topological and an equivalent algebraic characterization of a strongly stable C-stationary point for MPCC. Strong stability refers to the local uniqueness, existence and continuous dependence of a solution for each sufficiently small perturbed problem where perturbations up to second order are allowed. This concept of strong stability was originally introduced by Kojima for standard nonlinear optimization; here, its generalization to MPCC demands a sophisticated technique which takes the disjunctive properties of the solution set of MPCC into account.

Tensor complementarity problem (TCP) has attracted many attentions in recent years. In this paper, we equivalently reformulate tensor complementarity problem as a fixed point equation. Based on the fixed point equation, projected fixed point iterative methods are proposed and corresponding convergence proofs on the fixed point iterative methods for the tensor complementarity problem associated with a power Lipschitz tensor are investigated. Furthermore, the monotone convergence analysis of the fixed point iteration method for the tensor complementarity problem involving an $${\mathcal {L}}$$ tensor is given. Numerical examples are tested to illustrate the given approach.

International audience; This article is dedicated to the analysis of quadratic optimal control of linear complementarity systems (LCS), which are a class of strongly nonlinear and nonsmooth dynamical systems. Necessary first-order conditions are derived, that take the form of an LCS with inequality constraints, hence are numerically tractable. Sufficiency is proved in a specific sense. Numerical examples illustrate the theoretical developments and demonstrate the efficiency of the complementarity approach.

The operator splitting method has shown to be an effective approach for solving the linear complementarity problem for pricing American options. It has been successfully applied to various Black–Scholes models, and it is implementation friendly because the differential equation and the complementarity conditions are decoupled and easily solved on its own part. However, despite its popularity, no stability and error analysis is available for these operator splitting methods. The challenge mainly arises from the special splitting associated with the slack function and the complementarity constraints. In this paper, we establish stability results for the operator splitting schemes based on the backward Euler and BDF2 methods, as well as an error estimate for the scheme based on the backward Euler method. We also provide numerical experiments to demonstrate the convergence behaviors of the two operator splitting methods.

In this paper, we analyze the solution of horizontal linear complementarity problems arising from finite-difference discretizations of differential problems. In particular, we do so in the framework of the modeling of cavitation in lubricated contacts. We analyze the solution of such complementarity problems by recently introduced generalizations of projected and modulus-based matrix splitting methods. In this context, we extend the convergence analysis of some modulus-based matrix splitting methods to the problems of our concern. Finally, we analyze numerically the considered solution techniques by solving several test problems arising in hydrodynamic lubrication.

This work concerns the spectral analysis of connected graphs from a non-traditional point of view. Instead of the usual eigenvalues of the adjacency matrix A G of a graph G under consideration, we compute and analyze the complementarity eigenvalues of A G . The complementarity eigenvalues of a general square matrix are defined in terms of a certain complementarity system relative to the componentwise ordering. The complementarity eigenvalues of A G form the so-called complementarity spectrum of G. In general, the structure of a connected graph is better discriminated in terms of its complementarity spectrum than in terms of its usual spectrum. This observation is one of the leading motivation behind our work.

We introduce strong B-matrices and strong B-Nekrasov matrices, for which some error bounds for linear complementarity problems are analyzed. In particular, it is proved that the bounds of Garcia-Esnaola and Pena (Appl. Math. Lett. 22, 1071–1075, 2009) and of (Numer. Algor. 72, 435–445, 2016) are asymptotically optimal for strong B-matrices and strong B-Nekrasov matrices, respectively. Other comparisons with a bound of Li and Li (Appl. Math. Lett. 57, 108–113, 2016) are performed.

This paper is devoted to dealing with a flaw that existed in a recent paper (Xu et al. 2014). We give a new proof, which is a correction of the original Method 2.1 and proof in Xu et al. (2014).

This paper studies the difference-of-convex (DC) penalty formulations and the associated difference-of-convex algorithm (DCA) for computing stationary solutions of linear programs with complementarity constraints (LPCCs). We focus on three such formulations and establish connections between their stationary solutions and those of the LPCC. Improvements of the DCA are proposed to remedy some drawbacks in a straightforward adaptation of the DCA to these formulations. Extensive numerical results, including comparisons with an existing nonlinear programming solver and the mixed-integer formulation, are presented to elucidate the effectiveness of the overall DC approach.

We present a new covering theorem for a nonlinear mapping on a convex cone, under the assumptions weaker than the classical Robinson’s regularity condition. When the latter is violated, one cannot expect to cover the entire neighborhood of zero in the image space. Nevertheless, our covering theorem gives rise to natural conditions guaranteeing stability of a solution of a cone-constrained equation subject to wide classes of perturbations, and allowing for nonisolated solutions, and for systems with the same number of equations and variables. These features make these results applicable to various classes of variational problems, like nonlinear complementarity problems. We also consider the related stability issues for generalized Nash equilibrium problems.

A large number of free boundary problems can be formulated as linear-complementarity problems. In this paper, we propose an inexact alternating direction method of multipliers for solving linear complementarity problem arising from free boundary problems by using the special structure of these problems. The convergence of our proposed method is proved. Numerical results show that the proposed method is feasible and effective, and it is significantly faster than modified alternating direction implicit algorithm and many other methods, especially when dimension of the problem being solved is large.

This paper deals with the complementarity system over the second-order cone (denoted by CSSOC) which contains a wide class of problems. We extend a class of regularized Chen–Harker–Kanzow–Smale smoothing functions studied by Huang and Sun (Appl Math Optim 52:237–262, 2005) for the linear complementarity problem to the CSSOC. Based on this class of functions, we propose a smoothing algorithm for solving the CSSOC. Under weak assumptions, we prove that the proposed algorithm has global and local quadratic convergence. The proposed algorithm is different from existing smoothing algorithms for solving the CSSOC because it adopts a new nonmonotone line search rule. In addition, our algorithm solves a new equation reformulation of the CSSOC. Numerical experiments indicate that the proposed algorithm is quite effective.

This paper studies tensor eigenvalue complementarity problems. Basic properties of standard and complementarity tensor eigenvalues are discussed. We formulate tensor eigenvalue complementarity problems as constrained polynomial optimization. When one tensor is strictly copositive, the complementarity eigenvalues can be computed by solving polynomial optimization with normalization by strict copositivity. When no tensor is strictly copositive, we formulate the tensor eigenvalue complementarity problem equivalently as polynomial optimization by a randomization process. The complementarity eigenvalues can be computed sequentially. The formulated polynomial optimization can be solved by Lasserre's hierarchy of semidefinite relaxations. We show that it has finite convergence for general tensors. Numerical experiments are presented to show the efficiency of proposed methods., Comment: 26 pages

A nonsmooth Levenberg-Marquard (LM) method with double parameter adjusting strategies is presented for solving vertical complementarity problems based on the computation of an element of a vextor-valued minimum function’s B-differential in this paper. At each iteration, the LM parameter is adjusted based on the norm of the vector-valued minimum function and the ratio between the actual reduction and the predicted reduction. Under the local error bound condition, which is strictly weaker than nonsingular assumption, the local convergence rate is discussed. Finally, the numerical tests indicate that the present algorithm is effective.

In this paper a special semi-smooth equation associated to the second order cone is studied. It is shown that, under mild assumptions, the semi-smooth Newton method applied to this equation is well-defined and the generated sequence is globally and Q-linearly convergent to a solution. As an application, the obtained results are used to study the linear second order cone complementarity problem, with special emphasis on the particular case of positive definite matrices. Moreover, some computational experiments designed to investigate the practical viability of the method are presented.

For a matrix A whose off-diagonal entries are nonpositive, its nonnegative invertibility (namely, that A is an invertible M -matrix) is equivalent to A being a P -matrix, which is necessary and sufficient for the unique solvability of the linear complementarity problem defined by A . This, in turn, is equivalent to the statement that A is strictly semimonotone. In this paper, an analogue of this result is proved for singular symmetric Z -matrices. This is achieved by replacing the inverse of A by the group generalized inverse and by introducing the matrix classes of strictly range semimonotonicity and range column sufficiency. A recently proposed idea of P # -matrices plays a pivotal role. Some interconnections between these matrix classes are also obtained.