Deterministic and stochastic global optimization techniques for planar covering with ellipses problems

Problems of planar covering with ellipses are tackled in this work. Ellipses can have a fixed angle or each of them can be freely rotated. Deterministic global optimization methods are developed for both cases, while a stochastic version of the method is also proposed for large instances of the latter case. Numerical results show the effectiveness and efficiency of the proposed methods.     

A black-box scatter search for optimization problems with integer variables

The goal of this work is the development of a black-box solver based on the scatter search methodology. In particular, we seek a solver capable of obtaining high quality outcomes to optimization problems for which solutions are represented as a vector of integer values. We refer to these problems as integer optimization problems. We assume that the decision variables are bounded and that there may be constraints that require that the black-box evaluator is called in order to know whether they are satisfied. Problems of this type are common in operational research areas of applications such as telecommunications, project management, engineering design and the like.Our experimental testing includes 171 instances within four classes of problems taken from the literature. The experiments compare the performance of the proposed method with both the best context-specific procedures designed for each class of problem as well as context-independent commercial software. The experiments show that the proposed solution method competes well against commercial software and that can be competitive with specialized procedures in some problem classes.     

Implicitly and densely discrete black-box optimization problems

This paper addresses derivative-free optimization problems where the variables lie implicitly in an unknown discrete closed set. The evaluation of the objective function follows a projection onto the discrete set, which is assumed dense (and not sparse as in integer programming). Such a mathematical setting is a rough representation of what is common in many real-life applications where, despite the continuous nature of the underlying models, a number of practical issues dictate rounding of values or projection to nearby feasible figures. We discuss a definition of minimization for these implicitly discrete problems and outline a direct-search algorithm framework for its solution. The main asymptotic properties of the algorithm are analyzed and numerically illustrated.     

A derivative-free algorithm for linearly constrained optimization problems

Based on the NEWUOA algorithm, a new derivative-free algorithm is developed, named LCOBYQA. The main aim of the algorithm is to find a minimizer $x^{*} \in\mathbb{R}^{n}$ of a non-linear function, whose derivatives are unavailable, subject to linear inequality constraints. The algorithm is based on the model of the given function constructed from a set of interpolation points. LCOBYQA is iterative, at each iteration it constructs a quadratic approximation (model) of the objective function that satisfies interpolation conditions, and leaves some freedom in the model. The remaining freedom is resolved by minimizing the Frobenius norm of the change to the second derivative matrix of the model. The model is then minimized by a trust-region subproblem using the conjugate gradient method for a new iterate. At times the new iterate is found from a model iteration, designed to improve the geometry of the interpolation points. Numerical results are presented which show that LCOBYQA works well and is very competing against available model-based derivative-free algorithms.     

GOSH: derivative-free global optimization using multi-dimensional space-filling curves

Global optimization is a field of mathematical programming dealing with finding global (absolute) minima of multi-dimensional multiextremal functions. Problems of this kind where the objective function is non-differentiable, satisfies the Lipschitz condition with an unknown Lipschitz constant, and is given as a “black-box” are very often encountered in engineering optimization applications. Due to the presence of multiple local minima and the absence of differentiability, traditional optimization techniques using gradients and working with problems having only one minimum cannot be applied in this case. These real-life applied problems are attacked here by employing one of the mostly abstract mathematical objects—space-filling curves. A practical derivative-free deterministic method reducing the dimensionality of the problem by using space-filling curves and working simultaneously with all possible estimates of Lipschitz and Hölder constants is proposed. A smart adaptive balancing of local and global information collected during the search is performed at each iteration. Conditions ensuring convergence of the new method to the global minima are established. Results of numerical experiments on 1000 randomly generated test functions show a clear superiority of the new method w.r.t. the popular method DIRECT and other competitors.     

Dynamic optimization problems with bounded terminal conditions

