A penalty method for a mixed nonlinear complementarity problem

We propose a power penalty method for a mixed nonlinear complementarity problem (MNCP) and show that the solution to the penalty equation converges to that of the MNCP exponentially as the penalty parameter approaches infinity, provided that the mapping involved in the MNCP is both continuous and ξ-monotone. Furthermore, a convergence theorem is established when the monotonicity assumption on the mapping is removed. To demonstrate the usefulness and the convergence rates of this method, we design a non-trivial test MNCP problem arising in shape-preserving bi-harmonic interpolation and apply our method to this test problem. The numerical results confirm our theoretical findings.     

A TRULY GLOBALLY CONVERGENT FEASIBLE NEWTON-TYPE METHOD FOR MIXED COMPLEMENTARITY PROBLEMS

Typical solution methods for solving mixed complementarity problems either generatefeasible iterates but have to solve relatively complicated subproblems such as quadraticprograms or linear complementarity problems,or(those methods)have relatively simplesubproblems such as system of linear equations but possibly generate infeasible iterates.In this paper,we propose a new Newton-type method for solving monotone mixed com-plementarity problems,which ensures to generate feasible iterates,and only has to solve asystem of well-conditioned linear equations with reduced dimension per iteration.Withoutany regularity assumption,we prove that the whole sequence of iterates converges to a so-lution of the problem(truly globally convergent).Furthermore,under suitable conditions,the local superlinear rate of convergence is also established.     

A Regularization Newton Method for Solving Nonlinear Complementarity Problems

In this paper we construct a regularization Newton method for solving the nonlinear complementarity problem (NCP(F )) and analyze its convergence properties under the assumption that F is a P ₀ -function. We prove that every accumulation point of the sequence of iterates is a solution of NCP(F ) and that the sequence of iterates is bounded if the solution set of NCP(F ) is nonempty and bounded. Moreover, if F is a monotone and Lipschitz continuous function, we prove that the sequence of iterates is bounded if and only if the solution set of NCP(F ) is nonempty by setting , where is a parameter. If NCP(F) has a locally unique solution and satisfies a nonsingularity condition, then the convergence rate is superlinear (quadratic) without strict complementarity conditions. At each step, we only solve a linear system of equations. Numerical results are provided and further applications to other problems are discussed. Accepted 25 March 1998     

A local convergence property of primal-dual methods for nonlinear programming

We prove a new local convergence property of some primal-dual methods for solving nonlinear optimization problems. We consider a standard interior point approach, for which the complementarity conditions of the original primal-dual system are perturbed by a parameter driven to zero during the iterations. The sequence of iterates is generated by a linearization of the perturbed system and by applying the fraction to the boundary rule to maintain strict feasibility of the iterates with respect to the nonnegativity constraints. The analysis of the rate of convergence is carried out by considering an arbitrary sequence of perturbation parameters converging to zero. We first show that, once an iterate belongs to a neighbourhood of convergence of the Newton method applied to the original system, then the whole sequence of iterates converges to the solution. In addition, if the perturbation parameters converge to zero with a rate of convergence at most superlinear, then the sequence of iterates becomes asymptotically tangent to the central trajectory in a natural way. We give an example showing that this property can be false when the perturbation parameter goes to zero quadratically.      

A New Complexity Analysis for Full-Newton Step Infeasible Interior-Point Algorithm for Horizontal Linear Complementarity Problems

In this paper, we first present a full-Newton step feasible interior-point algorithm for solving horizontal linear complementarity problems. We prove that the full-Newton step to the central path is quadratically convergent. Then, we generalize an infeasible interior-point method for linear optimization to horizontal linear complementarity problems based on new search directions. This algorithm starts from strictly feasible iterates on the central path of a perturbed problem that is produced by a suitable perturbation in the horizontal linear complementarity problem. We use the so-called feasibility steps that find strictly feasible iterates for the next perturbed problem. By using centering steps for the new perturbed problem, we obtain a strictly feasible iterate close enough to the central path of the new perturbed problem. The complexity of the algorithm coincides with the best known iteration bound for infeasible interior-point methods.     

Local path-following property of inexact interior methods in nonlinear programming

