A Heuristic Rejection Criterion in Internal Global Optimization Algorithms

This paper investigates the properties of the inclusion functions on subintervals while a Branch-and-Bound algorithm is solving global optimization problems. It has been found that the relative place of the global minimum value within the inclusion interval of the inclusion function of the objective function at the actual interval mostly indicates whether the given interval is close to minimizer point. This information is used in a heuristic interval rejection rule that can save a big amount of computation. Illustrative examples are discussed and a numerical study completes the investigation.This revised version was published online in October 2005 with corrections to the Cover Date.     

A New Inclusion Function for Optimization: Kite – The One Dimensional Case

In this paper the kite inclusion function is presented for branch-and-bound type interval global optimization using at least gradient information. The basic idea comes from the simultaneous usage of the centered forms and the linear boundary value forms. We will show that the new technique is not worse and usually considerably better than these two. The best choice for the center of the kite inclusion will be given. The isotonicity and at least quadratical convergence hold and there is a pruning effect of the kite which is derived from the construction of the inclusion, thus more function evaluations are not needed to use it. A numerical investigation on large standard multiextremal test functions has been done to show the performance.     

Theoretical rate of convergence for interval inclusion functions

Geometric branch-and-bound methods are commonly used solution algorithms for non-convex global optimization problems in small dimensions, say for problems with up to six or ten variables, and the efficiency of these methods depends on some required lower bounds. For example, in interval branch-and-bound methods various well-known lower bounds are derived from interval inclusion functions. The aim of this work is to analyze the quality of interval inclusion functions from the theoretical point of view making use of a recently introduced and general definition of the rate of convergence in geometric branch-and-bound methods. In particular, we compare the natural interval extension, the centered form, and Baumann’s inclusion function. Furthermore, our theoretical findings are justified by detailed numerical studies using the Weber problem on the plane with some negative weights as well as some standard global optimization benchmark problems.     

Empirical convergence speed of inclusion functions for facility location problems

One of the key points in interval global optimization is the selection of a suitable inclusion function which allows to solve the problem efficiently. Usually, the tighter the inclusions provided by the inclusion function, the better, because this will make the accelerating devices used in the algorithm more effective at discarding boxes. On the other hand, whereas more sophisticated inclusion functions may give tighter inclusions, they require more computational effort than others providing larger overestimations. In an earlier paper, the empirical convergence speed of inclusion functions was defined and studied, and it was shown to be a good indicator of the inclusion precision. If the empirical convergence speed is analyzed for a given type of functions, then one can select the appropriate inclusion function to be used when dealing with those type of functions. In this paper we present such a study, dealing with functions used in competitive facility location problems.     

Bound constrained interval global optimization in the COCONUT Environment

We introduce a new interval global optimization method for solving bound constrained problems. The method originates from a small standalone software and is implemented in the COCONUT Environment, a framework designed for the development of complex algorithms, containing numerous state-of-the-art methods in a common software platform. The original algorithm is enhanced by various new methods implemented in COCONUT, regarding both interval function evaluations (such as first and second order derivatives with backward automatic differentiation, slopes, slopes of derivatives, bicentered forms, evaluations on the Karush–John conditions, etc.) and algorithmic elements (inclusion/exclusion boxes, local search, constraint propagation). This resulted in a substantial performance increase as compared to the original code. During the selection of the best combination of options, we performed comparison tests that gave empirical answers to long-lasting algorithmic questions (such as whether to use interval gradients or use slopes instead), that have never been studied numerically in such detail before. The new algorithm, called coco_gop_ex, was tested against the prestigious BARON software on an extensive set of bound constrained problems. We found that in addition to accepting a wider class of bound constrained problems and providing more output information (by locating all global minimizers), coco_gop_ex is competitive with BARON in terms of the solution success rates (with the exception of a set of nonlinear least squares problems), and it often outperforms BARON in running time. In particular, coco_gop_ex was around 21 % faster on average over the set of problems solved by both software systems.     

