5
$\begingroup$

Suppose that we have an objective function $f$ which have as parameters $x_1, x_2$.

$f$ is an objective function to be maximized for a given problem.Lets say:

$$f(x_1,x_2)=x_1+x_2+E(x_1,x_2)$$

where $E$ is a neural network model. Thus $E$ is not expressed as an explicit mathematical relation.

Let's also assume that the problem have one constraint:

$$G(x_1, x_2) < C$$

where $C$ is a constant and $G$ as for $E$ is modelled using a neural network.

My question is the following:

  1. Is it possible to optimize this problem assuming that we do not know how $F$ and $G$ executes the results?
  2. Are there any tools that can deal with sort of problems?
$\endgroup$
6
$\begingroup$

For black-box optimization, most state of the art approaches currently use some form of surrogate modeling, also known as model-based optimization. This is where the objective function is locally approximated via some parametric model (e.g. linear/quadratic response surface or Gaussian process regression). This approach is "derivative free optimization" (DFO) in the sense that only the parametric model derivatives are used, vs. finite differences of the black-box function. Note that the local models are typically fitted in a "large" neighborhood, compared to finite differences.

A good comparison of the current state of the art in unconstrained (and box-constrained) DFO methods is the recent paper

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

This study benchmarks various DFO methods for global and local optimization. (See my answer here for further discussion, including limits on problem size.)

For constrained optimization there is less work, but several generalizations exist for the polynomial response-surface DFO methods, at least. These methods tend to be formulated as sequential linear programming or sequential quadratic programming (SQP) algorithms$\mathbf{^*}$, depending on the degree of the polynomial approximation. Note that cubic or higher order polynomials are generally not used, due to ill conditioning.

I have not used these programs, but some possible recommendations might be:

  • Linear Case: The COBYLA algorithm by M.J.D. Powell.
  • Quadratic Case: CONDOR (based on an unconstrained SQP algorithm by Powell)

I have used Powell's box-constrained SQP solver (BOBYQA) with good results, and his software/algorithms are very reliable in my experience, as they were honed by years of practical industrial applications. Hence my recommendation. (His quadratic DFO variants also rank very well in the benchmark study cited above.)


$\mathbf{^*}$Penalty methods are a viable alternative for many constrained optimization problems, as suggested in the answer by Ami Tavory (since deleted). If you go this route, I would not recommend using Nelder-Mead. Many better alternatives exist, as outlined in the Rios & Sahinidis study.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Just for the newcomers, GPflowOpt offers this functionality. Also refer to their publication GPflowOpt: a bayesian optimization library using tensorflow in NIPS 2017.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is being automatically flagged as low quality, probably because it is so short. At present it is more of a comment than an answer by our standards. Can you expand on it? We can also turn it into a comment. $\endgroup$ – gung - Reinstate Monica May 22 '19 at 19:20
1
$\begingroup$

For this task I would use population-based optimisation algorithm, where, at each iteration you create a population of possible points (also referred to as candidates). At the "creation" time you check each candidate whether they meet the constraint $G$ and then, once the whole population is built, you evaluate the whole population using your black-box objective $f$.

A good Global Optimisation algorithms that you could look at are Genetic Algorithm, Particle Swarm Optimisation or Simulated Annealing (see my response here). Other methods would include Pattern search or, if evaluating your $E$ is expensive, Surrogate Optimisation.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.