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.     

Growth Behavior of Two Classes of Merit Functions for Symmetric Cone Complementarity Problems

In the solution methods of the symmetric cone complementarity problem (SCCP), the squared norm of a complementarity function serves naturally as a merit function for the problem itself or the equivalent system of equations reformulation. In this paper, we study the growth behavior of two classes of such merit functions, which are induced by the smooth EP complementarity functions and the smooth implicit Lagrangian complementarity function, respectively. We show that, for the linear symmetric cone complementarity problem (SCLCP), both the EP merit functions and the implicit Lagrangian merit function are coercive if the underlying linear transformation has the P-property; for the general SCCP, the EP merit functions are coercive only if the underlying mapping has the uniform Jordan P-property, whereas the coerciveness of the implicit Lagrangian merit function requires an additional condition for the mapping, for example, the Lipschitz continuity or the assumption as in (45). The authors would like to thank the two anonymous referees for their helpful comments which improved the presentation of this paper greatly. The research of J.-S. Chen was partially supported by National Science Council of Taiwan.     

Merit functions for semi-definite complemetarity problems

Merit functions such as the gap function, the regularized gap function, the implicit Lagrangian, and the norm squared of the Fischer-Burmeister function have played an important role in the solution of complementarity problems defined over the cone of nonnegative real vectors. We study the extension of these merit functions to complementarity problems defined over the cone of block-diagonal symmetric positive semi-definite real matrices. The extension suggests new solution methods for the latter problems. This research is supported by National Science Foundation Grant CCR-9311621.     

Finding solutions of implicit complementarity problems by isotonicity of the metric projection

Isac and Németh [G. Isac and A. B. Németh, Projection method, isotone projection cones and the complementarity problem, J. Math. Anal. App., 153, 258-275(1990)] 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 paper, the notion of *-isotone projection cones is employed and an iterative algorithm is presented in connection with an implicit complementarity problem on *-isotone projection cones. 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. The question of finding nonzero solutions of these problems is also studied.     

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.     

A Linearly Convergent Derivative-Free Descent Method for Strongly Monotone Complementarity Problems

We establish the first rate of convergence result for the class of derivative-free descent methods for solving complementarity problems. The algorithm considered here is based on the implicit Lagrangian reformulation [26, 35] of the nonlinear complementarity problem, and makes use of the descent direction proposed in [42], but employs a different Armijo-type linesearch rule. We show that in the strongly monotone case, the iterates generated by the method converge globally at a linear rate to the solution of the problem.     

Stationary Points of Bound Constrained Minimization Reformulations of Complementarity Problems

We consider two merit functions which can be used for solving the nonlinear complementarity problem via nonnegatively constrained minimization. One of the functions is the restricted implicit Lagrangian (Refs. 1–3), and the other appears to be new. We study the conditions under which a stationary point of the minimization problem is guaranteed to be a solution of the underlying complementarity problem. It appears that, for both formulations, the same regularity condition is needed. This condition is closely related to the one used in Ref. 4 for unrestricted implicit Lagrangian. Some new sufficient conditions are also given.     

Existence of solutions for generalized implicit vector variational-like inequalities

In this paper, we introduce a new class of generalized implicit vector variational-like inequalities in Hausdorff topological vector spaces and Banach spaces which contain implicit vector equilibrium problems, implicit vector variational inequalities and implicit vector complementarity problems as special cases. We derive some new results by using the KKM–Fan theorem, under compact and noncompact assumptions on underlying convex sets.     

On implicit vector equilibrium problems

In this paper, we introduce and study a class of implicit vector equilibrium problems, which includes a number of (scalar) implicit equilibrium problems, implicit variational inequalities, and implicit complementarity problems as special cases. By using KKM-Fan theorem, we prove some new existence theorems of solutions for this kind of implicit vector equilibrium problems in Hausdorff topological vector spaces. Our results extend and unify some corresponding results of several authors.     

一类隐式集值向量均衡问题解的存在性和解集的稳定性

研究一类隐式集值向量均衡问题,它是隐式向量均衡问题、隐式变分不等式问题、隐式相补问题、向量均衡问题和向量变分不等式问题等的推广.利用截口定理,在Hausdorff拓扑线性空间的非紧子集上得出了一些隐式集值向量均衡问题解的存在性结果.并且还讨论了该隐式集值向量均衡问题解集的通有稳定性.这些结果推广和统一了近期的一些相关结果.     

基于支持向量机的多类分类问题的一种新算法

在K-SVCR算法结构的基础上构造了新的模型.模型的特点是它的一阶最优化条件可以转化为一个线性互补问题,通过Lagrangian隐含数,可以将其进一步转化成一个强凸的无约束优化问题.利用共轭梯度技术对其进行求解,在有限步内得到分类超平面.最后在标准数据集进行了初步试验.试验结果显示了提出的算法在分类的精度和速度上都有明显提高.     