An Algorithm for Global Optimization using the Taylor–Bernstein Form as Inclusion Function

We investigate the use of higher order inclusion functions in the Moore–Skelboe (MS) algorithm of interval analysis (IA) for unconstrained global optimization. We first propose an improvement of the Taylor–Bernstein (TB) form given in (Lin and Rokne (1996) 101) which has the property of higher order convergence. We make the improvement so that the TB form is more effective in practice. We then use the improved TB form as an inclusion function in a prototype MS algorithm and also modify the cut-off test and termination condition in the algorithm. We test and compare on several examples the performances of the proposed algorithm, the MS algorithm, and the MS algorithm with the Taylor model of Berz and Hoffstatter (1998; 97) as inclusion function. The results of these (preliminary) tests indicate that the proposed algorithm with the improved TB form as inclusion function is quite effective for low to medium dimension problems studied.     

An interval set model for learning rules from incomplete information table

A novel interval set approach is proposed in this paper to induce classification rules from incomplete information table, in which an interval-set-based model to represent the uncertain concepts is presented. The extensions of the concepts in incomplete information table are represented by interval sets, which regulate the upper and lower bounds of the uncertain concepts. Interval set operations are discussed, and the connectives of concepts are represented by the operations on interval sets. Certain inclusion, possible inclusion, and weak inclusion relations between interval sets are presented, which are introduced to induce strong rules and weak rules from incomplete information table. The related properties of the inclusion relations are proved. It is concluded that the strong rules are always true whatever the missing values may be, while the weak rules may be true when missing values are replaced by some certain known values. Moreover, a confidence function is defined to evaluate the weak rule. The proposed approach presents a new view on rule induction from incomplete data based on interval set.     

Global optimization using interval analysis: The one-dimensional case

We show how interval analysis can be used to compute the minimum value of a twice continuously differentiable function of one variable over a closed interval. When both the first and second derivatives of the function have a finite number of isolated zeros, our method never fails to find the global minimum.     

Interval oriented multi-section techniques for global optimization

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.     

求解全局最优问题的多重点样本水平值估计的相对熵算法

研究有界闭箱约束下的全局最优化问题,利用相对熵及广义方差函数方程的最大根与全局最小值之间的等价关系,设计求解全局最优值的积分型水平值估计算法.对采用重点样本采样技巧产生的函数值按一定规则进行聚类,从而在各聚类中产生的若干新重点样本,结合相对熵算法,构造出多重点样本进行全局搜索的新算法.该算法的优点在于每次迭代选用当前较好的函数值信息,以达到随机搜索到更好的函数值信息.同时多重点样本可有利挖掘出更好的全局信息.一系列的数值实验表明该算法是非常有效的.     

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.     

An Algorithm for Finding Global Minimum of Nonlinear Integer Programming

A filled function is proposed by R.Ge[2] for finding a global minimizer of a function of several continuous variables. In [4], an approach for finding a global integer minimizer of nonlinear function using the above filled function is given. Meanwhile a major obstacle is met: if $ρ > 0$ is small, and $||x_I-\overset{*}{x}_I||$ is large, where $x_I$ - an integer point, $\overset{*}{x}_I$ - a current local integer minimizer, then the value of the filled function almost equals zero. Thus it is difficult to recognize the size of the value of the filled function and can not find the global integer minimizer of nonlinear function. In this paper, two new filled functions are proposed for finding global integer minimizer of nonlinear function, and the new filled function improves some properties of the filled function proposed by R. Ge [2].Some numerical results are given, which indicate the new filled function (4.1) to find global integer minimizer of nonlinear function is efficient.     

Some feasibility sampling procedures in interval methods for constrained global optimization

Three feasibility sampling procedures are developed as add-on acceleration strategies in interval methods for solving global optimization problem over a bounded interval domain subject to one or two additional linear constraints. The main features of all three procedures are their abilities to quickly test any sub-domain’s feasibility and to actually locate a feasible point if the feasible set within the sub-domain is nonempty. This add-on feature of feasibility sampling can significantly lower upper bounds of the best objective function value in any interval method and improve its convergence and effectiveness.     

