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.     

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

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

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

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.     

An interior point potential reduction method for constrained equations

We study the problem of solving a constrained system of nonlinear equations by a combination of the classical damped Newton method for (unconstrained) smooth equations and the recent interior point potential reduction methods for linear programs, linear and nonlinear complementarity problems. In general, constrained equations provide a unified formulation for many mathematical programming problems, including complementarity problems of various kinds and the Karush-Kuhn-Tucker systems of variational inequalities and nonlinear programs. Combining ideas from the damped Newton and interior point methods, we present an iterative algorithm for solving a constrained system of equations and investigate its convergence properties. Specialization of the algorithm and its convergence analysis to complementarity problems of various kinds and the Karush-Kuhn-Tucker systems of variational inequalities are discussed in detail. We also report the computational results of the implementation of the algorithm for solving several classes of convex programs. The work of this author was based on research supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and the Office of Naval Research under grant N00014-93-1-0228. The work of this author was based on research supported by the National Science Foundation under grant DMI-9496178 and the Office of Naval Research under grants N00014-93-1-0234 and N00014-94-1-0340.     

More results on the convergence of iterative methods for the symmetric linear complementarity problem

In an earlier paper, the author has given some necessary and sufficient conditions for the convergence of iterative methods for solving the linear complementarity problem. These conditions may be viewed as global in the sense that they apply to the methods regardless of the constant vector in the linear complementarity problem. More precisely, the conditions characterize a certain class of matrices for which the iterative methods will converge, in a certain sense, to a solution of the linear complementarity problem for all constant vectors. In this paper, we improve on our previous results and establish necessary and sufficient conditions for the convergence of iterative methods for solving each individual linear complementarity problem with a fixed constant vector. Unlike the earlier paper, our present analysis applies only to the symmetric linear complementarity problem. Various applications to a strictly convex quadratic program are also given.The author gratefully acknowledges several stimulating conversations with Professor O. Mangasarian on the subject of this paper. He is also grateful to a referee, who has suggested Lemma 2.2 and the present (stronger) version of Theorem 2.1 as well as several other constructive comments.This research was based on work supported by the National Science Foundation under Grant No. ECS-81-14571, sponsored by the United States Army under Contract No. DAAG29-80-C-0041, and was completed while the author was visiting the Mathematics Research Center at the University of Wisconsin, Madison, Wisconsin.     

一类广义隐互补问题的外梯度法

隐互补问题在自然科学中的诸多领域有着广泛的应用.本文研究了一类广义隐互补问题.本文将外梯度法应用到这类广义隐互补问题中,研究了在伪单调的条件下算法的收敛性,并证明了算法具有R-线性收敛性.     

QPCOMP: A quadratic programming based solver for mixed complementarity problems

QPCOMP is an extremely robust algorithm for solving mixed nonlinear complementarity problems that has fast local convergence behavior. Based in part on the NE/SQP method of Pang and Gabriel [14], this algorithm represents a significant advance in robustness at no cost in efficiency. In particular, the algorithm is shown to solve any solvable Lipschitz continuous, continuously differentiable, pseudo-monotone mixed nonlinear complementarity problem. QPCOMP also extends the NE/SQP method for the nonlinear complementarity problem to the more general mixed nonlinear complementarity problem. Computational results are provided, which demonstrate the effectiveness of the algorithm. This material is based on research supported by National Science Foundation Grant CCR-9157632, Department of Energy Grant DE-FG03-94ER61915, and the Air Force Office of Scientific Research Grant F49620-94-1-0036.     

On polynomiality of the Mehrotra-type predictor—corrector interior-point algorithms

Recently, Mehrotra [3] proposed a predictor—corrector primal—dual interior-point algorithm for linear programming. At each iteration, this algorithm utilizes a combination of three search directions: the predictor, the corrector and the centering directions, and requires only one matrix factorization. At present, Mehrotra's algorithmic framework is widely regarded as the most practically efficient one and has been implemented in the highly successful interior-point code OB1 [2]. In this paper, we study the theoretical convergence properties of Mehrotra's interior-point algorithmic framework. For generality, we carry out our analysis on a horizontal linear complementarity problem that includes linear and quadratic programming, as well as the standard linear complementarity problem. Under the monotonicity assumption, we establish polynomial complexity bounds for two variants of the Mehrotra-type predictor—corrector interior-point algorithms. These results are summarized in the last section in a table.Research supported in part by NSF DMS-9102761, DOE DE-FG05-91ER25100 and DOE DE-FG02-93ER25171.Corresponding author.     

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

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

Evolution of phase transitions in methane hydrate

We consider a simplified model of methane hydrates which we cast as a nonlinear evolution problem. For its well-posedness we extend the existing theory to cover the case in which the problem involves a measurable family of graphs. We represent the nonlinearity as a subgradient and prove a useful comparison principle, thus optimal regularity results follow. For the numerical solution we apply a fully implicit scheme without regularization and use the semismooth Newton algorithm for a solver, and the graph is realized as a complementarity constraint (CC). The algorithm is very robust and we extend it to define an easy and superlinearly convergent fully implicit scheme for the Stefan problem and other multivalued examples.     

