A smoothing Newton method for mathematical programs governed by second-order cone constrained generalized equations

In this paper, we consider a class of mathematical programs governed by second-order cone constrained parameterized generalized equations. We reformulate the necessary optimality conditions as a system of nonsmooth equations under linear independence constraint qualification and the strict complementarity condition. A set of second order sufficient conditions is proposed, which is proved to be sufficient for the second order growth of the stationary point. The smoothing Newton method in [40] is employed to solve the system of nonsmooth equations whose strongly BD-regularity at a solution point is demonstrated under the second order sufficient conditions. Several illustrative examples are provided and discussed.     

Enlarging the domain of starting points for Newton’s method under center conditions on the first Fréchet-derivative

We analyze the semilocal convergence of Newton’s method under center conditions on the first Fréchet-derivative of the operator involved. We see that we can extend the known results so far, since we provide different starting points from the point where the first Fréchet-derivative is centered (that is the situation usually considered by other authors), so that the domain of starting points is enlarged for Newton’s method. We also illustrate the theoretical results obtained with some mildly nonlinear elliptic equations.     

非线性系统周期解不动点迭代法

本文提出一种求解非线性系统周期解的数值方法。首先对非线性自治系统和非自治系统给出不同的点映射定义。其次指出用线性映射逼近原非线性映射,而线性映射是由非线性映射插值获得的。继而求取线性映射的不动点,作为原系统不动点的近似解。如不满足精度则作为下次映射的初始点。本文还提出了研究周期解稳定性的相应方法。     

Convergence rate of solutions toward stationary solutions to the compressible Navier-Stokes equation in a half line

We study a large time behavior of a solution to the initial boundary value problem for an isentropic and compressible viscous fluid in a one-dimensional half space. The unique existence and the asymptotic stability of a stationary solution are proved by S. Kawashima, S. Nishibata and P. Zhu for an outflow problem where the fluid blows out through the boundary. The main concern of the present paper is to investigate a convergence rate of a solution toward the stationary solution. For the supersonic flow at spatial infinity, we obtain an algebraic or an exponential decay rate. Precisely, if an initial perturbation decays with the algebraic or the exponential rate in the spatial asymptotic point, the solution converges to the corresponding stationary solution with the same rate in time as time tends to infinity. An algebraic convergence rate is also obtained for the transonic flow. These results are proved by the weighted energy method.     

Analytic construction of the near field in a transonic flow near a thin axisymmetric body

A solution of the axisymmetric problem of unsteady transonic flow around thin bodies of revolution is proposed in the form of a double series expansion in powers of the distance to the axis of symmetry and its logarithm in a neighborhood of a given point at the symmetry axis. Chains of recurrence equations are obtained for the coefficients of the series. The convergence of the constructed series is proved by the method of special majorants. The theorem of existence and uniqueness of the solution to the boundary-value problem for a nonlinear partial differential equation with a singularity at the symmetry axis is obtained in the asymptotic model of unsteady transonic flow under consideration. Thereby the application of the proposed series is justified to the problems of unsteady transonic flow around thin axisymmetric bodies with a drift of the nonpenetration condition onto the symmetry axis. Hence, these series can be used in numerical-analytical methods and model computations.     

Parametrizations of Kojima’s system and relations to penalty and barrier functions

We investigate two homotopies that perturb Kojima’s system for describing critical points of a nonlinear optimization problem in finite dimension. Each of them characterizes stationary points of a usual penalty and a new “barrier” function. The latter is a continuous deformation of the objective, symmetric to the penalty from a formal point of view. Stationary points of these functions appear as perturbed critical points and vice versa. This permits new interpretations of the related solution methods and allows estimates of the solutions by using implicit function theorems for Lipschitzian equations.     

Generalized Kojima–Functions and Lipschitz Stability of Critical Points

In this paper we consider systems of equations which are defined by nonsmooth functions of a special structure. Functions of this type are adapted from Kojima's form of the Karush–Kuhn–Tucker conditions for C²—optimization problems. We shall show that such systems often represent conditions for critical points of variational problems (nonlinear programs, complementarity problems, generalized equations, equilibrium problems and others). Our main purpose is to point out how different concepts of generalized derivatives lead to characterizations of different Lipschitz properties of the critical point or the stationary solution set maps.     

Transonic nozzle flows and free boundary problems for the full Euler equations

