共查询到20条相似文献,搜索用时 140 毫秒
1.
Livinus U. Uko 《Mathematical Programming》1996,73(3):251-268
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. 相似文献
2.
We construct a novel multi-step iterative method for solving systems of nonlinear equations by introducing a parameter θ to generalize the multi-step Newton method while keeping its order of convergence and computational cost. By an appropriate selection of θ, the new method can both have faster convergence and have larger radius of convergence. The new iterative method only requires one Jacobian inversion per iteration, and therefore, can be efficiently implemented using Krylov subspace methods. The new method can be used to solve nonlinear systems of partial differential equations, such as complex generalized Zakharov systems of partial differential equations, by transforming them into systems of nonlinear equations by discretizing approaches in both spatial and temporal independent variables such as, for instance, the Chebyshev pseudo-spectral discretizing method. Quite extensive tests show that the new method can have significantly faster convergence and significantly larger radius of convergence than the multi-step Newton method. 相似文献
3.
Exact penalties for variational inequalities with applications to nonlinear complementarity problems
Thiago A. de André Paulo J. S. Silva 《Computational Optimization and Applications》2010,47(3):401-429
In this paper, we present a new reformulation of the KKT system associated to a variational inequality as a semismooth equation.
The reformulation is derived from the concept of differentiable exact penalties for nonlinear programming. The best theoretical
results are presented for nonlinear complementarity problems, where simple, verifiable, conditions ensure that the penalty
is exact. We close the paper with some preliminary computational tests on the use of a semismooth Newton method to solve the
equation derived from the new reformulation. We also compare its performance with the Newton method applied to classical reformulations
based on the Fischer-Burmeister function and on the minimum. The new reformulation combines the best features of the classical
ones, being as easy to solve as the reformulation that uses the Fischer-Burmeister function while requiring as few Newton
steps as the one that is based on the minimum. 相似文献
4.
Alfonso Reinoza 《Mathematical Programming》1985,31(3):307-320
Global Newton methods for computing solutions of nonlinear systems of equations have recently received a great deal of attention.
By using the theory of generalized equations, a homotopy method is proposed to solve problems arising in complementarity and
mathematical programming, as well as in variational inequalities. We introduce the concepts of generalized homotopies and
regular values, characterize the solution sets of such generalized homotopies and prove, under boundary conditions similar
to Smale’s [10], the existence of a homotopy path which contains an odd number of solutions to the problem. We related our
homotopy path to the Newton method for generalized equations developed by Josephy [3]. An interpretation of our results for
the nonlinear programming problem will be given. 相似文献
5.
C. Durazzi 《Journal of Optimization Theory and Applications》2000,104(1):73-90
Interior-point methods have been developed largely for nonlinear programming problems. In this paper, we generalize the global Newton interior-point method introduced in Ref. 1 and we establish a global convergence theory for it, under the same assumptions as those stated in Ref. 1. The generalized algorithm gives the possibility of choosing different descent directions for a merit function so that difficulties due to small steplength for the perturbed Newton direction can be avoided. The particular choice of the perturbation enables us to interpret the generalized method as an inexact Newton method. Also, we suggest a more general criterion for backtracking, which is useful when the perturbed Newton system is not solved exactly. We include numerical experimentation on discrete optimal control problems. 相似文献
6.
关于广义Newton法的收敛性问题 总被引:4,自引:0,他引:4
本文在较弱的条件下,证明了B-可微方程组的广义Newton法的局部超线性收敛性,为该算法直接应用于非线性规划问题、变分不等问题以及非线性互补问题等提供了理论依据。最后,本文给出了广义Newton法付之实践的具体策略。数值结果表明,算法是行之有效的。 相似文献
7.
There recently has been much interest in smoothing Newton method for solving nonlinear complementarity problems. We extend
such method to symmetric cone complementarity problems (SCCP). In this paper, we first investigate a one-parametric class
of smoothing functions in the context of symmetric cones, which contains the Fischer–Burmeister smoothing function and the
CHKS smoothing function as special cases. Then we propose a smoothing Newton method for the SCCP based on the one-parametric
class of smoothing functions. For the proposed method, besides the classical step length, we provide a new step length and
the global convergence is obtained. Finally, preliminary numerical results are reported, which show the effectiveness of the
two step lengthes in the algorithm and provide efficient domains of the parameter for the complementarity problems. 相似文献
8.
The Markov-Bernstein inequalities for generalized Gegenbauer weight are studied. A special basis of the vector space Pn of real polynomials in one variable of degree at most equal to n is proposed. It is produced by quasi-orthogonal polynomials with respect to this generalized Gegenbauer measure. Thanks to this basis the problem to find the Markov-Bernstein constant is separated in two eigenvalue problems. The first has a classical form and we are able to give lower and upper bounds of the Markov-Bernstein constant by using the Newton method and the classical qd algorithm applied to a sequence of orthogonal polynomials. The second is a generalized eigenvalue problem with a five diagonal matrix and a tridiagonal matrix. A lower bound is obtained by using the Newton method applied to the six term recurrence relation produced by the expansion of the characteristic determinant. The asymptotic behavior of an upper bound is studied. Finally, the asymptotic behavior of the Markov-Bernstein constant is O(n2) in both cases. 相似文献
9.
Walter Alt 《Annals of Operations Research》2001,101(1-4):101-117
In a recent paper we proved a mesh-independence principle for Newton's method applied to stable and consistent discretizations of generalized equations. In this paper we introduce a new consistency condition which is easier to check in applications. Using this new condition we show that the mesh-independence principle holds for the Lagrange–Newton method applied to nonlinear optimal control problems with mixed control-state constraints and their discretizations by Euler's method or Ritz type methods. 相似文献
10.
N. N. Kalitkin I. P. Poshivailo 《Computational Mathematics and Mathematical Physics》2008,48(7):1113-1118
Newton’s method is most frequently used to find the roots of a nonlinear algebraic equation. The convergence domain of Newton’s method can be expanded by applying a generalization known as the continuous analogue of Newton’s method. For the classical and generalized Newton methods, an effective root-finding technique is proposed that simultaneously determines root multiplicity. Roots of high multiplicity (up to 10) can be calculated with a small error. The technique is illustrated using numerical examples. 相似文献
11.
In this paper, we propose a regularized version of the generalized
NCP-function proposed by Hu, Huang and Chen [J. Comput. Appl. Math., 230 (2009),
pp. 69-82]. Based on
this regularized function, we propose a semismooth Newton method for
solving nonlinear complementarity problems, where a non-monotone
line search scheme is used. In particular, we show that the proposed
non-monotone method is globally and locally superlinearly
convergent under suitable assumptions. We test the
proposed method by solving the test problems from MCPLIB.
Numerical experiments indicate that this algorithm has better
numerical performance in the case of $p=5$ and $\theta\in[0.25,075]$ than other cases. 相似文献
12.
徐勤亚 《应用数学与计算数学学报》2002,16(2):68-72
牛顿法是求解非线性方程F(x)=0的一种经典方法。在一般假设条件下,牛顿法只具有局部收敛性。本文证明了一维凸函数牛顿法的全局收敛性,并且给出了它在全局优化积分水平集方法中的应用。 相似文献
13.
In this paper, we present a hybrid method for the solution of a class of composite semismooth equations encountered frequently in applications. The method is obtained by combining a generalized finite-difference Newton method to an inexpensive direct search method. We prove that, under standard assumptions, the method is globally convergent with a local rate of convergence which is superlinear or quadratic. We report also several numerical results obtained applying the method to suitable reformulations of well-known nonlinear complementarity problems. 相似文献
14.
M. D. Smooke 《Journal of Optimization Theory and Applications》1983,39(4):489-511
The solution of nonlinear, two-point boundary value problems by Newton's method requires the formation and factorization of a Jacobian matrix at every iteration. For problems in which the cost of performing these operations is a significant part of the cost of the total calculation, it is natural to consider using the modified Newton method. In this paper, we derive an error estimate which enables us to determine an upper bound for the size of the sequence of modified Newton iterates, assuming that the Kantorovich hypotheses are satisfied. As a result, we can efficiently determine when to form a new Jacobian and when to continue the modified Newton algorithm. We apply the result to the solution of several nonlinear, two-point boundary value problems occurring in combustion. 相似文献
15.
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. 相似文献
16.
Tanabe (1988) proposed a variation of the classical Newton method for solving nonlinear systems of equations, the so-called Centered Newton
method. His idea was based on a deviation of the Newton direction towards a variety called “Central Variety”. In this paper
we prove that the Centered Newton method is locally convergent and we present a globally convergent method based on the centered
direction used by Tanabe. We show the effectiveness of our proposal for solving nonlinear system of equations and compare
with the Newton method with line search. 相似文献
17.
Optimal control problems involving PDEs often lead in practice to the numerical computation of feedback laws for an optimal control. This is achieved through the solution of a Riccati equation which can be large scale, since the discretized problems are large scale and require special attention in their numerical solution. The Kleinman-Newton method is a classical way to solve an algebraic Riccati equation. We look at two versions of an extension of this method to an inexact Newton method. It can be shown that these two implementable versions of Newton's method are identical in the exact case, but differ substantially for the inexact Newton method. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
18.
We investigate local and semi-local convergence of the combined Newton-Kurchatov method under the classical and generalized Lipschitz conditions for solving nonlinear equations. The convergence order of the method is examined and the uniqueness ball for the solution of the nonlinear equation is proved. Numerical experiments are conducted on test problems. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
19.
Seppo Pulkkinen Marko M. Mäkelä Napsu Karmitsa 《Computational Optimization and Applications》2014,57(1):129-165
In practical applications related to, for instance, machine learning, data mining and pattern recognition, one is commonly dealing with noisy data lying near some low-dimensional manifold. A well-established tool for extracting the intrinsically low-dimensional structure from such data is principal component analysis (PCA). Due to the inherent limitations of this linear method, its extensions to extraction of nonlinear structures have attracted increasing research interest in recent years. Assuming a generative model for noisy data, we develop a probabilistic approach for separating the data-generating nonlinear functions from noise. We demonstrate that ridges of the marginal density induced by the model are viable estimators for the generating functions. For projecting a given point onto a ridge of its estimated marginal density, we develop a generalized trust region Newton method and prove its convergence to a ridge point. Accuracy of the model and computational efficiency of the projection method are assessed via numerical experiments where we utilize Gaussian kernels for nonparametric estimation of the underlying densities of the test datasets. 相似文献
20.
In this paper, we focus on solving a class of nonlinear complementarity problems with non-Lipschitzian functions. We first introduce a generalized class of smoothing functions for the plus function. By combining it with Robinson's normal equation, we reformulate the complementarity problem as a family of parameterized smoothing equations. Then, a smoothing Newton method combined with a new nonmonotone line search scheme is employed to compute a solution of the smoothing equations. The global and local superlinear convergence of the proposed method is proved under mild assumptions. Preliminary numerical results obtained applying the proposed approach to nonlinear complementarity problems arising in free boundary problems are reported. They show that the smoothing function and the nonmonotone line search scheme proposed in this paper are effective. 相似文献