非光滑非线性互补问题的牛顿法

研究了非光滑的非线性互补问题. 首先将非光滑的非线性互补问题转化为一个非光滑方程组,然后用牛顿法求解这个非光滑方程组. 在该牛顿法中,每次迭代只需一个原始函数B-微分中的一个元素. 最后证明了该牛顿法的超线性收敛性.     

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.     

An inexact NE/SQP method for solving the nonlinear complementarity problem

In this paper, we present an extension to the NE/SQP method; the latter is a robust algorithm that we proposed for solving the nonlinear complementarity problem in an earlier article. In this extended version of NE/SQP, instead of exactly solving the quadratic program subproblems, approximate solutions are generated via an inexact rule.Under a proper choice for this rule, this inexact method is shown to inherit the same convergence properties of the original NE/SQP method. In addition to developing the convergence theory for the inexact method, we also present numerical results of the algorithm tested on two problems of varying size.     

A Hybrid Smoothing Method for Mixed Nonlinear Complementarity Problems

In this paper, we describe a new, integral-based smoothing method for solving the mixed nonlinear complementarity problem (MNCP). This approach is based on recasting MNCP as finding the zero of a nonsmooth system and then generating iterates via two types of smooth approximations to this system. Under weak regularity conditions, we establish that the sequence of iterates converges to a solution if the limit point of this sequence is regular. In addition, we show that the rate is Q-linear, Q-superlinear, or Q-quadratic depending on the level of inexactness in the subproblem calculations and we make use of the inexact Newton theory of Dembo, Eisenstat, and Steihaug. Lastly, we demonstrate the viability of the proposed method by presenting the results of numerical tests on a variety of complementarity problems.     

A PENALTY TECHNIQUE FOR NONLINEAR COMPLEMENTARITY PROBLEMS