We study the local behavior of a primal-dual inexact interior point methods for solving nonlinear systems arising from the solution of nonlinear optimization problems or more generally from nonlinear complementarity problems. The algorithm is based on the Newton method applied to a sequence of perturbed systems that follows by perturbation of the complementarity equations of the original system. In case of an exact solution of the Newton system, it has been shown that the sequence of iterates is asymptotically tangent to the central path (Armand and Benoist in Math. Program. 115:199?C222, 2008). The purpose of the present paper is to extend this result to an inexact solution of the Newton system. We give quite general conditions on the different parameters of the algorithm, so that this asymptotic property is satisfied. Some numerical tests are reported to illustrate our theoretical results.     

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

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

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.     

Global convergence of slanting filter methods for nonlinear programming

In this paper, we present a general algorithm for nonlinear programming which uses a slanting filter criterion for accepting the new iterates. Independently of how these iterates are computed, we prove that all accumulation points of the sequence generated by the algorithm are feasible. Computing the new iterates by the inexact restoration method, we prove stationarity of all accumulation points of the sequence.     

Fixed Point Methods for the Complementarity Problem

This paper is concerned with iterative procedures for the monotone complementarity problem. Our iterative methods consist of finding fixed points of appropriate continuous maps. In the case of the linear complementarity problem, it is shown that the problem is solvable if and only if the sequence of iterates is bounded in which case summability methods are used to find a solution of the problem. This procedure is then used to find a solution of the nonlinear complementarity problem satisfying certain regularity conditions for which the problem has a nonempty bounded solution set.     

Quadratic Convergence of a Primal-Dual Interior Point Method for Degenerate Nonlinear Optimization Problems

Recently studies of numerical methods for degenerate nonlinear optimization problems have been attracted much attention. Several authors have discussed convergence properties without the linear independence constraint qualification and/or the strict complementarity condition. In this paper, we are concerned with quadratic convergence property of a primal-dual interior point method, in which Newton’s method is applied to the barrier KKT conditions. We assume that the second order sufficient condition and the linear independence of gradients of equality constraints hold at the solution, and that there exists a solution that satisfies the strict complementarity condition, and that multiplier iterates generated by our method for inequality constraints are uniformly bounded, which relaxes the linear independence constraint qualification. Uniform boundedness of multiplier iterates is satisfied if the Mangasarian-Fromovitz constraint qualification is assumed, for example. By using the stability theorem by Hager and Gowda (1999), and Wright (2001), the distance from the current point to the solution set is related to the residual of the KKT conditions.By controlling a barrier parameter and adopting a suitable line search procedure, we prove the quadratic convergence of the proposed algorithm.     

Extended LQP Method for Monotone Nonlinear Complementarity Problems

To solve nonlinear complementarity problems (NCP), the logarithmic-quadratic proximal (LQP) method solves a system of nonlinear equations at each iteration. In this paper, the iterates generated by the original LQP method are extended by explicit formulas and thus an extended LQP method is presented. It is proved theoretically that the lower bound of the progress obtained by the extended LQP method is greater than that by the original LQP method. Preliminary numerical results are provided to verify the theoretical assertions and the effectiveness of both the original and the extended LQP method.     

Strictly feasible equation-based methods for mixed complementarity problems

Summary.   We introduce a new algorithm for the solution of the mixed complementarity problem (MCP) which has stronger properties than most existing methods. In fact, typical solution methods for the MCP either generate feasible iterates but have to solve relatively complicated subproblems (like quadratic programs or linear complementarity problems), or they have relatively simple subproblems (like linear systems of equations) but generate not necessarily feasible iterates. The method to be presented here combines the nice features of these two classes of methods: It has to solve only one linear system of equations (of reduced dimension) at each iteration, and it generates feasible (more precisely: strictly feasible) iterates. The new method has some nice global and local convergence properties. Some preliminary numerical results will also be given. Received August 26, 1999 / Revised version recived April 11, 2000 / Published online February 5, 2001     

On the convergence of the coordinate descent method for convex differentiable minimization

The coordinate descent method enjoys a long history in convex differentiable minimization. Surprisingly, very little is known about the convergence of the iterates generated by this method. Convergence typically requires restrictive assumptions such as that the cost function has bounded level sets and is in some sense strictly convex. In a recent work, Luo and Tseng showed that the iterates are convergent for the symmetric monotone linear complementarity problem, for which the cost function is convex quadratic, but not necessarily strictly convex, and does not necessarily have bounded level sets. In this paper, we extend these results to problems for which the cost function is the composition of an affine mapping with a strictly convex function which is twice differentiable in its effective domain. In addition, we show that the convergence is at least linear. As a consequence of this result, we obtain, for the first time, that the dual iterates generated by a number of existing methods for matrix balancing and entropy optimization are linearly convergent.This work was partially supported by the U.S. Army Research Office, Contract No. DAAL03-86-K-0171, by the National Science Foundation, Grant No. ECS-8519058, and by the Science and Engineering Research Board of McMaster University.     

