Robustness of convergence proofs in numerical methods in unconstrained optimization

Abstract

An iterative method to compute the minimum point in an unconstrained optimization problem can be viewed as a control system. Thus to achieve robust solutions it is desirable to have feedback solution rather than open loop control policies. A typical proof of a numerical method in optimization examines what happens along the total path of a trajectory for all admissible initial values. Thus, it is an open loop type of analysis. On the other hand, a proof of convergence of a numerical method by Lyapunov theorem in an unconstrained optimization problem examines what happens to changes in the value of the objective function relative to the level sets of the function in a typical iteration and it is re-started with numerical errors of the state variable. This is an example of feedback type control analysis and thus it is robust to numerical errors in the computation of the current position. We shall draw on an example due to Barbashin and Krasovskii and use Lyapunov function theory to illustrate the differences between open loop and closed loop convergence analysis of a numerical method in unconstrained optimization. It will also be demonstrated that open loop type of convergence along each trajectory for all possible initial conditions may not guarantee convergence to a global mini- mum point. It only establishes convergence to stationary points. What is needed is the concept of properly nested level sets of the objective function which is a key requirement for global convergence in a proof by using Lyapunov function theorem. Globally, an objective function has properly nested level sets if all the level sets are topologically equivalent to concentric spherical surfaces. For convenience, brief reviews of Lyapunov function theorem for the global con- vergence of an iterative system and the Zoutendijk theorem for the convergence of a line search method in optimization will be given