Abstract
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.
Similar content being viewed by others
References
Ortega, J.M.: Stability of difference equations and convergence of iterative processes. SIAM J. Numer. Anal. 10, 268–282 (1973)
Goh, B.S.: Algorithms for unconstrained optimization problems via control theory. J. Optim. Theory Appl. 92, 581–604 (1997)
Park, P.C.: A.M. Lyapunov’s stability theory-100 years on. IMA J. Math. Control Inform. 9, 275–303 (1992)
LaSalle, J.P.: Recent advances in Lyapunov stability theory. SIAM Rev. 6, 1–11 (1964)
LaSalle, J.P.: The Stability of Dynamical Systems. SIAM, Philadelphia (1976)
Kalman, R.E., Bertram, J.E.: Control system analysis and design via the second method of Lyapunov, II: discrete-time systems. ASME J. Basic Eng. 82, 394–400 (1960)
Vincent, T.L., Grantham, W.J.: Nonlinear and Optimal Control Systems. Wiley, New York (1997)
Grantham, W.J.: Trajectory following optimization by gradient transformation differential equations. In: Proceedings of 42nd IEEE Conference on Decision and Control, Hawaii, pp. 5496–5501 (2003)
Goh, B.S.: Management and Analysis of Biological Populations. Elsevier, Amsterdam (1980)
Goh, B.S.: Global convergence of some differential equation algorithms for solving equations involving positive variables. BIT 18, 84–90 (1978)
Corless, M., Leitmann, G.: Continuous state feedback guaranteeing uniform ultimate boundedness for uncertain dynamic systems. IEEE Trans. Autom. Control 26, 1139–1144 (1981)
Leitmann, G.: On one approach to the control of uncertain systems. In: Proceedings of 33rd IEEE Conference on Decision and Control, Lake Buena Vista, FL, pp. 2112–2116 (1994)
Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (1999)
Gilbert, J.C., Nocedal, J.: Global convergence properties of conjugate gradient methods for optimization. SIAM J. Optim. 2, 21–42 (1992)
Shi, Z.J., Shen, J.: A gradient-related algorithm with inexact line searches. J. Comput. Appl. Math. 170, 349–370 (2004)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by F.E. Udwadia.
I thank Professors Bingsheng He and Mark Wu for support and help in this research.
I thank the referees for useful comments which improved the paper.
Rights and permissions
About this article
Cite this article
Goh, B.S. Convergence of Algorithms in Optimization and Solutions of Nonlinear Equations. J Optim Theory Appl 144, 43–55 (2010). https://doi.org/10.1007/s10957-009-9583-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-009-9583-7