Optimization of a blackbox function

Question

Let's say that we have an objective function $f(\mathbf x,\mathbf y)$ which has the parameters $\mathbf x=[x_1\ldots x_n]$ and $\mathbf y=[y_1\ldots y_n]$. Here, $\mathbf y$ is a blackbox variable which is calculated from a simulation of a network $\mathcal N$ by taking $\mathbf x$ as input.

$f$ is an objective function to be minimized for a given problem. Let's say:

$$ f(\mathbf x,\mathbf y) = \sum\limits_{i=1}^{n}\alpha_ix_i+\beta_ix_iy_i $$

where $\mathbf y= \mathcal N(\mathbf x)$ is a blackbox function whose analytical form is unknown which takes $\mathbf x$ as input

$\mathcal N$ refers to a network being simulated.

$\alpha_i$ and $\beta_i$ are constants, $i=1,\ldots,n$.

The problem has the following constraints:

$$ \sum\limits_{i=1}^{n}x_i=C\\ x_i^\min \leq x_i \leq x_i^\max\\ 0 \leq y_i \leq y_i^\max\\ 0 \leq x_iy_i \leq (x_iy_i)^\max $$ $C,x_i^\min, x_i^\max,y_i^\max,(x_iy_i)^\max$ being some fixed constants, $i=1,\ldots,n$.

A two-variable ($n=2$) example is as follows:

Objective:

$$ \min 2x_1+4x_1y_1+3x_2+5x_2y_2 $$

where

$$ [y_1,y_2]=\mathcal N([x_1,x_2]) $$

and $\alpha_1=2,\alpha_2=3,\beta_1=4,\beta_2=5$ according to the previous definitions.

Constraints:

$$ x_1+x_2 = 10\\ 0\leq x_1\leq 10\\ 5\leq x_2 \leq 10\\ 0\leq y_1\leq 5\\ 0\leq y_2\leq 10\\ 0\leq x_1y_1\leq 50\\ 0\leq x_2y_2\leq 50\\ $$

I have gone through some of the stochastic algorithms such as simulated annealing, hill climbing, evolutionary algorithms like genetic algorithms, and so on. And I'm also aware that my problem containing a blackbox function within itself and subjected to a number of constraints has a high chance of falling into the ugly world of "No Free Lunch Theorem".

Are there any appropriate algorithms or suggestions that can solve such a problem?

Answer 1

Please have a look at the really great review and comparison of 22 derivative-free algorithms [1] (written by two well-known and respected optimizers). Here, the authors use the terms "derivative-free" and "black box optimization" synonymously (emphasis is mine):

In addition, what we refer to as derivative-free optimization is often also referred to as optimization over black boxes. The literature on these terms is often inconsistent and confusing.

Reference

1: Rios, L. M., & Sahinidis, N. V. (2013). Derivative-free optimization: a review of algorithms and comparison of software implementations. Journal of Global Optimization, 56(3), 1247-1293.

Answer 2

NLopt is a nonlinear optimization library that can handle these kinds of problems. Most libraries cannot handle all of those constraints, but NLopt has some algorithms that can. From the algorithms page,

Of these algorithms, only ISRES and ORIG_DIRECT support nonlinear inequality constraints, and only ISRES supports nonlinear equality constraints.

ISRES can be a little computationally intensive but it's the only global optimization algorithm I know of that allows nonlinear equality constraints.

The NLopt library has really nice bindings to Julia at NLopt.jl if you'd like to use it in a higher level language.

Answer 3

You may give a try to my method: https://github.com/avaneev/biteopt

I've tested it on a lot of functions, including those with non-linear constraints (but constraint programming requires a special approach which is demonstrated in examples).