A bracketing technique to ensure desirable convergence in univariate minimization (Q1115354)

The paper gives a class of three-point iterative processes for minimizing a lower semicontinuous function f(x), \(x\in E^ 1\). At each iteration of the proposed general algorithm current points \(x^-\), \(x^ 0\), \(x^+\) are generated such that \[ (1)\quad x^-<x^ 0<x^+,\quad f(x^ 0)\leq \min \{f(x^-),\quad f(x^+)\}, \] where \(x^ 0\) is the current approximation to the minimizing point of f(x). The reiteration of the points \(x^-\), \(x^ 0\), \(x^+\) is based on the projection of some trial point on the interval \([x^--\sigma\), \(x^++\sigma]\) where \(\sigma >0\) depends on \(| x^+-x^-|\). The next set of three points is defined by dropping either \(x^-\) or \(x^+\) according to condition (1). It is shown that the sequences \(\{x^-\}\), \(\{x^ 0\}\), \(\{x^+\}\) generated by the algorithm converge to the stationary (in the sense of F. Clarke) point of f(x). For the general case of a lower semi-continuous f(x) the estimation of the rate of convergence is established. In particular if f(x) is twice continuously differentiable and convex then the rate of convergence is superlinear.