Browse Prior Art Database

Interpolation for Univariate Optimization

IP.com Disclosure Number: IPCOM000086583D
Original Publication Date: 1976-Sep-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 2 page(s) / 15K

Publishing Venue

IBM

Related People

Wolfe, PS: AUTHOR

Abstract

The nature and importance of the task of the minimization of a function of one variable has already been described [1]. This article deals with the interpolation phase of univariate minimization, which was not discussed in the reference. However, the same notation is used.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Interpolation for Univariate Optimization

The nature and importance of the task of the minimization of a function of one variable has already been described [1]. This article deals with the interpolation phase of univariate minimization, which was not discussed in the reference. However, the same notation is used.

All of the rather small amount of literature, examined on univariate minimization when derivatives are available, and all of the computer routines adhere to this outline: the interpolation phase of univariate minimization begins when, as a result of extrapolation, values x[k - 1], x[k] of the independent variable have been found with f'(x[k - 1])<0, f'(x[k])>0, but neither of these values satisfies an appropriate test for optimality. The values x[k - 1], x[k] define the endpoints of the initial interval I, which is known to contain a minimizing point.
(a) A polynomial p (usually a cubic) fitting the data at the

endpoints of I is formed, and the unique interior point y

minimizing p(y) is determined;
(b) f(y) and f'(y) are found and used to check y for optimality;

if it is not optimal, then
(c) the interval I is divided into two subintervals by y;

is replaced by the left subinterval if f'(y) > 0 and by the

right subinterval otherwise, and one begins again with (a).

(Sometimes the 'check for optimality' is vacuous, and the result of the first (b) step is used. As discussed in the reference, that is not satisfactory practice.)

The step (c) above has a bad flaw which has not been noticed previously. It can readily happen that the problem is such that the current interval I is always replaced by a subinterval on the same side, so that only one endpoint is ever "updated". The point which is not updated is a poor approximation to the minimum, and makes the polynomial p a poor approximation to the function. The result will be that the overall process converges slowly to the desired minimum. An example of this behavior appears at the end of this presentation. That flaw is not always disastrous when the univariate optimization is done as a subprocess of multivariate optimization, for it has no effect until the fourth evaluation of the function, by which time a sufficiently accurate solution may be at hand. However, it will increase the amount of work needed for such problems in many cases, and will greatly increase the amount of work needed for problems where high accuracy is required.

The algorithm described below corrects that flaw, resulting in a procedure which is generally rapidly convergent. It is readily described in words. As above, the endpoints of the shortest interval in which the minimum is known to lie are always retained. If those points give the lowest values of the function so far found, then we proceed just as above. In any case the two points having the lowest values are retained (it turns out that at le...