Optimal Control Formulation for Complementarity Dynamical Systems

In this paper, we show that the complementarity dynamical systems can be reformulated as optimal control problems. By using this reformulation, we present a pseudospectral scheme to discretize the complementarity dynamical systems. Applying this discretization, the complementarity dynamical system is reduced to a sequence of nonlinear programming problems. Numerical examples and comparison with two other methods are included to demonstrate the capability of the proposed method.     

An iterative method for a system of linear complementarity problems with perturbations and interval data

In this paper, we introduce a total step method for solving a system of linear complementarity problems with perturbations and interval data. It is applied to two interval matrices [A] and [B] and two interval vectors [b] and [c]. We prove that the sequence generated by the total step method converges to ([x^∗],[y^∗]) which includes the solution set for the system of linear complementarity problems defined by any fixed A∈[A],B∈[B],b∈[b] and c∈[c]. We also consider a modification of the method and show that, if we start with two interval vectors containing the limits, then the iterates contain the limits. We close our paper with two examples which illustrate our theoretical results.     

Dual Convergence for Penalty Algorithms in Convex Programming

Algorithms for convex programming, based on penalty methods, can be designed to have good primal convergence properties even without uniqueness of optimal solutions. Taking primal convergence for granted, in this paper we investigate the asymptotic behavior of an appropriate dual sequence obtained directly from primal iterates. First, under mild hypotheses, which include the standard Slater condition but neither strict complementarity nor second-order conditions, we show that this dual sequence is bounded and also, each cluster point belongs to the set of Karush–Kuhn–Tucker multipliers. Then we identify a general condition on the behavior of the generated primal objective values that ensures the full convergence of the dual sequence to a specific multiplier. This dual limit depends only on the particular penalty scheme used by the algorithm. Finally, we apply this approach to prove the first general dual convergence result of this kind for penalty-proximal algorithms in a nonlinear setting.     

An iterative method for generalized nonlinear complementarity problems

An iterative method for solving generalized nonlinear complementarity problems (Ref. 1) involving stronglyK-copositive operators is introduced. Conditions are presented which guarantee the convergence of the method; in addition, the sequence of iterates is used to prove the existence of a solution to the problem under conditions not included in the previous study. Separate consideration is given to the generalized linear complementarity problem.This research was partially supported by National Science Foundation, Grant No. GP-16293. This paper constitutes part of the junior author's doctoral thesis written at Rensselaer Polytechnic Institute. Research support was provided by an NDEA Fellowship and an RPI Fellowship.     

Analysis on Newton projection method for the split feasibility problem

In this paper, based on a merit function of the split feasibility problem (SFP), we present a Newton projection method for solving it and analyze the convergence properties of the method. The merit function is differentiable and convex. But its gradient is a linear composite function of the projection operator, so it is nonsmooth in general. We prove that the sequence of iterates converges globally to a solution of the SFP as long as the regularization parameter matrix in the algorithm is chosen properly. Especially, under some local assumptions which are necessary for the case where the projection operator is nonsmooth, we prove that the sequence of iterates generated by the algorithm superlinearly converges to a regular solution of the SFP. Finally, some numerical results are presented.     

Power iteration and inverse power iteration for eigenvalue complementarity problem

In this paper, an inverse complementarity power iteration method (ICPIM) for solving eigenvalue complementarity problems (EiCPs) is proposed. Previously, the complementarity power iteration method (CPIM) for solving EiCPs was designed based on the projection onto the convex cone K. In the new algorithm, a strongly monotone linear complementarity problem over the convex cone K is needed to be solved at each iteration. It is shown that, for the symmetric EiCPs, the CPIM can be interpreted as the well‐known conditional gradient method, which requires only linear optimization steps over a well‐suited domain. Moreover, the ICPIM is closely related to the successive quadratic programming (SQP) via renormalization of iterates. The global convergence of these two algorithms is established by defining two nonnegative merit functions with zero global minimum on the solution set of the symmetric EiCP. Finally, some numerical simulations are included to evaluate the efficiency of the proposed algorithms.