共查询到20条相似文献,搜索用时 15 毫秒
1.
Christian Kanzow 《Numerische Mathematik》2001,89(1):135-160
Summary. We introduce a new algorithm for the solution of the mixed complementarity problem (MCP) which has stronger properties than
most existing methods. In fact, typical solution methods for the MCP either generate feasible iterates but have to solve relatively
complicated subproblems (like quadratic programs or linear complementarity problems), or they have relatively simple subproblems
(like linear systems of equations) but generate not necessarily feasible iterates. The method to be presented here combines
the nice features of these two classes of methods: It has to solve only one linear system of equations (of reduced dimension)
at each iteration, and it generates feasible (more precisely: strictly feasible) iterates. The new method has some nice global
and local convergence properties. Some preliminary numerical results will also be given.
Received August 26, 1999 / Revised version recived April 11, 2000 / Published online February 5, 2001 相似文献
2.
Summary. We propose an algorithm for the numerical solution of
large-scale symmetric positive-definite linear complementarity problems.
Each step of the algorithm combines an application of the successive
overrelaxation
method with projection (to determine an approximation of the optimal active
set) with the preconditioned conjugate gradient method (to solve the reduced
residual systems of linear equations). Convergence of the iterates to the
solution is proved. In the experimental part we compare the efficiency of the
algorithm with several other methods. As test example we consider the
obstacle problem with different obstacles.
For problems of dimension up to 24\,000 variables, the algorithm finds the
solution in less then 7 iterations, where each iteration
requires about 10
matrix-vector multiplications.
Received July 14, 1993 / Revised version received February 1994 相似文献
3.
Summary. This paper proposes a validation method for solutions of nonlinear complementarity problems. The validation procedure performs
a computational test. If the result of the test is positive, then it is guaranteed that a given multi-dimensional interval
either includes a solution or excludes all solutions of the nonlinear complementarity problem.
Received September 22, 2000 / Revised version received April 11, 2001 / Published online October 17, 2001 相似文献
4.
Krzysztof C. Kiwiel 《Numerische Mathematik》1994,68(3):325-340
Summary.
A quadratic programming method is given for minimizing a
sum of piecewise linear functions and a proximal quadratic term,
subject to simple bounds on variables. It may be used for search
direction finding in nondifferentiable optimization algorithms. An
efficient implementation is described that updates a Cholesky
factorization of active constraints and provides good accuracy via
iterative refinement. Numerical experience is reported for some
large problems.
Received March 29, 1993 / Revised version received December 18, 1993 相似文献
5.
Summary. We present a semi-discrete method for constructing approximate solutions to the initial value problem for the -dimensional convection-diffusion equation . The method is based on the use of operator splitting to isolate the convection part and the diffusion part of the equation.
In the case , dimensional splitting is used to reduce the -dimensional convection problem to a series of one-dimensional problems. We show that the method produces a compact sequence
of approximate solutions which converges to the exact solution. Finally, a fully discrete method is analyzed, and demonstrated
in the case of one and two space dimensions.
ReceivedFebruary 1, 1996 / Revised version received June 24, 1996 相似文献
6.
Summary. This paper proposes a validation method for solutions of linear complementarity problems. The validation procedure consists
of two sufficient conditions that can be tested on a digital computer. If the first condition is satisfied then a given multidimensional
interval centered at an approximate solution of the problem is guaranteed to contain an exact solution. If the second condition
is satisfied then the multidimensional interval is guaranteed to contain no exact solution. This study is based on the mean
value theorem for absolutely continuous functions and the reformulation of linear complementarity problems as nonsmooth nonlinear
systems of equations.
Received August 21, 1997 / Revised version July 2, 1998 相似文献
7.
Summary. We consider a smoothing-type method for the solution of linear programs. Its main idea is to reformulate the primal-dual
optimality conditions as a nonlinear and nonsmooth system of equations, and to apply a Newton-type method to a smooth approximation
of this nonsmooth system. The method presented here is a predictor-corrector method, and is closely related to some methods
recently proposed by Burke and Xu on the one hand, and by the authors on the other hand. However, here we state stronger global
and/or local convergence properties. Moreover, we present quite promising numerical results for the whole netlib test problem
collection.
Received August 9, 2000 / Revised version received September 28, 2000 / Published online June 7, 2001 相似文献
8.
Florian Jarre 《Numerische Mathematik》1994,68(1):81-94
Summary. We define the notion of self-concordance of
order two
for the restriction
of a logarithmic barrier function to a
given
line. Based on this notion we prove an inner approximation of the domain
of , as well as a lower bound of the distance from
a point $t$ to the minimum of .
These results provide the theoretical tools to
develop a simple and efficient search step for
finding the minimum of the barrier function along a given line.
The new bound on the size of the line-search step is better than
the optimal bound known
for the case of a self-concordant function (of order one).
We conclude with some numerical examples that
illustrate the promise of the new line-search step.
Received May 24, 1993 / Revised version received February 1994 相似文献
9.
Semi-implicit finite volume scheme for solving nonlinear diffusion equations in image processing 总被引:1,自引:0,他引:1
Summary. We propose and prove a convergence of the semi-implicit finite volume approximation scheme for the numerical solution of
the modified (in the sense of Catté, Lions, Morel and Coll) Perona–Malik nonlinear image selective smoothing equation (called
anisotropic diffusion in the image processing). The proof is based on a-priori estimates and Kolmogorov's compactness theorem. The implementation aspects and computational results are discussed.
Received January 7, 1999 / Revised version received May 31, 2000 / Published online March 20, 2001 相似文献
10.
Naoki Osada 《Numerische Mathematik》1996,73(4):521-531
Summary.
The ρ-algorithm of Wynn is an excellent device for
accelerating the convergence of some logarithmically convergent
sequences.
Until now a convergence theorem and an acceleration theorem for the
ρ-algorithm have not been obtained.
The purpose of this paper is to give an acceleration theorem for the
ρ-algorithm.
Moreover, it is proved that the ρ-algorithm cannot accelerate
linear convergence.
Numerical examples are given.
Received October 20, 1994 / Revised version received July 2,
1995 相似文献
11.
Xiulin Zou 《Numerische Mathematik》1999,82(3):491-519
The quasi-Laguerre's iteration formula, using first order logarithmic derivatives at two points, is derived for finding roots
of polynomials. Three different derivations are presented, each revealing some different properties of the method. For polynomials
with only real roots, the method is shown to be optimal, and the global and monotone convergence, as well as the non-overshooting
property, of the method is justified. Different ways of forming quasi-Laguerre's iteration sequence are addressed. Local convergence
of the method is proved for general polynomials that may have complex roots and the order of convergence is .
Received June 30, 1996 / Revised version received August 12, 1996 相似文献
12.
On the numerical analysis of non-convex variational problems 总被引:1,自引:0,他引:1
Pablo Pedregal 《Numerische Mathematik》1996,74(3):325-336
Summary.
We discuss a numerical method for
finding Young-measure-valued minimizers of
non-convex variational problems. To have any hope of a
convergence theorem, one must work in a setting where
the minimizer is unique and minimizing sequences
converge strongly. This paper has two main goals: (i) we
specify a method for producing strongly-convergent
minimizing sequences, despite the failure of strict
convexity; and (ii) we show how uniqueness of the
Young measure can be parlayed into a numerical
convergence theorem. The treatment of (ii) is done in the
setting of two model problems, one involving scalar
valued functions and a multiwell energy, the other from
micromagnetics.
Received July 29, 1995 相似文献
13.
Numerical solution of constant coefficient linear delay differential equations as abstract Cauchy problems 总被引:2,自引:0,他引:2
Summary. In this paper we present an approach for the numerical solution of delay differential equations
where , and , different from the classical step-by-step method. We restate (1) as an abstract Cauchy problem and then we discretize it
in a system of ordinary differential equations. The scheme of discretization is proved to be convergent. Moreover the asymptotic
stability is investigated for two significant classes of asymptotically stable problems (1).
Received May 4, 1998 / Revised version received January 25, 1999 / Published online November 17, 1999 相似文献
14.
Summary. In the study of the choice of the regularization parameter for Tikhonov regularization of nonlinear ill-posed problems, Scherzer,
Engl and Kunisch proposed an a posteriori strategy in 1993. To prove the optimality of the strategy, they imposed many very
restrictive conditions on the problem under consideration. Their results are difficult to apply to concrete problems since
one can not make sure whether their assumptions are valid.
In this paper we give a further study on this strategy, and show that Tikhonov regularization is order optimal for each with the regularization parameter chosen according to this strategy under some simple and easy-checking assumptions. This
paper weakens the conditions needed in the existing results, and provides a theoretical guidance to numerical experiments.
Received August 8, 1997 / Revised version received January 26, 1998 相似文献
15.
Summary. We describe an algorithm to approximate the minimizer of an elliptic functional in the form on the set of convex functions u in an appropriate functional space X. Such problems arise for instance in mathematical economics [4]. A special case gives the convex envelope of a given function . Let be any quasiuniform sequence of meshes whose diameter goes to zero, and the corresponding affine interpolation operators. We prove that the minimizer over is the limit of the sequence , where minimizes the functional over . We give an implementable characterization of . Then the finite dimensional problem turns out to be a minimization problem with linear constraints.
Received November 24, 1999 / Published online October 16, 2000 相似文献
16.
Summary. This analysis of convergence of a coupled FEM-IEM is based on our previous work on the FEM and the IEM for exterior Helmholtz
problems. The key idea is to represent both the exact and the numerical solution by the Dirichlet-to-Neumann operators that
they induce on the coupling hypersurface in the exterior of an obstacle. The investigation of convergence can then be related
to a spectral analysis of these DtN operators. We give a general outline of our method and then proceed to a detailed investigation
of the case that the coupling surface is a sphere. Our main goal is to explore the convergence mechanism. In this context,
we show well-posedness of both the continuous and the discrete models. We further show that the discrete inf-sup constants
have a positive lower bound that does not depend on the number of DOF of the IEM. The proofs are based on lemmas on the spectra
of the continuous and the discrete DtN operators, where the spectral characterization of the discrete DtN operator is given
as a conjecture from numerical experiments. In our convergence analysis, we show algebraic (in terms of N) convergence of arbitrary order and generalize this result to exponential convergence.
Received April 10, 1999 / Revised version received November 10, 1999 / Published online October 16, 2000 相似文献
17.
Michel Chipot 《Numerische Mathematik》1999,83(3):325-352
Summary. The goal of the paper is to analyze the creation of microstructure in problems of Calculus of Variations with wells. More
precisely we consider a case with strong incompatibility between the wells. This forces the minimizing sequences to use other
gradients than the wells in a puzzling way. Using a method we are then able to single out discrete minimizing sequences and to give energy estimates in terms of the mesh size.
Received December 23, 1997 / Revised version received September 7, 1998 / Published online: June 29, 1999 相似文献
18.
Stefano Serra 《Numerische Mathematik》1999,81(3):461-495
Summary. In previous works [21–23] we proposed the use of [5] and band Toeplitz based preconditioners for the solution of 1D and 2D boundary value problems (BVP) by means of the preconditioned
conjugate gradient (PCG) methods. As and band Toeplitz linear systems can be solved [4] by using fast sine transforms [8], these methods become especially attractive
in a parallel environment of computation. In this paper we extend this technique to the nonlinear, nonsymmetric case and,
in addition, we prove some clustering properties for the spectra of the preconditioned matrices showing why these methods
exhibit a convergence speed which results to be more than linear. Therefore these methods work much finer than those based on separable preconditioners [18,45], on incomplete LU factorizations
[36,13,27], and on circulant preconditioners [9,30,35] since the latter two techniques do not assure a linear rate of convergence.
On the other hand, the proposed technique has a wider range of application since it can be naturally used for nonlinear, nonsymmetric
problems and for BVP in which the coefficients of the differential operator are not strictly positive and only piecewise smooth.
Finally the several numerical experiments performed here and in [22,23] confirm the effectiveness of the theoretical analysis.
Received December 19, 1995 / Revised version received September 15, 1997 相似文献
19.
New properties of a nonlinear conjugate gradient method 总被引:6,自引:0,他引:6
Yu-Hong Dai 《Numerische Mathematik》2001,89(1):83-98
Summary. This paper provides several new properties of the nonlinear conjugate gradient method in [5]. Firstly, the method is proved
to have a certain self-adjusting property that is independent of the line search and the function convexity. Secondly, under
mild assumptions on the objective function, the method is shown to be globally convergent with a variety of line searches.
Thirdly, we find that instead of the negative gradient direction, the search direction defined by the nonlinear conjugate
gradient method in [5] can be used to restart any optimization method while guaranteeing the global convergence of the method.
Some numerical results are also presented.
Received March 12, 1999 / Revised version received April 25, 2000 / Published online February 5, 2001 相似文献
20.
Shape optimization by the homogenization method 总被引:4,自引:0,他引:4
Grégoire Allaire Eric Bonnetier Gilles Francfort Francois Jouve 《Numerische Mathematik》1997,76(1):27-68
Summary. In the context of shape optimization, we seek minimizers of the sum of the elastic compliance and of the weight of a solid
structure under specified loading. This problem is known not to be well-posed, and a relaxed formulation is introduced. Its
effect is to allow for microperforated composites as admissible designs. In a two-dimensional setting the relaxed formulation
was obtained in [6] with the help of the theory of homogenization and optimal bounds for composite materials. We generalize
the result to the three dimensional case. Our contribution is twofold; first, we prove a relaxation theorem, valid in any
dimensions; secondly, we introduce a new numerical algorithm for computing optimal designs, complemented with a penalization
technique which permits to remove composite designs in the final shape. Since it places no assumption on the number of holes
cut within the domain, it can be seen as a topology optimization algorithm. Numerical results are presented for various two
and three dimensional problems.
Received July 4, 1995 相似文献