Let's imagine I have a function $f(x)$ whose evaluation cost (monetary or in time) is not constant: for instance, evaluating $f(x)$ costs $c(x)\in\mathbb{R}$ for a known function $c$. I am not interested in minimizing it in few iterations, but rather in minimizing it using "cheap" evaluations. (E.g. maybe a few cheap evaluations are more "informative" to locate the minima, rather than using closer-to-the-minima and costly evaluations.)

My questions are: Has this been studied or formalized? If so, can you point me to some references or the name under which this kind of optimization is known?

Just to clarify, I am not interested in either of these:

  • Standard optimization, since its "convergence rate" is linked to the total number of function evaluations.
  • Constrained optimization, since my constraint on minimizing $f(x)$ is not defined in terms of the subspace allowed to $x$, but in terms of the added costs of all the evaluations during the minimization of $f$.
  • Goal optimization, since using few resources to minimize $f$ can not be expressed (I think) as a goal.


Surrogate-based optimization has been proposed as a solution. While it faces the fact that the function is expensive to compute, it does not face (straightforwardly) the fact that different inputs imply different evaluations costs. I absolutely think that surrogate-based optimization could be used to solve the problem. In this line, is there a study of how to select points $x_i$ to estimate the "optimization gain"? In terms of surrogate-based optimization: what surrrogate model and what kind of Design of Experiment (DoE) could let me estimate the expected improvement?

Also, some remarks to contextualize. Originally, I was thinking on tuning the hyperparameters of machine learning algorithms. E.g., training with lots of data and lots of epochs is costly, but different architectures may be ranked based on cheaper trainings and then fine-tuned. Therefore:

  • Let us assume that $c(x)$ can be estimated at zero cost.
  • There is some structure in $c(x)$: large regions have higher cost, large regions have cheaper cost, the cost is smooth, the minima may be in either region.
  • Let us assume that $f(x)$ is smooth. Also, if possible, let us assume it has some stochastic error that we can model (such as Gaussian error with zero mean and known variance).
  • $\begingroup$ Can you cheaply predict whether the evaluation at a particular point will be cheap or expensive? Is your objective smooth? are the expensive points randomly scattered or are they in regions near the minimum? $\endgroup$ – Brian Borchers Jul 1 at 15:49
  • $\begingroup$ Here is a good paper on the subject with >1000 citations ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19990009055.pdf $\endgroup$ – whpowell96 Jul 1 at 16:12
  • $\begingroup$ You could be interested by the fact that this is what online plant optimization does. Get better operating conditions updated regularly. It is never the optimum optimorum but better than before. For sure, everything is done using simulation based on first principles of physics. Here we speak about a lot of money. $\endgroup$ – Claude Leibovici Jul 1 at 17:13
  • $\begingroup$ Thanks to everyone for the comments. @BrianBorchers I added some contextualization, the cost can be regarded as known (i.e. zero cost to predict whether evaluations are cheap or expensive) $\endgroup$ – Pirer Jul 2 at 12:53

Yes, this has been studied before.

The replacement of a (computationally) heavy cost function with a cheaper, but less accurate version, is known as surrogate cost/fitness function. You might look for Surrogate-Based Modeling and Optimization techniques (in this reference are quite some available).


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.