Minimization Algorithm


Minimization Algorithms

The purpose of the minimization algorithm is to detect the minimum of the objective function in the n-dimensional parameter space. In multiphase flow modeling, the calculated system response is a highly non-linear function of the input parameters. Consequently, the objective function is non-quadratic when applying least-squares. Starting from an initial parameter set, the minimum has to be found iteratively by evaluating the value and/or gradient of the objective function, and performing small steps towards the minimum. Different minimization algorithms are available in iTOUGH2 , each with its advantages and disadvantages. The choice depends on the characteristics of the objective function, the number of parameters to be estimated, and the efficiency with which the forward problem can be solved.


Levenberg-Marquardt Algorithm

The Levenberg-Marquardt modification of the Gauss-Newton algorithm for the minimization of non-quadratic objective functions was found to be an efficient and robust method for most iTOUGH2 inversions. After local linearization of the objective function with respect to the parameters to be estimated, the Levenberg-Marquardt algorithm performs initially small, but robust steps along the steepest descent direction, and switches to more efficient quadratic Gauss-Newton steps as the minimum is approached. The derivatives are calculated numerically using the perturbation method.


Downhill Simplex Algorithm

The downhill simplex method requires only function evaluations (i.e., no derivatives) and is therefore a robust but inefficient minimization method. Starting with a simplex consisting of n+1 points in the n-dimensional parameter space, a series of steps is taken, most of which just moving the point of the simplex with the highest objective function through the opposite face of the simplex to a lower point. Other search directions are generated by reflection, expansion, and contraction of the simplex from the previous step. The simplex algorithm should be used in iTOUGH2 when minimizing discontinuous cost functions or if the numerical evaluation of the derivatives is unstable.


Simulated Annealing

A continuous version of the method of simulated annealing has been implemented in iTOUGH2. Simulated annealing is a technique to find the (ideally global) minimum of the objective function in the presence of many local minima. Random steps in the parameter space are performed. A step is always accepted if the objective function is lowered, and it is sometimes accepted with a certain, decreasing probability, if an uphill step is taken. This scheme allows the algorithm of escaping from local minima. Simulate annealing requires many forward runs and is thus only applicable to small problems.


Grid Search

The global minimum can always be identified by evaluating the objective function in the entire parameter space. Moreover, contouring the objective function reveals the potential presence of local minima, non-uniqueness problems, the correlation structure, stability problems, and non-linearity effects. Evaluating the objective function on a grid in the entire parameter space is prohibitively expensive for higher dimensional parameter spaces. iTOUGH2 offers this option for up to three parameters. This example of a two-dimensional grid search shows the objective function in the parameter space spanned by the logarithm of the absolute permeability and the pore size distribution index of the Brooks-Corey model. A three-dimensional grid search has been performed to generate the picture shown at the top of this page.

 


Top of Page | Flow Chart
Parameters | Observations | Objective Function | Minimization Algorithm | Error Analysis
Examples | Bibliography | Availability | Updates | Command Index
iTOUGH2 Home | TOUGH2 Home | ESD Home | LBNL Home

Page updated: July 8, 1997