We establish the existence and uniqueness of transonic flows with a transonic shock through a two-dimensional nozzle of slowly varying cross-sections. The transonic flow is governed by the steady, full Euler equations. Given an incoming smooth flow that is close to a constant supersonic state (i.e., smooth Cauchy data) at the entrance and the subsonic condition with nearly horizontal velocity at the exit of the nozzle, we prove that there exists a transonic flow whose downstream smooth subsonic region is separated by a smooth transonic shock from the upstream supersonic flow. This problem is approached by a one-phase free boundary problem in which the transonic shock is formulated as a free boundary. The full Euler equations are decomposed into an elliptic equation and a system of transport equations for the free boundary problem. An iteration scheme is developed and its fixed point is shown to exist, which is a solution of the free boundary problem, by combining some delicate estimates for the elliptic equation and the system of transport equations with the Schauder fixed point argument. The uniqueness of transonic nozzle flows is also established by employing the coordinate transformation of Euler-Lagrange type and detailed estimates of the solutions.     

A semismooth Newton method for SOCCPs based on a one-parametric class of SOC complementarity functions

In this paper, we present a detailed investigation for the properties of a one-parametric class of SOC complementarity functions, which include the globally Lipschitz continuity, strong semismoothness, and the characterization of their B-subdifferential. Moreover, for the merit functions induced by them for the second-order cone complementarity problem (SOCCP), we provide a condition for each stationary point to be a solution of the SOCCP and establish the boundedness of their level sets, by exploiting Cartesian P-properties. We also propose a semismooth Newton type method based on the reformulation of the nonsmooth system of equations involving the class of SOC complementarity functions. The global and superlinear convergence results are obtained, and among others, the superlinear convergence is established under strict complementarity. Preliminary numerical results are reported for DIMACS second-order cone programs, which confirm the favorable theoretical properties of the method.     

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…     

Numerical experience with the truncated Newton method for unconstrained optimization

The truncated Newton algorithm was devised by Dembo and Steihaug (Ref. 1) for solving large sparse unconstrained optimization problems. When far from a minimum, an accurate solution to the Newton equations may not be justified. Dembo's method solves these equations by the conjugate direction method, but truncates the iteration when a required degree of accuracy has been obtained. We present favorable numerical results obtained with the algorithm and compare them with existing codes for large-scale optimization.     

Projektive Newton-Verfahren und Anwendungen auf nichtlineare Randwertaufgaben

Summary In this paper we consider the following Newton-like methods for the solution of nonlinear equations. In each step of the Newton method the linear equations are solved approximatively by a projection method. We call this a Projective Newton method. For a fixed projection method the approximations often are the same as those of the Newton method applied to a nonlinear projection method. But the efficiency can be increased by adapting the accuracy of the projection method to the convergence of the approximations. We investigate the convergence and the order of convergence for these methods. The results are applied to some Projective Newton methods for nonlinear two point boundary value problems. Some numerical results indicate the efficiency of these methods.

     

解非线性约束方程的拉格朗日全局投影方法

基于最优化方法求解约束非线性方程组的一个突出困难是计算 得到的仅是该优化问题的稳定点或局部极小点,而非方程组的解点.由此引出的问题是如何从一个稳定点出发得到一个相对于方程组解更好的点. 该文采用投影型算法,推广了Nazareth-Qi$^{[8,9]}$ 求解无约束非线性方程组的拉格朗日全局算法(Lagrangian Global-LG)于约束方程上; 理论上证明了从优化问题的稳定点出发,投影LG方法可寻找到一个更好的点. 数值试验证明了LG方法的有效性.     

Finite element method in the solution of the Euler and Navier-Stokes equations for internal flow

Finite element solutions of the Euler and Navier-Stokes equations are presented, using a simple dissipation model. The discretization is based on the weak-Galerkin weighted residual method and equal interpolation functions for all the unknowns are permitted. The nonlinearity is iterated upon using a Newton method and at each iteration the linear algebraic system is solved by a direct solver with all unknowns fully coupled. Results are presented for two-dimensional transonic inviscid flows and two- and three-dimensional incompressible viscous flows. Convergence of the algorithm is shown to be quadratic, reaching machine accuracy in very few iterations. The inviscid results demonstrate the existence of nonunique numerical solutions to the steady Euler equations.     

Truncated Newton method for sparse unconstrained optimization using automatic differentiation

