PaperlayerView exact revision on arXiv

Source-linked AI summary

Constrained Efficient Global Optimization of Expensive Black-box Functions

Wenjie Xu, Yuning Jiang, Bratislav Svetozarevic, Colin N. Jones

arXiv:2211.00162v4math.OC

TL;DR

The paper addresses constrained global optimization when objectives and constraints are expensive, unknown black-box functions. It proposes CONFIG, which uses lower confidence bound Gaussian-process surrogates to choose samples and detect infeasibility. Under regularity assumptions, CONFIG achieves strong regret and violation guarantees with competitive empirical performance.

  • Problem

    Expensive unknown objective and constraint functions make constrained global optimization difficult, while existing methods may require feasible starting points or lack infeasibility detection.

  • Method

    CONFIG solves an auxiliary constrained optimization problem using lower confidence bound Gaussian-process surrogates for both the objective and constraints.

  • Results

    CONFIG matches the unconstrained cumulative regret bound, obtains similar information-gain-based cumulative violation bounds, and shows competitive empirical performance across sampled, artificial, and building-control problems.

  • Takeaways & Limitations

    For Matern and Squared Exponential kernels, the sublinear bounds yield a convergence rate to the constrained optimum and support infeasibility declaration.

  • Takeaways & Limitations

    The auxiliary problem may be infeasible with misspecified hyperparameters, an issue left for future work.

Abstract

from arXiv · show

We study the problem of constrained efficient global optimization, where both the objective and constraints are expensive black-box functions that can be learned with Gaussian processes. We propose CONFIG (CONstrained efFIcient Global Optimization), a simple and effective algorithm to solve it. Under certain regularity assumptions, we show that our algorithm enjoys the same cumulative regret bound as that in the unconstrained case and similar cumulative constraint violation upper bounds. For commonly used Matern and Squared Exponential kernels, our bounds are sublinear and allow us to derive a convergence rate to the optimal solution of the original constrained problem. In addition, our method naturally provides a scheme to declare infeasibility when the original black-box optimization problem is infeasible. Numerical experiments on sampled instances from the Gaussian process, artificial numerical problems, and a black-box building controller tuning problem all demonstrate the competitive performance of our algorithm. Compared to the other state-of-the-art methods, our algorithm significantly improves the theoretical guarantees, while achieving competitive empirical performance.

1. Introduction

Constrained expensive black-box optimization must balance limited evaluations with unknown feasibility. CONFIG addresses limitations of existing safe, violation-tolerant, and penalty-based approaches while providing theoretical and empirical guarantees.

  • Motivation: Expensive black-box evaluations motivate global optimization methods that use few samples despite non-convex, multi-modal functions.Applications include hyperparameter tuning, control optimization, and drug or materials design.
  • Existing challenges: Unknown black-box constraints create a trade-off between requiring feasible initial solutions and allowing constraint violations during optimization.Some methods may lack feasible starting points or become stuck, while violation-tolerant methods limit total violations.
  • Existing challenges: Penalty-function and primal-dual approaches require critical parameter choices, and their performance can depend heavily on tuning effort.The cited methods use penalty coefficients or dual update step sizes, while one violation bound does not represent real total violations.
  • Scope and evaluation: CONFIG also provides a scheme to detect infeasibility, addressing cases where existing methods require an initial feasible solution or cannot report infeasibility.Numerical experiments cover sampled Gaussian-process instances, artificial problems, and building controller tuning.
  • CONFIG: CONFIG uses lower confidence bound surrogates as both objective and constraints in an auxiliary constrained optimization problem.The algorithm exploits optimism in the face of uncertainty and trades potential violation for faster learning.
  • Guarantees: Under regularity assumptions, CONFIG matches the unconstrained cumulative regret bound and obtains similar information-gain-based cumulative violation bounds.For Matern and Squared Exponential kernels, the bounds are sublinear and yield a convergence rate to the constrained optimum.

2. Notation and Preliminaries

The paper formulates constrained optimization of unknown functions under noisy zero-order feedback and introduces Gaussian-process surrogates and performance metrics. Its analysis assumes compactness, bounded RKHS norms, and—when studying feasible instances—the existence of an optimum.

  • Problem statement: The problem minimizes an unknown objective over a known candidate set subject to unknown inequality constraints.Equality constraints can be represented by two inequalities.
  • Assumptions: The analysis assumes a compact candidate set and objective and constraint functions with bounded norms in corresponding RKHSs.These are presented as commonly used regularity assumptions in efficient global optimization.
  • Assumptions: For feasible instances, the formulation assumes an optimal solution exists; infeasible instances are discussed separately.The Gaussian-process model is used to construct posterior quantities and information gain, while the functions remain deterministic under an agnostic setting.
  • Feedback model: The algorithm sequentially queries candidate solutions and receives noisy evaluations of the objective and constraints.The noise variables are independent sub-Gaussian terms, and sampled points are tracked over time.
  • Surrogates: Gaussian-process posterior means, covariances, confidence bounds, and maximum information gain are defined for the objective and constraints.These quantities support confidence intervals and the subsequent algorithm design.
  • Performance metrics: Performance is measured using instantaneous and cumulative regret together with instantaneous and cumulative constraint violation.Average regret and violation are also connected to convergence toward a constrained global optimum.

