共查询到20条相似文献,搜索用时 31 毫秒
1.
Vikram Sharma 《Mathematics in Computer Science》2007,1(1):71-109
We extend Smale’s concept of approximate zeros of an analytic function on a Banach space to two computational models that
account for errors in the computation: first, the weak model where the computations are done with a fixed precision; and second,
the strong model where the computations are done with varying precision. For both models, we develop a notion of robust approximate
zero and derive a corresponding robust point estimate.
A useful specialization of an analytic function on a Banach space is a system of integer polynomials. Given such a zero-dimensional
system, we bound the complexity of computing an absolute approximation to a root of the system using the strong model variant
of Newton’s method initiated from a robust approximate zero. The bound is expressed in terms of the condition number of the
system and is a generalization of a well-known bound of Brent to higher dimensions.
相似文献
2.
In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization
reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov’s optimal
method (Nesterov in Doklady AN SSSR 269:543–547, 1983; Math Program 103:127–152, 2005), Nesterov’s smooth approximation scheme
(Nesterov in Math Program 103:127–152, 2005), and Nemirovski’s prox-method (Nemirovski in SIAM J Opt 15:229–251, 2005), and
propose a variant of Nesterov’s optimal method which has outperformed the latter one in our computational experiments. We
also derive iteration-complexity bounds for these first-order methods applied to the proposed primal-dual reformulations of
the cone programming problem. The performance of these methods is then compared using a set of randomly generated linear programming
and semidefinite programming instances. We also compare the approach based on the variant of Nesterov’s optimal method with
the low-rank method proposed by Burer and Monteiro (Math Program Ser B 95:329–357, 2003; Math Program 103:427–444, 2005) for
solving a set of randomly generated SDP instances. 相似文献
3.
Alicia Cordero José L. Hueso Eulalia Martínez Juan R. Torregrosa 《Numerical Algorithms》2010,53(4):485-495
In this paper, we present two new three-step iterative methods for solving nonlinear equations with sixth convergence order.
The new methods are obtained by composing known methods of third order of convergence with Newton’s method and using an adequate
approximation for the derivative, that provides high order of convergence and reduces the required number of functional evaluations
per step. The first method is obtained from Potra-Pták’s method and the second one, from Homeier’s method, both reaching an
efficiency index of 1.5651. Our methods are comparable with the method of Parhi and Gupta (Appl Math Comput 203:50–55, 2008). Methods proposed by Kou and Li (Appl Math Comput 189:1816–1821, 2007), Wang et al. (Appl Math Comput 204:14–19, 2008) and Chun (Appl Math Comput 190:1432–1437, 2007) reach the same efficiency index, although they start from a fourth order method while we use third order methods and simpler
arithmetics. We prove the convergence results and check them with several numerical tests that allow us to compare the convergence
order, the computational cost and the efficiency order of our methods with those of the original methods. 相似文献
4.
Based on Ostrowski’s fourth order method, we derive a family of eighth order methods for the solution of nonlinear equations.
In terms of computational cost the family requires three evaluations of the function and one evaluation of first derivative.
Therefore, the efficiency index of the present methods is 1.682 which is better than the efficiency index 1.587 of Ostrowski’s
method. Kung and Traub conjectured that multipoint iteration methods without memory based on n evaluations have optimal order
2
n − 1. Thus, the family agrees with Kung–Traub conjecture for the case n = 4. The efficacy of the present methods is tested on a number of numerical examples. It is observed that our methods are
competitive with other similar robust methods and very effective in high precision computations. 相似文献
5.
Qunfeng Liu 《Numerical Algorithms》2011,58(4):461-474
Positive basis is an important concept in direct search methods. Although any positive basis can ensure the convergence in
theory, the maximum positive bases are often used to construct direct search algorithms. In this paper, two direct search
methods for computational expensive functions are proposed based on the minimal positive bases. The Coope–Price’s frame-based
direct search framework is employed to insure convergence. PRP+ method and a recently developed descent conjugate gradient
method are employed respectively to accelerate convergence. The data profiles and the performance profiles of the numerical
experiments show that the proposed methods are effective for computational expensive functions. 相似文献
6.
By using a smooth entropy function to approximate the non-smooth max-type function, a vertical linear complementarity problem
(VLCP) can be treated as a family of parameterized smooth equations. A Newton-type method with a testing procedure is proposed
to solve such a system. We show that under some milder than usual assumptions the proposed algorithm finds an exact solution
of VLCP in a finite number of iterations. Some computational results are included to illustrate the potential of this approach.
This author’s work was partially supported by the National Natural Science Foundation of China (Grant Nos. 10271002 and 10401038).
This author’s work was partially supported by the Scientific Research Foundation of Tianjin University for the Returned Overseas
Chinese Scholars and the Scientific Research Foundation of Liu Hui Center for Applied Mathematics, Nankai University-Tianjin
University. 相似文献
7.
In this paper, an interactive paired comparison simplex based method formultiple objective linear programming (MOLP) problems
is developed and compared to other interactive MOLP methods. The decision maker (DM)’s utility function is assumed to be unknown,
but is an additive function of his known linearized objective functions. A test for ‘utility efficiency’ for MOLP problems
is developed to reduce the number of efficient extreme points generated and the number of questions posed to the DM. The notion
of ‘strength of preference ’ is developed for the assessment of the DM’s unknown utility function where he can express his
preference for a pair of extreme points as ‘strong ’, ‘weak ’, or ‘almost indifferent ’. The problem of ‘inconsistency of
the DM’ is formalized and its resolution is discussed. An example of the method and detailed computational results comparing
it with other interactive MOLP methods are presented. Several performance measures for comparative evaluations of interactive
multiple objective programming methods are also discussed.
All rights reserved. This study, or parts thereof, may not be reproduced in any form without written permission of the authors. 相似文献
8.
A method of using Markov’s quadrature with a fixed node is proposed to calculate the coefficients of the expansion of a function
in a shifted Chebyshev series. Approximation properties of a partial sum of a series with approximate coefficients are considered.
This approach can be used to construct some numerical-analytic methods for solving ordinary differential equations. 相似文献
9.
We establish new iterative methods of local order fourteen to approximate the simple roots of nonlinear equations. The considered
three-step eighth-order construction can be viewed as a variant of Newton’s method in which the concept of Hermite interpolation
is used at the third step to reduce the number of evaluations. This scheme includes three evaluations of the function and
one evaluation of the first derivative per iteration, hence its efficiency index is 1.6817. Next, the obtained approximation
for the derivative of the Newton’s iteration quotient is again taken into consideration to furnish novel fourteenth-order
techniques consuming four function and one first derivative evaluations per iteration. In providing such new fourteenth-order
methods, we also take a special heed to the computational burden. The contributed four-step methods have 1.6952 as their efficiency
index. Finally, various numerical examples are given to illustrate the accuracy of the developed techniques. 相似文献
10.
New heuristics for the maximum diversity problem 总被引:1,自引:0,他引:1
Geiza C. Silva Marcos R. Q. de Andrade Luiz S. Ochi Simone L. Martins Alexandre Plastino 《Journal of Heuristics》2007,13(4):315-336
The maximum diversity problem (MDP) consists of identifying, in a population, a subset of elements, characterized by a set
of attributes, that present the most diverse characteristics among the elements of the subset. The identification of such
solution is an NP-hard problem. Some heuristics are available to obtain approximate solutions for this problem. In this paper,
we propose different GRASP heuristics for the MDP, using distinct construction procedures and including a path-relinking technique.
Performance comparison among related work and the proposed heuristics is provided. Experimental results show that the new
GRASP heuristics are quite robust and are able to find high-quality solutions in reasonable computational times.
G.C. Silva’s work sponsored by CAPES MSc scholarship. L.S. Ochi’s work sponsored by CNPq research grants 304103/2003-9 and
550059/2005-9. S.L. Martins’s work sponsored by CNPq research grant 475124/03-0. A. Plastino’s work sponsored by CNPq research
grants 300879/00-8 and 475124/03-0. 相似文献
11.
This paper provides an analysis of the polynomiality of primal-dual interior point algorithms for nonlinear complementarity
problems using a wide neighborhood. A condition for the smoothness of the mapping is used, which is related to Zhu’s scaled
Lipschitz condition, but is also applicable to mappings that are not monotone. We show that a family of primal-dual affine
scaling algorithms generates an approximate solution (given a precision ε) of the nonlinear complementarity problem in a finite
number of iterations whose order is a polynomial ofn, ln(1/ε) and a condition number. If the mapping is linear then the results in this paper coincide with the ones in Jansen
et al., SIAM Journal on Optimization 7 (1997) 126–140.
Research supported in part by Grant-in-Aids for Encouragement of Young Scientists (06750066) from the Ministry of Education,
Science and Culture, Japan.
Research supported by Dutch Organization for Scientific Research (NWO), grant 611-304-028 相似文献
12.
F. Jolai J. Razmi N. K. M. Rostami 《Central European Journal of Operations Research》2011,19(4):547-569
Integrated production–distribution planning is one of the most important issues in supply chain management (SCM). We consider
a supply chain (SC) network to consist of a manufacturer, with multiple plants, products, distribution centers (DCs), retailers
and customers. A multi-objective linear programming problem for integrating production–distribution, which considers various
simultaneously conflicting objectives, is developed. The decision maker’s imprecise aspiration levels of goals are incorporated
into the model using a fuzzy goal programming approach. Due to complexity of the considered problem we propose three meta-heuristics
to tackle the problem. A simple genetic algorithm and a particle swarm optimization (PSO) algorithm with a new fitness function,
and an improved hybrid genetic algorithm are developed. In order to show the efficiency of the proposed methods, two classes
of problems are considered and their instances are solved using all methods. The obtained results show that the improved hybrid
genetic algorithm gives us the best solutions in a reasonable computational time. 相似文献
13.
The presence of groups containing high leverage outliers makes linear regression a difficult problem due to the masking effect.
The available high breakdown estimators based on Least Trimmed Squares often do not succeed in detecting masked high leverage
outliers in finite samples. An alternative to the LTS estimator, called Penalised Trimmed Squares (PTS) estimator, was introduced
by the authors in Zioutas and Avramidis (2005) Acta Math Appl Sin 21:323–334, Zioutas et al. (2007) REVSTAT 5:115–136 and
it appears to be less sensitive to the masking problem. This estimator is defined by a Quadratic Mixed Integer Programming
(QMIP) problem, where in the objective function a penalty cost for each observation is included which serves as an upper bound
on the residual error for any feasible regression line. Since the PTS does not require presetting the number of outliers to
delete from the data set, it has better efficiency with respect to other estimators. However, due to the high computational
complexity of the resulting QMIP problem, exact solutions for moderately large regression problems is infeasible. In this
paper we further establish the theoretical properties of the PTS estimator, such as high breakdown and efficiency, and propose
an approximate algorithm called Fast-PTS to compute the PTS estimator for large data sets efficiently. Extensive computational
experiments on sets of benchmark instances with varying degrees of outlier contamination, indicate that the proposed algorithm
performs well in identifying groups of high leverage outliers in reasonable computational time. 相似文献
14.
We propose and analyze a numerical scheme for nonlinear degenerate parabolic convection–diffusion–reaction equations in two or three space dimensions. We discretize the diffusion term, which generally involves an inhomogeneous and anisotropic diffusion tensor, over an unstructured simplicial mesh of the space domain by means of the piecewise linear nonconforming (Crouzeix–Raviart) finite element method, or using the stiffness matrix of the hybridization of the lowest-order Raviart–Thomas mixed finite element method. The other terms are discretized by means of a cell-centered finite volume scheme on a dual mesh, where the dual volumes are constructed around the sides of the original mesh. Checking the local Péclet number, we set up the exact necessary amount of upstream weighting to avoid spurious oscillations in the convection-dominated case. This technique also ensures the validity of the discrete maximum principle under some conditions on the mesh and the diffusion tensor. We prove the convergence of the scheme, only supposing the shape regularity condition for the original mesh. We use a priori estimates and the Kolmogorov relative compactness theorem for this purpose. The proposed scheme is robust, only 5-point (7-point in space dimension three), locally conservative, efficient, and stable, which is confirmed by numerical experiments.This work was supported by the GdR MoMaS, CNRS-2439, ANDRA, BRGM, CEA, EdF, France. 相似文献
15.
Chen Zhongying Micchelli Charles A. Xu Yuesheng 《Advances in Computational Mathematics》1997,7(3):199-233
This paper continues the theme of the recent work [Z. Chen and Y. Xu, The Petrov–Galerkin and iterated Petrov–Galerkin methods
for second kind integral equations, SIAM J. Numer. Anal., to appear] and further develops the Petrov–Galerkin method for Fredholm
integral equations of the second kind. Specifically, we study wavelet Petrov–Galerkin schemes based on discontinuous orthogonal
multiwavelets and prove that the condition number of the coefficient matrix for the linear system obtained from the wavelet
Petrov–Galerkin scheme is bounded. In addition, we propose a truncation strategy which forms a basis for fast wavelet algorithms
and analyze the order of convergence and computational complexity of these algorithms.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
16.
Alper Atamtürk 《Mathematical Programming》2006,108(2-3):235-250
We introduce strong formulations for robust mixed 0–1 programming with uncertain objective coefficients. We focus on a polytopic
uncertainty set described by a ``budget constraint' for allowed uncertainty in the objective coefficients. We show that for
a robust 0–1 problem, there is an α–tight linear programming formulation with size polynomial in the size of an α–tight linear programming formulation for the nominal 0–1 problem. We give extensions to robust mixed 0–1 programming and
present computational experiments with the proposed formulations. 相似文献
17.
Richard Taylor 《Publications Mathématiques de L'IHéS》2008,108(1):183-239
We extend the results of [CHT] by removing the ‘minimal ramification’ condition on the lifts. That is we establish the automorphy
of suitable conjugate self-dual, regular (de Rham with distinct Hodge–Tate numbers), l-adic lifts of certain automorphic mod
l Galois representations of any dimension. The main innovation is a new approach to the automorphy of non-minimal lifts which
is closer in spirit to the methods of [TW] than to those of [W], which relied on Ihara’s lemma. 相似文献
18.
Katrin Schmallowsky 《Mathematical Methods of Operations Research》2008,68(3):551-564
We prove the nonsingularity of the standard primal–dual system for second order cone programs assuming Slater’s condition,
uniqueness and strict complementarity. This result is applied to the analysis of the augmented primal–dual method for solving
linear programs over second order cones. 相似文献
19.
To optimize a complicated function constructed from a solution of a system of ordinary differential equations (ODEs), it is
very important to be able to approximate a solution of a system of ODEs very precisely. The precision delivered by the standard
Runge-Kutta methods often is insufficient, resulting in a “noisy function” to optimize.
We consider an initial-value problem for a system of ordinary differential equations having polynomial right-hand sides with
respect to all dependent variables. First we show how to reduce a wide class of ODEs to such polynomial systems. Using the
estimates for the Taylor series method, we construct a new “aggregative” Taylor series method and derive guaranteed a priori
step-size and error estimates for Runge-Kutta methods of order r. Then we compare the 8,13-Prince-Dormand’s, Taylor series, and aggregative Taylor series methods using seven benchmark systems
of equations, including van der Pol’s equations, the “brusselator,” equations of Jacobi’s elliptic functions, and linear and
nonlinear stiff systems of equations. The numerical experiments show that the Taylor series method achieves the best precision,
while the aggregative Taylor series method achieves the best computational time.
The final section of this paper is devoted to a comparative study of the above numerical integration methods for systems of
ODEs describing the optimal flight of a spacecraft from the Earth to the Moon.
__________
Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 24, Dynamical
Systems and Optimization, 2005. 相似文献
20.
This paper addresses the role of centrality in the implementation of interior point methods. We provide theoretical arguments
to justify the use of a symmetric neighbourhood, and translate them into computational practice leading to a new insight into
the role of re-centering in the implementation of interior point methods. Second-order correctors, such as Mehrotra’s predictor–corrector,
can occasionally fail: we derive a remedy to such difficulties from a new interpretation of multiple centrality correctors.
Through extensive numerical experience we show that the proposed centrality correcting scheme leads to noteworthy savings
over second-order predictor–corrector technique and previous implementations of multiple centrality correctors. 相似文献