A Nonsmooth Global Optimization Technique Using Slopes: The One-Dimensional Case

In this paper we introduce a pruning technique based on slopes in the context of interval branch-and-bound methods for nonsmooth global optimization. We develop the theory for a slope pruning step which can be utilized as an accelerating device similar to the monotonicity test frequently used in interval methods for smooth problems. This pruning step offers the possibility to cut away a large part of the box currently investigated by the optimization algorithm. We underline the new technique's efficiency by comparing two variants of a global optimization model algorithm: one equipped with the monotonicity test and one equipped with the pruning step. For this reason, we compared the required CPU time, the number of function and derivative or slope evaluations, and the necessary storage space when solving several smooth global optimization problems with the two variants. The paper concludes on the test results for several nonsmooth examples.     

Multisection in Interval Branch-and-Bound Methods for Global Optimization – I. Theoretical Results

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 convergence properties of the multisplitting methods, an important class of multisection procedures are investigated in detail. We also studied theoretically the convergence improvements caused by multisection on algorithms which involve the accelerating tests (like e.g. the monotonicity test). The results are published in two papers, the second one contains the numerical test result.     

Global optimization of bounded factorable functions with discontinuities

A deterministic global optimization method is developed for a class of discontinuous functions. McCormick’s method to obtain relaxations of nonconvex functions is extended to discontinuous factorable functions by representing a discontinuity with a step function. The properties of the relaxations are analyzed in detail; in particular, convergence of the relaxations to the function is established given some assumptions on the bounds derived from interval arithmetic. The obtained convex relaxations are used in a branch-and-bound scheme to formulate lower bounding problems. Furthermore, convergence of the branch-and-bound algorithm for discontinuous functions is analyzed and assumptions are derived to guarantee convergence. A key advantage of the proposed method over reformulating the discontinuous problem as a MINLP or MPEC is avoiding the increase in problem size that slows global optimization. Several numerical examples for the global optimization of functions with discontinuities are presented, including ones taken from process design and equipment sizing as well as discrete-time hybrid systems.     

Randomized algorithms in interval global optimization

This paper is a critical survey of the interval optimization methods aimed at computing global optima for multivariable functions. To overcome some drawbacks of traditional deterministic interval techniques, we outline some ways of constructing stochastic (randomized) algorithms in interval global optimization, in particular, those based on the ideas of random search and simulated annealing.     

一类非光滑全局优化问题的区间展开方法

本文利用区间展开的特点,对一类全局优化问题提出一新的区间求解方法,该方 法能处理多元函数的全局优化问题.数值试验表明提出的方法是可行和有效的.     

What can interval analysis do for global optimization?

An overview of interval arithmetical tools and basic techniques is presented that can be used to construct deterministic global optimization algorithms. These tools are applicable to unconstrained and constrained optimization as well as to nonsmooth optimization and to problems over unbounded domains. Since almost all interval based global optimization algorithms use branch-and-bound methods with iterated bisection of the problem domain we also embed our overview in such a setting.     

New Interval Analysis Support Functions Using Gradient Information in a Global Minimization Algorithm

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.     

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

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

Decomposition and interval arithmetic applied to global minimization of polynomial and rational functions

A recent global optimization algorithm using decomposition (GOP), due to Floudas and Visweswaran, when specialized to the case of polynomial functions is shown to be equivalent to an interval arithmetic global optimization algorithm which applies natural extension to the cord-slope form of Taylor's expansion. Several more efficient variants using other forms of interval arithmetic are explored. Extensions to rational functions are presented. Comparative computational experiences are reported.     

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

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

Simulation of controlled uncertain nonlinear systems

In this paper a new method for the simulation of uncertain nonlinear discrete time systems is given. The problem of simulation is reformulated as an optimization problem. Using methods of global optimization, namely, interval analysis, the global solution to the optimization problem stated is computed. Derivatives of the objective function of the optimization problem are computed using methods of automatic differentiation. The presented approach is implemented on a SPARC Station using the language PASCAL-XSC. For a typical example simulation results are presented and discussed.     

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.     

Global Optimization on an Interval

This paper provides expressions for solutions of a one-dimensional global optimization problem using an adjoint variable which represents the available one-sided improvements up to the interval “horizon.” Interpreting the problem in terms of optimal stopping or optimal starting, the solution characterization yields two-point boundary problems as in dynamic optimization. Results also include a procedure for computing the adjoint variable, as well as necessary and sufficient global optimality conditions.     

A Newton-type univariate optimization algorithm for locating the nearest extremum

This paper introduces an algorithm for univariate optimization using linear lower bounding functions (LLBF's). An LLBF over an interval is a linear function which lies below the given function over an interval and matches the given function at one end point of the interval. We first present an algorithm using LLBF's for finding the nearest root of a function in a search direction. When the root-finding method is applied to the derivative of an objective function, it is an optimization algorithm which guarantees to locate the nearest extremum along a search direction. For univariate optimization, we show that this approach is a Newton-type method, which is globally convergent with superlinear convergence rate. The applications of this algorithm to global optimization and other optimization problems are also discussed.     

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

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

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 second-order pruning step for verified global optimization

We consider pruning steps used in a branch-and-bound algorithm for verified global optimization. A first-order pruning step was given by Ratz using automatic computation of a first-order slope tuple (Ratz, Automatic Slope Computation and its Application in Nonsmooth Global Optimization. Shaker Verlag, Aachen, 1998; J. Global Optim. 14: 365–393, 1999). In this paper, we introduce a second-order pruning step which is based on automatic computation of a second-order slope tuple. We add this second-order pruning step to the algorithm of Ratz. Furthermore, we compare the new algorithm with the algorithm of Ratz by considering some test problems for verified global optimization on a floating-point computer. This paper contains some results from the author’s dissertation [29].     

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.     

NONLINEAR INTEGER PROGRAMMING AND GLOBALOPTIMIZATION

1.IntroductionAlthoughthegenerallinearintegerprogrammingproblemisNP-hard,muchworkhasbeendevotedtoit(SeeNumhauserandWolsey[1988],Schrijver[1986]).Thesolutionmethodsincludethecuttingplane,theBranch-and-Bound,thedynamicprogrammingmethodsetc..However,thegeneralnonlinearintegerprogrammingproblemisdifficulttosolve.GareyandJohnson[1979]pointedoutthattheintegerprogrammingoverRewithalinearobjectivefunctionandquadraticconstraintsisundecidable.Soifanonlinearintegerprogrammingproblemishandled,itisalw…     

Order statistics and region-based evolutionary computation

Trust region algorithms are well known in the field of local continuous optimization. They proceed by maintaining a confidence region in which a simple, most often quadratic, model is substituted to the criterion to be minimized. The minimum of the model in the trust region becomes the next starting point of the algorithm and, depending on the amount of progress made during this step, the confidence region is expanded, contracted or kept unchanged. In the field of global optimization, interval programming may be thought as a kind of confidence region approach, with a binary confidence level: the region is guaranteed to contain the optimum or guaranteed to not contain it. A probabilistic version, known as branch and probability bound, is based on an approximate probability that a region of the search space contains the optimum, and has a confidence level in the interval [0,1]. The method introduced in this paper is an application of the trust region approach within the framework of evolutionary algorithms. Regions of the search space are endowed with a prospectiveness criterion obtained from random sampling possibly coupled with a local continuous algorithm. The regions are considered as individuals for an evolutionary algorithm with mutation and crossover operators based on a transformation group. The performance of the algorithm on some standard benchmark functions is presented.