2
$\begingroup$

I have to develop an optimizer for a simulation. There are 7 reference values $$ r_1, r_2,\ldots,r_7 $$ (certain values which are expected to show up) and 7 corresponding actual values $$ a_1,a_2,\ldots,a_7,$$ the simulations's results. The deviations between reference values and actual values are listed as one single value, the sum of squares of all deviations. $$ f(x)=\sum_{i=1}^{7}(r_i - a_i)^2=\sum_{i=1}^{7}e^2=||e||^2 $$ where $$x_1,x_2,\ldots,x_7 $$ denote the input values.

Given this, I can calculate an arbitrary number of results $f(x)$ for many input vectors $x$, while the results are scalar values. Obviously I want to minimize the deviations. My minimization method makes use of the gradient. How can I calculate the partial derivatives to build up the gradient without knowing the function?

I only know the input values and the result, but the relationships between input values is completely unknown!

$\endgroup$
4
  • $\begingroup$ Which minimization method are you using? If your simulation runs reasonably fast, you may be able to approximate the gradient numerically using a suitable adaptation of the Newton's formula $\frac{f(x+h) - f(x)}{h}$ for a choice of a small number $h$. Nonetheless, I think in this case a derivative-free method may be more efficient and reliable. $\endgroup$
    – Libra
    Nov 26, 2012 at 23:05
  • $\begingroup$ Let's assume that I add $$10^-4$$ to each element of the input vector x. x is not a single value but a vector vector holding the input values, so we can as well write it as $$ f(x_1, x_2, \ldots,x_7)$$. So h is $$h=(10^{-4}, 10^{-4},\ldots, 10^{-4})$$ (7 elements). What does the fraction then look like, what's the h in the denominator? $\endgroup$
    – bogus
    Nov 28, 2012 at 9:31
  • $\begingroup$ I have given some details in an answer. $\endgroup$
    – Libra
    Nov 28, 2012 at 10:08
  • $\begingroup$ From your question, I'm not clear on whether $x = (a_1,...,a_7)$ or whether it also includes the 7 $r$ values as well? Also, what is the context of the problem: is it to find the "best" simulator, i.e. the simulator that gives the least deviation from reality over a wide range of inputs? If this is the problem, then I would expect you to be asking how to tune the simulator, i.e. optimise over a number of parameter variables. From your question, it seems you are trying to optimise over the inputs $x$, but that will only tell you the points over which the simulator is most accurate. $\endgroup$
    – Assad Ebrahim
    Dec 19, 2012 at 8:46

1 Answer 1

Reset to default
2
$\begingroup$

You can assume:

$$\nabla f(\vec x) = (\frac{\partial f}{\partial x_1},\cdots, \frac{\partial f}{\partial x_7}) \approx (\frac{f(x_1+h)-f(x_1)}{h},\cdots,\frac{f(x_7+h)-f(x_7)}{h})$$

$h$ needs not to be a vector. Then, you can use the information given by the gradient to select the variable(s) to change. For example, adopting a steepest descent you may apply a change proportional to the negative of the (approximate) gradient of the function at the current point (see this Wikipedia entry, for example).

$\endgroup$
3
  • $\begingroup$ It may properly occur that the values in x are in different units and thus differ significantly in size. Due to that, I should probably make use of different values of h and consider h a vector of small values $\endgroup$
    – bogus
    Nov 28, 2012 at 10:37
  • $\begingroup$ @Bogus: to calculate the partial derivative you have to "move away" of a small quantity $h$ from the current point $x_i$, regardless the size of $x_i$. So, $h$ could be the same for any component of $\vec x$. Nonetheless, perhaps normalizing the dimensions could help. $\endgroup$
    – Libra
    Nov 29, 2012 at 7:16
  • 1
    $\begingroup$ @bogus: If you use different values of $h$, you lose the benefits of being able to compare the components of the gradient to decide on the direction of steepest descent. $\endgroup$
    – Assad Ebrahim
    Dec 19, 2012 at 8:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .