×

Analysis and design of optimization algorithms via integral quadratic constraints. (English) Zbl 1329.90103

Summary: This paper develops a new framework to analyze and design iterative optimization algorithms built on the notion of integral quadratic constraints (IQCs) from robust control theory. IQCs provide sufficient conditions for the stability of complicated interconnected systems, and these conditions can be checked by semidefinite programming. We discuss how to adapt IQC theory to study optimization algorithms, proving new inequalities about convex functions and providing a version of IQC theory adapted for use by optimization researchers. Using these inequalities, we derive numerical upper bounds on convergence rates for the Gradient method, the Heavy-ball method, Nesterov’s accelerated method, and related variants by solving small, simple semidefinite programming problems. We also briefly show how these techniques can be used to search for optimization algorithms with desired performance characteristics, establishing a new methodology for algorithm design.

MSC:

90C22 Semidefinite programming
90C25 Convex programming
90C30 Nonlinear programming
93C10 Nonlinear systems in control theory
93D99 Stability of control systems

Software:

Macaulay2; YALMIP; TFOCS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. Beck and M. Teboulle, {\it A fast iterative shrinkage-thresholding algorithm for linear inverse problems}, SIAM J. Imaging Sci., 2 (2009), pp. 183-202. · Zbl 1175.94009
[2] S. Becker, E. J. Candès, and M. Grant, {\it Templates for convex cone problems with applications to sparse signal recovery}, Math. Program. Comput., 3 (2011), pp. 165-218. · Zbl 1257.90042
[3] S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, {\it Linear Matrix Inequalities in System and Control Theory}, SIAM Stud. Appl. Math. 15, SIAM, Philadelphia, 1994. · Zbl 0816.93004
[4] S. P. Boyd and L. El Ghaoui, {\it Method of centers for minimizing generalized eigenvalues}, Linear Algebra Appl., 188 (1993), pp. 63-111. · Zbl 0781.65051
[5] O. Devolder, F. Glineur, and Y. Nesterov, {\it First-order methods of smooth convex optimization with inexact oracle}, Math. Program., 146 (2014), pp. 37-75. · Zbl 1317.90196
[6] J. Doyle, {\it Analysis of feedback systems with structured uncertainties}, Proc. IEE-D, 129 (1982), pp. 242-250.
[7] Y. Drori and M. Teboulle, {\it Performance of first-order methods for smooth convex minimization: A novel approach}, Math. Program., 145 (2014), pp. 451-482. · Zbl 1300.90068
[8] M. Grant and S. P. Boyd, {\it Graph implementations for nonsmooth convex programs}, in Recent Advances in Learning and Control, Lecture Notes in Control and Inform. Sci. 371, V. Blondel, S. Boyd, and H. Kimura, eds., Springer, London, 2008, pp. 95-110. · Zbl 1205.90223
[9] D. R. Grayson and M. E. Stillman, {\it Macaulay 2, a software system for research in algebraic geometry}, 2002.
[10] E. Hazan, {\it private communication}.
[11] W. P. Heath and A. G. Wills, {\it Zames-Falb multipliers for quadratic programming}, in Proceedings of the IEEE Conference on Decision and Control, 2005, pp. 963-968. · Zbl 1366.90155
[12] U. Jönsson, {\it A nonlinear Popov criterion}, in Proceedings of the IEEE Conference on Decision and Control, Vol. 4, 1997, pp. 3523-3527. · Zbl 0939.76500
[13] R. E. Kalman, {\it Lyapunov functions for the problem of Lur’e in automatic control}, Proc. Nat. Acad. Sci. U.S.A., 49 (1963), pp. 201-205. · Zbl 0113.07701
[14] H. K. Khalil, {\it Nonlinear Systems}, 3rd ed., Prentice-Hall, Upper Saddle River, NJ, 2002. · Zbl 1003.34002
[15] V. Kulkarni, S. K. Bohacek, and M. G. Safonov, {\it Robustness of interconnected systems with controller saturation and bounded delays}, in Proceedings of the American Control Conference, 1999.
[16] J. Löfberg, {\it YALMIP: A toolbox for modeling and optimization in MATLAB}, in Proceedings of the CACSD Conference, Taipei, Taiwan, 2004.
[17] A. I. Lur’e and V. N. Postnikov, {\it On the theory of stability of control systems}, Appl. Math. Mech., 8 (1944), pp. 246-248 (in Russian). · Zbl 0061.19407
[18] A. M. Lyapunov and A. T. Fuller, {\it General Problem of the Stability of Motion}, Control Theory and Applications Series, Taylor & Francis, London, 1992. Original text in Russian, 1892.
[19] A. Megretski and A. Rantzer, {\it System analysis via integral quadratic constraints}, IEEE Trans. Automat. Control, 42 (1997), pp. 819-830. · Zbl 0881.93062
[20] A. Megretski and S. Treil, {\it Power distribution inequalities in optimization and robustness of uncertain systems}, J. Math. Systems Estim. Control, 3 (1993), pp. 301-319. · Zbl 0781.93079
[21] A. Nemirovski, {\it The long-step method of analytic centers for fractional problems}, Math. Program., 77 (1997), pp. 191-224. · Zbl 0890.90168
[22] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro, {\it Robust stochastic approximation approach to stochastic programming}, SIAM J. Optim., 19 (2009), pp. 1574-1609. · Zbl 1189.90109
[23] Y. Nesterov, {\it Introductory Lectures on Convex Optimization: A Basic Course}, Appl. Optim. 87, Kluwer Academic Publishers, Boston, MA, 2004. · Zbl 1086.90045
[24] Y. Nesterov, {\it Efficiency of coordinate descent methods on huge-scale optimization problems}, SIAM J. Optim., 22 (2012), pp. 341-362. · Zbl 1257.90073
[25] Y. Nesterov, {\it Gradient methods for minimizing composite functions}, Math. Program., 140 (2013), pp. 125-161. · Zbl 1287.90067
[26] Y. Nesterov and A. Nemirovskii, {\it Interior-Point Polynomial Algorithms in Convex Programming}, SIAM, Philadelphia, 1994. · Zbl 0824.90112
[27] J. Nocedal and S. J. Wright, {\it Numerical Optimization}, 2nd ed., Springer, New York, 2006. · Zbl 1104.65059
[28] A. Packard and J. Doyle, {\it The complex structured singular value}, Automatica, 29 (1993), pp. 71-109. · Zbl 0772.93023
[29] A. Papachristodoulou and S. Prajna, {\it On the construction of Lyapunov functions using the sum of squares decomposition}, in Proceedings of the IEEE Conference on Decision and Control, Vol. 3, 2002, pp. 3482-3487.
[30] P. A. Parrilo and S. Lall, {\it Semidefinite programming relaxations and algebraic optimization in control}, Eur. J. Control, 9 (2003), pp. 307-321. · Zbl 1293.93302
[31] H. Pfifer and P. Seiler, {\it Robustness analysis of linear parameter varying systems using integral quadratic constraints}, in Proceedings of the American Control Conference, 2014, pp. 4476-4481.
[32] B. T. Polyak, {\it Introduction to Optimization}, Optimization Software, Inc., New York, 1987. · Zbl 0708.90083
[33] V. M. Popov, {\it Absolute stability of nonlinear systems of automatic control}, Avtomat. i Telemeh., 22 (1961), pp. 961-979 (in Russian); Automat. Remote Control, 22 (1961), pp. 857-875 (in English). · Zbl 0107.29601
[34] A. Rantzer and A. Megretski, {\it Stability criteria based on Integral Quadratic Constraints}, in Proceedings of the IEEE Conference on Decision and Control, Vol. 1, 1996, pp. 215-220.
[35] A. Rantzer and A. Megretski, {\it System Analysis via Integral Quadratic Constraints, Part II}, Technical Report ISRN LUTFD2/TFRT-7559-SE, Department of Automatic Control, Lund University, Lund, Sweden, 1997. · Zbl 0881.93062
[36] P. Rostalski and B. Sturmfels, {\it Dualities in convex algebraic geometry}, Rend. Mat. Appl. (7), 30 (2010), pp. 285-327. · Zbl 1234.90012
[37] S. Sastry and M. Bodson, {\it Adaptive Control: Stability, Convergence and Robustness}, Courier Dover Publications, New York, 2011. · Zbl 0721.93046
[38] P. Seiler, {\it Stability analysis with dissipation inequalities and integral quadratic constraints}, IEEE Trans. Automat. Control, 60 (2015), pp. 1704-1709. · Zbl 1360.93523
[39] J. S. Shamma, {\it Robustness analysis for time-varying systems}, in Proceedings of the IEEE Conference on Decision and Control, 1992.
[40] P. Tseng, {\it On accelerated proximal gradient methods for convex-concave optimization}, SIAM J. Optim., submitted.
[41] J. N. Tsitsiklis, D. P. Bertsekas, and M. Athans, {\it Distributed asynchronous deterministic and stochastic gradient optimization algorithms}, IEEE Trans. Automat. Control, 31 (1986), pp. 803-812. · Zbl 0602.90120
[42] J. C. Willems, {\it Dissipative dynamical systems–Part I: General theory}, Arch. Rational Mech. Anal., 45 (1972), pp. 321-351. · Zbl 0252.93002
[43] J. C. Willems, {\it Dissipative dynamical systems–Part II: Linear systems with quadratic supply rates}, Arch. Rational Mech. Anal., 45 (1972), pp. 352-393. · Zbl 0252.93003
[44] V. A. Yakubovich, {\it Frequency conditions for the absolute stability of control systems with several nonlinear or linear nonstationary units}, Avtomat. i Telemeh., 23 (1967), pp. 5-30 (in Russian). · Zbl 0155.14801
[45] V. A. Yakubovich, {\it S-procedure in nonlinear control theory}, Vestnik Leningrad Univ. Math., 4 (1977), pp. 73-93.
[46] V. A. Yakubovich, {\it Nonconvex optimization problem: The infinite-horizon linear-quadratic control problem with quadratic constraints}, Systems Control Lett., 19 (1992), pp. 13-22. · Zbl 0776.49009
[47] G. Zames, {\it On the input-output stability of time-varying nonlinear feedback systems–Part I: Conditions derived using concepts of loop gain, conicity, and positivity}, IEEE Trans. Automat. Control, 11 (1966), pp. 228-238.
[48] G. Zames, {\it On the input-output stability of time-varying nonlinear feedback systems–Part II: Conditions involving circles in the frequency plane and sector nonlinearities}, IEEE Trans. Automat. Control, 11 (1966), pp. 465-476.
[49] G. Zames and P. L. Falb, {\it Stability conditions for systems with monotone and slope-restricted nonlinearities}, SIAM J. Control, 6 (1968), pp. 89-108. · Zbl 0157.15801
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.