An improved univariate global optimization algorithm with improved linear lower bounding functions

Recently linear lower bounding functions (LLBF's) were proposed and used to find -global minima. Basically an LLBF over an interval is a linear function which lies below a given function over the interval and matches the function value at one end point. By comparing it with the best function value found, it can be used to eliminate subregions which do not contain -global minima. To develop a more efficient LLBF algorithm, two important issues need to be addressed: how to construct a better LLBF and how to use it efficiently. In this paper, an improved LLBF for factorable functions overn-dimensional boxes is derived, in the sense that the new LLBF is always better than those in [3] for continuously differentiable functions. Exploration of the properties of the LLBF enables us to develop a new LLBF-based univariate global optimization algorithm, which is again better than those in [3]. Numerical results on some standard test functions indicate the high potential of our algorithm.This work was supported in part by VLSI Technology Inc. and Tyecin Systems Inc. through the University of California MICRO proram with grant number 92-024.     

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.     

Initial Boundary Value Problems of the Camassa–Holm Equation

In this paper we study initial boundary value problems of the Camassa–Holm equation on the half line and on a compact interval. Using rigorously the conservation of symmetry, it is possible to convert these boundary value problems into Cauchy problems for the Camassa–Holm equation on the line and on the circle, respectively. Applying thus known results for the latter equations we first obtain the local well-posedness of the initial boundary value problems under consideration. Then we present some blow-up and global existence results for strong solutions. Finally we investigate global and local weak solutions for the equation on the half line and on a compact interval, respectively. An interesting result of our analysis shows that the Camassa–Holm equation on a compact interval possesses no nontrivial global classical solutions.     

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.     

A Sequential Convexification Method (SCM) for Continuous Global Optimization

A new method for continuous global minimization problems, acronymed SCM, is introduced. This method gives a simple transformation to convert the objective function to an auxiliary function with gradually fewer local minimizers. All Local minimizers except a prefixed one of the auxiliary function are in the region where the function value of the objective function is lower than its current minimal value. Based on this method, an algorithm is designed which uses a local optimization method to minimize the auxiliary function to find a local minimizer at which the value of the objective function is lower than its current minimal value. The algorithm converges asymptotically with probability one to a global minimizer of the objective function. Numerical experiments on a set of standard test problems with several problems' dimensions up to 50 show that the algorithm is very efficient compared with other global optimization methods.     

Nonsmooth exclusion test for finding all solutions of nonlinear equations

A new approach is proposed for finding all real solutions of systems of nonlinear equations with bound constraints. The zero finding problem is converted to a global optimization problem whose global minima with zero objective value, if any, correspond to all solutions of the original problem. A branch-and-bound algorithm is used with McCormick’s nonsmooth convex relaxations to generate lower bounds. An inclusion relation between the solution set of the relaxed problem and that of the original nonconvex problem is established which motivates a method to generate automatically, starting points for a local Newton-type method. A damped-Newton method with natural level functions employing the restrictive monotonicity test is employed to find solutions robustly and rapidly. Due to the special structure of the objective function, the solution of the convex lower bounding problem yields a nonsmooth root exclusion test which is found to perform better than earlier interval-analysis based exclusion tests. Both the componentwise Krawczyk operator and interval-Newton operator with Gauss-Seidel based root inclusion and exclusion tests are also embedded in the proposed algorithm to refine the variable bounds for efficient fathoming of the search space. The performance of the algorithm on a variety of test problems from the literature is presented, and for most of them, the first solution is found at the first iteration of the algorithm due to the good starting point generation.     

求一类多元多峰函数全局极小的区间斜率方法

Based on the interval analysis, an interval slope method is proposed for finding all global minimizers of a several peaks function f on domain X^0包含于R^n, which is given by interval slope discard tests and interval extension of objective function.Numerical results of representative test functions show that this method is practical and effective.