2
$\begingroup$

I have the following problem, there is an objective function f() depending on 7 variables x=(x1,x2,...x7), so f(x)=f((x1,x2,...x7)) and I want to find the combination of variables that minimize the objective function (x* for which f(x*) is minimum). The formula of the objective function is unknown. The problem is that the evaluation of objective function for a given point x, f(x), is difficult and requires running of a simulation software that can take time and computational resources so I want to do as few estimations of f() as possible. Which method/algorithm do you think would be most suitable here? What about Monte Carlo stochastic optimization?

I will add here more details about the objective function - this is a result of a simulation software called MIKE11 that models flow of water in rivers. The model of the river is 1D and the user's manual says that the equations used for the hydrodynamic part are Saint Venant equations. Now the objective function represents the maximum flow (in cubic meters per second) on a point on the river. And I want to minimize the objetive function (so I want the minimum of the maximum flow values). So to estimate the objetive function for the x vector of parameters I have to run one MIKE simulation.

Thank you

Improve this question
$\endgroup$
6
  • $\begingroup$ This is complementary to the answers, containing questions, which have already been posted. Do you believe your objective function is differentiable, even though the gradient is unknown, at most or all points? $\endgroup$
    – Mark L. Stone
    Commented Oct 19, 2016 at 23:47
  • $\begingroup$ Can you calculate or estimate the gradient directly by simulation? There are several methods of doing so even when the objective function can only be evaluated by Monte Carlo simulation. These include use of either the reverse (adjoint) mode of automatic differentiation or use of complex-step differentiation to implement Infinitesimal Perturbation Analysis (IPA), or Likelihood Ratio Method (LRM), or Measure-Valued Differentiation (MVD), a.k.a. weak derivatives? Or can you only evaluate or estimate gradient by using finite differences of objective function evaluations? $\endgroup$
    – Mark L. Stone
    Commented Oct 19, 2016 at 23:49
  • $\begingroup$ @MarkL.Stone I have added details about the objective function in the body of the original post. $\endgroup$
    – Sorin
    Commented Oct 20, 2016 at 12:26
  • $\begingroup$ It sounds like this is a deterministic simulation. is that correct? Is it the case that you don''t have access to source code used for objective function calculation, therefore could not apply any methods I listed in preceding comment for gradient calculation which require access to that source code? If so, you'd need either gradient -free optimization algorithm or use finite differences wi/ gradient-based method, such as finite difference Quasi-Newton. What is run time for each objective function evaluation? Any constraints? Any discrete variables? Is objective differentiable (smooth)? $\endgroup$
    – Mark L. Stone
    Commented Oct 20, 2016 at 18:32
  • $\begingroup$ Dimension of problem is 7, which is very low, so optimization algorithm run time will be dominated by objective function evaluation, So can use an optimization algorithm which spends more overhead effort in order to get the biggest bang for the buck out of each objective function evaluation. Are all 7 variables continuous, or are some discrete (integer or binary)? Tell us about constraints on the variables, such as lower bounds (such as zero) or upper bounds, linear equality or linear inequality constraints, or nonlinear equality or inequality onvstraints. $\endgroup$
    – Mark L. Stone
    Commented Oct 20, 2016 at 18:43

2 Answers 2

Reset to default
1
$\begingroup$

You haven't mentioned this, but if your function evaluations are the results of a complicated simulation, is the simulation a Monte Carlo simulation or deterministic? If the simulation is a Monte Carlo simulation, then your function values will be "noisy", making the problem even more complicated.

For problems with a small number of parameters, expensive function evaluations, and particularly if there are noisy function values, methods that fit a surrogate model (aka a "response surface") to the function are often your best bet. You then minimize over the surrogate model using a conventional minimization algorithm. You might also look into latin hypercube sampling.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I have added details about the objective function in the body of the original post $\endgroup$
    – Sorin
    Commented Oct 20, 2016 at 12:27
0
$\begingroup$

Gradient-based optimization is very simple to use (look at gradient descent and it's variations).

Newton-type methods generally have faster convergence. Using approximations of second-order derivatives (Hesse matrix) results in quasi-Newton methods (for example BFGS) which aren't necessarily more expensive in terms of the number of function evaluations.

Do you have more details about the character of your function? People in PDE optimization for example often use the "adjoint method" to compute a gradient of the objective function at a cost that is only a constant factor of the evaluation of the cost of the original function.

If you have the source code of your function available you can look into (adjoint) algorithmic differentiation or "automatic" differentiation to compute cheap gradients.

If you do least squares regression (like machine learning models) these usually also use steepest descent based on gradients computed through adjoint models (called backpropagation in machine learning).

Improve this answer
$\endgroup$
1
  • $\begingroup$ I have added details about the objective function in the body of the original post $\endgroup$
    – Sorin
    Commented Oct 20, 2016 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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