7 - Optimization

Summary

The goal of optimization is to find a vector solution x that minimizes some scalar function f (x). We will assume that the function is at least C² (i.e., is continuous, has continuous derivatives and has continuous second derivatives). The solution space may be subject to constraints, e.g., the positivity of some elements of x.

We have seen already one method, conjugate gradients (Section 4.1), which assumes a specific quadratic function f with a minimum that solves the linear equation Ax = b. We are now interested in more complicated functions, and for many such functions the solution is notoriously dificult. For example, the function may possess any number of local minima. In the neighborhood of a local minimum, quasi-Newton type methods will converge to the local minimum, which may be distant from the desired global minimum. None of the approaches described here can cope with that problem – the success of the methods relies on smoothness of the function f (x) and the quality of the starting guess x⁽⁰⁾.

We will examine separately the case of nonlinear functions f(x) without constraints (variable metric methods), and linear constraints applied to linear functions (linear programming). Methods for constrained nonlinear problems (nonlinear programming) are built on these simpler methods.

The variable metric methods for n-dimensional problems rely on accurate and stable methods for simpler one-dimensional (1D) problems. The problem of finding a local minimum in 1D is broken down into two parts. Problem I is called bracketing.