An official website of the United States government
Bayesian optimization relies on iteratively constructing and optimizing an acquisition function. The latter turns out to be a challenging, non-convex optimization problem itself. Despite the relative importance of this step, most algorithms employ sampling- or gradient-based methods, which do not provably converge to global optima. This work investigates mixed-integer programming (MIP) as a paradigm for global acquisition function optimization. Specifically, our Piecewise-linear Kernel Mixed Integer Quadratic Programming (PK-MIQP) formulation introduces a piecewise-linear approximation for Gaussian process kernels and admits a corresponding MIQP representation for acquisition functions. The proposed method is applicable to uncertainty-based acquisition functions for any stationary or dot-product kernel. We analyze the theoretical regret bounds of the proposed approximation, and empirically demonstrate the framework on synthetic functions, constrained benchmarks, and a hyperparameter tuning task.
more »
« less
A Computational Comparison of Simulation Optimization Methods using Single Observations within a Shrinking Ball on Noisy Black-Box Functions with Mixed Integer and Continuous Domains
We focus on simulation optimization algorithms that are designed to accommodate noisy black-box functions on mixed integer/continuous domains. There are several approaches used to account for noise which include aggregating multiple function replications from sample points and a newer method of aggregating single replications within a “shrinking ball.” We examine a range of algorithms, including, simulated annealing, interacting particle, covariance-matrix adaption evolutionary strategy, and particle swarm optimization to compare the effectiveness in generating optimal solutions using averaged function replications versus a shrinking ball approximation. We explore problems in mixed integer/continuous domains. Six test functions are examined with 10 and 20 dimensions, with integer restrictions enforced on 0%, 50%, and 100% of the dimensions, and with noise ranging from 10% to 20% of function output. This study demonstrates the relative effectiveness of using the shrinking ball approach, demonstrating that its use typically enhances solver performance for the tested optimization methods.
more »
« less
- Award ID(s):
- 1632793
- PAR ID:
- 10039379
- Date Published:
- Journal Name:
- Proceedings of the 2017 Winter Simulation Conference
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)A bstract In celestial conformal field theory, gluons are represented by primary fields with dimensions ∆ = 1 + iλ , λ ∈ ℝ and spin J = ±1, in the adjoint representation of the gauge group. All two- and three-point correlation functions of these fields are zero as a consequence of four-dimensional kinematic constraints. Four-point correlation functions contain delta-function singularities enforcing planarity of four-particle scattering events. We relax these constraints by taking a shadow transform of one field and perform conformal block decomposition of the corresponding correlators. We compute the conformal block coefficients. When decomposed in channels that are “compatible” in two and four dimensions, such four-point correlators contain conformal blocks of primary fields with dimensions ∆ = 2 + M + iλ , where M ≥ 0 is an integer, with integer spin J = −M, −M + 2 , … , M − 2 , M . They appear in all gauge group representations obtained from a tensor product of two adjoint representations. When decomposed in incompatible channels, they also contain primary fields with continuous complex spin, but with positive integer dimensions.more » « less
-
Optimizing the performance of complex systems modeled by stochastic computer simulations is a challenging task, partly because of the lack of structural properties (e.g., convexity). This challenge is magnified by the presence of random error whereby an adaptive algorithm searching for better designs can at times mistakenly accept an inferior design. In contrast to performing multiple simulations at a design point to estimate the performance of the design, we propose a framework for adaptive search algorithms that executes a single simulation for each design point encountered. Here the estimation errors are reduced by averaging the performances from previously evaluated designs drawn from a shrinking ball around the current design point. We show under mild regularity conditions for continuous design spaces that the accumulated errors, although dependent, form a martingale process, and hence, by the strong law of large numbers for martingales, the average errors converge to zero as the algorithm proceeds. This class of algorithms is shown to converge to a global optimum with probability one. By employing a shrinking ball approach with single observations, an adaptive search algorithm can simultaneously improve the estimates of performance while exploring new and potentially better design points. Numerical experiments offer empirical support for this paradigm of single observation simulation optimization.more » « less
-
Bayesian Networks (BNs) represent conditional probability relations among a set of random variables (nodes) in the form of a directed acyclic graph (DAG), and have found diverse applications in knowledge discovery. We study the problem of learning the sparse DAG structure of a BN from continuous observational data. The central problem can be modeled as a mixed-integer program with an objective function composed of a convex quadratic loss function and a regularization penalty subject to linear constraints. The optimal solution to this mathematical program is known to have desirable statistical properties under certain conditions. However, the state-of-the-art optimization solvers are not able to obtain provably optimal solutions to the existing mathematical formulations for medium-size problems within reasonable computational times. To address this difficulty, we tackle the problem from both computational and statistical perspectives. On the one hand, we propose a concrete early stopping criterion to terminate the branch-and-bound process in order to obtain a near-optimal solution to the mixed-integer program, and establish the consistency of this approximate solution. On the other hand, we improve the existing formulations by replacing the linear “big-M " constraints that represent the relationship between the continuous and binary indicator variables with second-order conic constraints. Our numerical results demonstrate the effectiveness of the proposed approaches.more » « less
-
Sustainability is increasingly recognized as a critical global issue. Multi-objective optimization is an important approach for sustainable decision-making, but problems with four or more objectives are hard to interpret due to its high dimensions. In our groups previous work, an algorithm capable of systematically reducing objective dimensionality for (mixed integer) linear Problem has been developed. In this work, we will extend the algorithm to tackle nonlinear many-objective problems. An outer approximation-like method is employed to systematically replace nonlinear objectives and constraints. After converting the original nonlinear problem to linear one, previous linear algorithm can be applied to reduce the dimensionality. The benchmark DTLZ5(I, M) problem set is used to evaluate the effectiveness of this approach. Our algorithm demonstrates the ability to identify appropriate objective groupings on benchmark problems of up to 20 objectives when algorithm hyperparameters are appropriately chosen. We also conduct extensive testing on the hyperparameters to determine their optimal settings. Additionally, we analyze the computation time required for different components of the algorithm, ensuring efficiency and practical applicability.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