Solvability of Implicit Complementarity Problems

In this paper, a new notion of exceptional family of elements (EFE) for a pair of functions involved in the implicit complementarity problem (ICP) is introduced. Based upon this notion and the Leray–Schauder Alternative, a general alternative is obtained which gives more general existence theorems for the implicit complementarity problem. Finally, via the techniques of continuous selections, these existence theorems are extended to the multi-valued implicit complementarity problems (MIPS).     

Smooth methods of multipliers for complementarity problems

This paper describes several methods for solving nonlinear complementarity problems. A general duality framework for pairs of monotone operators is developed and then applied to the monotone complementarity problem, obtaining primal, dual, and primal-dual formulations. We derive Bregman-function-based generalized proximal algorithms for each of these formulations, generating three classes of complementarity algorithms. The primal class is well-known. The dual class is new and constitutes a general collection of methods of multipliers, or augmented Lagrangian methods, for complementarity problems. In a special case, it corresponds to a class of variational inequality algorithms proposed by Gabay. By appropriate choice of Bregman function, the augmented Lagrangian subproblem in these methods can be made continuously differentiable. The primal-dual class of methods is entirely new and combines the best theoretical features of the primal and dual methods. Some preliminary computation shows that this class of algorithms is effective at solving many of the standard complementarity test problems. Received February 21, 1997 / Revised version received December 11, 1998? Published online May 12, 1999     

Solution behavior for parametric implicit complementarity problems

In this paper we study the solution behavior for a special class of quasi-variational inequalities, namely implicit complementarity problems. We derive conditions under which the perturbed solution of a parametric implicit complementarity problem is locally unique, continuous and Fréchet differentiable.     

隐式形式多值向量均衡问题解的存在性

考虑一类隐式形式多值向量均衡问题的解的存在性,该类问题包含了多值均衡问题、隐式向量均衡问题、多值变分不等式问题、向量变分不等式问题以及向量互补问题作为其特殊情形.利用广义Fan-Browder不动点定理,得到了拓扑向量空间中该类问题解的存要性定理,该结果推广并统一了已有问题解的存在性结果.     

Enumeration Approach for Linear Complementarity Problems Based on a Reformulation-Linearization Technique

In this paper, we consider the linear complementarity problem (LCP) and present a global optimization algorithm based on an application of the reformulation-linearization technique (RLT). The matrix M associated with the LCP is not assumed to possess any special structure. In this approach, the LCP is formulated first as a mixed-integer 0–1 bilinear programming problem. The RLT scheme is then used to derive a new equivalent mixed-integer linear programming formulation of the LCP. An implicit enumeration scheme is developed that uses Lagrangian relaxation, strongest surrogate and strengthened cutting planes, and a heuristic, designed to exploit the strength of the resulting linearization. Computational experience on various test problems is presented.     

Partial Augmented Lagrangian Method and Mathematical Programs with Complementarity Constraints

In this paper, we apply a partial augmented Lagrangian method to mathematical programs with complementarity constraints (MPCC). Specifically, only the complementarity constraints are incorporated into the objective function of the augmented Lagrangian problem while the other constraints of the original MPCC are retained as constraints in the augmented Lagrangian problem. We show that the limit point of a sequence of points that satisfy second-order necessary conditions of the partial augmented Lagrangian problems is a strongly stationary point (hence a B-stationary point) of the original MPCC if the limit point is feasible to MPCC, the linear independence constraint qualification for MPCC and the upper level strict complementarity condition hold at the limit point. Furthermore, this limit point also satisfies a second-order necessary optimality condition of MPCC. Numerical experiments are done to test the computational performances of several methods for MPCC proposed in the literature. This research was partially supported by the Research Grants Council (BQ654) of Hong Kong and the Postdoctoral Fellowship of The Hong Kong Polytechnic University. Dedicated to Alex Rubinov on the occassion of his 65th birthday.     

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).     

隐互补问题的极小化变形及其稳定点

1 引言 互补问题在最优化中有着广泛的应用,例如线性规划中的对偶问题,非线性规划中求稳定点的KKT条件以及变分不等式的求解都可以转化为互补问题,另外,某些均衡网络设计问题、信号最优化问题以及交通配置等问题也可利用互补问题来求解.     

Generalized vector implicit quasi complementarity problems

In this paper, we introduce and study a generalized class of vector implicit quasi complementarity problem and the corresponding vector implicit quasi variational inequality problem. By using Fan-KKM theorem, we derive existence of solutions of generalized vector implicit quasi variational inequalities without any monotonicity assumption and establish the equivalence between those problems in Banach spaces.