next up previous contents
Next: Optimization Up: The Objective Function Previous: The Objective Function

The Gradient of the Objective Function


An efficient optimization algorithm needs necessarily local information of higher order about the objective function. While there does not seem to be a simple way to compute tex2html_wrap_inline3291 and tex2html_wrap_inline3293, the gradient with respect to the locational decision variables tex2html_wrap_inline3295 (which are arguably the most important ones) can be approximated in the following way. Under suitable differentiability assumptions and integrability of tex2html_wrap_inline3281, we have that

Figure 5.1: Translating the origin tex2html_wrap_inline3299 of the pollutant source results in a translation of the pollutant cloud and of the effect.  

Taking a look at Figure 5.1, it is reasonable to make the assumption
for tex2html_wrap_inline3301. As a consequence, for tex2html_wrap_inline3303 we get
This is the approach chosen in OLAF. The differentials tex2html_wrap_inline3305 are approximated by finite differences of third order, where the discretization size is exactly the grid size of the computational grid in tex2html_wrap_inline3307-direction. In this way, the approximations to tex2html_wrap_inline3281 on the grid discretizing G are used to calculate the differential of tex2html_wrap_inline3281, and no further simulation run of the dispersion model or the cytodynamic model is necessary. Under analogous assumptions, the same reasoning holds for tex2html_wrap_inline3315. Additional objective function evaluations due to time-intensive numerical differentiation routines can therefore be avoided. Computational tests showed that the use of this scheme results in a large decrease in computation time, although the total number of iterations increases slightly when compared to an implementation where central differences have been used to approximate the gradient of the objective function. This might be attributed to the fact that in practical applications the accuracy of the approximation scheme above is lower than central differences. Consequently, descent algorithms which employ local information of higher order need more iterations, but less total computation time.

We may go even one step further. Using (5.3) and partial integration, we see that
holds whenever G has a smooth boundary and the function tex2html_wrap_inline3319 has compact support. Here, tex2html_wrap_inline3321 is the outer normal of G at a boundary point tex2html_wrap_inline3325. By choosing G large enough (or choosing a population distribution p with compact support small enough), we can make sure that the boundary integral gets arbitrary small, and we can approximate the differential of f with respect to tex2html_wrap_inline3333 by
Since tex2html_wrap_inline3335 is independent of tex2html_wrap_inline3221, it can be computed or approximated in whatever way necessary before any optimization takes place. Approximating tex2html_wrap_inline3339 then involves only the evaluation of the integral in (5.4), which can be done in the same way as the evaluation of f at tex2html_wrap_inline3221.

Unfortunately, none of these schemes works for the derivatives with respect to stack height and stack diameter. As a consequence, numerical differentiation with central differences is used to approximate the derivative of f with respect to h and w.

A different possibility would be to use automatic differentiation to compute derivatives of f with respect to h and w. Preliminary numerical experience [25, Chapter 1,] suggests that this approach is computationally very expensive for parametrized air dispersion models. No effort has been made to use automatic differentiation within OLAF.

next up previous contents
Next: Optimization Up: The Objective Function Previous: The Objective Function

Joerg Fliege
Wed Dec 22 12:25:31 CET 1999