共查询到20条相似文献,搜索用时 15 毫秒
1.
A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems 总被引:14,自引:0,他引:14
A new algorithm for the solation of large-scale nonlinear complementarity problems is introduced. The algorithm is based on
a nonsmooth equation reformulation of the complementarity problem and on an inexact Levenberg-Marquardt-type algorithm for
its solution. Under mild assumptions, and requiring only the approximate solution of a linear system at each iteration, the
algorithm is shown to be both globally and superlinearly convergent, even on degenerate problems. Numerical results for problems
with up to 10 000 variables are presented.
Partially supported by Agenzia Spaziale Italiana, Roma, Italy. 相似文献
2.
X. Chen 《Annals of the Institute of Statistical Mathematics》1990,42(2):387-401
In this paper, the author studies a Broyden-like method for solving nonlinear equations with nondifferentiable terms, which uses as updating matrices, approximations for Jacobian matrices of differentiable terms. Local and semilocal convergence theorems are proved. The results generalize those of Broyden, Dennis and Moré. 相似文献
3.
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. 相似文献
4.
In this paper, we present a convergence analysis of the inexact Newton method for solving Discrete-time algebraic Riccati equations (DAREs) for large and sparse systems. The inexact Newton method requires, at each iteration, the solution of a symmetric Stein matrix equation. These linear matrix equations are solved approximatively by the alternating directions implicit (ADI) or Smith?s methods. We give some new matrix identities that will allow us to derive new theoretical convergence results for the obtained inexact Newton sequences. We show that under some necessary conditions the approximate solutions satisfy some desired properties such as the d-stability. The theoretical results developed in this paper are an extension to the discrete case of the analysis performed by Feitzinger et al. (2009) [8] for the continuous-time algebraic Riccati equations. In the last section, we give some numerical experiments. 相似文献
5.
借助于一种新的微分 - -微分 ,本文给出极大值函数及其光滑复合的非光滑方程组的牛顿法 .最后证明了该牛顿法具有全局收敛性 . 相似文献
6.
Márcia A. Gomes-Ruggiero Véra Lucia Rocha Lopes Julia Victoria Toledo-Benavides 《Annals of Operations Research》2008,157(1):193-205
In inexact Newton methods for solving nonlinear systems of equations, an approximation to the step s
k
of the Newton’s system J(x
k
)s=−F(x
k
) is found. This means that s
k
must satisfy a condition like ‖F(x
k
)+J(x
k
)s
k
‖≤η
k
‖F(x
k
)‖ for a forcing term η
k
∈[0,1). Possible choices for η
k
have already been presented. In this work, a new choice for η
k
is proposed. The method is globalized using a robust backtracking strategy proposed by Birgin et al. (Numerical Algorithms
32:249–260, 2003), and its convergence properties are proved. Several numerical experiments with boundary value problems are presented. The
numerical performance of the proposed algorithm is analyzed by the performance profile tool proposed by Dolan and Moré (Mathematical
Programming Series A 91:201–213, 2002). The results obtained show a competitive inexact Newton method for solving academic and applied problems in several areas.
Supported by FAPESP, CNPq, PRONEX-Optimization. 相似文献
7.
Y. Gao 《Journal of Optimization Theory and Applications》2006,131(3):417-428
The Newton method and the inexact Newton method for solving quasidifferentiable equations via the quasidifferential are investigated. The notion of Q-semismoothness for a quasidifferentiable function is proposed. The superlinear convergence of the Newton method proposed by Zhang and Xia is proved under the Q-semismooth assumption. An inexact Newton method is developed and its linear convergence is shown.Project sponsored by Shanghai Education Committee Grant 04EA01 and by Shanghai Government Grant T0502. 相似文献
8.
Jinhai Chen 《Computational Optimization and Applications》2008,40(1):97-118
In this paper, inexact Gauss–Newton methods for nonlinear least squares problems are studied. Under the hypothesis that derivative
satisfies some kinds of weak Lipschitz conditions, the local convergence properties of inexact Gauss–Newton and inexact Gauss–Newton
like methods for nonlinear problems are established with the modified relative residual control. The obtained results can
provide an estimate of convergence ball for inexact Gauss–Newton methods. 相似文献
9.
Liu YangYanping Chen Xiaojiao TongChunlin Deng 《Applied mathematics and computation》2011,217(24):9855-9863
In this paper, a new smoothing Newton method is proposed for solving constrained nonlinear equations. We first transform the constrained nonlinear equations to a system of semismooth equations by using the so-called absolute value function of the slack variables, and then present a new smoothing Newton method for solving the semismooth equations by constructing a new smoothing approximation function. This new method is globally and quadratically convergent. It needs to solve only one system of unconstrained equations and to perform one line search at each iteration. Numerical results show that the new algorithm works quite well. 相似文献
10.
In this work we study a class of secant-like iterations for solving nonlinear equations in Banach spaces. We consider a condition for divided differences which generalizes the usual ones, i.e., Lipschitz and Hölder continuous conditions. A semilocal convergence result is obtained for nondifferentiable operators. For that, we use a technique based on a new system of recurrence relations to obtain domains of existence and uniqueness of the solution. Finally, we apply our results to the numerical solution of several examples. 相似文献
11.
We prove that under semi-local assumptions, the inexact Newton method with a fixed relative residual error tolerance converges Q-linearly to a zero of the nonlinear operator under consideration. Using this result we show that the Newton method for minimizing a self-concordant function or to find a zero of an analytic function can be implemented with a fixed relative residual error tolerance. 相似文献
12.
Zhen-Jun Shi 《Journal of Mathematical Analysis and Applications》2006,315(1):120-131
Quasi-Newton method is a well-known effective method for solving optimization problems. Since it is a line search method, which needs a line search procedure after determining a search direction at each iteration, we must decide a line search rule to choose a step size along a search direction. In this paper, we propose a new inexact line search rule for quasi-Newton method and establish some global convergent results of this method. These results are useful in designing new quasi-Newton methods. Moreover, we analyze the convergence rate of quasi-Newton method with the new line search rule. 相似文献
13.
M. Verani 《Applied Mathematics Letters》2003,16(8):1301-1306
For the solution of nonlinear equations, we present an adaptive wavelet scheme, which couples an inexact Newton method and the idea of nonlinear wavelet approximation. In particular, we obtain a result of quadratic convergence. 相似文献
14.
Marek J. Śmietański 《Numerical Algorithms》2013,63(1):89-106
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. 相似文献
15.
In this paper, we prove that the order of a new secant-like method presented recently with the so-called order of 2.618 is only 2.414. Some mistakes in the derivation leading to such a conclusion are pointed out. Meanwhile, under the assumption that the second derivative of the involved function is bounded, the convergence radius of the secant-like method is given, and error estimates matching its convergence order are also provided by using a generalized Fibonacci sequence. 相似文献
16.
提出一类对称张量绝对值方程问题,给出了求解此类问题的一类非光滑牛顿法,并且在一般的假设条件下,给出了算法的局部收敛性.最后给出相关的数值实验表明了算法的有效性. 相似文献
17.
Parallel iterative methods are powerful in solving large systems of linear equations (LEs). The existing parallel computing research results focus mainly on sparse systems or others with particular structure. Most are based on parallel implementation of the classical relaxation methods such as Gauss-Seidel, SOR, and AOR methods which can be efficiently carried out on multiprocessor system. In this paper, we propose a novel parallel splitting operator method in which we divide the coefficient matrix into two or three parts. Then we convert the original problem (LEs) into a monotone (linear) variational inequality problem (VI) with separable structure. Finally, an inexact parallel splitting augmented Lagrangian method is proposed to solve the variational inequality problem (VI). To avoid dealing with the matrix inverse operator, we introduce proper inexact terms in subproblems such that the complexity of each iteration of the proposed method is O(n2). In addition, the proposed method does not require any special structure of system of LEs under consideration. Convergence of the proposed methods in dealing with two and three separable operators respectively, is proved. Numerical computations are provided to show the applicability and robustness of the proposed methods. 相似文献
18.
本文主要解决奇异非光滑方程组的解法。应用一种新的次微分的外逆,我们提出了牛顿法和不精确牛顿法,它们的收敛性同时也得到了证明。这种方法能更容易在一引起实际应用中实现。这种方法可以看作是已存在的解非光滑方程组的方法的延伸。 相似文献
19.
In this paper, we study the convergence properties of a Newton-type method for solving generalized equations under a majorant condition. To this end, we use a contraction mapping principle. More precisely, we present semi-local convergence analysis of the method for generalized equations involving a set-valued map, the inverse of which satisfying the Aubin property. Our analysis enables us to obtain convergence results under Lipschitz, Smale and Nesterov-Nemirovski's self-concordant conditions. 相似文献