Particle swarm with radial basis function surrogates for expensive black-box optimization

This paper develops the OPUS (Optimization by Particle swarm Using Surrogates) framework for expensive black-box optimization. In each iteration, OPUS considers multiple trial positions for each particle in the swarm and uses a surrogate model to identify the most promising trial position. Moreover, the current overall best position is refined by finding the global minimum of the surrogate in the neighborhood of that position. OPUS is implemented using an RBF surrogate and the resulting OPUS-RBF algorithm is applied to a 36-D groundwater bioremediation problem, a 14-D watershed calibration problem, and ten mostly 30-D test problems. OPUS-RBF is compared with a standard PSO, CMA-ES, two other surrogate-assisted PSO algorithms, and an RBF-assisted evolution strategy. The numerical results suggest that OPUS-RBF is promising for expensive black-box optimization.     

Minimax efficient finite-difference stochastic gradient estimators using black-box function evaluations

Standard approaches to stochastic gradient estimation, with only noisy black-box function evaluations, use the finite-difference method or its variants. Though natural, it is open to our knowledge whether their statistical accuracy is the best possible. This paper argues so by showing that central finite-difference is a nearly minimax optimal zeroth-order gradient estimator for a suitable class of objective functions and mean squared risk, among both the class of linear estimators and the much larger class of all (nonlinear) estimators.     

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.     

Constrained optimization involving expensive function evaluations: A sequential approach

This paper presents a new sequential method for constrained nonlinear optimization problems. The principal characteristics of these problems are very time consuming function evaluations and the absence of derivative information. Such problems are common in design optimization, where time consuming function evaluations are carried out by simulation tools (e.g., FEM, CFD). Classical optimization methods, based on derivatives, are not applicable because often derivative information is not available and is too expensive to approximate through finite differencing.The algorithm first creates an experimental design. In the design points the underlying functions are evaluated. Local linear approximations of the real model are obtained with help of weighted regression techniques. The approximating model is then optimized within a trust region to find the best feasible objective improving point. This trust region moves along the most promising direction, which is determined on the basis of the evaluated objective values and constraint violations combined in a filter criterion. If the geometry of the points that determine the local approximations becomes bad, i.e. the points are located in such a way that they result in a bad approximation of the actual model, then we evaluate a geometry improving instead of an objective improving point. In each iteration a new local linear approximation is built, and either a new point is evaluated (objective or geometry improving) or the trust region is decreased. Convergence of the algorithm is guided by the size of this trust region. The focus of the approach is on getting good solutions with a limited number of function evaluations.     

A proximal trust-region method for nonsmooth optimization with inexact function and gradient evaluations

Mathematical Programming - Many applications require minimizing the sum of smooth and nonsmooth functions. For example, basis pursuit denoising problems in data science require minimizing a measure...     

Using parallel function evaluations to improve hessian approximation for unconstrained optimization

This paper presents a new class of methods for solving unconstrained optimization problems on parallel computers. The methods are intended to solve small to moderate dimensional problems where function and derivative evaluation is the dominant cost. They utilize multiple processors to evaluate the function, (finite difference) gradient, and a portion of the finite difference Hessian simultaneously at each iterate. We introduce three types of new methods, which all utilize the new finite difference Hessian information in forming the new Hessian approximation at each iteration; they differ in whether and how they utilize the standard secant information from the current step as well. We present theoretical analyses of the rate of convergence of several of these methods. We also present computational results which illustrate their performance on parallel computers when function evaluation is expensive.Research supported by AFOSR grant AFOSR-85-0251, ARO contract DAAG 29-84-K-0140, NSF grant DCR-8403483, and NFS cooperative agreement DCR -8420944.     

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

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

Deterministic global derivative-free optimization of black-box problems with bounded Hessian

Obtaining guaranteed lower bounds for problems with unknown algebraic form has been a major challenge in derivative-free optimization. In this work, we pre     

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.     

Local optimization of black-box functions with high or infinite-dimensional inputs: application to nuclear safety

