×

Stability of primal-dual gradient dynamics and applications to network optimization. (English) Zbl 1205.93138

Summary: This paper considers dynamic laws that seek a saddle point of a function of two vector variables, by moving each in the direction of the corresponding partial gradient. This method has old roots in the classical work of Arrow, Hurwicz and Uzawa on convex optimization, and has seen renewed interest with its recent application to resource allocation in communication networks. This paper brings other tools to bear on this problem, in particular Krasovskii’s method to find Lyapunov functions, and recently obtained extensions of the LaSalle invariance principle for hybrid systems. These methods are used to obtain stability proofs of these primal-dual laws in different scenarios, and applications to cross-layer network optimization are exhibited.

MSC:

93D30 Lyapunov and storage functions
93D05 Lyapunov and other classical stabilities (Lagrange, Poisson, \(L^p, l^p\), etc.) in control theory
90C25 Convex programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Arrow, K.; Hurwicz, L.; Uzawa, H., Studies in linear and non-linear programming, (1958), Stanford University Press California, Stanford · Zbl 0091.16002
[2] Boyd, S.; Vandenberghe, L., Convex optimization, (2004), Cambridge University Press · Zbl 1058.90049
[3] Chiang, M.; Low, S.H.; Calderbank, A.R.; Doyle, J.C., Layering as optimization decomposition: a mathematical theory of network architectures, Proceedings of the IEEE, 95, January, 255-312, (2007)
[4] Feijer, D., & Paganini, F. (2009). Krasovskii’s method in the stability of network control. In Proceedings of the American control conference. · Zbl 1205.93138
[5] Freund, R.M., Penalty and barrier methods for constrained optimization, ()
[6] Kelly, F.P.; Maulloo, A.; Tan, D., Rate control for communication networks: shadow prices, proportional fairness and stability, Journal of the operations research society, 49, 3, 237-252, (1998) · Zbl 1111.90313
[7] Khalil, H.K., Nonlinear systems, (1996), Prentice-Hall · Zbl 0626.34052
[8] Krasovskii, N.N., Problems of the theory of stability of motion, (1963), Stanford University Press, (in Russian). English Translation · Zbl 0109.06001
[9] Lee, J.-W.; Chiang, M.; Calderbank, A.R., Utility-optimal random-access control, IEEE transactions on wireless communications, 6, 7, 2741-2751, (2007)
[10] Lee, J.-W.; Chiang, M.; Calderbank, A.R., Jointly optimal congestion and contention control based on network utility maximization, IEEE communication letters, 10, 3, 216-218, (2006)
[11] Lin, X.; Shroff, N.; Srikant, R., A tutorial on cross-layer optimization in wireless networks, IEEE journal on selected areas in communications, Aug, 1452-1463, (2006)
[12] Lygeros, J.; Johansson, K.H.; Simic, S.N.; Zhang, J.; Sastry, S.S., Dynamical properties of hybrid automata, IEEE transactions on automatic control, 48, 2-17, (2003) · Zbl 1364.93503
[13] Mo, J.; Walrand, J., Fair end-to-end window-based congestion control, IEEE/ACM transanctions on netwworking, 8, 5, 556-567, (2000)
[14] Nedic, A.; Ozdaglar, A., Subgradient methods for saddle point problems, Journal of optimization theorem and applications theory and applications, 142, 1, 205-228, (2009) · Zbl 1175.90415
[15] Srikant, R., The mathematics of Internet congestion control, (2004), Birkhauser · Zbl 1086.68018
[16] Wen, J.T., & Arcak, M. (2003). A unifying passivity framework for network flow control. In IEEE Infocom. · Zbl 1365.90042
[17] Yu, Y.; Giannakis, G.B., Cross-layer congestion and contention control for wireless ad hoc networks, IEEE transactions on wireless communications, 7, 1, (2008)
[18] Zhang, J.; Zheng, D.; Chiang, M., The impact of stochastic noisy feedback on distributed network utility maximization, IEEE transactions on information theory, 54, 2, 645-665, (2008) · Zbl 1304.94008
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.