Introduction to FMQA¶
Black-box optimization¶
FMQA is one of the black box optimization methods. Usually, in mathematical optimization, the
objective
is to find a set of decision variables $\boldsymbol{x}$ such that some objective function $y =
f(\boldsymbol{x})$ is minimized (or maximized). Here, $\boldsymbol{x}$ is assumed to be a binary
variable
vector with size $d$ and each element taking the value 0 or 1.
$$
\begin{aligned}
\mathrm{Minimize}&\,\,f(\boldsymbol{x}) \\
\mathrm{subject\,\,to\,\,}&\boldsymbol{x} \in [0,1]^d
\end{aligned}
$$
Here, if information about the objective function $f(\boldsymbol{x})$ (functional form, gradient,
submodularity, convexity, etc.) is given, efficient optimization can be performed. For example,
suppose
the function $f(\boldsymbol{x})$ is known (and is quadratic in $\boldsymbol{x}$), as in some
optimization
problems shown in the Amplify demo tutorial. In such a case, $f(\boldsymbol{x})$ can be used as the
objective function to perform the optimization directly as a quadratic unconstrained binary
optimization
(QUBO: Quadratic Unconstrained Binary Optimization) problem.
On the other hand, in the case of optimization to minimize (or maximize) values obtained by
simulation or
experiment for physical or social phenomena, the objective function $f(\boldsymbol{x})$ corresponds to
simulation or experiment, and the function cannot be described explicitly. Mathematical optimization
for
such an unknown objective function $f(\boldsymbol{x})$ is called black-box optimization.
In addition, evaluating such an objective function (running simulations or experiments) is usually
relatively expensive (in terms of time and money, etc). Therefore, even if the set of decision
variables
is finite, optimization by full search is generally difficult. Therefore, an optimization method with
as
few objective function evaluations as possible is required.