非光滑方程组牛顿法的全局收敛性分析

通过定义一种新的*-微分,本文给出了局部Lipschitz非光滑方程组的牛顿法,并对其全局收敛性进行了研究.该牛顿法结合了非光滑方程组的局部收敛性和全局收敛性.最后,我们把这种牛顿法应用到非光滑函数的光滑复合方程组问题上,得到了较好的收敛性.     

Generalized equations and the generalized Newton method

We give some convergence results on the generalized Newton method (referred to by some authors as Newton's method) and the chord method when applied to generalized equations. The main results of the paper extend the classical Kantorovich results on Newton's method to (nonsmooth) generalized equations. Our results also extend earlier results on nonsmooth equations due to Eaves, Robinson, Josephy, Pang and Chan. We also propose inner-iterative schemes for the computation of the generalized Newton iterates. These schemes generalize popular iterative methods (Richardson's method, Jacobi's method and the Gauss-Seidel method) for the solution of linear equations and linear complementarity problems and are shown to be convergent under natural generalizations of classical convergence criteria. Our results are applicable to equations involving single-valued functions and also to a class of generalized equations which includes variational inequalities, nonlinear complementarity problems and some nonsmooth convex minimization problems.     

A perturbed version of an inexact generalized Newton method for solving nonsmooth equations

In this paper, we present the combination of the inexact Newton method and the generalized Newton method for solving nonsmooth equations F(x)?=?0, characterizing the local convergence in terms of the perturbations and residuals. We assume that both iteration matrices taken from the B-differential and vectors F(x ^(k)) are perturbed at each step. Some results are motivated by the approach of C?tina? regarding to smooth equations. We study the conditions, which determine admissible magnitude of perturbations to preserve the convergence of method. Finally, the utility of these results is considered based on some variant of the perturbed inexact generalized Newton method for solving some general optimization problems.     

On a new exponential iterative method for solving nonsmooth equations

In this paper, we propose a new distinctive version of a generalized Newton method for solving nonsmooth equations. The iterative formula is not the classic Newton type, but an exponential one. Moreover, it uses matrices from B‐differential instead of generalized Jacobian. We prove local convergence of the method and we present some numerical examples.     

A parameterized Newton method and a quasi-Newton method for nonsmooth equations

This paper presents a parameterized Newton method using generalized Jacobians and a Broyden-like method for solving nonsmooth equations. The former ensures that the method is well-defined even when the generalized Jacobian is singular. The latter is constructed by using an approximation function which can be formed for nonsmooth equations arising from partial differential equations and nonlinear complementarity problems. The approximation function method generalizes the splitting function method for nonsmooth equations. Locally superlinear convergence results are proved for the two methods. Numerical examples are given to compare the two methods with some other methods.This work is supported by the Australian Research Council.     

Affine scaling inexact generalized Newton algorithm with interior backtracking technique for solving bound-constrained semismooth equations

We develop and analyze an affine scaling inexact generalized Newton algorithm in association with nonmonotone interior backtracking line technique for solving systems of semismooth equations subject to bounds on variables. By combining inexact affine scaling generalized Newton with interior backtracking line search technique, each iterate switches to inexact generalized Newton backtracking step to strict interior point feasibility. The global convergence results are developed in a very general setting of computing trial steps by the affine scaling generalized Newton-like method that is augmented by an interior backtracking line search technique projection onto the feasible set. Under some reasonable conditions we establish that close to a regular solution the inexact generalized Newton method is shown to converge locally p-order q-superlinearly. We characterize the order of local convergence based on convergence behavior of the quality of the approximate subdifferentials and indicate how to choose an inexact forcing sequence which preserves the rapid convergence of the proposed algorithm. A nonmonotonic criterion should bring about speeding up the convergence progress in some ill-conditioned cases.     

Pseudotransient Continuation for Solving Systems of Nonsmooth Equations with Inequality Constraints

This paper investigates a pseudotransient continuation algorithm for solving a system of nonsmooth equations with inequality constraints. We first transform the inequality constrained system of nonlinear equations to an augmented nonsmooth system, and then employ the pseudotransient continuation algorithm for solving the corresponding augmented nonsmooth system. The method gets its global convergence properties from the dynamics, and inherits its local convergence properties from the semismooth Newton method. Finally, we illustrate the behavior of our approach by some numerical experiments.     

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

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

求解线性互补问题的一种新算法

本文针对线性互补问题,提出了与其等价的非光滑方程的逐次逼近阻尼牛顿法,并在一定条件下证明了该算法具有的全局收敛性．同时给出了一些数值例子,得到很好的数值结果．     

PICARD ITERATION FOR NONSMOOTH EQUATIONS

1. IntroductionConsider the following nonsmooth equationsF(x) = 0 (l)where F: R" - R" is LipsChitz continuous. A lot of work has been done and is bellg doneto deal with (1). It is basicly a genera1ization of the cIassic Newton method [8,10,11,14],Newton-lthe methods[1,18] and quasiNewton methods [6,7]. As it is discussed in [7], the latter,quasiNewton methods, seem to be lindted when aPplied to nonsmooth caJse in that a boundof the deterioration of uPdating matrir can not be maintained w…     

Globalizing a nonsmooth Newton method via nonmonotone path search

We give a framework for the globalization of a nonsmooth Newton method. In part one we start with recalling B. Kummer’s approach to convergence analysis of a nonsmooth Newton method and state his results for local convergence. In part two we give a globalized version of this method. Our approach uses a path search idea to control the descent. After elaborating the single steps, we analyze and prove the global convergence resp. the local superlinear or quadratic convergence of the algorithm. In the third part we illustrate the method for nonlinear complementarity problems.     

Some quadrature-based versions of the generalized Newton method for solving nonsmooth equations

In this paper, modifications of a generalized Newton method based on some rules of quadrature are studied. The methods considered are Newton-like iterative schemes for numerical solving systems of nonsmooth equations. Some mild conditions are given that ensure superlinear convergence to a solution. Moreover, a parameterized version of the midpoint version is presented. Finally, results of numerical tests are established.     

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

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

A B-differentiable equation-based,globally and locally quadratically convergent algorithm for nonlinear programs,complementarity and variational inequality problems

This paper presents a globally convergent, locally quadratically convergent algorithm for solving general nonlinear programs, nonlinear complementarity and variational inequality problems. The algorithm is based on a unified formulation of these three mathematical programming problems as a certain system of B-differentiable equations, and is a modification of the damped Newton method described in Pang (1990) for solving such systems of nonsmooth equations. The algorithm resembles several existing methods for solving these classes of mathematical programs, but has some special features of its own; in particular, it possesses the combined advantage of fast quadratic rate of convergence of a basic Newton method and the desirable global convergence induced by one-dimensional Armijo line searches. In the context of a nonlinear program, the algorithm is of the sequential quadratic programming type with two distinct characteristics: (i) it makes no use of a penalty function; and (ii) it circumvents the Maratos effect. In the context of the variational inequality/complementarity problem, the algorithm provides a Newton-type descent method that is guaranteed globally convergent without requiring the F-differentiability assumption of the defining B-differentiable equations.This work was based on research supported by the National Science Foundation under Grant No. ECS-8717968.     

Newton Methods for Solving Two Classes of Nonsmooth Equations

The paper is devoted to two systems of nonsmooth equations. One is the system of equations of max-type functions and the other is the system of equations of smooth compositions of max-type functions. The Newton and approximate Newton methods for these two systems are proposed. The Q-superlinear convergence of the Newton methods and the Q-linear convergence of the approximate Newton methods are established. The present methods can be more easily implemented than the previous ones, since they do not require an element of Clarke generalized Jacobian, of B-differential, or of b-differential, at each iteration point.     

Smoothing Newton method for operator equations in Banach spaces

In this paper, the global and superlinear convergence of smoothing Newton method for solving nonsmooth operator equations in Banach spaces are shown. The feature of smoothing Newton method is to use a smooth function to approximate the nonsmooth mapping. Under suitable assumptions, we prove that the smoothing Newton method is superlinearly convergent. As an application, we use the smoothing Newton method to solve a constrained optimal control problem.     

Smoothing Newton method for nonsmooth second-order cone complementarity problems with application to electric power markets

This paper is dedicated to solving a nonsmooth second-order cone complementarity problem, in which the mapping is assumed to be locally Lipschitz continuous, but not necessarily to be continuously differentiable everywhere. With the help of the vector-valued Fischer-Burmeister function associated with second-order cones, the nonsmooth second-order cone complementarity problem can be equivalently transformed into a system of nonsmooth equations. To deal with this reformulated nonsmooth system, we present an approximation function by smoothing the inner mapping and the outer Fischer-Burmeister function simultaneously. Different from traditional smoothing methods, the smoothing parameter introduced is treated as an independent variable. We give some conditions under which the Jacobian of the smoothing approximation function is guaranteed to be nonsingular. Based on these results, we propose a smoothing Newton method for solving the nonsmooth second-order cone complementarity problem and show that the proposed method achieves globally superlinear or quadratic convergence under suitable assumptions. Finally, we apply the smoothing Newton method to a network Nash-Cournot game in oligopolistic electric power markets and report some numerical results to demonstrate its effectiveness.

     

On the convergence of the proximal algorithm for nonsmooth functions involving analytic features

We study the convergence of the proximal algorithm applied to nonsmooth functions that satisfy the ?jasiewicz inequality around their generalized critical points. Typical examples of functions complying with these conditions are continuous semialgebraic or subanalytic functions. Following ?jasiewicz’s original idea, we prove that any bounded sequence generated by the proximal algorithm converges to some generalized critical point. We also obtain convergence rate results which are related to the flatness of the function by means of ?jasiewicz exponents. Apart from the sharp and elliptic cases which yield finite or geometric convergence, the decay estimates that are derived are of the type O(k ^?s ), where s ∈ (0, + ∞) depends on the flatness of the function.     

双障碍问题的逐次逼近阻尼牛顿法

1．引言及算法考虑Rn中的双障碍问题：求＊E年使其中f：Rn→Rn连续可微,c＝｛x-∈Rn|0≤x≤c｝,c∈Rn为常向量．若记c＝（c1,…,cn）T,则不准证明问题（1）等价于求解下面的非光滑方程组其中算子max,min是指分量的最大或最小．显然,由（2）式定义的函数H：Rn→Rn的第i个分量函数Hi：Rn→R为由（2）定义的函数H一般不是厂可微的,但我们可对H作如下分解：设住k｝是一单调递减且趋于O的正数序列,xk00,八k（）都是R”－＋R”的映射,其中bk（儿,W汕地分别由下式定义：其中圳的二v：二;＜人（x）一。k｝,B（x）二F：人（……