Bounded terminal conditions of nonlinear optimization problems are converted to equality terminal conditions via the Valentine's device. In so doing, additional unknown parameters are introduced into the problem. The transformed problems can still be easily solved using the sequential gradient-restoration algorithm (SGRA) via a simple augmentation of the unknown parameter vector . Three example problems with bounded terminal conditions are solved to verify this technique.This research was supported in part by the National Aeronautics and Space Administration under NASA Grant No. NCC 2-106.     

服务台不可靠的重试排队系统均衡分析

本文研究服务台不可靠的M/M/1常数率重试排队系统中顾客的均衡进队策略, 其中服务台在正常工作和空闲状态下以不同的速率发生故障。在该系统中, 服务台前没有等待空间, 如果到达的顾客发现服务台处于空闲状态, 该顾客可占用服务台开始服务。否则, 如果服务台处于忙碌状态, 顾客可以选择留下信息, 使得服务台在空闲时可以按顺序在重试空间中寻找之前留下信息的顾客进行服务。当服务台发生故障时, 正在被服务的顾客会发生丢失, 且系统拒绝新的顾客进入系统。根据系统提供给顾客的不同程度的信息, 研究队长可见和不可见两种信息情形下系统的稳态指标, 以及顾客基于收入-支出函数的均衡进队策略, 并建立单位时间内服务商的收益和社会福利函数。比较发现, 披露队长信息不一定能提高服务商收益和社会福利。     

Worst-case global optimization of black-box functions through Kriging and relaxation

A new algorithm is proposed to deal with the worst-case optimization of black-box functions evaluated through costly computer simulations. The input variables of these computer experiments are assumed to be of two types. Control variables must be tuned while environmental variables have an undesirable effect, to which the design of the control variables should be robust. The algorithm to be proposed searches for a minimax solution, i.e., values of the control variables that minimize the maximum of the objective function with respect to the environmental variables. The problem is particularly difficult when the control and environmental variables live in continuous spaces. Combining a relaxation procedure with Kriging-based optimization makes it possible to deal with the continuity of the variables and the fact that no analytical expression of the objective function is available in most real-case problems. Numerical experiments are conducted to assess the accuracy and efficiency of the algorithm, both on analytical test functions with known results and on an engineering application.     

Deterministic global optimization in ab-initio quantum chemistry

A large number of problems in ab-initio quantum chemistry involve finding the global minimum of the total system energy. These problems are traditionally solved by numerical approaches equivalent to local optimization. While these approaches are relatively efficient, they do not provide guarantees of global optimality unless a starting point sufficiently close to the global minimum is known apriori. Due to the enormous amount of computational effort required to solve these problems, more mathematically rigorous alternatives have so far received very little attention. Taking the above issue into consideration, this paper explores the use of deterministic global optimization in the context of Hartree-Fock theory, an important mathematical model applied in many quantum chemistry methods. In particular, it presents a general purpose approach for generating linear relaxations for problems arising from Hartree-Fock theory. This was then implemented as an extension to the ${{\tt COUENNE}}$ (Convex Over and Under ENvelopes for Nonlinear Estimation) branch and bound mixed integer non-linear programs solver. Proof of concept calculations that simultaneously optimise the orbital coefficients and the location of the nuclei in closed-shell Hartree-Fock calculations are presented and discussed.     

Deterministic global optimization in isothermal reactor network synthesis

The reactor network synthesis problem involves the simultaneous determination of the structure and operating conditions of a reactor system to optimize a given performance measure. This performance measure may be the yield of a given product, the selectivity between products, or the overall profitability of the process. The problem is formulated as a nonlinear program (NLP) using a superstructure based method in which plug flow reactors (PFRs) in the structure are modeled using differential-algebraic equations (DAEs). This formulation exhibits multiple local minima. To overcome this, a novel deterministic global optimization method tailored to the special structure and characteristics of this problem will be presented. Examples of isothermal networks will be discussed to show the nature of the local minima and illustrate various components of the proposed approach.     

A Kriging-based constrained global optimization algorithm for expensive black-box functions with infeasible initial points