When solving large complex optimization problems, the user is faced with three major problems. These are (i) the cost in human time in obtaining accurate expressions for the derivatives involved; (ii) the need to store second derivative information; and (iii), of lessening importance, the time taken to solve the problem on the computer. For many problems, a significant part of the latter can be attributed to solving Newton-like equations. In the algorithm described, the equations are solved using a conjugate direction method that only needs the Hessian at the current point when it is multiplied by a trial vector. In this paper, we present a method that finds this product using automatic differentiation while only requiring vector storage. The method takes advantage of any sparsity in the Hessian matrix and computes exact derivatives. It avoids the complexity of symbolic differentiation, the inaccuracy of numerical differentiation, the labor of finding analytic derivatives, and the need for matrix store. When far from a minimum, an accurate solution to the Newton equations is not justified, so an approximate solution is obtained by using a version of Dembo and Steihaug's truncated Newton algorithm (Ref. 1).This paper was presented at the SIAM National Meeting, Boston, Massachusetts, 1986.     

On inexact Newton methods based on doubling iteration scheme for non‐symmetric algebraic Riccati equations

Newton iteration method can be used to find the minimal non‐negative solution of a certain class of non‐symmetric algebraic Riccati equations. However, a serious bottleneck exists in efficiency and storage for the implementation of the Newton iteration method, which comes from the use of some direct methods in exactly solving the involved Sylvester equations. In this paper, instead of direct methods, we apply a fast doubling iteration scheme to inexactly solve the Sylvester equations. Hence, a class of inexact Newton iteration methods that uses the Newton iteration method as the outer iteration and the doubling iteration scheme as the inner iteration is obtained. The corresponding procedure is precisely described and two practical methods of monotone convergence are algorithmically presented. In addition, the convergence property of these new methods is studied and numerical results are given to show their feasibility and effectiveness for solving the non‐symmetric algebraic Riccati equations. Copyright © 2010 John Wiley & Sons, Ltd.     

New reformulation and feasible semismooth Newton method for a class of stochastic linear complementarity problems

A class of stochastic linear complementarity problems (SLCPs) with finitely many realizations is considered. We first formulate the problem as a new constrained minimization problem. Then, we propose a feasible semismooth Newton method which yields a stationary point of the constrained minimization problem. We study the condition for the level set of the objective function to be bounded. As a result, the condition for the solution set of the constrained minimization problem is obtained. The global and quadratic convergence of the proposed method is proved under certain assumptions. Preliminary numerical results show that this method yields a reasonable solution with high safety and within a small number of iterations.     

A stabilized multi-level method for non-singular finite volume solutions of the stationary 3D Navier–Stokes equations

This paper proposes and analyzes a stabilized multi-level finite volume method (FVM) for solving the stationary 3D Navier?CStokes equations by using the lowest equal-order finite element pair without relying on any solution uniqueness condition. This multi-level stabilized FVM consists of solving the nonlinear problem on the coarsest mesh and then performing one Newton correction step on each subsequent mesh, thus only solving a large linear system. An optimal convergence rate for the finite volume approximations of nonsingular solutions is first obtained with the same order as that for the usual finite element solution by using a relationship between the stabilized FVM and a stabilized finite element method. Then the multi-level finite volume approximate solution is shown to have a convergence rate of the same order as that of the stabilized finite volume solution of the stationary Navier?CStokes equations on a fine mesh with an appropriate choice of the mesh size: ${ h_{j} ~ h_{j-1}^{2}, j = 1,\ldots, J}$ . Finally, numerical results presented validate our theoretical findings.     

Preconditioners for Incompressible Navier-Stokes Solvers

<正>In this paper we give an overview of the present state of fast solvers for the solution of the incompressible Navier-Stokes equations discretized by the finite element method and linearized by Newton or Picard's method.It is shown that block preconditioners form an excellent approach for the solution,however if the grids are not to fine preconditioning with a Saddle point ILU matrix(SILU) may be an attractive alternative. The applicability of all methods to stabilized elements is investigated.In case of the stand-alone Stokes equations special preconditioners increase the efficiency considerably.     

一类奇摄动非线性边值问题激波解的Sinc—Galerkin方法

讨论了一类非线性奇摄动方程的激波问题．利用Sinc—Galerkin方法,构造出边值问题的激波解,并由Newton法得到其近似解．