Convergence of Algorithms in Optimization and Solutions of Nonlinear Equations

摘要

It is desirable that an algorithm in unconstrained optimization converges when the guessed initial position is anywhere in a large region containing a minimum point. Furthermore, it is useful to have a measure of the rate of convergence which can easily be computed at every point along a trajectory to a minimum point. The Lyapunov function method provides a powerful tool to study convergence of iterative equations for computing a minimum point of a nonlinear unconstrained function or a solution of a system of nonlinear equations. It is surprising that this popular and powerful tool in the study of dynamical systems is not used directly to analyze the convergence properties of algorithms in optimization. We describe the Lyapunov function method and demonstrate how it can be used to study convergence of algorithms in optimization and in solutions of nonlinear equations. We develop an index which can measure the rate of convergence at all points along a trajectory to a minimum point and not just at points in a small neighborhood of a minimum point. Furthermore this index can be computed when the calculations are being carried out. Keywords Convergence - Rates of convergence - Lyapunov function - Unconstrained optimization - Solutions of equations - Steepest descent method - Newton method Communicated by F.E. Udwadia.