非光滑总体优化的区间算法[英文]

本文利用区间工具及目标函数的特殊导数，给出一个非光滑总体优化的区间算法，该算法提供了目标函数总体极小值及总体极小点的取值界限（在给定的精度范围内）。我们也将算法推广到并行计算中。数值实验表明本文方法是可靠和有效的。     

Heuristic Rejection in Interval Global Optimization

Based on the investigation carried out in Ref. 1, this paper incorporates new studies about the properties of inclusion functions on subintervals while a branch-and-bound algorithm is solving global optimization problems. It is found that the relative place of the global minimum value within the inclusion function value of the objective function at the current interval indicates mostly whether the given interval is close to a minimizer point. This information is used in a heuristic interval rejection rule that can save a considerable amount of computation. Illustrative examples are discussed and an extended numerical study shows the advantages of the new approach.     

Interval Analysis on Directed Acyclic Graphs for Global Optimization

A directed acyclic graph (DAG) representation of optimization problems represents each variable, each operation, and each constraint in the problem formulation by a node of the DAG, with edges representing the flow of the computation. Using bounds on ranges of intermediate results, represented as weights on the nodes and a suitable mix of forward and backward evaluation, it is possible to give efficient implementations of interval evaluation and automatic differentiation. It is shown how to combine this with constraint propagation techniques to produce narrower interval derivatives and slopes than those provided by using only interval automatic differentiation preceded by constraint propagation. The implementation is based on earlier work by L.V. Kolev, (1997), Reliable Comput., 3, 83–93 on optimal slopes and by C. Bliek, (1992), Computer Methods for Design Automation, PhD Thesis, Department of Ocean Engineering, Massachusetts Institute of Technology on backward slope evaluation. Care is taken to ensure that rounding errors are treated correctly. Interval techniques are presented for computing from the DAG useful redundant constraints, in particular linear underestimators for the objective function, a constraint, or a Lagrangian. The linear underestimators can be found either by slope computations, or by recursive backward underestimation. For sufficiently sparse problems the work is proportional to the number of operations in the calculation of the objective function (resp. the Lagrangian). Mathematics Subject Classification (2000). primary 65G40, secondary 90C26     

Global Interval Methods for Local Nonsmooth Optimization

An interval method for determining local solutions of nonsmooth unconstrained optimization problems is discussed. The objective function is assumed to be locally Lipschitz and to have appropriate interval inclusions. The method consists of two parts, a local search and a global continuation and termination. The local search consists of a globally convergent descent algorithm showing similarities to -bundle methods. While -bundle methods use polytopes as inner approximations of the -subdifferentials, which are the main tools of almost all bundle concepts, our method uses axes parallel boxes as outer approximations of the -subdifferentials. The boxes are determined almost automatically with inclusion techniques of interval arithmetic. The dimension of the boxes is equal to the dimension of the problem and remains constant during the whole computation. The application of boxes does not suffer from the necessity to invest methodical and computational efforts to adapt the polytopes to the latest state of the computation as well as to simplify them when the number of vertices becomes too large, as is the case with the polytopes. The second part of the method applies interval techniques of global optimization to the approximative local solution obtained from the search of the first part in order to determine guaranteed error bounds or to improve the solution if necessary. We present prototype algorithms for both parts of the method as well as a complete convergence theory for them and demonstrate how outer approximations can be obtained.     

一类约束全局优化的区间方法

在区间分析的基础上,对一类不等式约束的全局优化问题,给出几种新的不含全局极小的区域删除准则,提出了一个求不等式约束全局优化问题的区间算法.数值结果表明算法是可行和有效的.     

Multi-dimensional pruning from the Baumann point in an Interval Global Optimization Algorithm

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.     

求非光滑全局优化问题的区间算法

本文通过区间工具和目标函数的特殊导数提出了一个非光滑全局优化问题的区间算法，所提出的方法能给出问题的全部全局极小点及全局极小值，理论分析和数值结构均表明本文方法是有效的。     

New Subinterval Selection Criteria for Interval Global Optimization

The theoretical convergence properties of interval global optimization algorithms that select the next subinterval to be subdivided according to a new class of interval selection criteria are investigated. The latter are based on variants of the RejectIndex: , a recently thoroughly studied indicator, that can quite reliably show which subinterval is close to a global minimizer point. Extensive numerical tests on 40 problems confirm that substantial improvements can be achieved both on simple and sophisticated algorithms by the new method (utilizing the known minimum value), and that these improvements are larger when hard problems are to be solved.     

Generalized Subinterval Selection Criteria for Interval Global Optimization

The convergence properties of interval global optimization algorithms are studied which select the next subinterval to be subdivided with the largest value of the indicator pf(f _k ,X)=(f _k ? $\underline F $ (X))/( $\overline F $ (X)? $\underline F $ (X)). This time the more general case is investigated, when the global minimum value is unknown, and thus its estimation f _k in the iteration k has an important role. A sharp necessary and sufficient condition is given on the f _k values approximating the global minimum value that ensure convergence of the optimization algorithm. The new theoretical result enables new, more efficient implementations that utilize the advantages of the pf ^* based interval selection rule, even for the more general case when no reliable estimation of the global minimum value is available.     

On an Efficient Use of Gradient Information for Accelerating Interval Global Optimization Algorithms

This paper analyzes and evaluates an efficient n-dimensional global optimization algorithm. It is a natural n-dimensional extension of the algorithm of Casado et al. [1]. This algorithm takes advantage of all available information to estimate better bounds of the function. Numerical comparison made on a wide set of multiextremal test functions has shown that on average the new algorithm works faster than a traditional interval analysis global optimization method.     

A Multidimensional Branch-and-Prune Method for Interval Global Optimization

