A bracketing technique to ensure desirable convergence in univariate minimization

This paper gives a general safeguarded bracketing technique for minimizing a function of a single variable. In certain cases the technique guarantees convergence to a stationary point and, when combined with sequential polynomial and/or polyhedral fitting algorithms, preserves rapid convergence. Each bracket has an interior point whose function value does not exceed those of the two bracket endpoints. The safeguarding technique consists of replacing the fitting algorithm's iterate candidate by a close point whose distance from the three bracket points exceeds a positive multiple of the square of the bracket length. It is shown that a given safeguarded quadratic fitting algorithm converges in a certain better than linear manner with respect to the bracket endpoints for a strongly convex twice continuously differentiable function.Research sponsored by the Institut National de Recherche en Informatique et en Automatique, Rocquencourt, France, and by the Air Force Office of Scientific Research, Air Force System Command, USAF, under Grant Number AFOSR-83-0210. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.Research sponsored, in part, by the Institut National de Recherche en Informatique et en Automatique, Rocquencourt, France.