On the resolution of monotone complementarity problems

A reformulation of the nonlinear complementarity problem (NCP) as an unconstrained minimization problem is considered. It is shown that any stationary point of the unconstrained objective function is a solution of NCP if the mapping F involved in NCP is continuously differentiable and monotone, and that the level sets are bounded if F is continuous and strongly monotone. A descent algorithm is described which uses only function values of F. Some numerical results are given.     

Error bounds for monotone linear complementarity problems

We give a bound on the distance between an arbitrary point and the solution set of a monotone linear complementarity problem in terms of a condition constant that depends on the problem data only and a residual function of the violations of the complementary problem conditions by the point considered. When the point satisfies the linear inequalities of the complementarity problem, the residual consists of the complementarity condition plus its square root. This latter term is essential and without it the error bound cannot hold. We also show that another natural residual that has been employed to bound errors for strictly monotone linear complementarity problems fails to bound errors for the monotone case considered here. Sponsored by the United States Army under contract No. DAAG29-80-C-0041. This material is based on research sponsored by National Foundation Grant DCR-8420963 and Air Force Office of Scientific Research Grant AFOSR-ISSA-85-00080.     

Robust solution of monotone stochastic linear complementarity problems

We consider the stochastic linear complementarity problem (SLCP) involving a random matrix whose expectation matrix is positive semi-definite. We show that the expected residual minimization (ERM) formulation of this problem has a nonempty and bounded solution set if the expected value (EV) formulation, which reduces to the LCP with the positive semi-definite expectation matrix, has a nonempty and bounded solution set. We give a new error bound for the monotone LCP and use it to show that solutions of the ERM formulation are robust in the sense that they may have a minimum sensitivity with respect to random parameter variations in SLCP. Numerical examples including a stochastic traffic equilibrium problem are given to illustrate the characteristics of the solutions.     

Error bounds for nondegenerate monotone linear complementarity problems

Error bounds and upper Lipschitz continuity results are given for monotone linear complementarity problems with a nondegenerate solution. The existence of a nondegenerate solution considerably simplifies the error bounds compared with problems for which all solutions are degenerate. Thus when a point satisfies the linear inequalities of a nondegenerate complementarity problem, the residual that bounds the distance from a solution point consists of the complementarity condition alone, whereas for degenerate problems this residual cannot bound the distance to a solution without adding the square root of the complementarity condition to it. This and other simplified results are a consequence of the polyhedral characterization of the solution set as the intersection of the feasible region {zMz + q 0, z 0} with a single linear affine inequality constraint.This material is based on research supported by National Science Foundation Grants CCR-8723091 and DCR-8521228 and Air Force Office of Scientific Research Grant AFOSR-86-0172.     

A descent algorithm for solving monotone variational inequalities and monotone complementarity problems

The paper provides a descent algorithm for solving certain monotone variational inequalities and shows how this algorithm may be used for solving certain monotone complementarity problems. Convergence is proved under natural monotonicity and smoothness conditions; neither symmetry nor strict monotonicity is required.The author is grateful to two anonymous referees for their very valuable comments on an earlier draft of this paper.     

Solution of monotone complementarity problems with locally Lipschitzian functions

The paper deals with complementarity problems CP(F), where the underlying functionF is assumed to be locally Lipschitzian. Based on a special equivalent reformulation of CP(F) as a system of equationsφ(x)=0 or as the problem of minimizing the merit functionΘ=1/2∥Φ∥ ₂ ² , we extend results which hold for sufficiently smooth functionsF to the nonsmooth case. In particular, ifF is monotone in a neighbourhood ofx, it is proved that 0 εδθ(x) is necessary and sufficient forx to be a solution of CP(F). Moreover, for monotone functionsF, a simple derivative-free algorithm that reducesΘ is shown to possess global convergence properties. Finally, the local behaviour of a generalized Newton method is analyzed. To this end, the result by Mifflin that the composition of semismooth functions is again semismooth is extended top-order semismooth functions. Under a suitable regularity condition and ifF isp-order semismooth the generalized Newton method is shown to be locally well defined and superlinearly convergent with the order of 1+p.     

Positive definite and Gram tensor complementarity problems

Given a continuous function Open image in new window and Open image in new window , the non-linear complementarity problem \(\text{ NCP }(g,q)\) is to find a vector Open image in new window such that

$$\begin{aligned} x \ge 0,~~y:=g(x) +q\ge 0~~\text{ and }~~x^Ty=0. \end{aligned}$$

We say that g has the Globally Uniquely Solvable (\(\text{ GUS }\))-property if \(\text{ NCP }(g,q)\) has a unique solution for all Open image in new window and C-property if \(\mathrm{NCP}(g,q)\) has a convex solution set for all Open image in new window . In this paper, we find a class of non-linear functions that have the \(\text{ GUS }\)-property and C-property. These functions are constructed by some special tensors which are positive semidefinite. We call these tensors as Gram tensors.

     

Column sufficient tensors and tensor complementarity problems

