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

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

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.     

求解无限维非线性互补问题的光滑化牛顿法

研究一类无限维非线性互补问题的光滑化牛顿法.借助于非线性互补函数,将无限维非线性互补问题转化为一个非光滑算子方程.构造光滑算子逼近非光滑算子,在光滑逼近算子满足方向可微相容性的条件下,证明了光滑化牛顿法具有超线性收敛性.     

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.     

求解对称张量绝对值方程问题的非光滑牛顿法

提出一类对称张量绝对值方程问题,给出了求解此类问题的一类非光滑牛顿法,并且在一般的假设条件下,给出了算法的局部收敛性.最后给出相关的数值实验表明了算法的有效性.     

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

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

The Lagrangian Globalization Method for Nonsmooth Constrained Equations

The difficulty suffered in optimization-based algorithms for the solution of nonlinear equations lies in that the traditional methods for solving the optimization problem have been mainly concerned with finding a stationary point or a local minimizer of the underlying optimization problem, which is not necessarily a solution of the equations. One method to overcome this difficulty is the Lagrangian globalization (LG for simplicity) method. This paper extends the LG method to nonsmooth equations with bound constraints. The absolute system of equations is introduced. A so-called Projected Generalized-Gradient Direction (PGGD) is constructed and proved to be a descent direction of the reformulated nonsmooth optimization problem. This projected approach keeps the feasibility of the iterates. The convergence of the new algorithm is established by specializing the PGGD. Numerical tests are given. This author's work was done when she was visiting The Hong Kong Polytechnic University. His work is also supported by the Research Grant Council of Hong Kong.     

非光滑方程的方向牛顿法

通过引入广义梯度,将求解含n个未知量方程的方向牛顿法推广到非光滑的情形.证明了该方法在半光滑条件下的收敛性定理,给出了解的存在性以及先验误差界.     

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.     

Generalized Newton’s method based on graphical derivatives

This paper concerns developing a numerical method of the Newton type to solve systems of nonlinear equations described by nonsmooth continuous functions. We propose and justify a new generalized Newton algorithm based on graphical derivatives, which have never been used to derive a Newton-type method for solving nonsmooth equations. Based on advanced techniques of variational analysis and generalized differentiation, we establish the well-posedness of the algorithm, its local superlinear convergence, and its global convergence of the Kantorovich type. Our convergence results hold with no semismoothness and Lipschitzian assumptions, which is illustrated by examples. The algorithm and main results obtained in the paper are compared with well-recognized semismooth and B-differentiable versions of Newton’s method for nonsmooth Lipschitzian equations.     

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.     

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.     

Lagrange optimality system for a class of nonsmooth convex optimization

In this paper, we revisit the augmented Lagrangian method for a class of nonsmooth convex optimization. We present the Lagrange optimality system of the augmented Lagrangian associated with the problems, and establish its connections with the standard optimality condition and the saddle point condition of the augmented Lagrangian, which provides a powerful tool for developing numerical algorithms: we derive a Lagrange–Newton algorithm for the nonsmooth convex optimization, and establish the nonsingularity of the Newton system and the local convergence of the algorithm.     

A verified inexact implicit Runge–Kutta method for nonsmooth ODEs

Structural pounding and oscillations have been extensively investigated by using ordinary differential equations (ODEs). In many applications, force functions are defined by piecewise continuously differentiable functions and the ODEs are nonsmooth. Implicit Runge–Kutta (IRK) methods for solving the nonsmooth ODEs are numerically stable, but involve systems of nonsmooth equations that cannot be solved exactly in practice. In this paper, we propose a verified inexact IRK method for nonsmooth ODEs which gives a global error bound for the inexact solution. We use the slanting Newton method to solve the systems of nonsmooth equations, and interval method to compute the set of matrices of slopes for the enclosure of solution of the systems. Numerical experiments show that the algorithm is efficient for verification of solution of systems of nonsmooth equations in the inexact IRK method. We report numerical results of nonsmooth ODEs arising from simulation of the collapse of the Tacoma Narrows suspension bridge, steel to steel impact experiment, and pounding between two adjacent structures in 27 ground motion records for 12 different earthquakes. This work is partly supported by a Grant-in-Aid from Japan Society for the Promotion of Science and a scholarship from Egyptian Government.     

解奇异非光滑方程组的牛顿法和不精确牛顿法

本文主要解决奇异非光滑方程组的解法。应用一种新的次微分的外逆，我们提出了牛顿法和不精确牛顿法，它们的收敛性同时也得到了证明。这种方法能更容易在一引起实际应用中实现。这种方法可以看作是已存在的解非光滑方程组的方法的延伸。     

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.     

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.     

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.

     

求解非光滑方程组的三次正则化方法

考虑求解非光滑方程组的三次正则化方法及其收敛性分析.利用信赖域方法的技巧,保证该方法是全局收敛的.在子问题非精确求解和BD正则性条件成立的前提下,分析了非光滑三次正则化方法的局部收敛速度.最后,数值实验结果验证了该算法的有效性.