In this paper a new multidimensional extension of the recently developed one-dimensional enclosure method called kite is given for interval global optimization. A more sophisticated version of the pruning technique based on the kite method is introduced. By the new componentwise approach all the one-dimensional theoretical results and procedures can be used in the higher-dimensional case. The possibilities in the implementation of the new algorithm together with numerical results on 40 standard test problems are presented.     

Interval Algorithm for a Kind of Nonsmooth Global Optimization

§１．　ＩｎｔｒｏｄｕｃｔｉｏｎＴｈｅｆｏｌｌｏｗｉｎｇｇｌｏｂａｌｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｉｓｃｏｎｓｉｄｅｒｅｄ：ｇｌｏｂａｌｍｉｎｉｍｉｚｅｆ（ｘ）,ｆ：Ｘ０Ｒｎ→Ｒ,（１）ｗｈｅｒｅＸ０ｉｓａｎｙｃｌｏｓｅｄｄｏｍａｉｎ,ｆｉｓａｃｏｎｔｉｎｕｏｕｓａｎｄｐｉｅｃｅｗｉｓｅｓｍｏｏｔｈｆｕｎｃｔｉｏｎｏｖｅｒＸ０,ａｎｄｉｔｓｒｉｇｈｔａｎｄｌｅｆｔｄｅｒｉｖａｔｉｖｅｅｘｉｓｔａｔｎｏｎ－ｄｉｆｆｉｅｒｅｎｔｉａｂｌｅｐｏｉｎｔ,ｆｉｓｃａｌｌｅｄｑｕａｓｉ－ｓｍｏｏｔ…     

一类非光滑总体极值的区间算法

本文利用区间分析知识 ,构造了一类 n维非光滑函数总体极值的区间算法 ,理论分析和实例计算均表明本文算法安全可靠 ;能求出全部总体极小点 ;收敛速度也比以前方法[1] 明显加快     

Optimal Multisections in Interval Branch-and-Bound Methods of Global Optimization

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.     

Advances in Interval Methods for Deterministic Global Optimization in Chemical Engineering

In recent years, it has been shown that strategies based on an interval-Newton approach can be used to reliably solve a variety of nonlinear equation solving and optimization problems in chemical process engineering, including problems in parameter estimation and in the computation of phase behavior. These strategies provide a mathematical and computational guarantee either that all solutions have been located in an equation solving problem or that the global optimum has been found in an optimization problem. The primary drawback to this approach is the potentially high computational cost. In this paper, we consider strategies for bounding the solution set of the linear interval equation system that must be solved in the context of the interval-Newton method. Recent preconditioning techniques for this purpose are reviewed, and a new bounding approach based on the use of linear programming (LP) techniques is presented. Using this approach it is possible to determine the desired bounds exactly (within round out), leading to significant overall improvements in computational efficiency. These techniques will be demonstrated using several global optimization problems, with focus on problems arising in chemical engineering, including parameter estimation and molecular modeling. These problems range in size from under ten variables to over two hundred, and are solved deterministically using the interval methodology.     

Interval Branch and Bound with Local Sampling for Constrained Global Optimization

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.     

An Improved Interval Global Optimization Algorithm Using Higher-order Inclusion Function Forms

We propose an improved algorithm for unconstrained global optimization in the framework of the Moore–Skelboe algorithm of interval analysis (H. Ratschek and J. Rokne, New computer methods for global optimization, Wiley, New York, 1988). The proposed algorithm is an improvement over the one recently proposed in P.S.V. Nataraj and K. Kotecha, (J. Global Optimization, 24 (2002) 417). A novel and powerful feature of the proposed algorithm is that it uses a variety of inclusion function forms for the objective function – the simple natural inclusion, the Taylor model (M. Berz and G. Hoffstatter, Reliable Computing, 4 (1998) 83), and the combined Taylor–Bernstein form (P.S.V. Nataraj and K. Kotecha, Reliable Computing, in press). Several improvements are also proposed for the combined Taylor–Bernstein form. The performance of the proposed algorithm is numerically tested and compared with those of existing algorithms on 11 benchmark examples. The results of the tests show the proposed algorithm to be overall considerably superior to the rest, in terms of the various performance metrics chosen for comparison.     

Multisection in Interval Branch-and-Bound Methods for Global Optimization II. Numerical Tests

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.     

A Global Optimization Algorithm using Lagrangian Underestimates and the Interval Newton Method

Convex relaxations can be used to obtain lower bounds on the optimal objective function value of nonconvex quadratically constrained quadratic programs. However, for some problems, significantly better bounds can be obtained by minimizing the restricted Lagrangian function for a given estimate of the Lagrange multipliers. The difficulty in utilizing Lagrangian duality within a global optimization context is that the restricted Lagrangian is often nonconvex. Minimizing a convex underestimate of the restricted Lagrangian overcomes this difficulty and facilitates the use of Lagrangian duality within a global optimization framework. A branch-and-bound algorithm is presented that relies on these Lagrangian underestimates to provide lower bounds and on the interval Newton method to facilitate convergence in the neighborhood of the global solution. Computational results show that the algorithm compares favorably to the Reformulation–Linearization Technique for problems with a favorable structure.     

Integrating Interval Estimates of Global Optima and Local Search Methods for Combinatorial Optimization Problems

The problem of estimating the global optimal values of intractable combinatorial optimization problems is of interest to researchers developing and evaluating heuristics for these problems. In this paper we present a method for combining statistical optimum prediction techniques with local search methods such as simulated annealing and tabu search and illustrate the approach on a single machine scheduling problem. Computational experiments show that the approach yields useful estimates of optimal values with very reasonable computational effort.