# The Power of Human-Algorithm Collaboration in Solving Combinatorial Optimization Problems
## 2 Bayesian Optimization  
Global optimization (GO) aims to find optimal value(s) of functions, called _objective functions_, either in finite or bounded domains [14]. The optimal values, depending on the context, can be the global maximal or minimal values. In general, global optimization is intractable--the number of function evaluations increases exponentially in the problem dimensions and exponentially in the domain size [15]. The GO problems for continuous functions and functions with finite domains, respectively are as follows:  
\[\text{maximize }F(x),\ s.t.\ x\in[0,1]^{d},d\in\mathbb{N} \tag{1}\]  
\[\text{maximize }F(x),\ s.t.\ x\in N,N\in\mathbb{N} \tag{2}\]  
In some cases, there can be more constraints besides the domain. Those problems, however, are not in the scope of this research. We also note that any minimization problem can be reduced into a maximization problem by simply using \(F:=-F\). Bayesian optimization (BO) is a technique used in GO to search for globally optimal values in continuous, combinatorial, and discrete domains [16]. BO has a wide range of applications and recent years, its usage in optimizing hard black box functions has increased [17]. BO is often used in low data regimes where evaluation of the objective function is costly or not otherwise efficient [18]. These problems include, robot navigation and planning [19], tuning the hyperparameters of deep learning models [20], predicting earthquake intensities [21], finding optimal stock values in stock markets [22], and much more [23]. The advantage of the BO is that it can optimize any set of black box functions. That is, if one can only access function values and not, say, gradient information, then BO can be very efficient [17]. In addition, BO does not usually make any assumptions on the function it optimizes unlike multiple state-of-the-art optimization algorithms [16] that expect the objective function to be Lipschitz continuous [24], unimodal [25], or have a certain shape close to the global optimizer [26]. _Fully_ BO, however, assumes that the user has some knowledge or expectation on the shape of the objective function, which is realized as a (Gaussian) _prior_. Moreover, the main difference between BO and traditional GO is that in BO, one is not expected to provide, say, a differentiable function--one just has to know what the kind of function it is to some extent. BO is mainly based on Gaussian processes [27], which are stochastic process such that every finite collection of random variables has a multivariate normal distribution. It is completely defined by its covariance function \(\Sigma\) (or covariance matrix in finite domains) and its mean function \(\mu\)[16]: that is, \(N(\mu,\Sigma)\). In this paper, it is assumed that for _any_ function \(F\) is considered as  
\[F\sim N(\mu,\Sigma) \tag{3}\]  
and \(\mu\) is some constant, say 0 for a centered Gaussian process. This is a very common assumption made in BO literature. In BO, one places a (Gaussian) _prior_ on the unknown and possible non-convex function. This reflects one's understanding of the function--whether the function is continuous, differentiable, smooth, unimodal, and so forth [16]. It is usually assumed that \(\mu\) is 0 and hence, the prior is defined only by its covariance function (or covariance matrix) \(\Sigma\). After the prior is set over the unknown function, an algorithm suggests points where the optimal values would lie. Based on these suggestions and function evaluations, the algorithm updates the prior to _posterior_ and uses the posterior to suggest even better points where the possible optimum would be located. In many settings, the BO finds the global optimum much faster than, say, a brute force search [17]. The suggestions and how they are derived from the prior and posterior are defined by an acquisition function [16], for which multiple different possibilities exist. These include upper confidence bound [28], expected improvement [29], and Thompson sampling [30], to name few.