Implicit complementarity problems on isotone projection cones

Isac and Németh [G. Isac and A. B. Németh, Projection methods, isotone projection cones and the complementarity problem, J. Math. Anal. Appl. 153 (1990), pp. 258–275] proved that solving a coincidence point equation (fixed point problem) in turn solves the corresponding implicit complementarity problem (nonlinear complementarity problem) and they exploited the isotonicity of the metric projection onto isotone projection cones to solve implicit complementarity problems (nonlinear complementarity problems) defined by these cones. In this article an iterative algorithm is studied in connection with an implicit complementarity problem. It is proved that if the sequence generated through the defined algorithm is convergent, then its limit is a solution of the coincidence point equation and thus solves the implicit complementarity problem. Sufficient conditions are given for this sequence to be convergent for implicit complementarity problems defined by isotone projection cones, extending the results of Németh [S.Z. Németh, Iterative methods for nonlinear complementarity problems on isotone projection cones, J. Math. Anal. Appl. 350 (2009), pp. 340–370]. Some existing concepts from the latter paper are extended to solve the problem of finding nonzero solutions of the implicit complementarity problem.     

Solving nonlinear complementarity problems by isotonicity of the metric projection

The main motivation for introducing the notion of isotone projection cones was to solve nonlinear complementarity problems. The notion of *-isotone projection cones is introduced by this paper in a similar fashion. Iterative methods for finding solutions of complementarity problems on *-isotone projection cones are presented. The problem of finding nonzero solutions of these problems is also considered.     

How to project onto an isotone projection cone

The solution of the complementarity problem defined by a mapping f:Rⁿ→Rⁿ and a cone K⊂Rⁿ consists of finding the fixed points of the operator P_K°(I-f), where P_K is the projection onto the cone K and I stands for the identity mapping. For the class of isotone projection cones (cones admitting projections isotone with respect to the order relation they generate) and f satisfying certain monotonicity properties, the solution can be obtained by iterative processes (see G. Isac, A.B. Németh, Projection methods, isotone projection cones, and the complementarity problem, J. Math. Anal. Appl. 153(1) (1990) 258-275 and S.Z. Németh, Iterative methods for nonlinear complementarity problems on isotone projection cones, J. Math. Anal. Appl. 350(1) (2009) 340-347). These algorithms require computing at each step the projection onto the cone K. In general, computing the projection mapping onto a cone K is a difficult and computationally expensive problem. In this note it is shown that the projection of an arbitrary point onto an isotone projection cone in Rⁿ can be obtained by projecting recursively at most n-1 times into subspaces of decreasing dimension. This emphasizes the efficiency of the algorithms mentioned above and furnishes a handy tool for some problems involving special isotone projection cones, as for example the non-negative monotone cones occurring in reconstruction problems (see e.g. Section 5.13 in J. Dattorro, Convex Optimization and Euclidean Distance Geometry, Meboo, 2005, v2009.04.11).     

Isotone retraction cones in Hilbert spaces

A mapping is called isotone if it is monotone increasing with respect to the order induced by a pointed closed convex cone. Finding the pointed closed convex generating cones for which the projection mapping onto the cone is isotone is a difficult problem which was analyzed in Isac and Németh (1986, 1990, 1992) [1], [2], [3], [4] and [5]. Such cones are called isotone projection cones. In particular it was shown that any isotone projection cone is latticial (Isac (1990) [2]). This problem is extended by replacing the projection mapping with continuous retractions onto the cone. By introducing the notion of sharp mappings, it is shown that a pointed closed convex generating cone is latticial if and only if there is a continuous retraction onto the cone whose complement is sharp. Several particular cases are considered and examples are given.     

Characterization of subdual latticial cones in Hilbert spaces by the isotonicity of the metric projection

The subdual latticial cones in Hilbert spaces are characterized by the isotonicity of a generalization of the positive part mapping which can be expressed in terms of the metric projection only. Although Németh characterized the positive cone of Hilbert lattices with the metric projection and ordering only [A.B. Németh, Characterization of a Hilbert vector lattice by the metric projection onto its positive cone, J. Approx. Theory 123 (2) (2003), pp. 295–299.], this has been done for the first time for subdual latticial cones in this article. We also note that the normal generating pointed closed convex cones for which the projection onto the cone is isotone are subdual latticial cones, but there are subdual latticial cones for which the metric projection onto the cone is not isotone [G. Isac, A.B. Németh, Monotonicity of metric projections onto positive cones of ordered Euclidean spaces, Arch. Math. 46 (6) (1986), pp. 568–576; G. Isac, A.B. Néemeth, Every generating isotone projection cone is latticial and correct, J. Math. Anal. Appl. 147 (1) (1990), pp. 53–62; G. Isac, A.B. Németh, Isotone projection cones in Hilbert spaces and the complementarity problem, Boll. Un. Mat. Ital. B 7 (4) (1990), pp. 773–802; G. Isac, A.B. Németh, Projection methods, isotone projection cones, and the complementarity problem, J. Math. Anal. Appl. 153 (1) (1990), pp. 258–275; G. Isac, A.B. Németh, Isotone projection cones in Eucliden spaces, Ann. Sci. Math Québec 16 (1) (1992), pp. 35–52].     