In many engineering optimization problems, the objective and the constraints which come from complex analytical models are often black-box functions with extensive computational effort. In this case, it is necessary for optimization process to use sampling data to fit surrogate models so as to reduce the number of objective and constraint evaluations as soon as possible. In addition, it is sometimes difficult for the constrained optimization problems based on surrogate models to find a feasible point, which is the premise of further searching for a global optimal feasible solution. For this purpose, a new Kriging-based Constrained Global Optimization (KCGO) algorithm is proposed. Unlike previous Kriging-based methods, this algorithm can dispose black-box constrained optimization problem even if all initial sampling points are infeasible. There are two pivotal phases in KCGO algorithm. The main task of the first phase is to find a feasible point when there is no feasible data in the initial sample. And the aim of the second phase is to obtain a better feasible point under the circumstances of fewer expensive function evaluations. Several numerical problems and three design problems are tested to illustrate the feasibility, stability and effectiveness of the proposed method.     

An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization

Powerful response surface methods based on kriging and radial basis function (RBF) interpolation have been developed for expensive, i.e. computationally costly, global nonconvex optimization. We have implemented some of these methods in the solvers rbfSolve and EGO in the TOMLAB Optimization Environment (http://www.tomopt.com/tomlab/). In this paper we study algorithms based on RBF interpolation. The practical performance of the RBF algorithm is sensitive to the initial experimental design, and to the static choice of target values. A new adaptive radial basis interpolation (ARBF) algorithm, suitable for parallel implementation, is presented. The algorithm is described in detail and its efficiency is analyzed on the standard test problem set of Dixon–Szegö. Results show that it outperforms the published results of rbfSolve and several other solvers.     

Efficient computation of spectral bounds for Hessian matrices on hyperrectangles for global optimization

We compare two established and a new method for the calculation of spectral bounds for Hessian matrices on hyperrectangles by applying them to a large collection of 1,522 objective and constraint functions extracted from benchmark global optimization problems. Both the tightness of the spectral bounds and the computational effort of the three methods, which apply to $C^2$ functions ${\varphi }:\mathbb{R }^n\rightarrow \mathbb{R }$ that can be written as codelists, are assessed. Specifically, we compare eigenvalue bounds obtained with the interval variant of Gershgorin’s circle criterion (Adjiman et al. in Comput Chem Eng 22(9):1137–1158, 1998; Gershgorin in Izv. Akad. Nauk SSSR, Ser. fizmat. 6:749–754, 1931), Hertz (IEEE Trans Autom Control 37:532–535, 1992) and Rohn’s (SIAM J Matrix Anal Appl 15(1):175–184, 1994) method for tight bounds of interval matrices, and a recently proposed Hessian matrix eigenvalue arithmetic (Mönnigmann in SIAM J. Matrix Anal. Appl. 32(4): 1351–1366, 2011), which deliberately avoids the computation of interval Hessians. The eigenvalue arithmetic provides tighter, as tight, and less tight bounds than the interval variant of Gershgorin’s circle criterion in about 15, 61, and 24 % of the examples, respectively. Hertz and Rohn’s method results in bounds that are always as tight as or tighter than those from Gershgorin’s circle criterion, and as tight as or tighter than those from the eigenvalue arithmetic in 96 % of the cases. In 4 % of the examples, the eigenvalue arithmetic results in tighter bounds than Hertz and Rohn’s method. This result is surprising, since Hertz and Rohn’s method provides tight bounds for interval matrices. The eigenvalue arithmetic provides tighter bounds in these cases, since it is not based on interval matrices.     

基于Kronecker型替换的黑盒多项式稀疏插值

本文基于新的Kronecker型替换,给出两个由黑盒表示的稀疏多项式的新确定性插值算法.令f∈R[x1,……,xn]是一个稀疏黑盒多项式,其次数上界为D.当R是C或者是有限域时,相对于已有算法,新算法具有更好的计算复杂度或者关于D的复杂度更低.特别地,对于一般黑盒模型,D是复杂度中的主要因素,而在所有的确定性算法中,本文的第二个算法的复杂度关于D是最低的.