×

zbMATH — the first resource for mathematics

Reduced order solution of structured linear systems arising in certain PDE-constrained optimization problems. (English) Zbl 1266.49061
The author investigates solving of structured algebraic linear systems whose blocks stem from the discretized first-order optimality conditions for PDE-constrained optimal control problems. The numerical solution of the corresponding large scale system is analyzed. An ordered reduction is performed firstly and the reduced system is solved iteratively using specifically designed preconditioning techniques. The analysis is completed by numerical experiments on an Dirichlet problem for the Poisson equation and on a simplified Monge-Kantorovich mass transfer problem.

MSC:
49M30 Other numerical methods in calculus of variations (MSC2010)
49K20 Optimality conditions for problems involving partial differential equations
49M25 Discrete approximations in optimal control
35J20 Variational methods for second-order elliptic equations
49Q20 Variational problems in a geometric measure-theoretic setting
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bai, Z., Demmel, J., Dongarra, J., Ruhe, A., van der Vorst, H. (eds.): Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. SIAM, Philadelphia (2000) · Zbl 0965.65058
[2] Bai, Z.-Z., Benzi, M., Chen, F., Wang, Z.-Q.: Preconditioned MHSS iteration methods for a class of block two-by-two linear systems with applications to distributed control problems. Technical Report 2011-001, Math/CS Department, Emory University (January 2011). To appear in IMA J. Numer. Anal. · Zbl 1271.65100
[3] Benzi, M., Haber, E., Taralli, L.: A preconditioning technique for a class of PDE-constrained optimization problems. Adv. Comput. Math. 35, 149–173 (2011) · Zbl 1293.65041 · doi:10.1007/s10444-011-9173-8
[4] Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numer. 14, 1–137 (2005) · Zbl 1115.65034 · doi:10.1017/S0962492904000212
[5] Bergamaschi, L., Gondzio, J., Venturin, M., Zilli, G.: Inexact constraint preconditioners for linear systems arising in interior point methods. Comput. Optim. Appl. 36(2–3), 137–147 (2007) · Zbl 1148.90349 · doi:10.1007/s10589-006-9001-0
[6] Borzì, A., Schulz, V.: Multigrid methods for PDE optimization. SIAM Rev. 51(2), 361–395 (2009) · Zbl 1167.35354 · doi:10.1137/060671590
[7] Boyle, J., Mihajlović, M.D., Scott, J.A.: HSL_MI20: an efficient AMG preconditioner. Int. J. Numer. Methods Eng., 82(1), 64–98 (2010) · Zbl 1183.76799
[8] Brandt, A.: Algebraic multigrid theory: the symmetric case. Appl. Math. Comput. 19, 23–56 (1986) · Zbl 0616.65037 · doi:10.1016/0096-3003(86)90095-0
[9] Cao, Z.-H.: Augmentation block preconditioners for saddle point-type matrices with singular (1, 1) blocks. Numer. Linear Algebra Appl. 15, 515–533 (2008) · Zbl 1212.65146 · doi:10.1002/nla.572
[10] Dollar, H.S., Gould, N.I.M., Schilders, W.H.A., Wathen, A.J.: Implicit-factorization preconditioning and iterative solvers for regularized saddle-point systems. SIAM J. Matrix Anal. Appl. 28, 170–189 (2006) · Zbl 1104.65310 · doi:10.1137/05063427X
[11] Durazzi, C., Ruggiero, V.: Indefinitely preconditioned conjugate gradient method for large sparse equality and inequality constrained quadratic problems. Numer. Linear Algebra Appl. 10, 673–688 (2003) · Zbl 1071.65512 · doi:10.1002/nla.308
[12] Elman, H.C., Silvester, D.J., Wathen, A.J.: Finite Elements and Fast Iterative Solvers, with Applications in Incompressible Fluid Dynamics. Numerical Mathematics and Scientific Computation, vol. 21. Oxford University Press, London (2005) · Zbl 1083.76001
[13] Gould, N., Simoncini, V.: Spectral analysis of saddle point matrices with indefinite leading blocks. SIAM J. Matrix Anal. Appl. 31, 1152–1171 (2009) · Zbl 1200.15007 · doi:10.1137/080733413
[14] Gould, N.I.M., Hribar, M.E., Nocedal, J.: On the solution of equality constrained quadratic programming problems arising in optimization. SIAM J. Sci. Comput. 23, 1376–1395 (2001) · Zbl 0999.65050 · doi:10.1137/S1064827598345667
[15] Greif, C., Schötzau, D.: Preconditioners for saddle point linear systems with highly singular (1, 1) blocks. Electron. Trans. Numer. Anal. 22, 114–121 (2006) · Zbl 1112.65042
[16] Greif, C., Overton, M.: An analysis of low-rank modifications of preconditioners for saddle point systems. Electron. Trans. Numer. Anal. 37, 307–320 (2010) · Zbl 1205.65142
[17] Haber, E., Ascher, U.: Preconditioned all-at-once methods for large, sparse parameter estimation problems. Inverse Probl. 17, 1847–1864 (2001) · Zbl 0995.65110 · doi:10.1088/0266-5611/17/6/319
[18] Herzog, R., Sachs, E.: Preconditioned conjugate gradient method for optimal control problems with control and state constraints. SIAM J. Matrix Anal. Appl. 31(5), 2291–2317 (2010) · Zbl 1209.49038 · doi:10.1137/090779127
[19] Krzyzanowski, P.: On block preconditioners for saddle point problems with singular or indefinite (1, 1) block. Numer. Linear Algebra Appl. 18(1), 123–140 (2011) · Zbl 1249.65059 · doi:10.1002/nla.717
[20] Lukšan, L., Vlček, J.: Indefinitely preconditioned inexact Newton method for large sparse equality constrained non-linear programming problems. Numer. Linear Algebra Appl. 5, 219–247 (1998) · Zbl 0937.65066 · doi:10.1002/(SICI)1099-1506(199805/06)5:3<219::AID-NLA134>3.0.CO;2-7
[21] Mardal, K.-A., Winther, R.: Preconditioning discretizations of systems of partial differential equations. Numer. Linear Algebra Appl. 18(1), 1–40 (2011) · Zbl 1249.65246 · doi:10.1002/nla.716
[22] The MathWorks, Inc. MATLAB 7, September 2004
[23] Oberle, H.J., Grimm, W.: BNDSCO-A Program for the numerical solution of optimal control problems. Technical report, Institute for Flight Systems Dynamics, DLR, Oberpfaffenhofen (1989)
[24] Olshanskii, M., Simoncini, V.: Acquired clustering properties and solution of certain saddle point systems. SIAM J. Matrix Anal. Appl. 31, 2754–2768 (2010) · Zbl 1213.65060 · doi:10.1137/100792652
[25] Perugia, I., Simoncini, V.: Block–diagonal and indefinite symmetric preconditioners for mixed finite element formulations. Numer. Linear Algebra Appl. 7, 585–616 (2000) · Zbl 1051.65038 · doi:10.1002/1099-1506(200010/12)7:7/8<585::AID-NLA214>3.0.CO;2-F
[26] Rees, T., Stoll, M., Wathen, A.: All-at-once preconditioning in PDE-constrained optimization. Kybernetika 46(2), 341–360 (2010) · Zbl 1195.65083
[27] Rees, T., Wathen, A.J.: Preconditioning iterative methods for the optimal control of the Stokes equations. SIAM J. Sci. Comput. 33, 2903–2926 (2011) · Zbl 1300.49009 · doi:10.1137/100798491
[28] Rees, T., Greif, C.: A preconditioner for linear systems arising from interior point optimization methods. SIAM J. Sci. Comput. 29(5), 1992–2007 (2007) · Zbl 1155.65048 · doi:10.1137/060661673
[29] Rees, T.: Preconditioning iterative methods for PDE constrained optimization. Ph.D. thesis, University of Oxford (2010)
[30] Rees, T., Stoll, M.: Block-triangular preconditioners for PDE-constrained optimization. Numer. Linear Algebra Appl. 17(6), 977–996 (2010) · Zbl 1240.65097 · doi:10.1002/nla.693
[31] Ruge, J.W., Stüben, K.: Algebraic multigrid. In: Multigrid Methods, Frontiers Appl. Math. SIAM, Philadelphia (1987)
[32] Saad, Y.: A flexible inner-outer preconditioned GMRES. SIAM J. Sci. Comput. 14, 461–469 (1993) · Zbl 0780.65022 · doi:10.1137/0914028
[33] Schöberl, J., Zulehner, W.: Symmetric indefinite preconditioners for saddle point problems with applications to PDE-constrained optimization problems. SIAM J. Matrix Anal. Appl. 29(3), 752–773 (2007) · Zbl 1154.65029 · doi:10.1137/060660977
[34] Sesana, D., Simoncini, V.: Spectral analysis of inexact constraint preconditioning for symmetric saddle point matrices. Technical report, Dipartimento di Matematica, Università di Bologna (2010) · Zbl 1263.65029
[35] Silvester, D., Mihajlovic, M.: A black-box multigrid preconditioner for the biharmonic equation. BIT Numer. Math. 44, 151–163 (2004) · Zbl 1053.65092 · doi:10.1023/B:BITN.0000025094.68655.c7
[36] Silvester, D., Wathen, A.: Fast iterative solution of stabilized Stokes systems part II: using general block preconditioners. SIAM J. Numer. Anal. 31, 1352–1367 (1994) · Zbl 0810.76044 · doi:10.1137/0731070
[37] Simoncini, V.: Solution of structured algebraic linear systems in PDE-constrained optimization problems. Available at http://www.dm.unibo.it/\(\sim\)simoncin/ , July 2010. Slides of the talk given at the ”Erice 2010 Workshop on Nonlinear Optimization, Variational Inequalities and Equilibrium Problems, 2–10 July 2010”
[38] Simoncini, V., Szyld, D.B.: Recent computational developments in Krylov subspace methods for linear systems. Numer. Linear Algebra Appl. 14(1), 1–59 (2007) · Zbl 1199.65112 · doi:10.1002/nla.499
[39] Stoll, M., Wathen, A.: All-at-once solution of time-dependent PDE-constrained optimization problems. Technical Report 1017, The Mathematical Institute, University of Oxford (2010) · Zbl 1195.65083
[40] Thorne, H.S.: Distributed control and constraint preconditioners. Technical Report RAL-TR-2010-016, Rutherford Appleton Laboratory (2010) · Zbl 1433.49047
[41] Tröltzsch, F.: Optimal Control of Partial Differential Equations: Theory, Methods and Applications. Am. Math. Soc., Providence (2010). Translated by J. Sprekels · Zbl 1195.49001
[42] Wathen, A., Rees, T.: Chebyshev semi-iteration in preconditioning for problems including the mass matrix. Electron. Trans. Numer. Anal. 34, 125–135 (2008–2009) · Zbl 1189.65065
[43] Zulehner, W.: Nonstandard norms and robust estimates for saddle point problems. SIAM. J. Matrix Anal. Appl. 32, 536 (2011) · Zbl 1251.65078 · doi:10.1137/100814767
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.