Brown's Method and Some Generalizations, With Applications to Minimization Problems

Abstract

Newton's method attempts to find a zero of $f \in C^{1}(IR^{n})$ by taking a step which is intended to make all components of $f$ vanish at once. In this respect Newton's method processes the components of $f$ in parallel. Contrasting to this, Brown's method and the generalizations thereof considered in this thesis process the components of $f$ serially, one after another. One major iteration of these methods may be described as follows: given the starting point (i.e. current major iterate) $y_{0}$, linearize the first component $f_{1}$ of $f$ at $y_{0}$ and find a point $y_{1}$ in the $n-1$ dimensional hyperplane $H_{1}$ on which this linearization vanishes; in general, having found a point $y_{k} (1 \leq k less than n)$ in the $n-k$ dimensional hyperplane $H_{k}$ on which the heretofore constructed linearizations vanish, restrict $f_{k+1}$ to $H_{k}$, linearize this restriction at $y_{k}$, and find a point $y_{k+1}$ in the $n-(k+1)$ dimensional hyperplane $H_{k+1}$ on which this linearization vanishes; stop when $Y_{n}$ has been found and let $y_{n}$ be the next major iterate. When $f$ is a general nonlinear function and finite differences are used to construct the linearizations, this approach must do work equivalent to approximating only about half the components of $f'$ and thus requires only about half as many function evaluations per major iteration as the corresponding finite difference Newton's method, while still enjoying the same rate of local convergence.