Unidimensional search

Newton and Quasi-Newton Methods of Unidimensional Search.157... 

Some unidimensional search procedures require that a bracket of the minimum be obtained as the first part of the strategy, and then the bracket is narrowed. Along with the statement of the objective function f(x) there must be some statement of bounds on x or else the implicit assumption that x is unbounded (—oo[Pg.156]

NEWTON AND QUASI-NEWTON METHODS OF UNIDIMENSIONAL SEARCH... 

A unidimensional search for a local minimum of a multimodal objective function leads to an unbounded solution. 

In minimizing a function /(x) of several variables, the general procedure is to (a) calculate a search direction and (b) reduce the value of/(x) by taking one or more steps in that search direction. Chapter 6 describes in detail how to select search directions. Here we explain how to take steps in the search direction as a function of a single variable, the step length a. The process of choosing a is called a unidimensional search or line search. 

Execution of a unidimensional search involves calculating a value of a and then taking steps in each of the coordinate directions as follows ... 

In this chapter we described and illustrated only a few unidimensional search methods. Refer to Luenberger (1984), Bazarra et al. (1993), or Nash and Sofer (1996) for many others. Naturally, you can ask which unidimensional search method is best to use, most robust, most efficient, and so on. Unfortunately, the various algorithms are problem-dependent even if used alone, and if used as subroutines in optimization codes, also depend on how well they mesh with the particular code. Most codes simply take one or a few steps in the search direction, or in more than one direction, with no requirement for accuracy—only that fix) be reduced by a sufficient amount. 

Numerical values for each parameter are given in parentheses. Obtain the maximum time for filtration as a function of xc by a numerical unidimensional search. 

Another class of methods of unidimensional minimization locates a point x near x, the value of the independent variable corresponding to the minimum of /(x), by extrapolation and interpolation using polynomial approximations as models of/(x). Both quadratic and cubic approximation have been proposed using function values only and using both function and derivative values. In functions where/ (x) is continuous, these methods are much more efficient than other methods and are now widely used to do line searches within multivariable optimizers. 

Line search. The oldest and simplest method of calculating a to obtain Ax is via a unidimensional line search. In a given direction that reduces/(x), take a step, or a sequence of steps yielding an overall step, that reduces/(x) to some acceptable degree. This operation can be carried out by any of the one-dimensional search... 

Trust regions. The name trust region refers to the region in which the quadratic model can be trusted to represent /(x) reasonably well. In the unidimensional line search, the search direction is retained but the step length is reduced if the Newton step proves to be unsatisfactory. In the trust region approach, a shorter step length is selected and then the search direction determined. Refer to Dennis and Schnabel (1996) and Section 8.5.1 for details. 

---