Solution of Complementarity Problems via Piecewise Linearization

My master thesis concerns the solution linear complementarity problems (LCP). The Lemke algorithm, the most commonly used algorithm for solving a LCP until this day, was compared with the piecewise Newton method (PLN algorithm). The piecewise Newton method is an algorithm to solve a piecewise linear system on the basis of damped Newton methods. The linear complementarity problem is formulated as a piecewise linear system for the applicability of the PLN algorithm. Then, different application examples will be presented, solved with the PLN algorithm. As a result of the findings (of my master thesis) it can be assumed that – under the condition of coherent orientation – the PLN-algorithm requires fewer iterations to solve a linear complementarity problem than the Lemke algorithm. The coherent orientation for piecewise linear problems corresponds for linear complementarity problems to the P-matrix-property. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Strongly and Superlinearly Convergent SQP Algorithm for Optimization Problems with Linear Complementarity Constraints

This paper discusses a kind of optimization problem with linear complementarity constraints, and presents a sequential quadratic programming (SQP) algorithm for solving a stationary point of the problem. The algorithm is a modification of the SQP algorithm proposed by Fukushima et al. [Computational Optimization and Applications, 10 (1998), 5-34], and is based on a reformulation of complementarity condition as a system of linear equations. At each iteration, one quadratic programming and one system of equations needs to be solved, and a curve search is used to yield the step size. Under some appropriate assumptions, including the lower-level strict complementarity, but without the upper-level strict complementarity for the inequality constraints, the algorithm is proved to possess strong convergence and superlinear convergence. Some preliminary numerical results are reported.     

An Interior Point Algorithm for Mixed Complementarity Nonlinear Problems

Nonlinear complementarity and mixed complementarity problems arise in mathematical models describing several applications in Engineering, Economics and different branches of physics. Previously, robust and efficient feasible directions interior point algorithm was presented for nonlinear complementarity problems. In this paper, it is extended to mixed nonlinear complementarity problems. At each iteration, the algorithm finds a feasible direction with respect to the region defined by the inequality conditions, which is also monotonic descent direction for the potential function. Then, an approximate line search along this direction is performed in order to define the next iteration. Global and asymptotic convergence for the algorithm is investigated. The proposed algorithm is tested on several benchmark problems. The results are in good agreement with the asymptotic analysis. Finally, the algorithm is applied to the elastic–plastic torsion problem encountered in the field of Solid Mechanics.     

Merit functions for nonsmooth complementarity problems and related descent algorithm

Under some assumptions, the solution set of a nonlinear complementarity problem coincides with the set of local minima of the corresponding minimization problem. This paper uses a family of new merit functions to deal with nonlinear complementarity problem where the underlying function is assumed to be a continuous but not necessarily locally Lipschitzian map and gives a descent algorithm for solving the nonsmooth continuous complementarity problems. In addition, the global convergence of the derivative free descent algorithm is also proved.     

A smoothing conic trust region filter method for the nonlinear complementarity problem

This paper discusses nonlinear complementarity problems; its goal is to present a globally and superlinearly convergent algorithm for the discussed problems. Filter methods are extensively studied to handle nonlinear complementarity problem. Because of good numerical results, filter techniques are attached. By means of a filter strategy, we present a new trust region method based on a conic model for nonlinear complementarity problems. Under a proper condition, the superlinear convergence of the algorithm is established without the strict complementarity condition.     

Nonmonotone Inexact Newton Method for the Extended Linear Complementarity Problem

This paper presents a nonmonotone inexact Newton-type method for the extended linear complementarity problem (ELCP). We first reformulate the optimization system of the ELCP problem into a system of smoothed equations. Then we solve this system by a nonmonotone inexact Newton-type algorithm. The global convergence is obtained and numerical tests for some classes of ELCP include linear complementarity, horizontal linear complementarity, and generalized linear complementarity problems are also given to show the e?ciency of the proposed algorithm.     

A projected–gradient interior–point algorithm for complementarity problems

Interior–point algorithms are among the most efficient techniques for solving complementarity problems. In this paper, a procedure for globalizing interior–point algorithms by using the maximum stepsize is introduced. The algorithm combines exact or inexact interior–point and projected–gradient search techniques and employs a line–search procedure for the natural merit function associated with the complementarity problem. For linear problems, the maximum stepsize is shown to be acceptable if the Newton interior–point search direction is employed. Complementarity and optimization problems are discussed, for which the algorithm is able to process by either finding a solution or showing that no solution exists. A modification of the algorithm for dealing with infeasible linear complementarity problems is introduced which, in practice, employs only interior–point search directions. Computational experiments on the solution of complementarity problems and convex programming problems by the new algorithm are included.     

A Superlinearly Convergent Implicit Smooth SQP Algorithm for Mathematical Programs with Nonlinear Complementarity Constraints