Stimulated by the study of sufficient matrices in linear complementarity problems, we study column sufficient tensors and tensor complementarity problems. Column sufficient tensors constitute a wide range of tensors that include positive semi-definite tensors as special cases. The inheritance property and invariant property of column sufficient tensors are presented. Then, various spectral properties of symmetric column sufficient tensors are given. It is proved that all H-eigenvalues of an even-order symmetric column sufficient tensor are nonnegative, and all its Z-eigenvalues are nonnegative even in the odd order case. After that, a new subclass of column sufficient tensors and the handicap of tensors are defined. We prove that a tensor belongs to the subclass if and only if its handicap is a finite number. Moreover, several optimization models that are equivalent with the handicap of tensors are presented. Finally, as an application of column sufficient tensors, several results on tensor complementarity problems are established.     

Inexact non-interior continuation method for monotone semidefinite complementarity problems

Chen and Tseng (Math Program 95:431?C474, 2003) extended non-interior continuation methods for solving linear and nonlinear complementarity problems to semidefinite complementarity problems (SDCP), in which a system of linear equations is exactly solved at each iteration. However, for problems of large size, solving the linear system of equations exactly can be very expensive. In this paper, we propose a version of one of the non-interior continuation methods for monotone SDCP presented by Chen and Tseng that incorporates inexactness into the linear system solves. Only one system of linear equations is inexactly solved at each iteration. The global convergence and local superlinear convergence properties of the method are given under mild conditions.     

Solvability conditions and monotone iterative scheme for boundary-value problems related to nonlinear monotone potential operators

This article deals with boundary-value problems (BVPs) for the second-order nonlinear differential equations with monotone potential operators of type Au := ??(k(|?u|²)?u(x)) + q(u ²)u(x), x ∈ Ω ? R ⁿ . An analysis of nonlinear problems shows that the potential of the operator A as well as the potential of related BVP plays an important role not only for solvability of these problems and linearization of the nonlinear operator, but also for the strong convergence of solutions of corresponding linearized problems. A monotone iterative scheme for the considered BVP is proposed.     

Simple bounds for solutions of monotone complementarity problems and convex programs

For a solvable monotone complementarity problem we show that each feasible point which is not a solution of the problem provides simple numerical bounds for some or all components of all solution vectors. Consequently for a solvable differentiable convex program each primal-dual feasible point which is not optimal provides simple bounds for some or all components of all primal-dual solution vectors. We also give an existence result and simple bounds for solutions of monotone compementarity problems satisfying a new, distributed constraint qualification. This result carries over to a simple existence and boundedness result for differentiable convex programs satisfying a similar constraint qualification.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041. This material is based on work sponsored by National Science Foundation Grants MCS-8200632 and MCS-8102684.     

A note on least two norm solutions of monotone complementarity problems

Growth rates for approximate solutions of monotone complementary problems are considered and an application to the linear case is given.     

The largest step path following algorithm for monotone linear complementarity problems

Path-following algorithms take at each iteration a Newton step for approaching a point on the central path, in such a way that all the iterates remain in a given neighborhood of that path. This paper studies the case in which each iteration uses a pure Newton step with the largest possible reduction in complementarity measure (duality gap). This algorithm is known to converge superlinearly in objective values. We show that with the addition of a computationally trivial safeguard it achieves Q-quadratic convergence, and show that this behaviour cannot be proved by usual techniques for the original method. Research done while visiting Delft University of Technology, and supported in part by CAPES-Brazil.     

Existence and proximal point algorithms for nonlinear monotone complementarity problems *

The purpose of the present paper is a statement of the nonlinear complementarity problem associated to monotone operators in Hilbert spaces. Existence results are proved, and proximal point algorithms are given     

Strictly semi-positive tensors and the boundedness of tensor complementarity problems

In this paper, we present the boundedness of solution set of tensor complementarity problem defined by a strictly semi-positive tensor. For strictly semi-positive tensor, we prove that all \(H^+(Z^+)\)-eigenvalues of each principal sub-tensor are positive. We define two new constants associated with \(H^+(Z^+)\)-eigenvalues of a strictly semi-positive tensor. With the help of these two constants, we establish upper bounds of an important quantity whose positivity is a necessary and sufficient condition for a general tensor to be a strictly semi-positive tensor. The monotonicity and boundedness of such a quantity are established too.     

On the analyticity properties of infeasible-interior-point paths for monotone linear complementarity problems

Infeasible-interior-point paths , a positive vector, for a horizontal linear complementarity problem are defined as the solution of () If the path converges for , then it converges to a solution of . This paper deals with the analyticity properties of and its derivatives with respect to r near r = 0 for solvable monotone complementarity problems . It is shown for with a strictly complementary solution that the path , , has an extension to which is analytic also at . If has no strictly complementary solution, then , , has an extension to that is analytic at . Received May 24, 1996 / Revised version received February 25, 1998     

随机R0张量互补问题的投影Levenberg-Marquardt方法

本文考虑一类离散型随机$R_0$张量互补问题,利用Fischer-Burmeister函数将问题转化为约束优化问题,并用投影Levenberg-Marquardt方法对其进行了求解。在一般的条件下得到了该方法的全局收敛性,相关的数值实验表明了该方法的有效性。