共查询到20条相似文献,搜索用时 10 毫秒
1.
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 相似文献
2.
K.A. Ariyawansa 《Numerische Mathematik》1998,80(3):363-376
Summary. Many successful quasi-Newton methods for optimization are based on positive definite local quadratic approximations to the
objective function that interpolate the values of the gradient at the current and new iterates. Line search termination criteria
used in such quasi-Newton methods usually possess two important properties. First, they guarantee the existence of such a
local quadratic approximation. Second, under suitable conditions, they allow one to prove that the limit of the component
of the gradient in the normalized search direction is zero. This is usually an intermediate result in proving convergence.
Collinear scaling algorithms proposed initially by Davidon in 1980 are natural extensions of quasi-Newton methods in the sense
that they are based on normal conic local approximations that extend positive definite local quadratic approximations, and
that they interpolate values of both the gradient and the function at the current and new iterates. Line search termination criteria that guarantee the existence
of such a normal conic local approximation, which also allow one to prove that the component of the gradient in the normalized
search direction tends to zero, are not known. In this paper, we propose such line search termination criteria for an important
special case where the function being minimized belongs to a certain class of convex functions.
Received February 1, 1997 / Revised version received September 8, 1997 相似文献
3.
S. Maset 《Numerische Mathematik》2000,87(2):355-371
Summary. This paper investigates the stability of Runge-Kutta methods when they are applied to the complex linear scalar delay differential equation . This kind of stability is called stability. We give a characterization of stable Runge-Kutta methods and then we prove that implicit Euler method is stable. Received November 3, 1998 / Revised version received March 23, 1999 / Published online July 12, 2000 相似文献
4.
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 相似文献
5.
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 相似文献
6.
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 相似文献
7.
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 相似文献
8.
Infeasible-interior-point paths , a positive vector, for a horizontal linear complementarity problem are defined as the solution of () If the path converges for , then it converges to a solution of . This paper deals with the analyticity properties of and its derivatives with respect to r near r = 0 for solvable monotone complementarity problems . It is shown for with a strictly complementary solution that the path , , has an extension to which is analytic also at . If has no strictly complementary solution, then , , has an extension to that is analytic at .
Received May 24, 1996 / Revised version received February 25, 1998 相似文献
9.
Summary.
The design of cost-efficient networks satisfying certain
survivability constraints
is of major concern to the telecommunications industry.
In this paper we study a problem of extending
the capacity of a network by discrete steps as cheaply as possible,
such that the given traffic demand can be accommodated
even when a single edge or node in the network fails.
We derive valid and nonredundant inequalities
for the polyhedron of capacity design variables,
by exploiting its relationship to connectivity network design
and knapsack-like subproblems.
A cutting plane algorithm and heuristics for the problem
are described,
and preliminary computational results are reported.
Received August 26, 1993 / Revised version received
February 1994 相似文献
10.
Summary. Inequality constrained minimization problems are often solved by
considering a sequence of parameterized barrier functions. Each barrier
function is approximately minimized and the relevant parameters
subsequently adjusted.
It is common for the estimated solution to one barrier function problem
to be used as a starting estimate for the next. However, this has
unfortunate repercussions for the standard Newton-like methods applied to
the barrier subproblem.
In this note, we consider a class of alternative Newton methods which
attempt to avoid such difficulties.
Such schemes have already proved of use in the Harwell Subroutine Library
quadratic programming codes {\tt VE14} and {\tt VE19}.
Received May 2, 1993/Revised form received February 12, 1994 相似文献
11.
Summary.
We construct and analyse a family of absorbing boundary
conditions for diffusion equations with variable coefficients, curved
artifical boundary, and arbitrary convection. It relies on the geometric
identification of the Dirichlet to Neumann map and rational
interpolation of in the complex plane.
The boundary conditions
are stable, accurate, and practical for computations.
Received
December 12, 1992 / Revised version received July 4, 1994 相似文献
12.
Summary. The authors describe a continuous, orthogonal and symplectic factorization procedure for integrating unstable linear Hamiltonian
systems. The method relies on the development of an orthogonal, symplectic change of variables to block triangular Hamiltonian
form. Integration is thus carried out within the class of linear Hamiltonian systems. Use of an appropriate timestepping strategy
ensures that the symplectic pairing of eigenvalues is automatically preserved. For long-term integrations, as are needed in
the calculation of Lyapunov exponents, the favorable qualitative properties of such a symplectic framework can be expected
to yield improved estimates. The method is illustrated and compared with other techniques in numerical experiments on the
Hénon-Heiles and spatially discretized Sine-Gordon equations.
Received December 11, 1995 / Revised version received April 18, 1996 相似文献
13.
R. Pytlak 《Numerische Mathematik》2002,91(2):319-321
Summary. We show that the example given in [Dai, Y., Yuan, Y. (1999): Global convergence of the method of shortest residuals, Numerische
Mathematik 83, 581–598] does not contradict the results of [Pytlak, R. (1994): On the convergence of conjugate gradient algorithms,
IMA J. Numerical Analysis 14, 443–460].
Received September 9, 2000 / Revised version received November 28, 2000 / Published online July 25, 2001 相似文献
14.
Summary. This paper studies the convergence properties of general Runge–Kutta methods when applied to the numerical solution of a
special class of stiff non linear initial value problems. It is proved that under weaker assumptions on the coefficients of
a Runge–Kutta method than in the standard theory of B-convergence, it is possible to ensure the convergence of the method
for stiff non linear systems belonging to the above mentioned class. Thus, it is shown that some methods which are not algebraically
stable, like the Lobatto IIIA or A-stable SIRK methods, are convergent for the class of stiff problems under consideration.
Finally, some results on the existence and uniqueness of the Runge–Kutta solution are also presented.
Received November 18, 1996 / Revised version received October 6, 1997 相似文献
15.
Summary. In this paper, the regularized solutions of an ill–conditioned system of linear equations are computed for several values
of the regularization parameter . Then, these solutions are extrapolated at by various vector rational extrapolations techniques built for that purpose. These techniques are justified by an analysis
of the regularized solutions based on the singular value decomposition and the generalized singular value decomposition. Numerical
results illustrate the effectiveness of the procedures.
Received June 23, 1997 / Revised version received October 24, 1997 相似文献
16.
Summary.
The existence of a true orbit near a numerically
computed approximate orbit -- shadowing -- of
autonomous system of ordinary differential equations
is investigated.
A general shadowing theorem for finite time,
which guarantees the existence of shadowing
in ordinary differential equations
and provides error bounds for the distance between
the true and the approximate orbit in terms of computable
quantities, is proved.
The practical use and the effectiveness of this theorem
is demonstrated in the numerical computations
of chaotic orbits of the Lorenz equations.
Received December 15, 1993 相似文献
17.
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 相似文献
18.
Christian Kanzow 《Numerische Mathematik》1998,80(4):557-577
Summary. We consider a quadratic programming-based method for nonlinear complementarity problems which allows inexact solutions of
the quadratic subproblems. The main features of this method are that all iterates stay in the feasible set and that the method
has some strong global and local convergence properties. Numerical results for all complementarity problems from the MCPLIB
test problem collection are also reported.
Received February 24, 1997 / Revised version received September 5, 1997 相似文献
19.
Summary.
Hybrid methods for the solution of systems of linear equations
consist of a first phase where some information about the associated
coefficient matrix is acquired, and a second phase in which a
polynomial iteration designed with respect to this information is
used. Most of the hybrid algorithms proposed recently for the
solution of nonsymmetric systems rely on the direct use of
eigenvalue estimates constructed by the Arnoldi process in Phase I.
We will show the limitations of this approach and propose an
alternative, also based on the Arnoldi process, which approximates
the field of values of the coefficient matrix and of its inverse in
the Krylov subspace. We also report on numerical experiments
comparing the resulting new method with other hybrid algorithms.
Received May 27, 1993 / Revised version received
November 14, 1994 相似文献
20.
Summary. In this paper, we are concerned with a matrix equation
where A is an real matrix and x and b are n-vectors. Assume that an approximate solution is given together with an approximate LU decomposition. We will present fast algorithms for proving nonsingularity of A and for calculating rigorous error bounds for . The emphasis is on rigour of the bounds. The purpose of this paper is to propose different algorithms, the fastest with
flops computational cost for the verification step, the same as for the LU decomposition. The presented algorithms exclusively use library routines for LU decomposition and for all other matrix and vector operations.
Received June 16, 1999 / Revised version received January 25, 2001 / Published online June 20, 2001 相似文献