This paper discusses a special class of mathematical programs with nonlinear complementarity constraints, its goal is to present a globally and superlinearly convergent algorithm for the discussed problems. We first reformulate the complementarity constraints as a standard nonlinear equality and inequality constraints by making use of a class of generalized smoothing complementarity functions, then present a new SQP algorithm for the discussed problems. At each iteration, with the help of a pivoting operation, a master search direction is yielded by solving a quadratic program, and a correction search direction for avoiding the Maratos effect is generated by an explicit formula. Under suitable assumptions, without the strict complementarity on the upper-level inequality constraints, the proposed algorithm converges globally to a B-stationary point of the problems, and its convergence rate is superlinear.AMS Subject Classification: 90C, 49MThis work was supported by the National Natural Science Foundation (10261001) and the Guangxi Province Science Foundation (0236001, 0249003) of China.     

A Polynomial Interior-Point Algorithm for Monotone Linear Complementarity Problems

In this paper, we propose an interior-point algorithm for monotone linear complementarity problems. The algorithm is based on a new technique for finding the search direction and the strategy of the central path. At each iteration, we use only full-Newton steps. Moreover, it is proven that the number of iterations of the algorithm coincides with the well-known best iteration bound for monotone linear complementarity problems.     

A regularization smoothing method for second-order cone complementarity problem

In this paper, the second-order cone complementarity problem is studied. Based on the Fischer–Burmeister function with a perturbed parameter, which is also called smoothing parameter, a regularization smoothing Newton method is presented for solving the sequence of regularized problems of the second-order cone complementarity problem. Under proper conditions, the global convergence and local superlinear convergence of the proposed algorithm are obtained. Moreover, the local superlinear convergence is established without strict complementarity conditions. Preliminary numerical results suggest the effectiveness of the algorithm.     

求解特征值互补问题的一类ABS算法

ABS算法是20世纪80年代初,由Abaffy,Broyden和Spedicato完成的用于求解线性方程组的含有三个参量的投影算法,是一类有限次迭代直接法。目前,ABS算法不仅可以求解线性与非线性方程组,还可以求解线性规划和具有线性约束的非线性规划等问题。本文即是利用ABS算法求解特征值互补问题的一种尝试,构造了求解特征值互补问题的ABS算法,证明了求解特征值互补问题的ABS算法的收敛性。数值例子充分验证了求解特征值互补问题的ABS算法的有效性。     

A Smoothing Newton Algorithm for a Class of Non-monotonic Symmetric Cone Linear Complementarity Problems

Recently, the study of symmetric cone complementarity problems has been a hot topic in the literature. Many numerical methods have been proposed for solving such a class of problems. Among them, the problems concerned are generally monotonic. In this paper, we consider symmetric cone linear complementarity problems with a class of non-monotonic transformations. A smoothing Newton algorithm is extended to solve this class of non-monotonic symmetric cone linear complementarity problems; and the algorithm is proved to be well-defined. In particular, we show that the algorithm is globally and locally quadratically convergent under mild assumptions. The preliminary numerical results are also reported.     

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

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

Analysis of a smoothing Newton method for second-order cone complementarity problem

In this paper, we consider the second-order cone complementarity problem with P ₀-property. By introducing a smoothing parameter into the Fischer-Burmeister function, we present a smoothing Newton method for the second-order cone complementarity problem. The proposed algorithm solves only a linear system of equations and performs only one line search at each iteration. At the same time, the algorithm does not have restrictions on its starting point and has global convergence. Under the assumption of nonsingularity, we establish the locally quadratic convergence of the algorithm without strict complementarity condition. Preliminary numerical results show that the algorithm is promising.     

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.     

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.     

Integral global optimization method for solution of nonlinear complementarity problems

The mapping in a nonlinear complementarity problem may be discontinuous. The integral global optimization algorithm is proposed to solve a nonlinear complementarity problem with a robust piecewise continuous mapping. Numerical examples are given to illustrate the effectiveness of the algorithm.     

Computing integral solutions of complementarity problems

In this paper an algorithm is proposed to find an integral solution of (nonlinear) complementarity problems. The algorithm starts with a nonnegative integral point and generates a unique sequence of adjacent integral simplices of varying dimension. Conditions are stated under which the algorithm terminates with a simplex, one of whose vertices is an integral solution of the complementarity problem under consideration.     

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.     

Complementarity Active-Set Algorithm for Mathematical Programming Problems with Equilibrium Constraints

In this paper, an algorithm for solving a mathematical programming problem with complementarity (or equilibrium) constraints (MPEC) is introduced, which uses the active-set methodology while maintaining the complementarity restrictions throughout the procedure. Finite convergence of the algorithm to a strongly stationary point of the MPEC is established under reasonable hypotheses. The algorithm can be easily implemented by adopting any active-set code for nonlinear programming. Computational experience is included to highlight the efficacy of the proposed method in practice.