1.IntroductionConsiderthefollowingnonlinearcomplementarityproblemsNCP(F)offindinganxER",suchthatwhereFisamappingfromR"intoitself.ItisanimportantformofthefollowingvariationalinequalityVI(F,X)offindinganxEX,suchthatwhereXCReisaclosedconvexset.WhenX=R7,(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.     

基于一个新的NCP函数的光滑牛顿法求解非线性互补问题

本文研究了非线性互补的光滑化问题.利用一个新的光滑NCP函数将非线性互补问题转化为等价的光滑方程组,并在此基础上建立了求解P0-函数非线性互补问题的一个完全光滑化牛顿法,获得了算法的全局收敛性和局部二次收敛性的结果.并给出数值实验验证了理论分析的正确性.     

A smoothing inexact Newton method for nonlinear complementarity problems

In this article, we propose a new smoothing inexact Newton algorithm for solving nonlinear complementarity problems (NCP) base on the smoothed Fischer-Burmeister function. In each iteration, the corresponding linear system is solved only approximately. The global convergence and local superlinear convergence are established without strict complementarity assumption at the NCP solution. Preliminary numerical results indicate that the method is effective for large-scale NCP.     

Inexact Interior-Point Method

In this paper, we introduce an inexact interior-point algorithm for a constrained system of equations. The formulation of the problem is quite general and includes nonlinear complementarity problems of various kinds. In our convergence theory, we interpret the inexact interior-point method as an inexact Newton method. This enables us to establish a global convergence theory for the proposed algorithm. Under the additional assumption of the invertibility of the Jacobian at the solution, the superlinear convergence of the iteration sequence is proved.     

A modified damped Newton method for linear complementarity problems

We present a modified damped Newton method for solving large sparse linear complementarity problems, which adopts a new strategy for determining the stepsize at each Newton iteration. The global convergence of the new method is proved when the system matrix is a nondegenerate matrix. We then apply the matrix splitting technique to this new method, deriving an inexact splitting method for the linear complementarity problems. The global convergence of the resulting inexact splitting method is proved, too. Numerical results show that the new methods are feasible and effective for solving the large sparse linear complementarity problems.     

非线性互补问题非精确逐次逼近法的全局收敛性

本文针对非线性互补问题,提出了与其等价的非光滑方程的非精确逐次逼近算法,并在一定条件下证明了该算法的全局收敛性。     

On the convergence of an inexact Gauss–Newton trust-region method for nonlinear least-squares problems with simple bounds

We introduce an inexact Gauss–Newton trust-region method for solving bound-constrained nonlinear least-squares problems where, at each iteration, a trust-region subproblem is approximately solved by the Conjugate Gradient method. Provided a suitable control on the accuracy to which we attempt to solve the subproblems, we prove that the method has global and asymptotic fast convergence properties. Some numerical illustration is also presented.     

INEXACT DAMPED NEWTON METHOD FOR NONLINEAR COMPLEMENTARITY PROBLEMS

In this paper, we propose an inexact clamped Newton method for solving nonlinear complementarity problems based on the equivalent B-differentiable equations.Global convergence and locally quadratic convergence are obtained,and numerical results are given.     

A proximal point algorithm for the monotone second-order cone complementarity problem

This paper is devoted to the study of the proximal point algorithm for solving monotone second-order cone complementarity problems. The proximal point algorithm is to generate a sequence by solving subproblems that are regularizations of the original problem. After given an appropriate criterion for approximate solutions of subproblems by adopting a merit function, the proximal point algorithm is verified to have global and superlinear convergence properties. For the purpose of solving the subproblems efficiently, we introduce a generalized Newton method and show that only one Newton step is eventually needed to obtain a desired approximate solution that approximately satisfies the appropriate criterion under mild conditions. Numerical comparisons are also made with the derivative-free descent method used by Pan and Chen (Optimization 59:1173–1197, 2010), which confirm the theoretical results and the effectiveness of the algorithm.     

An inexactQP-based method for nonlinear complementarity problems

Summary. We consider a quadratic programming-based method for nonlinear complementarity problems which allows inexact solutions of the quadratic subproblems. The main features of this method are that all iterates stay in the feasible set and that the method has some strong global and local convergence properties. Numerical results for all complementarity problems from the MCPLIB test problem collection are also reported. Received February 24, 1997 / Revised version received September 5, 1997     

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.     

求解非线性互补问题的一种序列线性方程组方法

１　引　言 设Ｆ：Ｒｎ→Ｒｎ．则非线性互补问题ＮＣＰ（Ｆ）的形式如下：求ｘ∈ＲＮ,使ＮＣＰ（Ｆ）是如下变分不等式ＶＩ（Ｆ,Ｘ）的一种重要形式：求ｘ∈Ｘ　Ｒ　使当Ｘ＝Ｒｎ＋时,ＶＩ（Ｆ,Ｘ）即为ＮＣＰ（Ｆ）．由于ＮＣＰ和ＶＩ在工程和经济等领域中有广泛的应用,因而,对其研究受到了很大的重视．目前,关于（１．２）的求解已发展了一系列算法,线性化方法是常用的一类算法．线性化方法的局部收敛性研究已有了许多好的结果（见［９,１０］等）．全局收敛性成为了当前研究ＶＩ（Ｆ,Ｘ）算法的一个热门课题．并在Ｎｅｗｔｏ…     

A partial proximal point algorithm for nuclear norm regularized matrix least squares problems

We introduce a partial proximal point algorithm for solving nuclear norm regularized matrix least squares problems with equality and inequality constraints. The inner subproblems, reformulated as a system of semismooth equations, are solved by an inexact smoothing Newton method, which is proved to be quadratically convergent under a constraint non-degeneracy condition, together with the strong semi-smoothness property of the singular value thresholding operator. Numerical experiments on a variety of problems including those arising from low-rank approximations of transition matrices show that our algorithm is efficient and robust.     

Inexact non-interior continuation method for solving large-scale monotone SDCP

For exact Newton method for solving monotone semidefinite complementarity problems (SDCP), one needs to exactly solve a linear system of equations at each iteration. For problems of large size, solving the linear system of equations exactly can be very expensive. In this paper, we propose a new inexact smoothing/continuation algorithm for solution of large-scale monotone SDCP. At each iteration the corresponding linear system of equations is solved only approximately. Under mild assumptions, the algorithm is shown to be both globally and superlinearly convergent.