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

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

Two Classes of Merit Functions for Infinite-Dimensional Second Order Complimentary Problems

In this article, we extend two classes of merit functions for the second-order complementarity problem (SOCP) to infinite-dimensional SOCP. These two classes of merit functions include several popular merit functions, which are used in nonlinear complementarity problem, (NCP)/(SDCP) semidefinite complementarity problem, and SOCP, as special cases. We give conditions under which the infinite-dimensional SOCP has a unique solution and show that all these merit functions provide an error bound for infinite-dimensional SOCP and have bounded level sets. These results are very useful for designing solution methods for infinite-dimensional SOCP.     

On the regularization of mixed complementarity problems

A variational inequality problem (VIP) satisfying a constraint qualification can be reduced to a mixed complementarity problem (MOP). Monotonicity of the VIP implies that the MOP is also monotone. Introducing regularizing perturbations, a sequence of strictly monotone mixed complementarity problems is generated. It is shown that, if the original problem is solvable, the sequence of computable inexact solutions of the strictly monotone MCP's is bounded and every accumulation point is a solution. Under an additional condition on the precision used for solving each subproblem, the sequence converges to the minimum norm solution of the MCP.     

On the convergence of a basic iterative method for the implicit complementarity problem

In Part 1 of this study (Ref. 1), we have defined the implicit complementarity problem and investigated its existence and uniqueness of solution. In the present paper, we establish a convergence theory for a certain iterative algorithm to solve the implicit complementarity problem. We also demonstrate how the algorithm includes as special cases many existing iterative methods for solving a linear complementarity problem.This research was prepared as part of the activities of the Management Sciences Research Group, Carnegie-Mellon University, under Contract No. N00014-75-C-0621-NR-047-048 with the Office of Naval Research.     

A multilevel iterative method for symmetric,positive definite linear complementarity problems

A fast iterative method for the solution of large, sparse, symmetric, positive definite linear complementarity problems is presented. The iterations reduce to linear iterations in a neighborhood of the solution if the problem is nondegenerate. The variational setting of the method guarantees global convergence.As an application, we consider a discretization of a Dirichlet obstacle problem by triangular linear finite elements. In contrast to usual iterative methods, the observed rate of convergence does not deteriorate with step size.The results presented here were announced at the XI. International Symposium on Mathematical Programming, Bonn, August 1982.     

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.     

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

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

On the convergence of iterative methods for symmetric linear complementarity problems

We prove convergence of the whole sequence generated by any of a large class of iterative algorithms for the symmetric linear complementarity problem (LCP), under the only hypothesis that a quadratic form associated with the LCP is bounded below on the nonnegative orthant. This hypothesis holds when the matrix is strictly copositive, and also when the matrix is copositive plus and the LCP is feasible. The proof is based upon the linear convergence rate of the sequence of functional values of the quadratic form. As a by-product, we obtain a decomposition result for copositive plus matrices. Finally, we prove that the distance from the generated sequence to the solution set (and the sequence itself, if its limit is a locally unique solution) have a linear rate of R-convergence.Research for this work was partially supported by CNPq grant No. 301280/86.     

Iterative methods for variational and complementarity problems

In this paper, we study both the local and global convergence of various iterative methods for solving the variational inequality and the nonlinear complementarity problems. Included among such methods are the Newton and several successive overrelaxation algorithms. For the most part, the study is concerned with the family of linear approximation methods. These are iterative methods in which a sequence of vectors is generated by solving certain linearized subproblems. Convergence to a solution of the given variational or complementarity problem is established by using three different yet related approaches. The paper also studies a special class of variational inequality problems arising from such applications as computing traffic and economic spatial equilibria. Finally, several convergence results are obtained for some nonlinear approximation methods.This research was based on work supported by the National Science Foundation under grant ECS-7926320.     

An Iterative Method for Finding the Least Solution to the Tensor Complementarity Problem

In this paper, we are concerned with finding the least solution to the tensor complementarity problem. When the involved tensor is strongly monotone, we present a way to estimate the nonzero elements of the solution in a successive manner. The procedure for identifying the nonzero elements of the solution gives rise to an iterative method of solving the tensor complementarity problem. In each iteration, we obtain an iterate by solving a lower-dimensional tensor equation. After finitely many iterations, the method terminates with a solution to the problem. Moreover, the sequence generated by the method is monotonically convergent to the least solution to the problem. We then extend this idea for general case and propose a sequential mathematical programming method for finding the least solution to the problem. Since the least solution to the tensor complementarity problem is the sparsest solution to the problem, the method can be regarded as an extension of a recent result by Luo et al. (Optim Lett 11:471–482, 2017). Our limited numerical results show that the method can be used to solve the tensor complementarity problem efficiently.     

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 matrix-splitting method for symmetric affine second-order cone complementarity problems

The affine second-order cone complementarity problem (SOCCP) is a wide class of problems that contains the linear complementarity problem (LCP) as a special case. The purpose of this paper is to propose an iterative method for the symmetric affine SOCCP that is based on the idea of matrix splitting. Matrix-splitting methods have originally been developed for the solution of the system of linear equations and have subsequently been extended to the LCP and the affine variational inequality problem. In this paper, we first give conditions under which the matrix-splitting method converges to a solution of the affine SOCCP. We then present, as a particular realization of the matrix-splitting method, the block successive overrelaxation (SOR) method for the affine SOCCP involving a positive definite matrix, and propose an efficient method for solving subproblems. Finally, we report some numerical results with the proposed algorithm, where promising results are obtained especially for problems with sparse matrices.     

