×

Projected dynamical systems on irregular, non-Euclidean domains for nonlinear optimization. (English) Zbl 1464.34038

Authors’ abstract: In this paper, we study a generalized class of projected dynamical systems in finite dimensions that allows for oblique projection directions. These variable projection directions are described by means of a (possibly nondifferentiable) metric \(g\) and are essential in providing a coordinate-free definition of projected dynamical systems on low-regularity Riemannian manifolds. Compared to previous work, we do not make a priori assumptions on the regularity (or convexity) of the feasible domain \(\chi\) or the vector field \(f\). Instead, we strive to illustrate the necessity of those assumptions that we require by a series of (non)examples. Our main contribution is the development of a self-contained and comprehensive theory for this general setup. Namely, we provide weak requirements on the feasible set \(\chi\), the vector field \(f\), the metric \(g\), and the differentiable structure of the underlying manifold that guarantee the existence and uniqueness of trajectories, as well as other properties.

MSC:

34A60 Ordinary differential inclusions
49J27 Existence theories for problems in abstract spaces
49K27 Optimality conditions for problems in abstract spaces
53B20 Local Riemannian geometry
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] P.-A. Absil and K. Kurdyka, On the stable equilibrium points of gradient systems, Systems Control Lett., 55 (2006), pp. 573-577. · Zbl 1129.34320
[2] P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2008. · Zbl 1147.65043
[3] S. Adly, F. Nacry, and L. Thibault, Preservation of prox-regularity of sets with applications to constrained optimization, SIAM J. Optim., 26 (2016), pp. 448-473. · Zbl 1333.49031
[4] Y. I. Alber, Generalized projection operators in Banach spaces: Properties and applications, in Theory and Applications of Nonlinear Operators of Monotone and Accretive Type, Marcel Dekker, New York, 1996, pp. 15-50. · Zbl 0883.47083
[5] K. J. Arrow, L. Hurwicz, and H. Uzawa, Studies in Linear and Nonlinear Programming, Stanford University Press, Palo Alto, CA, 1958. · Zbl 0091.16002
[6] J. P. Aubin, Viability Theory, Systems Control Found. Appl., Springer, New York, 1991. · Zbl 0755.93003
[7] J.-P. Aubin and A. Cellina, Differential Inclusions: Set-Valued Maps and Viability Theory, Grundlehren Math. Wiss. 264, Springer, New York, 1984. · Zbl 0538.34007
[8] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, John Wiley & Sons, Hoboken, NJ, 2006. · Zbl 1140.90040
[9] F. Bernicot and J. Venel, Sweeping process by prox-regular sets in Riemannian Hilbert manifolds, J. Differential Equations, 259 (2015), pp. 4086-4121. · Zbl 1365.34035
[10] A. Bernstein, E. Dall’Anese, and A. Simonetto, Online primal-dual methods with measurement feedback for time-varying convex optimization, IEEE Trans. Signal Process., 67 (2019), pp. 1978-1991. · Zbl 1458.90508
[11] R. W. Brockett, Dynamical systems that sort lists, diagonalize matrices and solve linear programming problems, in Proceedings of the IEEE Conference on Decision and Control (CDC), Vol. 1, Austin, TX, 1988, pp. 799-803.
[12] B. Brogliato, A. Daniilidis, C. Lemaréchal, and V. Acary, On the equivalence between complementarity systems, projected systems and differential inclusions, Systems Control. Lett., 55 (2006), pp. 45-51. · Zbl 1129.90358
[13] A. Cherukuri, E. Mallada, and J. Cortés, Asymptotic convergence of constrained primal\textendashdual dynamics, Systems Control Lett., 87 (2016), pp. 10-15. · Zbl 1327.49057
[14] F. Clarke, Optimization and Nonsmooth Analysis, Classics Appl. Math., SIAM, Philadelphia, 1990. · Zbl 0696.49002
[15] F. H. Clarke, Y. S. Ledyaev, R. J. Stern, and P. R. Wolenski, Nonsmooth Analysis and Control Theory, Grad. Texts in Math. 178, Springer, New York, 1998. · Zbl 1047.49500
[16] M.-G. Cojocaru and L. Jonker, Existence of solutions to projected differential equations in Hilbert spaces, Proc. Amer. Math. Soc., 132 (2004), pp. 183-193. · Zbl 1055.34118
[17] M. G. Cojocaru and S. Pia, Nonpivot and implicit projected dynamical systems on Hilbert spaces, J. Funct. Spaces Appl., 2012 (2012). · Zbl 1284.37014
[18] M. Colombino, E. Dall’Anese, and A. Bernstein, Online Optimization as a Feedback Controller: Stability and Tracking, IEEE Trans. Control Netw. Syst., 71 (2020), pp. 422-432. · Zbl 1516.93058
[19] B. Cornet, Existence of slow solutions for a class of differential inclusions, J. Math. Anal. Appl., 96 (1983), pp. 130-147. · Zbl 0558.34011
[20] J. Cortés, Discontinuous dynamical systems, IEEE Control Syst., 28 (2008), pp. 36-73. · Zbl 1395.34023
[21] E. Dall’Anese and A. Simonetto, Optimal Power Flow Pursuit, IEEE Trans. Smart Grid, 9 (2018), pp. 942-952.
[22] M. Fazlyab, A. Ribeiro, M. Morari, and V. M. Preciado, Analysis of optimization algorithms via integral quadratic constraints: Nonstrongly convex problems, SIAM J. Optim., 28 (2018), pp. 2654-2689. · Zbl 1406.90089
[23] A. F. Filippov, Differential Equations with Discontinuous Righthand Sides: Control Systems, Math. Appl. (Soviet Series), Springer, New York, 1988. · Zbl 0664.34001
[24] S. Giuffrè, G. Idone, and S. Pia, Some classes of projected dynamical systems in Banach spaces and variational inequalities, J. Global Optim., 40 (2008), pp. 119-128. · Zbl 1194.49015
[25] R. Goebel, R. G. Sanfelice, and A. R. Teel, Hybrid Dynamical Systems: Modeling, Stability, and Robustness, Princeton University Press, Princeton, NJ, 2012. · Zbl 1241.93002
[26] V. Häberle, A. Hauswirth, L. Ortmann, S. Bolognani, and F. Dörfler, Non-convex feedback optimization with input and output constraints, IEEE Control Syst. Lett., 5 (2020), pp. 343-348.
[27] G. Haddad, Monotone trajectories of differential inclusions and functional differential inclusions with memory, Israel J. Math., 39 (1981), pp. 83-100. · Zbl 0462.34048
[28] P. Hartman, On the local uniqueness of geodesics, Amer. J. Math., 72 (1950), pp. 723-730. · Zbl 0039.16803
[29] A. Hauswirth, S. Bolognani, and F. Dörfler, Projected Dynamical Systems on Irregular, Non-Euclidean Domains for Nonlinear Optimization, https://arxiv.org/abs/1809.04831, 2018.
[30] A. Hauswirth, S. Bolognani, G. Hug, and F. Dörfler, Projected gradient descent on Riemannian manifolds with applications to online power system optimization, in Proceedings of the 54th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, 2016, pp. 225-232.
[31] A. Hauswirth, F. Dörfler, and A. R. Teel, Anti-Windup Approximations of Oblique Projected Dynamical Systems for Feedback-Based Optimization, https://arxiv.org/abs/2003.00478, 2020.
[32] A. Hauswirth, F. Dörfler, and A. R. Teel, On the differentiability of projected trajectories and the robust convergence of non-convex anti-windup gradient flows, IEEE Control Syst. Lett., 4 (2020), pp. 620-625.
[33] A. Hauswirth, A. Zanardi, S. Bolognani, F. Dörfler, and G. Hug, Online optimization in closed loop on the power flow manifold, in Proceedings of the IEEE PowerTech Conference, Manchester, UK, 2017.
[34] W. P. M. H. Heemels, J. M. Schumacher, and S. Weiland, Projected dynamical systems in a complementarity formalism, Oper. Res. Lett., 27 (2000), pp. 83-91. · Zbl 0980.93031
[35] U. Helmke and J. B. Moore, Optimization and Dynamical Systems, Comm. Control Engrg., 2nd ed., Springer, New York, 1996. · Zbl 0984.49001
[36] C. Henry, An existence theorem for a class of differential equations with multivalued right-hand side, J. Math. Anal. Appl., 41 (1973), pp. 179-186. · Zbl 0262.49019
[37] J.-B. Hiriart-Urruty and C. Lemaréchal, Fundamentals of Convex Analysis, Grundlehren Text Ed., Springer, New York, 2012.
[38] S. Hosseini and M. Pouryayevali, On the metric projection onto prox-regular subsets of Riemannian manifolds, Proc. Amer. Math. Soc., 141 (2013), pp. 233-244. · Zbl 1277.58005
[39] F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, Rate control for communication networks: Shadow prices, proportional fairness and stability, J. Oper. Res. Soc., 49 (1998), pp. 237-252. · Zbl 1111.90313
[40] W. Krichene, A. Bayen, and P. L. Bartlett, Accelerated mirror descent in continuous and discrete time, in Proceedings of the Advances in Neural Information Processing Systems (NIPS), Montreal, 2015, pp. 2845-2853.
[41] J. D. Lee, Y. Sun, and M. A. Saunders, Proximal Newton-type methods for minimizing composite functions, SIAM J. Optim., 24 (2014), pp. 1420-1443. · Zbl 1306.65213
[42] L. Lessard, B. Recht, and A. Packard, Analysis and design of optimization algorithms via integral quadratic constraints, SIAM J. Optim., 26 (2016), pp. 57-95. · Zbl 1329.90103
[43] D. Liberzon, Switching in Systems and Control, Systems Control Found. Appl., Birkhäuser, Basel, Switzerland, 2003. · Zbl 1036.93001
[44] S. H. Low, F. Paganini, and J. C. Doyle, Internet Congestion Control, IEEE Control Syst., 22 (2002), pp. 28-43. · Zbl 1061.93074
[45] J. Lygeros, K. H. Johansson, S. N. Simic, J. Zhang, and S. S. Sastry, Dynamical properties of hybrid automata, IEEE Trans. Automat. Control, 48 (2003), pp. 2-17. · Zbl 1364.93503
[46] S. Menta, A. Hauswirth, S. Bolognani, G. Hug, and F. Dörfler, Stability of dynamic feedback optimization with applications to power systems, in the 56th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, 2018, pp. 136-143.
[47] D. K. Molzahn, F. Dörfler, H. Sandberg, S. H. Low, S. Chakrabarti, R. Baldick, and J. Lavaei, A survey of distributed optimization and control algorithms for electric power systems, IEEE Trans. Smart Grid, 8 (2017), pp. 2941-2962.
[48] A. Nagurney and D. Zhang, Projected Dynamical Systems and Variational Inequalities with Applications, 1st ed., Springer, New York, 1996. · Zbl 0865.90018
[49] Z. E. Nelson and E. Mallada, An integral quadratic constraint framework for real-time steady-state optimization of linear time-invariant systems, in Proceedings of the American Control Conference (ACC), Milwaukee, WI, 2018, pp. 597-603.
[50] J. Nocedal and S. J. Wright, Numerical Optimization, Springer Ser. Oper. Res., 2nd ed., Springer, New York, 2006. · Zbl 1104.65059
[51] J. Peypouquet, Convex Optimization in Normed Spaces: Theory, Methods and Examples, Springer Briefs Optim., Springer, New York, 2015. · Zbl 1322.90004
[52] R. Poliquin and R. Rockafellar, Prox-regular functions in variational analysis, Trans. Amer. Math. Soc., 348 (1996), pp. 1805-1838. · Zbl 0861.49015
[53] R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Grundlehren Math. Wiss. 317, Springer, New York, 2009.
[54] H. Royden and P. Fitzpatrick, Real Analysis, 4th ed., Pearson, Upper Saddle River, NJ, 1988. · Zbl 1191.26002
[55] E. P. Ryan, An Integral Invariance Principle for Differential Inclusions with Applications in Adaptive Control, SIAM J. Control Optim., 36 (1998), pp. 960-980. · Zbl 0911.93046
[56] S. N. Simić, K. H. Johansson, S. Sastry, and J. Lygeros, Towards a geometric theory of hybrid systems, in Proceedings of the International Workshop on Hybrid Systems: Computation and Control, Lecture Notes in Comput. Sci., Springer, New York, 2000, pp. 421-436. · Zbl 0963.93044
[57] W. Su, S. Boyd, and E. Candes, A differential equation for modeling Nesterov’s accelerated gradient method: Theory and insights, in Proceedings of Advances in Neural Information Processing Systems (NIPS), Montreal, 2014, pp. 2510-2518.
[58] Y. Tang, K. Dvijotham, and S. Low, Real-time optimal power flow, IEEE Trans. Smart Grid, 8 (2017), pp. 2963-2973.
[59] A. Wibisono, A. C. Wilson, and M. I. Jordan, A variational perspective on accelerated methods in optimization, Proc. Natl. Acad. Sci. USA, 113 (2016), pp. E7351-E7358. · Zbl 1404.90098
[60] A. C. Wilson, B. Recht, and M. I. Jordan, A Lyapunov analysis of momentum methods in optimization, https://arxiv.org/abs/1611.02635, 2016.
[61] X. Zhang, A. Papachristodoulou, and N. Li, Distributed control for reaching optimal steady state in network systems: An optimization approach, IEEE Trans. Automat. Control, 63 (2018), pp. 864-871. · Zbl 1390.93359
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.