Fixed-Point Technique for Implicit Complementarity Problem in Hilbert Lattice

In this paper, we consider and study the implicit complementarity problem in the setting of a Hilbert lattice. It has been shown that this problem can be formulated as a fixed-point problem by using a suitable change of variables. Moreover, this formulation allows us to prove the existence and uniqueness of solutions of the implicit complementarity problem.     

Two-stage parallel iterative methods for the symmetric linear complementarity problem

In this paper, we propose a two-stage parallel iterative method for solving the symmetric linear complementarity problem. When implemented in a parallel computing environment, the method decomposes the problem into subproblems which are solved by certain iterative procedures concurrently on separate processors. Convergence of the overall method is established under some mild assumptions on how the inner iterations are terminated. Applications of the proposed method to solve strictly convex quadratic programs are discused and numerical results on both a sequential computer (IBM 4381) and a super-computer (CRAYX-MP/24) are reported.This research was based on work supported by the National Science Foundation under grant ECS-8407240 and by a 1986 University Research and Development grant from Cray Research Inc.     

Multi-sweep asynchronous parallel successive overrelaxation for the nonsymmetric linear complementarity problem

Convergence is established for themulti-sweep asynchronous parallel successive overrelaxation (SOR) algorithm for thenonsymmetric linear complementarity problem. The algorithm was originally introduced in [4] for the symmetric linear complementarity problem. Computational tests show the superiority of the multi-sweep asynchronous SOR algorithm over its single-sweep counterpart on both symmetric and nonsymmetric linear complementarity problems.This material is based on research supported by National Science Foundation Grants CCR-8723091 and DCR-8521228, and Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-86-0124.     

对称双正型线性互补问题的多重网格迭代解收敛性理论

多重网格法是七十年代产生并获得迅速发展的快速送代法.八十年代初,此方法开始应用于变分不等式的求解,其中包括一类互补问题,近十年来大量的数值实验证实,算法是成功的,而算法的收敛性理论也正在逐步建立,当A正定对称时的多重网格收敛性可见[3]和[7];[4]讨论了A半正定时的情况·本文考虑A为更广的一类矩阵:对称双正阵(见定义1.1),建立互补问题:     

Iterative linear programming solution of convex programs

An iterative linear programming algorithm for the solution of the convex programming problem is proposed. The algorithm partially solves a sequence of linear programming subproblems whose solution is shown to converge quadratically, superlinearly, or linearly to the solution of the convex program, depending on the accuracy to which the subproblems are solved. The given algorithm is related to inexact Newton methods for the nonlinear complementarity problem. Preliminary results for an implementation of the algorithm are given.This material is based on research supported by the National Science Foundation, Grants DCR-8521228 and CCR-8723091, and by the Air Force Office of Scientific Research, Grant AFOSR-86-0172. The author would like to thank Professor O. L. Mangasarian for stimulating discussions during the preparation of this paper.     

对称线性互补问题的乘性Schwarz算法

本文提出了求解对称性互补问题的乘性Schwarz算法,其中子问题用投影迭代方法求解.利用投影迭代算子的性质及投影迭代的收敛性,证明了算法产生的迭代点列的聚点为原互补问题的解,并在一定条件下,证明算法产生的迭代点列的聚点存在.     

模糊(Fuzzy)映象的广义补余问题*

本文引入一类关于模糊(Fuzzy)映象的新的广义补余问题,构造出一类新的迭代算法.我们讨论这类广义补余问题解的存在性及迭代序列的收敛性.     

Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems

In this paper, we propose a Newton-type method for solving a semismooth reformulation of monotone complementarity problems. In this method, a direction-finding subproblem, which is a system of linear equations, is uniquely solvable at each iteration. Moreover, the obtained search direction always affords a direction of sufficient decrease for the merit function defined as the squared residual for the semismooth equation equivalent to the complementarity problem. We show that the algorithm is globally convergent under some mild assumptions. Next, by slightly modifying the direction-finding problem, we propose another Newton-type method, which may be considered a restricted version of the first algorithm. We show that this algorithm has a superlinear, or possibly quadratic, rate of convergence under suitable assumptions. Finally, some numerical results are presented. Supported by Research Fellowships of the Japan Society for the Promotion of Science for Young Scientists. Supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science and Culture, Japan.     

Implicit iterative algorithms of the split common fixed point problem for Bregman quasi-nonexpansive mapping in Banach spaces

In this paper, we study a modified implicit rule for finding a solution of split common fixed point problem of a Bregman quasi-nonexpansive mapping in Banach spaces. We propose a new iterative algorithm and prove the strong convergence theorem under appropriate conditions. As an application, the results are applied to solving the zero problem and the equilibrium problem.