共查询到11条相似文献,搜索用时 0 毫秒
1.
A new pruning method for interval branch and bound algorithms is presented. In reliable global optimization methods there
are several approaches to make the algorithms faster. In minimization problems, interval B&B methods use a good upper bound
of the function at the global minimum and good lower bounds of the function at the subproblems to discard most of them, but
they need efficient pruning methods to discard regions of the subproblems that do not contain global minimizer points. The
new pruning method presented here is based on the application of derivative information from the Baumann point. Numerical
results were obtained by incorporating this new technique into a basic Interval B&B Algorithm in order to evaluate the achieved
improvements.
This work has been supported by the Ministry of Education and Science of Spain through grants TIC 2002-00228, TIN2005-00447,
and research project SEJ2005-06273 and by the Integral Action between Spain and Hungary by grant HH2004-0014.
Boglárka Tóth: On leave from the Research Group on Artificial Intelligence of the Hungarian Academy of Sciences and the University
of Szeged, H-6720 Szeged, Aradi vértanúk tere 1., Hungary. 相似文献
2.
New Interval Analysis Support Functions Using Gradient Information in a Global Minimization Algorithm 总被引:1,自引:0,他引:1
L.G. Casado J.A. MartÍnez I. GarcÍa Ya.D. Sergeyev 《Journal of Global Optimization》2003,25(4):345-362
The performance of interval analysis branch-and-bound global optimization algorithms strongly depends on the efficiency of selection, bounding, elimination, division, and termination rules used in their implementation. All the information obtained during the search process has to be taken into account in order to increase algorithm efficiency, mainly when this information can be obtained and elaborated without additional cost (in comparison with traditional approaches). In this paper a new way to calculate interval analysis support functions for multiextremal univariate functions is presented. The new support functions are based on obtaining the same kind of information used in interval analysis global optimization algorithms. The new support functions enable us to develop more powerful bounding, selection, and rejection criteria and, as a consequence, to significantly accelerate the search. Numerical comparisons made on a wide set of multiextremal test functions have shown that on average the new algorithm works almost two times faster than a traditional interval analysis global optimization method. 相似文献
3.
In this article, we introduce a global optimization algorithm that integrates the basic idea of interval branch and bound,
and new local sampling strategies along with an efficient data structure. Also included in the algorithm are procedures that
handle constraints. The algorithm is shown to be able to find all the global optimal solutions under mild conditions. It can
be used to solve various optimization problems. The local sampling (even if done stochastically) is used only to speed up
the convergence and does not affect the fact that a complete search is done. Results on several examples of various dimensions
ranging from 1 to 100 are also presented to illustrate numerical performance of the algorithm along with comparison with another
interval method without the new local sampling and several noninterval methods. The new algorithm is seen as the best performer
among those tested for solving multi-dimensional problems. 相似文献
4.
Mihály Csaba Markót Tibor Csendes András Erik Csallner 《Journal of Global Optimization》2000,16(3):219-228
We have investigated variants of interval branch-and-bound algorithms for global optimization where the bisection step was substituted by the subdivision of the current, actual interval into many subintervals in a single iteration step. The results are published in two papers, the first one contains the theoretical investigations on the convergence properties. An extensive numerical study indicates that multisection can substantially improve the efficiency of interval global optimization procedures, and multisection seems to be indispensable in solving hard global optimization problems in a reliable way. 相似文献
5.
This paper deals with two different optimization techniques to solve the bound-constrained nonlinear optimization problems based on division criteria of a prescribed search region, finite interval arithmetic and interval ranking in the context of a decision maker’s point of view. In the proposed techniques, two different division criteria are introduced where the accepted region is divided into several distinct subregions and in each subregion, the objective function is computed in the form of an interval using interval arithmetic and the subregion containing the best objective value is found by interval ranking. The process is continued until the interval width for each variable in the accepted subregion is negligible. In this way, the global optimal or close to global optimal values of decision variables and the objective function can easily be obtained in the form of an interval with negligible widths. Both the techniques are applied on several benchmark functions and are compared with the existing analytical and heuristic methods. 相似文献
6.
Experiments with a new selection criterion in a fast interval optimization algorithm 总被引:3,自引:0,他引:3
Usually, interval global optimization algorithms use local search methods to obtain a good upper (lower) bound of the solution. These local methods are based on point evaluations. This paper investigates a new local search method based on interval analysis information and on a new selection criterion to direct the search. When this new method is used alone, the guarantee to obtain a global solution is lost. To maintain this guarantee, the new local search method can be incorporated to a standard interval GO algorithm, not only to find a good upper bound of the solution, but also to simultaneously carry out part of the work of the interval B&B algorithm. Moreover, the new method permits improvement of the guaranteed upper bound of the solution with the memory requirements established by the user. Thus, the user can avoid the possible memory problems arising in interval GO algorithms, mainly when derivative information is not used. The chance of reaching the global solution with this algorithm may depend on the established memory limitations. The algorithm has been evaluated numerically using a wide set of test functions which includes easy and hard problems. The numerical results show that it is possible to obtain accurate solutions for all the easy functions and also for the investigated hard problems. 相似文献
7.
Chandra Sekhar Pedamallu Linet Özdamar Tibor Csendes 《Journal of Global Optimization》2007,37(2):177-194
In bound constrained global optimization problems, partitioning methods utilizing Interval Arithmetic are powerful techniques
that produce reliable results. Subdivision direction selection is a major component of partitioning algorithms and it plays
an important role in convergence speed. Here, we propose a new subdivision direction selection scheme that uses symbolic computing
in interpreting interval arithmetic operations. We call this approach symbolic interval inference approach (SIIA). SIIA targets
the reduction of interval bounds of pending boxes directly by identifying the major impact variables and re-partitioning them
in the next iteration. This approach speeds up the interval partitioning algorithm (IPA) because it targets the pending status
of sibling boxes produced. The proposed SIIA enables multi-section of two major impact variables at a time. The efficiency
of SIIA is illustrated on well-known bound constrained test functions and compared with established subdivision direction
selection methods from the literature. 相似文献
8.
An interval expansion method is presented to find the solution of nonlinear equation in several variables with guaranteed accuracy. In this method, the existence theorem for the solution of nonlinear equation is obtained by using two newly defined operators. A new algorithm for solving nonlinear equation in several variables is given. Furthermore, we prove that the new method is global convergent under mild conditions. 相似文献
9.
In this paper we define multisections of intervals that yield sharp lower bounds in branch-and-bound type methods for interval global optimization. A so called 'generalized kite', defined for differentiable univariate functions, is built simultaneously with linear boundary forms and suitably chosen centered forms. Proofs for existence and uniqueness of optimal cuts are given. The method described may be used either as an accelerating device or in a global optimization algorithm with an efficient pruning effect. A more general principle for decomposition of boxes is suggested. 相似文献
10.
Sonja Berner 《Journal of Global Optimization》1996,9(1):1-22
We present a new parallel method for verified global optimization, using a centralized mediator for the dynamic load balancing. The new approach combines the advantages of two previous models, the master slave model and the processor farm. Numerical results show the efficiency of this new method. For a large number of problems at least linear speedup is reached. The efficiency of this new method is also confirmed by a comparison with other parallel methods for verified global optimization. A theoretical study proves that using the best-first strategy to choose the next box for subdivision, no real superlinear speedup may be expected concerning the number of iterations. Moreover, the potential of parallelization of methods of verified global optimization is discussed in general. 相似文献
11.
José Fernández Blas Pelegrı´n Frank Plastria Boglárka Tóth 《European Journal of Operational Research》2007
A chain wants to set up a single new facility in a planar market where similar facilities of competitors, and possibly of its own chain, are already present. Fixed demand points split their demand probabilistically over all facilities in the market proportionally with their attraction to each facility, determined by the different perceived qualities of the facilities and the distances to them, through a gravitational or logit type model. Both the location and the quality (design) of the new facility are to be found so as to maximise the profit obtained for the chain. Several types of constraints and costs are considered. 相似文献