共查询到20条相似文献,搜索用时 359 毫秒
1.
Global and Finite Convergence of a Generalized Newton Method for Absolute Value Equations 总被引:1,自引:0,他引:1
We investigate an efficient method for solving the absolute value equation Ax−|x|=b when the interval matrix [A−I,A+I] is regular. A generalized Newton method which combines the semismooth and the smoothing Newton steps is proposed. We establish
global and finite convergence of the method. Preliminary numerical results indicate that the generalized Newton method is
promising. 相似文献
2.
El-Alem M. M. El-Sayed S. El-Sobky B. 《Journal of Optimization Theory and Applications》2004,120(3):487-502
In this paper, a formulation for an interior-point Newton method of general nonlinear programming problems is presented. The formulation uses the Coleman-Li scaling matrix. The local convergence and the q-quadratic rate of convergence for the method are established under the standard assumptions of the Newton method for general nonlinear programming. 相似文献
3.
Smoothing Newton methods for nonlinear complementarity problems NCP(F) often require F to be at least a P
0-function in order to guarantee that the underlying Newton equation is solvable. Based on a special equation reformulation of NCP(F), we propose a new smoothing Newton method for general nonlinear complementarity problems. The introduction of Kanzow and Pieper's gradient step makes our algorithm to be globally convergent. Under certain conditions, our method achieves fast local convergence rate. Extensive numerical results are also reported for all complementarity problems in MCPLIB and GAMSLIB libraries with all available starting points. 相似文献
4.
Yinnian He Yan Zhang Yueqiang Shang Hui Xu 《Numerical Methods for Partial Differential Equations》2012,28(5):1620-1642
A combination method of the Newton iteration and two‐level finite element algorithm is applied for solving numerically the steady Navier‐Stokes equations under the strong uniqueness condition. This algorithm is motivated by applying the m Newton iterations for solving the Navier‐Stokes problem on a coarse grid and computing the Stokes problem on a fine grid. Then, the uniform stability and convergence with respect to ν of the two‐level Newton iterative solution are analyzed for the large m and small H and h << H. Finally, some numerical tests are made to demonstrate the effectiveness of the method. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2012 相似文献
5.
Efficient dynamic programming implementations of Newton's method for unconstrained optimal control problems 总被引:1,自引:0,他引:1
Naive implementations of Newton's method for unconstrainedN-stage discrete-time optimal control problems with Bolza objective functions tend to increase in cost likeN
3 asN increases. However, if the inherent recursive structure of the Bolza problem is properly exploited, the cost of computing a Newton step will increase only linearly withN. The efficient Newton implementation scheme proposed here is similar to Mayne's DDP (differential dynamic programming) method but produces the Newton step exactly, even when the dynamical equations are nonlinear. The proposed scheme is also related to a Riccati treatment of the linear, two-point boundary-value problems that characterize optimal solutions. For discrete-time problems, the dynamic programming approach and the Riccati substitution differ in an interesting way; however, these differences essentially vanish in the continuous-time limit.This work was supported by the National Science Foundation, Grant No. DMS-85-03746. 相似文献
6.
An n-by-n real matrix is called a Newton matrix (and its eigenvalues a Newton spectrum) if the normalized coefficients of its characteristic polynomial satisfy the Newton inequalities.A number of basic observations are made about Newton matrices, including closure under inversion, and then it is shown that a Newton matrix with nonnegative coefficients remains Newton under right translations. Those matrices that become (and stay) Newton under translation are characterized. In particular, Newton spectra in low dimensions are characterized. 相似文献
7.
Joseph W. Jerome 《Numerische Mathematik》1989,55(6):619-632
Summary An approximate Newton method, based upon the fixed point mapT, is introduced for scalar gradient equations. Although the exact Newton method coincides for such scalar equations with the standard iteration, the structure of the fixed point map provides a way of defining anR-quadratically convergent finite element iteration in the spirit of the Kantorovich theory. The loss of derivatives phenomenon, typically experienced in approximate Newton methods, is thereby avoided. It is found that two grid parameters are sssential,h and
. The latter is used to calculate the approximate residual, and is isolated as a fractional step; it is equivalent to the approximation ofT. The former is used to calculate the Newton increment, and this is equivalent to the approximation ofT. The complexity of the finite element computation for the Newton increment is shown to be of optimal order, via the Vitukin inequality relating metric entropy andn-widths.Research supported by National Science Foundation grant DMS-8721742 相似文献
8.
Stephen J. Wright 《Mathematical Programming》2001,90(1):71-100
In the Newton/log-barrier method, Newton steps are taken for the log-barrier function for a fixed value of the barrier parameter
until a certain convergence criterion is satisfied. The barrier parameter is then decreased and the Newton process is repeated.
A naive analysis indicates that Newton’s method does not exhibit superlinear convergence to the minimizer of each instance
of the log-barrier function until it reaches a very small neighborhood, namely within O(μ2) of the minimizer, where μ is the barrier parameter. By analyzing the structure of the barrier Hessian and gradient in terms
of the subspace of active constraint gradients and the associated null space, we show that this neighborhood is in fact much
larger –O(μσ) for any σ∈(1,2] – thus explaining why reasonably fast local convergence can be attained in practice. Moreover, we show that
the overall convergence rate of the Newton/log-barrier algorithm is superlinear in the number of function/derivative evaluations,
provided that the nonlinear program is formulated with a linear objective and that the schedule for decreasing the barrier
parameter is related in a certain way to the step length and convergence criteria for each Newton process.
Received: October 10, 1997 / Accepted: September 10, 2000?Published online February 22, 2001 相似文献
9.
We formulate a locally superlinearly convergent projected Newton method for constrained minimization in a Cartesian product of balls. For discrete-time,N-stage, input-constrained optimal control problems with Bolza objective functions, we then show how the required scaled tangential component of the objective function gradient can be approximated efficiently with a differential dynamic programming scheme; the computational cost and the storage requirements for the resulting modified projected Newton algorithm increase linearly with the number of stages. In calculations performed for a specific control problem with 10 stages, the modified projected Newton algorithm is shown to be one to two orders of magnitude more efficient than a standard unscaled projected gradient method.This work was supported by the National Science Foundation, Grant No. DMS-85-03746. 相似文献
10.
M. C. Recchioni 《Journal of Optimization Theory and Applications》1995,86(1):223-244
The modified Newton method for multiple roots is organized in an interval method to include simultaneously the distinct roots of a given polynomialP in complex circular interval arithmetic. A condition on the starting disks which ensures convergence is given, and convergence is shown to be quadratic. As a consequence, a simple parallel algorithm to approach all the distinct roots ofP is derived from the modified Newton method.The research reported in this paper has been made possible through the support and the sponsorship of the Italian Government through the Ministero per l'Universitá e la Ricerca Scientifica under Contract MURST 60%, 1990 at the Universitá di L'Aquila. 相似文献
11.
An equivalent model of nonsmooth equations for a constrained minimax problem is derived by using a KKT optimality condition. The Newton method is applied to solving this system of nonsmooth equations. To perform the Newton method, the computation of an element of the b-differential for the corresponding function is developed.This work has been supported by Shanghai Education Committee (04EA01).This revised version was published online in April 2005 with a corrected missing date string. 相似文献
12.
Numerical solution of a two-dimensional nonlinear singularly perturbed elliptic partial differential equation ∈ Δu = f(x, u), 0 < x, y < 1, with Dirichlet boundary condition is discussed here. The modified Newton method of third-order convergence is employed
to linearize the nonlinear problem in place of the standard Newton method. The finite-element method is used to find the solution
of the nonlinear differential equation. Numerical results are provided to demonstrate the usefulness of the method. 相似文献
13.
Kristian Witsch 《Numerische Mathematik》1978,30(3):333-347
Summary In this paper we investigate projective Newton methods for nonlinear elliptic boundary value problems. These methods yield approximations by solving the linear equations of the Newton method by a projection method, e.g. the Ritz method. Using subspaces of finite elements or polynominals we obtain error estimates and optimal convergence theorems (inH
1 andL
2). 相似文献
14.
We propose a new smoothing Newton method for solving the P
0-matrix linear complementarity problem (P
0-LCP) based on CHKS smoothing function. Our algorithm solves only one linear system of equations and performs only one line search per iteration. It is shown to converge to a P
0-LCP solution globally linearly and locally quadratically without the strict complementarity assumption at the solution. To the best of author's knowledge, this is the first one-step smoothing Newton method to possess both global linear and local quadratic convergence. Preliminary numerical results indicate that the proposed algorithm is promising. 相似文献
15.
N. L. Schryer 《Numerische Mathematik》1971,17(4):284-300
Summary Newton's method is applied to solving the boundary value problem for the equationLu=f(x,u) whereL is a linear second order uniformly elliptic operator andf(x,u) is a convex monotone increasing function ofu for each pointx in the domainD. The Newton iterates are shown to converge uniformly, quadratically and monotonically downward to the solution of the problem. The convergence is independent of the choice for the initial Newton iterate. Numerical results are presented for several problems of physical interest. 相似文献
16.
In this paper, the augmented Lagrangian SQP method is considered for the numerical solution of optimization problems with equality constraints. The problem is formulated in a Hilbert space setting. Since the augmented Lagrangian SQP method is a type of Newton method for the nonlinear system of necessary optimality conditions, it is conceivable that q-quadratic convergence can be shown to hold locally in the pair (x, ). Our interest lies in the convergence of the variable x alone. We improve convergence estimates for the Newton multiplier update which does not satisfy the same convergence properties in x as for example the least-square multiplier update. We discuss these updates in the context of parameter identification problems. Furthermore, we extend the convergence results to inexact augmented Lagrangian methods. Numerical results for a control problem are also presented. 相似文献
17.
Mihai Anitescu Dan I Coroian M. Zuhair Nashed Florian A Potra 《Numerical Functional Analysis & Optimization》2013,34(7-8):661-678
In this paper, a numerical method for solving overdetermined differential algebraic equations that arise in multi body dynamics is proposed. The method is based on Newton type iterations using outer inverses. We prove that the ssf method and tangent space parametrization can be regarded as particular cases of our method 相似文献
18.
Mario A. Casarin 《Numerische Mathematik》2001,89(2):307-339
Summary. The - spectral element discretization of the Stokes equation gives rise to an ill-conditioned, indefinite, symmetric linear system
for the velocity and pressure degrees of freedom. We propose a domain decomposition method which involves the solution of
a low-order global, and several local problems, related to the vertices, edges, and interiors of the subdomains. The original
system is reduced to a symmetric equation for the velocity, which can be solved with the conjugate gradient method. We prove
that the condition number of the iteration operator is bounded from above by , where C is a positive constant independent of the degree N and the number of subdomains, and is the inf-sup condition of the pair -. We also consider the stationary Navier-Stokes equations; in each Newton step, a non-symmetric indefinite problem is solved
using a Schwarz preconditioner. By using an especially designed low-order global space, and the solution of local problems
analogous to those decribed above for the Stokes equation, we are able to present a complete theory for the method. We prove
that the number of iterations of the GMRES method, at each Newton step, is bounded from above by . The constant C does not depend on the number of subdomains or N, and it does not deteriorate as the Newton iteration proceeds.
Received March 2, 1998 / Revised version received October 12, 1999 / Published online March 20, 2001 相似文献
19.
The Q method of semidefinite programming, developed by Alizadeh, Haeberly and Overton, is extended to optimization problems over
symmetric cones. At each iteration of the Q method, eigenvalues and Jordan frames of decision variables are updated using Newton’s method. We give an interior point
and a pure Newton’s method based on the Q method. In another paper, the authors have shown that the Q method for second-order cone programming is accurate. The Q method has also been used to develop a “warm-starting” approach for second-order cone programming. The machinery of Euclidean
Jordan algebra, certain subgroups of the automorphism group of symmetric cones, and the exponential map is used in the development
of the Newton method. Finally we prove that in the presence of certain non-degeneracies the Jacobian of the Newton system
is nonsingular at the optimum. Hence the Q method for symmetric cone programming is accurate and can be used to “warm-start” a slightly perturbed symmetric cone program. 相似文献
20.
E. T. Beazley 《Mathematische Zeitschrift》2009,263(3):499-540
We study the Newton stratification on SL
3(F), where F is a Laurent power series field. We provide a formula for the codimensions of the Newton strata inside each component of
the affine Bruhat decomposition on SL
3(F). These calculations are related to the study of certain affine Deligne–Lusztig varieties. In particular, we describe a method
for determining which of these varieties is non-empty in the case of SL
3(F). 相似文献