Next: Viterbi algorithm Up: NON-LINEAR OPTIMIZATION Previous: Unconstrained optimization

## Constrained optimization

Incorporating a predetermined model in the searching procedure usually produces a robust algorithm. The model constrains p to be certain type of functions of (t,x), for example, smoothed functions. This constraint excludes many possible estimation errors caused by noise and aliasing. Of course, the choice of predetermined model depends on the individual application. Ideally, the function should be constrained in both axes, however, doing this significantly complicates the search algorithm. Thus, I decide to constrain the solution in t axis only, which proves to be practical for many applications.

The constrained optimization can be formally stated as follows: for each x, find a function p(t) that satisfies certain constraints and minimizes

Because any function p(t) defines a path through the t-p plane, an alternative description of the constrained optimization is to find a constrained path p(t) in the t-p plane such that the total error measure summed along this path is minimum. Clearly, this is a shortest-path problem. There is an efficient and systematic algorithm for solving this type of problem.

Next: Viterbi algorithm Up: NON-LINEAR OPTIMIZATION Previous: Unconstrained optimization
Stanford Exploration Project
12/18/1997