共查询到20条相似文献,搜索用时 31 毫秒
1.
A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities 总被引:17,自引:0,他引:17
In this paper we take a new look at smoothing Newton methods for solving the nonlinear complementarity problem (NCP) and the
box constrained variational inequalities (BVI). Instead of using an infinite sequence of smoothing approximation functions,
we use a single smoothing approximation function and Robinson’s normal equation to reformulate NCP and BVI as an equivalent
nonsmooth equation H(u,x)=0, where H:ℜ
2n
→ℜ
2n
, u∈ℜ
n
is a parameter variable and x∈ℜ
n
is the original variable. The central idea of our smoothing Newton methods is that we construct a sequence {z
k
=(u
k
,x
k
)} such that the mapping H(·) is continuously differentiable at each z
k
and may be non-differentiable at the limiting point of {z
k
}. We prove that three most often used Gabriel-Moré smoothing functions can generate strongly semismooth functions, which
play a fundamental role in establishing superlinear and quadratic convergence of our new smoothing Newton methods. We do not
require any function value of F or its derivative value outside the feasible region while at each step we only solve a linear system of equations and if
we choose a certain smoothing function only a reduced form needs to be solved. Preliminary numerical results show that the
proposed methods for particularly chosen smoothing functions are very promising.
Received June 23, 1997 / Revised version received July 29, 1999?Published online December 15, 1999 相似文献
2.
We study the existence and asymptotic convergence when t→+∞ for the trajectories generated by
where is a parametric family of convex functions which approximates a given convex function f we want to minimize, and ε(t) is a parametrization such that ε(t)→ 0 when t→+∞ . This method is obtained from the following variational characterization of Newton's method:
where H is a real Hilbert space. We find conditions on the approximating family and the parametrization to ensure the norm convergence of the solution trajectories u(t) toward a particular minimizer of f . The asymptotic estimates obtained allow us to study the rate of convergence as well. The results are illustrated through
some applications to barrier and penalty methods for linear programming, and to viscosity methods for an abstract noncoercive
variational problem. Comparisons with the steepest descent method are also provided.
Accepted 5 December 1996 相似文献
3.
We present a new smoothing Newton method for nonlinear complementarity problems (NCP(F)) by using an NCP function to reformulate the problem to its equivalent form. Compared with most current smoothing methods, our method contains an estimating technique based on the active-set strategy. This technique focuses on the identification of the degenerate set for a solution x∗ of the NCP(F). The proposed method has the global convergence, each accumulation point is a solution of the problem. The introduction of the active-set strategy effectively reduces the scale of the problem. Under some regularity assumption, the degenerate set can be identified correctly near the solution and local superlinear convergence is obtained as well. 相似文献
4.
We present an interior-point penalty method for nonlinear programming (NLP), where the merit function consists of a piecewise linear penalty function and an ? 2-penalty function. The piecewise linear penalty function is defined by a set of break points that correspond to pairs of values of the barrier function and the infeasibility measure at a subset of previous iterates and this set is updated at every iteration. The ? 2-penalty function is a traditional penalty function defined by a single penalty parameter. At every iteration the step direction is computed from a regularized Newton system of the first-order equations of the barrier problem proposed in Chen and Goldfarb (Math Program 108:1?C36, 2006). Iterates are updated using a line search. In particular, a trial point is accepted if it provides a sufficient reduction in either of the penalty functions. We show that the proposed method has the same strong global convergence properties as those established in Chen and Goldfarb (Math Program 108:1?C36, 2006). Moreover, our method enjoys fast local convergence. Specifically, for each fixed small barrier parameter???, iterates in a small neighborhood (roughly within o(??)) of the minimizer of the barrier problem converge Q-quadratically to the minimizer. The overall convergence rate of the iterates to the solution of the nonlinear program is Q-superlinear. 相似文献
5.
R. S. Womersley 《Mathematical Programming》1985,32(1):69-89
This paper considers local convergence and rate of convergence results for algorithms for minimizing the composite functionF(x)=f(x)+h(c(x)) wheref andc are smooth buth(c) may be nonsmooth. Local convergence at a second order rate is established for the generalized Gauss—Newton method whenh is convex and globally Lipschitz and the minimizer is strongly unique. Local convergence at a second order rate is established for a generalized Newton method when the minimizer satisfies nondegeneracy, strict complementarity and second order sufficiency conditions. Assuming the minimizer satisfies these conditions, necessary and sufficient conditions for a superlinear rate of convergence for curvature approximating methods are established. Necessary and sufficient conditions for a two-step superlinear rate of convergence are also established when only reduced curvature information is available. All these local convergence and rate of convergence results are directly applicable to nonlinearing programming problems.This work was done while the author was a Research fellow at the Mathematical Sciences Research Centre, Australian National University. 相似文献
6.
Summary Based on a random sample from the normal cumulative distribution function ϕ(x; μ, σ) with unknown parameters μ and σ, one-sided confidence contours for ϕ(x; μ, σ), −∞<x<∞, and simultaneous confidence intervals for ϕ(y; μ, σ)−ϕ(x; μ, σ), −∞<x<y<∞, are constructed using the method outlined in [3]. Small sample and asymptotic distributions of the relevant statistics
are provided so that the construction could be completely carried out in any practical situation. 相似文献
7.
D. Sun 《Applied Mathematics and Optimization》1999,40(3):315-339
In this paper we construct a regularization Newton method for solving the nonlinear complementarity problem (NCP(F )) and analyze its convergence properties under the assumption that F is a P
0
-function. We prove that every accumulation point of the sequence of iterates is a solution of NCP(F ) and that the sequence of iterates is bounded if the solution set of NCP(F ) is nonempty and bounded. Moreover, if F is a monotone and Lipschitz continuous function, we prove that the sequence of iterates is bounded if and only if the solution
set of NCP(F ) is nonempty by setting , where is a parameter. If NCP(F) has a locally unique solution and satisfies a nonsingularity condition, then the convergence rate is superlinear (quadratic)
without strict complementarity conditions. At each step, we only solve a linear system of equations. Numerical results are
provided and further applications to other problems are discussed.
Accepted 25 March 1998 相似文献
8.
Convergence Properties of the Regularized Newton Method for the Unconstrained Nonconvex Optimization
The regularized Newton method (RNM) is one of the efficient solution methods for the unconstrained convex optimization. It
is well-known that the RNM has good convergence properties as compared to the steepest descent method and the pure Newton’s
method. For example, Li, Fukushima, Qi and Yamashita showed that the RNM has a quadratic rate of convergence under the local
error bound condition. Recently, Polyak showed that the global complexity bound of the RNM, which is the first iteration k such that ‖∇
f(x
k
)‖≤ε, is O(ε
−4), where f is the objective function and ε is a given positive constant. In this paper, we consider a RNM extended to the unconstrained “nonconvex” optimization. We
show that the extended RNM (E-RNM) has the following properties. (a) The E-RNM has a global convergence property under appropriate
conditions. (b) The global complexity bound of the E-RNM is O(ε
−2) if ∇
2
f is Lipschitz continuous on a certain compact set. (c) The E-RNM has a superlinear rate of convergence under the local error
bound condition. 相似文献
9.
We introduce a topological graph parameter σ(G), defined for any graph G. This parameter characterizes subgraphs of paths, outerplanar graphs, planar graphs, and graphs that have a flat embedding
as those graphs G with σ(G)≤1,2,3, and 4, respectively. Among several other theorems, we show that if H is a minor of G, then σ(H)≤σ(G), that σ(K
n
)=n−1, and that if H is the suspension of G, then σ(H)=σ(G)+1. Furthermore, we show that μ(G)≤σ(G) + 2 for each graph G. Here μ(G) is the graph parameter introduced by Colin de Verdière in [2]. 相似文献
10.
We propose a class of self-adaptive proximal point methods suitable for degenerate optimization problems where multiple minimizers
may exist, or where the Hessian may be singular at a local minimizer. If the proximal regularization parameter has the form
where η∈[0,2) and β>0 is a constant, we obtain convergence to the set of minimizers that is linear for η=0 and β sufficiently small, superlinear for η∈(0,1), and at least quadratic for η∈[1,2). Two different acceptance criteria for an approximate solution to the proximal problem are analyzed. These criteria
are expressed in terms of the gradient of the proximal function, the gradient of the original function, and the iteration
difference. With either acceptance criterion, the convergence results are analogous to those of the exact iterates. Preliminary
numerical results are presented using some ill-conditioned CUTE test problems.
This material is based upon work supported by the National Science Foundation under Grant Nos. 0203270, 0619080, and 0620286. 相似文献
11.
G. I. Shishkin 《Computational Mathematics and Mathematical Physics》2009,49(10):1748-1764
The initial-boundary value problem in a domain on a straight line that is unbounded in x is considered for a singularly perturbed reaction-diffusion parabolic equation. The higher order derivative in the equation
is multiplied by a parameter ɛ2, where ɛ ∈ (0, 1]. The right-hand side of the equation and the initial function grow unboundedly as x → ∞ at a rate of O(x
2). This causes the unbounded growth of the solution at infinity at a rate of O(Ψ(x)), where Ψ(x) = x
2 + 1. The initialboundary function is piecewise smooth. When ɛ is small, a boundary and interior layers appear, respectively,
in a neighborhood of the lateral part of the boundary and in a neighborhood of the characteristics of the reduced equation
passing through the discontinuity points of the initial function. In the problem under examination, the error of the grid
solution grows unboundedly in the maximum norm as x → ∞ even for smooth solutions when ɛ is fixed. In this paper, the proximity of solutions of the initial-boundary value problem
and its grid approximations is considered in the weighted maximum norm ∥·∥
w
with the weighting function Ψ−1(x); in this norm, the solution of the initial-boundary value problem is ɛ-uniformly bounded. Using the method of special grids
that condense in a neighborhood of the boundary layer or in neighborhoods of the boundary and interior layers, special finite
difference schemes are constructed and studied that converge ɛ-uniformly in the weighted norm. It is shown that the convergence
rate considerably depends on the type of nonsmoothness in the initial-boundary conditions. Grid approximations of the Cauchy
problem with the right-hand side and the initial function growing as O(Ψ(x)) that converge ɛ-uniformly in the weighted norm are also considered. 相似文献
12.
Daniel Berend 《Journal d'Analyse Mathématique》1985,45(1):255-284
The study of jointly ergodic measure preserving transformations of probability spaces, begun in [1], is continued, and notions
of joint weak and strong mixing are introduced. Various properties of ergodic and mixing transformations are shown to admit
analogues for several transformations. The case of endomorphisms of compact abelian groups is particularly emphasized. The
main result is that, given such commuting endomorphisms σ1σ2,...,σ, ofG, the sequence ((1/N)Σ
n=0
N−1
σ
1
n
f
1·σ
2
n
f
2· ··· · σ
s
n
f
sconverges inL
2(G) for everyf
1,f
2,…,f
s∈L
∞(G). If, moreover, the endomorphisms are jointly ergodic, i.e., if the limit of any sequence as above is Π
i=1
s
∫
G
f
1
d
μ, where μ is the Haar measure, then the convergence holds also μ-a.e. 相似文献
13.
P. M. Edwards 《Semigroup Forum》1989,39(1):257-262
For a congruence σ on a semigroupS a congruence μ(σ) onS, containing σ, is defined such that the semigroupS/σ is fundamental if and only if σ=μ(σ). The congruence μ(σ) is shown to possess maximality properties and for idempotent-surjective
semigroups, μ(σ) is the maximum congruence with respect to the partition of the idempotents determined by σ. Thus μ is the
maximum idempotent-separating congruence on any idempotent-surjective semigroup. It is shown that μ(μ(σ))=μ(σ).
If ρ is another congruence onS, possibly with the same partition of the idempotents as σ, then it is of interest to know when ρ⊆σ (or ρ⊆μ(σ)) implies μ(ρ)⊆μ(σ)
or even μ(ρ)=μ(σ). These implications are not true in general but if σ⊆ρ⊆μ(σ) then μ(ρ)⊆μ(σ). IfS is an idempotent-surjective semigroup and ρ and σ have the same partition of the idempotents then μ(ρ)=μ(σ). 相似文献
14.
Jean-Pierre Dussault Abdellatif Elafia 《Computational Optimization and Applications》2001,19(1):31-53
Since the pioneering work of Karmarkar, much interest was directed to penalty algorithms, in particular to the log barrier algorithm. We analyze in this paper the asymptotic convergence rate of a barrier algorithm when applied to non-linear programs. More specifically, we consider a variant of the SUMT method, in which so called extrapolation predictor steps allowing reducing the penalty parameter rk +1}k are followed by some Newton correction steps. While obviously related to predictor-corrector interior point methods, the spirit differs since our point of view is biased toward nonlinear barrier algorithms; we contrast in details both points of view. In our context, we identify an asymptotically optimal strategy for reducing the penalty parameter r and show that if rk+1=r
k
with < 8/5, then asymptotically only 2 Newton corrections are required, and this strategy achieves the best overall average superlinear convergence order (1.1696). Therefore, our main result is to characterize the best possible convergence order for SUMT type methods. 相似文献
15.
A globally and superlinearly convergent trust region method for LC
1 optimization problems 总被引:1,自引:0,他引:1
ZhangLiping LaiYanlian 《高校应用数学学报(英文版)》2001,16(1):72-80
Abstract. A new trust region algorithm for solving convex LC1 optimization problem is present-ed. It is proved that the algorithm is globally convergent and the rate of convergence is superlin-ear under some reasonable assumptions. 相似文献
16.
Rupert L. Frank 《Arkiv f?r Matematik》2006,44(2):277-298
We study spectral and scattering properties of the Laplacian H
(σ)=-Δ in corresponding to the boundary condition with a periodic function σ. For non-negative σ we prove that H
(σ) is unitarily equivalent to the Neumann Laplacian H
(0). In general, there appear additional channels of scattering due to surface states. We prove absolute continuity of the spectrum
of H
(σ) under mild assumptions on σ. 相似文献
17.
Reha H. Tütüncü 《Mathematical Programming》2001,90(1):169-203
Global and local convergence properties of a primal-dual interior-point pure potential-reduction algorithm for linear programming problems is analyzed. This algorithm is a primal-dual variant of the
Iri-Imai method and uses modified Newton search directions to minimize the Tanabe-Todd-Ye (TTY) potential function. A polynomial
time complexity for the method is demonstrated. Furthermore, this method is shown to have a unique accumulation point even
for degenerate problems and to have Q-quadratic convergence to this point by an appropriate choice of the step-sizes. This
is, to the best of our knowledge, the first superlinear convergence result on degenerate linear programs for primal-dual interior-point
algorithms that do not follow the central path.
Received: February 12, 1998 / Accepted: March 3, 2000?Published online January 17, 2001 相似文献
18.
Manuel A. Gómez 《Numerical Algorithms》1999,22(3-4):305-316
In this paper, an O(n
2) active set method is presented for minimizing the parametric quadratic function (1/2)x′Dx-a′x + λmax(c - γ x,0) subject to l ⩽ x ⩽ b, for all nonnegative values of the parameter γ. Here, D is a positive diagonal n x n matrix, a and γ are arbitrary N-vectors, c is an arbitrary scalar, l and b are arbitrary n-vectors, such thatl ⩽ b. An extension of this algorithm is presented for minimizing the parametric function (1/2)x′Dx-a
′
x + λ |γ′x - c| subject to l ⩽ x ⩽ b. It is also shown that these problems arise naturally in a tax programming problem.
This revised version was published online in August 2006 with corrections to the Cover Date. 相似文献
19.
We give general conditions on a generator of a C0-semigroup (resp. of a C0-resolvent) on Lp(E,μ), p ≥ 1, where E is an arbitrary (Lusin) topological space and μ a σ-finite measure on its Borel σ-algebra, so that it generates a sufficiently
regular Markov process on E. We present a general method how these conditions can be checked in many situations. Applications to solve stochastic differential
equations on Hilbert space in the sense of a martingale problem are given.
Dedicated to Giuseppe Da Prato on the occasion of his 70th birthday 相似文献
20.
Djamel Meraghni Abdelhakim Necir 《Methodology and Computing in Applied Probability》2007,9(4):557-572
The characteristic exponent α of a Lévy-stable law S
α
(σ, β, μ) was thoroughly studied as the extreme value index of a heavy tailed distribution. For 1 < α < 2, Peng (Statist. Probab. Lett. 52: 255–264, 2001) has proposed, via the extreme value approach, an asymptotically normal estimator for the location parameter μ. In this paper, we derive by the same approach, an estimator for the scale parameter σ and we discuss its limiting behavior.
相似文献