Minimum-support solutions of polyhedral concave programs *

Motivated by the successful application of mathematical programming techniques to difficult machine learning problems, we seek solutions of concave minimization problems over polyhedral sets with minimum number of nonzero components. We that if

such problems have a solution, they have a vertex solution with a minimal number of zeros. This includes linear programs and general linear complementarity problems. A smooth concave exponential approximation to a step function solves the minimumsupport problem exactly for a finite value of the smoothing parameter. A fast finite linear-programming-based iterative method terminates at a stationary point, which for many important real world problems provides very useful answers. Utilizing the

complementarity property of linear programs and linear complementarity problems, an upper bound on the number of nonzeros can be obtained by solving a single convex minimization problem on a polyhedral set     

An algorithm based on a sequence of linear complementarity problems applied to a walrasian equilibrium model: An example

The Walrasian equilibrium problem is cast as a complementarity problem, and its solution is computed by solving a sequence of linear complementarity problems (SLCP). Earlier numerical experiments have demonstrated the computational efficiency of this approach. So far, however, there exist few relevant theoretical results that characterize the performance of this algorithm. In the context of a simple example of a Walrasian equilibrium model, we study the iterates of the SLCP algorithm. We show that a particular LCP of this process may have no, one or more complementary solutions. Other LCPs may have both homogeneous and complementary solutions. These features complicate the proof of convergence for the general case. For this particular example, however, we are able to show that Lemke's algorithm computes a solution to an LCP if one exists,and that the iterative process converges globally.     

A fixed-point iteration approach for multibody dynamics with contact and small friction

Acceleration–force setups for multi-rigid-body dynamics are known to be inconsistent for some configurations and sufficiently large friction coefficients (a Painleve paradox). This difficulty is circumvented by time-stepping methods using impulse-velocity approaches, which solve complementarity problems with possibly nonconvex solution sets. We show that very simple configurations involving two bodies may have a nonconvex solution set for any nonzero value of the friction coefficient. We construct two fixed-point iteration algorithms that solve convex subproblems and that are guaranteed, for sufficiently small friction coefficients, to retrieve, at a linear convergence rate, the unique velocity solution of the nonconvex linear complementarity problem whenever the frictionless configuration can be disassembled. In addition, we show that one step of one of the iterative algorithms provides an excellent approximation to the velocity solution of the original, possibly nonconvex, problem if for all contacts we have that either the friction coefficient is small or the slip velocity is small.Subject Index. 70E55, 75M10, 75M15, 90C33A partial version of this work has appeared in the proceedings of the NATO Advanced Studies Institute on Virtual Nonlinear Multibody Systems, Prague, 2002.     

一类非单调二阶锥互补问题解集的非空性与有界性

本文在二阶锥上引入一类新的映射,称之为笛卡尔P_*(κ)映射,它是单调映射的推广.文中讨论涉及这类映射的二阶锥互补问题的解的存在性和解集的有界性.主要结论为:如果所考虑的互补问题是严格可行的,那么它的解集是非空有界的.     

The projected newton method for solving inverse eigenvalue problems - the case of multiple eigenvaues

This paper deals with the optimal solution of ill-posed linear problems, i.e..linear problems for which the solution operator is unbounded. We consider worst-case ar,and averagecase settings. Our main result is that algorithms having finite error (for a given setting) exist if and only if the solution operator is bounded (in that setting). In the worst-case setting, this means that there is no algorithm for solving ill-posed problems having finite error. In the average-case setting, this means that algorithms having finite error exist if and only lf the solution operator is bounded on the average. If the solution operator is bounded on the average, we find average-case optimal information of cardinality n and optimal algorithms using this information, and show that the average error of these algorithms tends to zero as n→∞. These results are then used to determine the [euro]-complexity, i.e., the minimal costof finding an [euro]-accurate approximation. In the worst-case setting, the [euro]comp1exity of an illposed problem is infinite for all [euro]>0; that is, we cannot find an approximation having finite error and finite cost. In the average-case setting, the [euro]-complexity of an ill-posed problem is infinite for all [euro]>0 iff the solution operator is not bounded on the average, moreover, if the the solutionoperator is bounded on the average, then the [euro]-complexity is finite for all [euro]>0.     

THE SPLIT GENERALIZED EQUILIBRIUM PROBLEM INVOLVING INVERSE-STRONGLY MONOTONE MAPPINGS AND ITS CONVERGENCE ALGORITHMS

In this paper, we introduce a split generalized equilibrium problem and consider some iterative sequences to find a solution of the equilibrium problem such that its image under a given bounded linear operator is a solution of another equilibrium problem. We obtain some strong and weak convergence theorems.     

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.     

Iterative algorithms for the multiple-sets split feasibility problem in Hilbert spaces

In this paper, for the multiple-sets split feasibility problem, that is to find a point closest to a family of closed convex subsets in one space such that its image under a linear bounded mapping will be closest to another family of closed convex subsets in the image space, we study several iterative methods for finding a solution, which solves a certain variational inequality. We show that particular cases of our algorithms are some improvements for existing ones in literature. We also give two numerical examples for illustrating our algorithms.