Iterative methods for nonlinear complementarity problems on isotone projection cones

In this paper we present a recursion related to a nonlinear complementarity problem defined by a closed convex cone in a Hilbert space and a continuous mapping defined on the cone. If the recursion is convergent, then its limit is a solution of the nonlinear complementarity problem. In the case of isotone projection cones sufficient conditions are given for the mapping so that the recursion to be convergent.     

Inequalities Characterizing Coisotone Cones in Euclidean Spaces

The isotone projection cone, defined by G. Isac and A. B. Németh, is a closed pointed convex cone such that the order relation defined by the cone is preserved by the projection operator onto the cone. In this paper the coisotone cone will be defined as the polar of a generating isotone projection cone. Several equivalent inequality conditions for the coisotonicity of a cone in Euclidean spaces will be given. Thanks are due to A. B. Németh who draw the author’s attention on the relation of latticial cones generated by vectors with pairwise non-accute angles with the theory of isotone cones.     

Characterization of latticial cones in Hilbert spaces by isotonicity and generalized infimum

A mapping is called isotone if it is monotone increasing with respect to the order defined by a pointed closed convex cone. Finding the pointed closed convex generating cones for which the projection mapping onto the cone is isotone is a difficult problem which was analyzed in [1, 2, 3, 4, 5]. Such cones are called isotone projection cones. In particular it was shown that any isotone projection cone is latticial [2]. This problem is extended by replacing the projection mapping with a continuous isotone retraction onto the cone. By introducing the notion of sharp mappings, it is shown that a pointed closed convex generating cone is latticial if and only if there is a continuous isotone retraction onto the cone whose complement is sharp. This result is used for characterizing a subdual latticial cone by the isotonicity of a generalization of the positive part mapping x ↦ x ⁺. This generalization is achieved by generalizing the infimum for subdual cones. The theoretical results of this paper exhibit fundamental properties of the lattice structure of the space which were not analysed before.     

A projection-filter method for solving nonlinear complementarity problems

The Josephy-Newton method attacks nonlinear complementarity problems which consists of solving, possibly inexactly, a sequence of linear complementarity problems. Under appropriate regularity assumptions, this method is known to be locally (superlinearly) convergent. Utilizing the filter method, we presented a new globalization strategy for this Newton method applied to nonlinear complementarity problem without any merit function. The strategy is based on the projection-proximal point and filter methodology. Our linesearch procedure uses the regularized Newton direction to force global convergence by means of a projection step which reduces the distance to the solution of the problem. The resulting algorithm is globally convergent to a solution. Under natural assumptions, locally superlinear rate of convergence was established.     

Isotonicity of the Metric Projection and Complementarity Problems in Hilbert Spaces

In this paper, as the extension of the isotonicity of the metric projection, the isotonicity characterizations with respect to two arbitrary order relations induced by cones of the metric projection operator are studied in Hilbert spaces, when one cone is a subdual cone and some relations between the two orders hold. Moreover, if the metric projection is not isotone in the whole space, we prove that the metric projection is isotone in some domains in both Hilbert lattices and Hilbert quasi-lattices. By using the isotonicity characterizations with respect to two arbitrary order relations of the metric projection, some solvability and approximation theorems for the complementarity problems are obtained. Our results generalize and improve various recent results in the field of study.     

Isotonicity of the Metric Projection by Lorentz Cone and Variational Inequalities

In this paper, we first discuss the geometric properties of the Lorentz cone and the extended Lorentz cone. The self-duality and orthogonality of the Lorentz cone are obtained in Hilbert spaces. These properties are fundamental for the isotonicity of the metric projection with respect to the order, induced by the Lorentz cone. According to the Lorentz cone, the quasi-sublattice and the extended Lorentz cone are defined. We also obtain the representation of the metric projection onto cones in Hilbert quasi-lattices. As an application, solutions of the classic variational inequality problem and the complementarity problem are found by the Picard iteration corresponding to the composition of the isotone metric projection onto the defining closed and convex set and the difference in the identity mapping and the defining mapping. Our results generalize and improve various recent results obtained by many others.     

Extended Lorentz cones and mixed complementarity problems