3. Algorithm

CONFIG selects samples by solving an auxiliary constrained problem built from lower confidence bound surrogates. It can declare infeasibility, while its auxiliary problem is generally cheaper than directly optimizing expensive black-box functions.

  • Algorithm: CONFIG is a lower-confidence-bound algorithm based on optimism in the face of uncertainty.It is designed for constrained efficient global optimization of expensive black-box functions.
  • Algorithm: At each step, CONFIG declares infeasibility if any constraint lower confidence bound remains positive everywhere.Otherwise, it minimizes the objective lower confidence bound subject to all constraint lower confidence bounds being non-positive.
  • Algorithm: After selecting a point, the algorithm obtains noisy objective and constraint evaluations and updates the Gaussian-process posterior.This loop repeats over the prescribed horizon.
  • Design rationale: The auxiliary problem uses lower confidence bound surrogates in place of the original black-box objective and constraints.Its solution cost can be much smaller than solving the original expensive problem, even when the auxiliary problem is non-convex.
  • Guarantee and implementation: When the original problem is feasible, the algorithm avoids declaring infeasibility with high probability under the stated assumptions.Rare false declarations can arise from potentially unbounded noise, and unknown horizons can be handled using a doubling trick.

4. Analysis

The analysis bounds CONFIG’s regret and constraint violation using posterior-uncertainty quantities and maximum information gain. These results match the unconstrained regret guarantee, yield convergence to the constrained optimum, and specialize to kernel-dependent rates.

  • General bounds: CONFIG’s analysis first bounds instantaneous regret and constraint violation, then bounds the cumulative posterior standard deviation used in the guarantees.The analysis invokes Lemmas 4.1 and 4.2 before stating the main theorem.
  • General bounds: The main theorem expresses kernel-independent guarantees through maximum information gain under Assumptions 2.1, 2.2, and 2.3.The theorem holds with probability at least 1 −δ.
  • General bounds: CONFIG has exactly the same regret bound as the unconstrained case and a similar cumulative constraint-violation bound.The comparison is stated directly after Theorem 4.3.
  • Kernel-specific results: Table 2 lists kernel-specific cumulative regret and violation bounds together with convergence rates, using maximum-information-gain bounds and parameters d and ν.For the Matérn kernel, the stated condition is ν > d; linear and squared exponential kernels satisfy the corresponding condition.
  • Convergence: Theorem 4.4 gives a convergence rate to the constrained optimal value for a selected sample point in the optimization sequence.The selected point ˜xT belongs to {x1, x2, · · · , xT} and the guarantee holds for every constraint j.

5. Infeasibility Declaration

CONFIG includes an infeasibility-detection scheme that avoids declaring feasible problems infeasible with high probability and detects infeasible problems within a bounded number of steps. When the horizon is unavailable or insufficient, the authors describe a doubling trick.

  • Motivation: The infeasibility scheme is needed because the original constrained black-box problem may itself be infeasible.The algorithm can declare infeasibility in line 1.
  • Guarantees: For feasible problems, Lemma 4.1 states that CONFIG does not declare infeasibility with high probability.This controls false positives.
  • Guarantees: For infeasible problems, Theorem 5.1 guarantees declaration within a specified number of steps with probability at least 1 −δ.The theorem assumes Assumptions 2.1 and 2.2 and a desired confidence level δ ∈(0, 1).
  • Implementation: When the horizon T is unknown or too small, the doubling trick increases T across successive rounds until it is sufficient for infeasibility declaration.The procedure starts with T = 1 and doubles T after each round.
  • Kernel-specific condition: The kernel-specific analysis notes that the relevant condition holds for linear and squared exponential kernels, while Matérn kernels require ν > d.Here d is the input dimension and ν is the Matérn smoothness parameter.

6. Experiments

Experiments compare CONFIG with constrained Bayesian optimization baselines on sampled Gaussian-process instances, artificial problems, and building-controller tuning. Across these settings, CONFIG achieves competitive solution quality while using lower-confidence-bound surrogates and maintains computational practicality for low-dimensional problems.

  • Experimental setup: CONFIG is evaluated against SafeOPT, CEI, primal-dual, and EPBO on sampled, artificial, and building-controller problems.The experiments use Gaussian-process instances, artificial numerical benchmarks, and a room-temperature controller tuning task.
  • Experimental setup: CONFIG uses lower-confidence-bound surrogates for both objective and constraints to select each next sample.The auxiliary constrained optimization is solved using explicit lower-confidence bounds, making its computational cost much smaller than expensive function evaluations.
  • Sampled Gaussian-process instances: CONFIG matches CEI competitively in both cumulative regret and cumulative violation, while SafeOPT has almost linear regret and the primal-dual method almost linear violation.EPBO can also suffer almost linear cumulative violation when its penalty is too small.
  • Sampled Gaussian-process instances: CONFIG achieves empirical convergence speed competitive with CEI for the best-observed suboptimality-plus-violation measure.This measure tracks convergence toward the optimal feasible solution as the number of optimization steps increases.
  • Infeasible instances: Over 50 infeasible instances, CONFIG consistently declares infeasibility within 16.3 steps on average.The instances are created by shifting the sampled constraint function so that the feasible set is empty.
  • Artificial numerical instances: In artificial benchmarks, CONFIG consistently achieves superior or comparable constrained-regret convergence, while SafeOPT can win when the global optimum lies in the initial local feasible set.CONFIG may spend more samples exploring globally, whereas SafeOPT benefits from restricting search to that local feasible set.
  • Building-controller tuning: Within 15 steps, CONFIG identifies the building-controller solution minimizing normalized energy consumption plus normalized temperature deviation.SafeOPT is overly cautious in this task and fails to find a comparably performing solution.