Black-box optimization problems when the input space is a high-dimensional space or a function space appear in more and more applications. In this context, the methods available for finite-dimensional data do not apply. The aim is then to propose a general method for optimization involving dimension reduction techniques. Different dimension reduction basis are considered (including data-driven basis). The methodology is illustrated on simulated functional data. The choice of the different parameters, in particular the dimension of the approximation space, is discussed. The method is finally applied to a problem of nuclear safety.     

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.     

Linear information versus function evaluations for -approximation

We study algorithms for the approximation of functions, the error is measured in an L₂ norm. We consider the worst case setting for a general reproducing kernel Hilbert space of functions. We analyze algorithms that use standard information consisting in n function values and we are interested in the optimal order of convergence. This is the maximal exponent b for which the worst case error of such an algorithm is of order n^-b.Let p be the optimal order of convergence of all algorithms that may use arbitrary linear functionals, in contrast to function values only. So far it was not known whether p>b is possible, i.e., whether the approximation numbers or linear widths can be essentially smaller than the sampling numbers. This is (implicitly) posed as an open problem in the recent paper [F.Y. Kuo, G.W. Wasilowski, H. Woźniakowski, On the power of standard information for multivariate approximation in the worst case setting, J. Approx. Theory, to appear] where the authors prove that implies . Here we prove that the case and b=0 is possible, hence general linear information can be exponentially better than function evaluation. Since the case is quite different, it is still open whether b=p always holds in that case.     

A lower bound for the number of function evaluations in an error estimate for numerical integration

A popular practical way to estimate the error in numerical integration is to use two cubature formulae. In this paper we give a lower bound for the number of function evaluations necessary to approximate the integral and the error.Communicated by Ronald A. DeVore.AMS classification: 65D30, 65G99.     

A Python/C library for bound-constrained global optimization with continuous GRASP

This paper describes ${\texttt{libcgrpp}}$ , a GNU-style dynamic shared Python/C library of the continuous greedy randomized adaptive search procedure (C-GRASP) for bound constrained global optimization. C-GRASP is an extension of the GRASP metaheuristic (Feo and Resende, 1989) and has been used to solve unstable and nondifferentiable problems, as well as hard global optimization problems, such as chemical equilibrium systems and robot kinematics applications (Hirsch et al. in Optim lett 1:201–212, 2007). After a brief introduction to C-GRASP, we show how to download, install, configure, and use the library through an illustrative example.     

CBLIB 2014: a benchmark library for conic mixed-integer and continuous optimization

The Conic Benchmark Library is an ongoing community-driven project aiming to challenge commercial and open source solvers on mainstream cone support. In this paper, 121 mixed-integer and continuous second-order cone problem instances have been selected from 11 categories as representative for the instances available online. Since current file formats were found incapable, we embrace the new Conic Benchmark Format as standard for conic optimization. Tools are provided to aid integration of this format with other software packages.     

Robust penalty function method for an uncertain multi-time control optimization problems

This paper gives some new results on multi-time first-order PDE constrained control optimization problem in the face of data uncertainty (MCOPU). We obtain the robust sufficient optimality conditions for (MCOPU). Further, we construct an unconstrained multi-time control optimization problem (MCOPU)_? corresponding to (MCOPU) via absolute value penalty function method. Then, we show that the robust optimal solution to the constrained problem and a robust minimizer to the unconstrained problem are equivalent under suitable hypotheses. Moreover, we give some non-trivial examples to validate the results established in this paper.     

Dynamic pricing for perishable items with costly price adjustments

Dynamic pricing is widely adopted in inventory management for perishable items, and the corresponding price adjustment cost should be taken into account. This work assumes that the price adjustment cost comprises of a fixed component and a variable one, and attempts to search for the optimal dynamic pricing strategy to maximize the firm’s profit. However, considering the fixed price adjustment cost turns this dynamic pricing problem to a non-smooth optimal control problem which cannot be solved directly by Pontryagin’s maximum principle. Hence, we first degenerate the original problem into a standard optimal control problem and calculate the corresponding solution. On the basis of this solution, we further propose a suboptimal pricing strategy which simultaneously combines static pricing and dynamic pricing strategies. The upper bound of profit gap between the suboptimal solution and the optimal one is obtained. Numerical simulation indicates that the suboptimal pricing strategy enjoys an efficient performance.