 CATEGORIES:

http://vimeo.com/77448578

Most engineering optimization problems are not linear. To solve nonlinear problems, one approach is to repeatedly numerically approximate the problem as a locally linear one.

To do this, one can start a numerical search at a feasible point in in Rn. At this point, one can numerically approximate the non-linear constraints by evaluating them at points around , and fitting a linear surface to f, g, and h. Then, one can solve this linear problem as above with a fast simplex method for a new point .Then one can re-linearize the problem at , and so on, until it converges to a solution. This approach is called sequential linearization. In particular, sequential quadratic programming is a method whereby the constraints are linearized and the objective function is reduced to the nearest quadratic approximation.

Sequential quadratic programming is implemented as a tool in many software systems, such as spreadsheets and MatlabTM.

Stopping Criteria

Given some numerical quantity to minimize over a search space, how do we know when we can stop the search? There are three answers to this question:

• When the separation in successive iterations becomes small: This criterion is valid, but sometimes the function changes quickly, and so the prediction has • When the difference in functional evaluations becomes small: This criterion will define as any point that is close enough; but sometimes the function might be very flat near , and so we might be placed very far away from as the agorithm slowly converges. Equation (16.33) must be checked to ensure [itself is not approaching zero (becomes less than e). If so, one can simply use the numerator. Generally, one should check both the relative and the absolute difference.

• When the difference in some arbitrary scalar function becomes small: This criterion has use when we discuss constraints, since we might want to define a stopping criterion as a function of both the function we are minimizing and the constraint functions.

These definitions imply that we need an order of magnitude estimate of f, and we then choose e to be a few orders of magnitude less than this estimate.

Global Optimality