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

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

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

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

Local Optimization Method with Global Multidimensional Search

This paper presents a new method for solving global optimization problems. We use a local technique based on the notion of discrete gradients for finding a cone of descent directions and then we use a global cutting angle algorithm for finding global minimum within the intersection of the cone and the feasible region. We present results of numerical experiments with well-known test problems and with the so-called cluster function. These results confirm that the proposed algorithms allows one to find a global minimizer or at least a deep local minimizer of a function with a huge amount of shallow local minima.     

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

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

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

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

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.     

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.     

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.     

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.     

A Hybrid Descent Method for Global Optimization

In this paper, a hybrid descent method, consisting of a simulated annealing algorithm and a gradient-based method, is proposed. The simulated annealing algorithm is used to locate descent points for previously converged local minima. The combined method has the descent property and the convergence is monotonic. To demonstrate the effectiveness of the proposed hybrid descent method, several multi-dimensional non-convex optimization problems are solved. Numerical examples show that global minimum can be sought via this hybrid descent method.     

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 Algorithm for a Kind of Nonsmooth Global Optimization

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

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     

全局优化问题的一个无参数填充函数算法

填充函数法是求解全局优化问题的一种有效的确定性算法,方法的关键在于填充函数的构造.对于一般无约束优化问题提出了一个新的无参数填充函数,通过定义证明了此填充函数能保持填充性质.利用其理论性质设计了相应的算法并对几个经典的算例进行了数值实验,实验结果表明算法有效可行.     

A New Filled Function Method for Global Optimization

A novel filled function is suggested in this paper for identifying a global minimum point for a general class of nonlinear programming problems with a closed bounded domain. Theoretical and numerical properties of the proposed filled function are investigated and a solution algorithm is proposed. The implementation of the algorithm on several test problems is reported with satisfactory numerical results.     

一种求约束总极值的水平值估计方法

给出了一种求约束总极值的水平值估计方法,说明了修正的方差方程的根与原始问题的最优值之间的等价性,给出了一种基于牛顿法的水平值估计算法并证明了实现算法的收敛性．初步的计算例子表明所给算法是有效的．     

A Radial Basis Function Method for Global Optimization

We introduce a method that aims to find the global minimum of a continuous nonconvex function on a compact subset of . It is assumed that function evaluations are expensive and that no additional information is available. Radial basis function interpolation is used to define a utility function. The maximizer of this function is the next point where the objective function is evaluated. We show that, for most types of radial basis functions that are considered in this paper, convergence can be achieved without further assumptions on the objective function. Besides, it turns out that our method is closely related to a statistical global optimization method, the P-algorithm. A general framework for both methods is presented. Finally, a few numerical examples show that on the set of Dixon-Szegö test functions our method yields favourable results in comparison to other global optimization methods.     

一个全局最优化问题的填充函数

本文给出了一个非线性全局最优化问题的填充函数定义,此定义不同于以前已有的填充函数定义。根据此定义,本文提出了一簇单参数填充函数和相应的填充函数算法．对几个算例的数据测试表明,该填充函数法是可行和有效的．     

Parametric Method for Global Optimization

This paper considers constrained and unconstrained parametric global optimization problems in a real Hilbert space. We assume that the gradient of the cost functional is Lipschitz continuous but not smooth. A suitable choice of parameters implies the linear or superlinear (supergeometric) convergence of the iterative method. From the numerical experiments, we conclude that our algorithm is faster than other existing algorithms for continuous but nonsmooth problems, when applied to unconstrained global optimization problems. However, because we solve 2n + 1 subproblems for a large number n of independent variables, our algorithm is somewhat slower than other algorithms, when applied to constrained global optimization.This work was partially supported by the NATO Outreach Fellowship - Mathematics 219.33.We thank Professor Hans D. Mittelmann, Arizona State University, for cooperation and support.