In this paper we extend the notion of a Lorentz cone in a Euclidean space as follows: we divide the index set corresponding to the coordinates of points in two disjoint classes. By definition a point belongs to an extended Lorentz cone associated with this division, if the coordinates corresponding to one class are at least as large as the norm of the vector formed by the coordinates corresponding to the other class. We call a closed convex set isotone projection set with respect to a pointed closed convex cone if the projection onto the set is isotone (i.e., order preserving) with respect to the partial order defined by the cone. We determine the isotone projection sets with respect to an extended Lorentz cone. In particular, a Cartesian product between an Euclidean space and any closed convex set in another Euclidean space is such a set. We use this property to find solutions of general mixed complementarity problems recursively.     

Characterization of the Cone and Applications in Banach Spaces

Abstract

In this article, we first discuss the subduality and orthogonality of the cones and the dual cones when the norm is monotone in Banach spaces. Then, under different assumptions, the necessary and sufficient conditions for the ordering increasing property of the metric projection onto cones and order intervals are studied. Moreover, representations of the metric projection onto cones and order intervals are obtained. As applications, the solvability and approximation results of solutions to nonlinear discontinuous variational inequality and complementarity problems are proved by partial ordering methods.     

一种新的向量互补问题

本文在实局部凸空间中引入了一种新的向量互补问题,这一向量互补问题不仅包含了由Ｙｕ和Ｙａｏ提出的广义向量互补问题由Ｃｈｅｎ和Ｙａｎｇ定义的弱向量互补问题,而且还包含了Ｉｓａｃ意义下的隐互补问题。本文还讨论了新的向量互补问题,向量变分不等式,向量单向极小化问题和最小元问题之间的关系,给出了这一向量互补问题解的存在定理。     

An extension of Tarski's fixed point theorem and its application to isotone complementarity problems

Tarski's fixed point theorem is extended to the case of set-valued mappings, and is applied to a class of complementarity problems defined by isotone set-valued operators in a complete vector lattice.     

Regular exceptional family of elements with respect to isotone projection cones in Hilbert spaces and complementarity problems

Conditions for the non-existence of a regular exceptional family of elements with respect to an isotone projection cone in a Hilbert space will be presented. The obtained results will be used for generating existence theorems for a complementarity problem with respect to an isotone projection cone in a Hilbert space.     

On Unconstrained and Constrained Stationary Points of the Implicit Lagrangian

Mangasarian and Solodov (Ref. 1) proposed to solve nonlinear complementarity problems by seeking the unconstrained global minima of a new merit function, which they called implicit Lagrangian. A crucial point in such an approach is to determine conditions which guarantee that every unconstrained stationary point of the implicit Lagrangian is a global solution, since standard unconstrained minimization techniques are only able to locate stationary points. Some authors partially answered this question by giving sufficient conditions which guarantee this key property. In this paper, we settle the issue by giving a necessary and sufficient condition for a stationary point of the implicit Lagrangian to be a global solution and, hence, a solution of the nonlinear complementarity problem. We show that this new condition easily allows us to recover all previous results and to establish new sufficient conditions. We then consider a constrained reformulation based on the implicit Lagrangian in which nonnegative constraints on the variables are added to the original unconstrained reformulation. This is motivated by the fact that often, in applications, the function which defines the complementarity problem is defined only on the nonnegative orthant. We consider the KKT-points of this new reformulation and show that the same necessary and sufficient condition which guarantees, in the unconstrained case, that every unconstrained stationary point is a global solution, also guarantees that every KKT-point of the new problem is a global solution.     

The convergence of a modified smoothing-type algorithm for the symmetric cone complementarity problem

The symmetric cone complementarity problem (denoted by SCCP) is a broad class of optimization problems, which contains the semidefinite complementarity problem, the second-order cone complementarity problem, and the nonlinear complementarity problem. In this paper we first extend the smoothing function proposed by Huang et al. (Sci. China 44:1107–1114, 2001) for the nonlinear complementarity problem to the context of symmetric cones and show that it is coercive under suitable assumptions. Based on this smoothing function, a smoothing-type algorithm, which is a modified version of the Qi-Sun-Zhou method (Qi et al. in Math. Program. 87:1–35, 2000), is proposed for solving the SCCP. By using the theory of Euclidean Jordan algebras, we prove that the proposed algorithm is globally and locally quadratically convergent under suitable assumptions. Preliminary numerical results for some second-order cone complementarity problems are reported which indicate that the proposed algorithm is effective.     

求解一类隐线性互补问题的投影MAOR算法

用MAOR迭代算法求解一类L-矩阵的隐线性互补问题.证明了由此算法产生的迭代序列的聚点是隐线性互补问题的解.并且当问题中的矩阵是M-矩阵时,算法产生的迭代序列单调收敛于隐互补问题的解.     

Kneser''s theorem and the multivalued generalized order complementarity problem

The Generalized Order Complementarity Problem studied by Isac and Kostreva is extended to multivalued mappings satisfying a condition proposed by Kneser. Existence of solutions to a related fixed point problem leads to existence theory for the new type of complementarity problem. Some important applications include problems in lubrication and in economics in which functions are set valued.