Optimal Dirichlet control of partial differential equations on networks. (English) Zbl 1473.49002
Summary: Differential equations on metric graphs can describe many phenomena in the physical world but also the spread of information on social media. To efficiently compute the optimal setup of the differential equation for a given desired state is a challenging numerical analysis task. In this work, we focus on the task of solving an optimization problem subject to a linear differential equation on a metric graph with the control defined on a small set of Dirichlet nodes. We discuss the discretization by finite elements and provide rigorous error bounds as well as an efficient preconditioning strategy to deal with the large-scale case. We show in various examples that the method performs very robustly.
MSC:
| 49J20 | Existence theories for optimal control problems involving partial differential equations |
| 49M25 | Discrete approximations in optimal control |
| 65L10 | Numerical solution of boundary value problems involving ordinary differential equations |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 90B10 | Deterministic network models in operations research |
| 65M60 | Finite element, Rayleigh-Ritz and Galerkin methods for initial value and initial-boundary value problems involving PDEs |
Keywords:
complex networks; optimal Dirichlet control; preconditioning; saddle point systems; error estimationReferences:
| [1] | T. APEL, M. MATEOS, J. PFEFFERER,ANDA. RÖSCH,Error estimates for Dirichlet control problems in polygonal domains: quasi-uniform meshes, Math. Control Relat. Fields, 8 (2018), pp. 217-245. · Zbl 1407.65277 |
| [2] | T. APEL, S. NICAISE,ANDJ. PFEFFERER,Discretization of the Poisson equation with non-smooth data and emphasis on non-convex domains, Numer. Methods Partial Differential Equations, 32 (2016), pp. 1433- · Zbl 1353.65117 |
| [3] | M. ARIOLI ANDM. BENZI,A finite element method for quantum graphs, IMA J. Numer. Anal., 38 (2018), pp. 1119-1163. · Zbl 1462.65176 |
| [4] | A.-L. BARABÁSI,Network Science, Cambridge University Press, Cambridge, 2016. · Zbl 1353.94001 |
| [5] | M. BENZI ANDP. BOITO,Matrix functions in network analysis, GAMM-Mitt., 43 (2020), Art. No. e202000012, 36 pages. · Zbl 1541.05102 |
| [6] | M. BENZI, G. H. GOLUB,ANDJ. LIESEN,Numerical solution of saddle point problems, Acta Numer., 14 (2005), pp. 1-137. · Zbl 1115.65034 |
| [7] | G. BERKOLAIKO ANDP. KUCHMENT,Introduction to Quantum Graphs, American Mathematical Society, Providence, 2013. · Zbl 1318.81005 |
| [8] | E. CASAS ANDJ.-P. RAYMOND,Error estimates for the numerical approximation of Dirichlet boundary control for semilinear elliptic equations, SIAM J. Control Optim., 45 (2006), pp. 1586-1611. · Zbl 1123.65061 |
| [9] | X. CHENG ANDJ. M. A. SCHERPEN,Clustering approach to model order reduction of power networks with distributed controllers, Adv. Comput. Math., 44 (2018), pp. 1917-1939. · Zbl 1405.93052 |
| [10] | F. R. K. CHUNG,Spectral Graph Theory, American Mathematical Society, Providence, 1997. · Zbl 0867.05046 |
| [11] | R. DÁGER ANDE. ZUAZUA,Wave Propagation, Observation and Control in 1-d Flexible Multi-Structures, Springer, Berlin, 2006. · Zbl 1083.74002 |
| [12] | P. DOMSCHKE, A. DUA, J. J. STOLWIJK, J. LANG,ANDV. MEHRMANN,Adaptive refinement strategies for the simulation of gas flow in networks using a model hierarchy, Electron. Trans. Numer. Anal., 48 (2018), pp. 97-113. http://etna.ricam.oeaw.ac.at/vol.48.2018/pp97-113.dir/pp97-113.pdf · Zbl 06862887 |
| [13] | P. DOMSCHKE, O. KOLB,ANDJ. LANG,Adjoint-based error control for the simulation and optimization of gas and water supply networks, Appl. Math. Comput., 259 (2015), pp. 1003-1018. · Zbl 1390.90105 |
| [14] | I. S. DUFF, A. M. ERISMAN,ANDJ. K. REID,Direct Methods for Sparse Matrices, Oxford University Press, New York, 1989. · Zbl 0666.65024 |
| [15] | H. EGGER ANDN. PHILIPPI,A hybrid discontinuous galerkin method for transport equations on networks, in International Conference on Finite Volumes for Complex Applications, R. Klöfkorn, E. Keilegavlen, F. A. Radu, J. Fuhrmann, eds., Springer, Cham, 2020, pp. 487-495. · Zbl 1454.65163 |
| [16] | H. EGGER ANDL. SCHÖBEL-KRÖHN,Chemotaxis on networks: analysis and numerical approximation, ESAIM Math. Model. Numer. Anal., 54 (2020), pp. 1339-1372. · Zbl 1445.35199 |
| [17] | H. C. ELMAN, D. J. SILVESTER,ANDA. J. WATHEN,Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics, Oxford University Press, New York, 2005. · Zbl 1083.76001 |
| [18] | P. ERD ˝OS ANDA. RÉNYI,On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl., 5 (1960), pp. 17-61. |
| [19] | L. C. EVANS,Partial Differential Equations, 2nd ed., American Mathematical Society, Providence, 2010. · Zbl 1194.35001 |
| [20] | R. FERES ANDM. WALLACE,Reaction-diffusion on metric graphs and conversion probability, Preprint on arXiv, 2015.https://arxiv.org/abs/1501.06976. |
| [21] | M. GARAVELLO ANDB. PICCOLI,Traffic Flow on Networks, American Institute of Mathematical Sciences, Springfield, 2006. · Zbl 1136.90012 |
| [22] | W. GONG, M. HINZE,ANDZ. ZHOU,Finite element method and a priori error estimates for Dirichlet boundary control problems governed by parabolic PDEs, J. Sci. Comput., 66 (2016), pp. 941-967. · Zbl 1372.49004 |
| [23] | L. J. GRADY ANDJ. R. POLIMENI,Discrete Calculus, Springer, London, 2010. |
| [24] | S. GRUNDEL ANDM. HERTY,Hyperbolic discretization via Riemann invariants, Preprint on arXiv, 2020. https://arxiv.org/abs/2005.12158. |
| [25] | S. GRUNDEL, N. HORNUNG,ANDS. ROGGENDORF,Numerical aspects of model order reduction for gas transportation networks, in Simulation-Driven Modeling and Optimization, S. Koziel, L. Leifsson, X.S. Yang, eds., Springer Proceedings in Mathematics & Statistics, Springer International Publishing, Basel, 2016, pp. 1-28. |
| [26] | M. GUGAT, M. HERTY,ANDV. SCHLEPER,Flow control in gas networks: exact controllability to a given demand, Math. Methods Appl. Sci., 34 (2010), pp. 745-757. · Zbl 1394.76112 |
| [27] | M. HERTY, J. MOHRING,ANDV. SACHERS,A new model for gas flow in pipe networks, Math. Methods Appl. Sci., 33 (2010), pp. 845-855. · Zbl 1334.76131 |
| [28] | M. HERTY ANDC. RINGHOFER,Averaged kinetic models for flows on unstructured networks, Kinet. Relat. Models, 4 (2011), pp. 1081-1096. · Zbl 1242.90035 |
| [29] | R. HERZOG ANDE. SACHS,Preconditioned conjugate gradient method for optimal control problems with control and state constraints, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2291-2317. · Zbl 1209.49038 |
| [30] | J. HILD ANDG. LEUGERING,Real-time control of urban drainage systems, in Mathematical Optimization of Water Networks, A. Martin, K. Klamroth, J. Lang, G. Leugering, A. Morsi, M. Oberlack, M. Ostrowski, and R. Rosen, eds., vol. 162 of Internat. Ser. Numer. Math., Birkhäuser/Springer, Basel, 2012, pp. 129-150. · Zbl 1458.76068 |
| [31] | M. HINTERMÜLLER, K. ITO,ANDK. KUNISCH,The primal-dual active set strategy as a semismooth Newton method, SIAM J. Optim., 13 (2002), pp. 865-888. · Zbl 1080.90074 |
| [32] | M. HINZE, R. PINNAU, M. ULBRICH,ANDS. ULBRICH,Optimization with PDE Constraints, Springer, New York, 2009. · Zbl 1167.49001 |
| [33] | K. ITO ANDK. KUNISCH,Lagrange Multiplier Approach to Variational Problems and Applications, SIAM, Philadelphia, 2008. · Zbl 1156.49002 |
| [34] | P. KUCHMENT ANDO. POST,On the spectra of carbon nano-structures, Comm. Math. Phys., 275 (2007), pp. 805-826. · Zbl 1145.81032 |
| [35] | K. KUNISCH ANDB. VEXLER,Constrained Dirichlet boundary control inL2for a class of evolution equations, SIAM J. Control Optim., 46 (2007), pp. 1726-1753. · Zbl 1144.49003 |
| [36] | J. E. LAGNESE, G. LEUGERING,ANDE. J. P. G. SCHMIDT,Modeling, Analysis and Control of Dynamic Elastic Multi-Link Structures, Birkhäuser, Boston, 1994. · Zbl 0810.73004 |
| [37] | G. LEUGERING, A. MARTIN, M. SCHMIDT,ANDM. SIRVENT,Nonoverlapping domain decomposition for optimal control problems governed by semilinear models for gas flow in networks, Control Cybernet., 46 (2017), pp. 191-225. · Zbl 1391.49059 |
| [38] | J.-L. LIONS ANDE. MAGENES,Non-Homogeneous Boundary Value Problems and Applications. Vol. II, Springer, New York, 1972. · Zbl 0223.35039 |
| [39] | K.-A. MARDAL ANDR. WINTHER,Preconditioning discretizations of systems of partial differential equations, Numer. Linear Algebra Appl., 18 (2011), pp. 1-40. · Zbl 1249.65246 |
| [40] | S. MAY, R. RANNACHER,ANDB. VEXLER,Error analysis for a finite element approximation of elliptic Dirichlet boundary control problems, SIAM J. Control Optim., 51 (2013), pp. 2585-2611. · Zbl 1273.65087 |
| [41] | D. MEIDNER ANDB. VEXLER,A priori error estimates for space-time finite element discretization of parabolic optimal control problems. II. Problems with control constraints, SIAM J. Control Optim., 47 (2008), pp. 1301-1329. · Zbl 1161.49035 |
| [42] | P. MLINARI ´C, S. GRUNDEL,ANDP. BENNER,Efficient model order reduction for multi-agent systems using qr decomposition-based clustering, in 2015 54th IEEE Conference on Decision and Control (CDC), IEEE |
| [43] | D. MUGNOLO,Semigroup Methods for Evolution Equations on Networks, Springer, Cham, 2014. · Zbl 1306.47001 |
| [44] | M. F. MURPHY, G. H. GOLUB,ANDA. J. WATHEN,A note on preconditioning for indefinite linear systems, SIAM J. Sci. Comput., 21 (2000), pp. 1969-1972. · Zbl 0959.65063 |
| [45] | A. NORDENFELT,Spectral analysis of discrete approximations of quantum graphs, Tech. Rep., Lund University, Lund, 2007. |
| [46] | G. OF, T. X. PHAN,ANDO. STEINBACH,An energy space finite element approach for elliptic Dirichlet boundary control problems, Numer. Math., 129 (2015), pp. 723-748. · Zbl 1311.49069 |
| [47] | S. F. OPPENHEIMER,A convection-diffusion problem in a network, Appl. Math. Comput., 112 (2000), pp. 223-240. · Zbl 1049.76605 |
| [48] | C. C. PAIGE ANDM. A. SAUNDERS,Solutions of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12 (1975), pp. 617-629. · Zbl 0319.65025 |
| [49] | J. W. PEARSON, M. STOLL,ANDA. J. WATHEN,Regularization-robust preconditioners for time-dependent PDE-constrained optimization problems, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 1126-1152. · Zbl 1263.65035 |
| [50] | J. W. PEARSON ANDA. J. WATHEN,A new approximation of the Schur complement in preconditioners for PDE-constrained optimization, Numer. Linear Algebra Appl., 19 (2012), pp. 816-829. · Zbl 1274.65187 |
| [51] | ,Fast iterative solvers for convection-diffusion control problems, Electron. Trans. Numer. Anal., 40 (2013), pp. 294-310. http://etna.ricam.oeaw.ac.at/vol.40.2013/pp294-310.dir/pp294-310.pdf · Zbl 1287.49031 |
| [52] | J. PFEFFERER ANDM. WINKLER,Finite element error estimates for normal derivatives on boundary concentrated meshes, SIAM J. Numer. Anal., 57 (2019), pp. 2043-2073. · Zbl 1425.35019 |
| [53] | Y. QIU, S. GRUNDEL, M. STOLL,ANDP. BENNER,Efficient numerical methods for gas network modeling and simulation, Netw. Heterog. Media, 15 (2020), pp. 653-679. · Zbl 1457.76013 |
| [54] | T. REES, H. S. DOLLAR,ANDA. J. WATHEN,Optimal solvers for PDE-constrained optimization, SIAM J. Sci. Comput., 32 (2010), pp. 271-298. · Zbl 1208.49035 |
| [55] | T. REES ANDM. STOLL,Block-triangular preconditioners for PDE-constrained optimization, Numer. Linear Algebra Appl., 17 (2010), pp. 977-996. · Zbl 1240.65097 |
| [56] | Y. ROMANO, M. ELAD,ANDP. MILANFAR,The little engine that could: regularization by denoising (RED), SIAM J. Imaging Sci., 10 (2017), pp. 1804-1844. · Zbl 1401.62101 |
| [57] | M. ROZLOŽNÍK,Saddle-Point Problems and Their Iterative Solution, Birkhäuser/Springer, Cham, 2018. · Zbl 1494.65001 |
| [58] | Y. SAAD ANDM. H. SCHULTZ,GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856-869. · Zbl 0599.65018 |
| [59] | J. SCHÖBERL ANDW. ZULEHNER,Symmetric indefinite preconditioners for saddle point problems with applications to PDE-constrained optimization problems, SIAM J. Matrix Anal. Appl., 29 (2007), pp. 752- 773. · Zbl 1154.65029 |
| [60] | D. I. SHUMAN, S. K. NARANG, P. FROSSARD, A. ORTEGA,ANDP. VANDERGHEYNST,The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains, IEEE Signal Proc. Mag., 30 (2013), pp. 83-98. |
| [61] | D. SPIELMAN,Spectral graph theory, in Combinatorial Scientific Computing, U. Naumann and O. Schenk, eds., Chapman & Hall/CRC Computational Science Series, CRC Press, Boca Raton, 2012, pp. 495-524. |
| [62] | G. STADLER,Elliptic optimal control problems withL1-control cost and applications for the placement of control devices, Comput. Optim. Appl., 44 (2009), pp. 159-181. · Zbl 1185.49031 |
| [63] | M. STOLL,One-shot solution of a time-dependent time-periodic PDE-constrained optimization problem, IMA J. Numer. Anal., 34 (2014), pp. 1554-1577. · Zbl 1303.65050 |
| [64] | ,A literature survey of matrix methods for data science, GAMM-Mitt., 43 (2020), Art.No. e202000013, 26 pages. · Zbl 1541.65030 |
| [65] | M. STOLL ANDA. WATHEN,Preconditioning for partial differential equation constrained optimization with control constraints, Numer. Linear Algebra Appl., 19 (2012), pp. 53-71. · Zbl 1274.65189 |
| [66] | F. TRÖLTZSCH,Optimal Control of Partial Differential Equations: Theory, Methods, and Applications, American Mathematical Society, Providence, 2010. · Zbl 1195.49001 |
| [67] | U.VONLUXBURG,A tutorial on spectral clustering, Stat. Comput., 17 (2007), pp. 395-416. |
| [68] | M. WINKLER,Error estimates for variational normal derivatives and Dirichlet control problems with energy regularization, Numer. Math., 144 (2020), pp. 413-445. · Zbl 1433.49048 |
| [69] | A. ZLOTNIK, M. CHERTKOV,ANDS. BACKHAUS,Optimal control of transient flow in natural gas networks, in Decision and Control (CDC), 2015 IEEE 54th Annual Conference on, IEEE Conference Proceedings, Los Alamitos, 2015, pp. 4563-4570. |
| [70] | W. ZULEHNER,Nonstandard norms and robust estimates for saddle point problems, SIAM J. Matrix Analysis Applications, 32 (2011), pp. 536-560 · Zbl 1251.65078 |
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.