7. Conclusion

CONFIG combines optimism-based constrained optimization with theoretical guarantees and competitive empirical performance. Its bounds support convergence for common kernels, and the method can declare infeasibility, although misspecified hyperparameters may make the auxiliary problem infeasible.

  • 7. Conclusion: CONFIG uses lower confidence bound surrogates for both objective and constraints to select each next sample.The algorithm solves an auxiliary constrained optimization problem at every step.
  • 7. Conclusion: CONFIG achieves the same cumulative regret bound as the unconstrained case and similar upper bounds for cumulative constraint violations.The violation bounds are expressed in terms of maximum information gain.
  • 7. Conclusion: Sublinear bounds for Matern (ν > d/2) and Squared Exponential kernels yield a convergence rate to the original constrained optimum.These guarantees apply under the paper’s regularity assumptions.
  • 7. Conclusion: CONFIG naturally provides a scheme to declare infeasibility and achieves competitive empirical performance across sampled, artificial, and building-controller problems.The paper reports significantly improved theoretical guarantees relative to state-of-the-art constrained methods.
  • 7. Conclusion: Misspecified hyperparameters can make the auxiliary problem infeasible, which the authors identify as a limitation for future work.This limitation concerns the auxiliary problem rather than the original optimization problem.

B. Proof of Corollary 2.6

The corollary proof establishes a simultaneous high-probability confidence event for the objective and constraint functions. It then uses probability union bounds and a preceding lemma to complete the result.

  • B. Proof of Corollary 2.6: The proof defines events ensuring lower and upper confidence bounds contain each objective and constraint function over all inputs and times.The events are defined with respect to randomness from observation noise.
  • B. Proof of Corollary 2.6: The conclusion follows after applying a probability union bound and Lemma 2.4.The proof explicitly attributes inequalities (24c) and (24d) to these steps.

C. Proof of Lemma 4.1

The lemma proof conditions on a joint high-probability event and uses feasibility of the optimal solution to establish feasibility for the auxiliary problem. It then bounds objective and constraint terms algebraically.

  • C. Proof of Lemma 4.1: All subsequent statements are conditioned on a joint event occurring with probability at least 1 − δ.The event is supplied by the preceding confidence result.
  • C. Proof of Lemma 4.1: Feasibility of the optimal solution implies that x* is feasible for the auxiliary problem, so infeasibility is not declared.The proof evaluates the relevant confidence bound at x*.
  • C. Proof of Lemma 4.1: The proof bounds positive-part objective and constraint terms using confidence inequalities and the inequality [a + b]+ ≤ [a]+ + [b]+.Auxiliary-problem feasibility is also used in the constraint-violation argument.

D. Proof of Theorem 4.3

The theorem proof combines confidence-width terms to bound cumulative quantities, then extracts an evaluated point whose objective regret and constraint violations satisfy the desired average guarantees.

  • D. Proof of Theorem 4.3: Combining the definition of β_i,t with the preceding inequalities yields bounds involving β_i,T, maximum information gain γ_i,T, and T.The proof applies this combination after establishing the relevant intermediate inequalities.
  • D. Proof of Theorem 4.3: There exists an evaluated point ˜x_T among {x_1, x_2, · · ·, x_T} satisfying the derived bound.The proof explicitly selects ˜x_T from the sampled points.
  • D. Proof of Theorem 4.3: Nonnegativity of [f(˜x_T) − f*]+ and [g_i(˜x_T)]+ converts the aggregate inequality into separate objective and constraint conclusions.The resulting constraint statement holds for every j ∈ [N].
  • D. Proof of Theorem 4.3: The proof concludes after applying the preceding inequalities to obtain the theorem’s desired result.No additional construction is introduced in the final step.

F. Proof of Theorem 5.1

The proof argues that, if infeasibility has not yet been declared, a bound eventually fails when the problem is infeasible. Consequently, infeasibility is declared by the first violation of that inequality.

  • The proof assumes infeasibility has not been declared through step T.
  • An infeasible problem guarantees a constraint index i_t attaining the maximum constraint value at x_t.
  • With probability at least 1 −δ, the proof derives the inequality used to detect infeasibility.
  • When T is large enough, inequality (33) is violated, so infeasibility is declared no later than the first such violation.
  • Table 4 lists the explicit functions used to construct the artificial numerical instances.
Loading 2211.00162v4…