Skip to main content
SpringerLink
Log in

Reduced order solution of structured linear systems arising in certain PDE-constrained optimization problems

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

The solution of PDE-constrained optimal control problems is a computationally challenging task, and it involves the solution of structured algebraic linear systems whose blocks stem from the discretized first-order optimality conditions. In this paper we analyze the numerical solution of this large-scale system: we first perform a natural order reduction, and then we solve the reduced system iteratively by exploiting specifically designed preconditioning techniques. The analysis is accompanied by numerical experiments on two application problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Notes

  1. In optimal control problems, the full rank assumption is actually an exceptional case, since it corresponds to having as many control variables as states, which is seldom encountered in practice.

  2. The computational cost will still grow with the problem size, as basic operations are performed with longer vectors when finer discretizations are used.

  3. With a little abuse of notation, the same letters will be used here to denote scalar functions and vectors.

  4. We thank one of the referees for pointing this out.

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)

    MATH  Google Scholar 

  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.

  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)

    Article  MathSciNet  MATH  Google Scholar 

  4. Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numer. 14, 1–137 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  6. Borzì, A., Schulz, V.: Multigrid methods for PDE optimization. SIAM Rev. 51(2), 361–395 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    MATH  Google Scholar 

  8. Brandt, A.: Algebraic multigrid theory: the symmetric case. Appl. Math. Comput. 19, 23–56 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    MATH  Google Scholar 

  13. Gould, N., Simoncini, V.: Spectral analysis of saddle point matrices with indefinite leading blocks. SIAM J. Matrix Anal. Appl. 31, 1152–1171 (2009)

    Article  MathSciNet  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  17. Haber, E., Ascher, U.: Preconditioned all-at-once methods for large, sparse parameter estimation problems. Inverse Probl. 17, 1847–1864 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  21. Mardal, K.-A., Winther, R.: Preconditioning discretizations of systems of partial differential equations. Numer. Linear Algebra Appl. 18(1), 1–40 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  25. Perugia, I., Simoncini, V.: Block–diagonal and indefinite symmetric preconditioners for mixed finite element formulations. Numer. Linear Algebra Appl. 7, 585–616 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  26. Rees, T., Stoll, M., Wathen, A.: All-at-once preconditioning in PDE-constrained optimization. Kybernetika 46(2), 341–360 (2010)

    MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  31. Ruge, J.W., Stüben, K.: Algebraic multigrid. In: Multigrid Methods, Frontiers Appl. Math. SIAM, Philadelphia (1987)

    Google Scholar 

  32. Saad, Y.: A flexible inner-outer preconditioned GMRES. SIAM J. Sci. Comput. 14, 461–469 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

  35. Silvester, D., Mihajlovic, M.: A black-box multigrid preconditioner for the biharmonic equation. BIT Numer. Math. 44, 151–163 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  37. Simoncini, V.: Solution of structured algebraic linear systems in PDE-constrained optimization problems. Available at http://www.dm.unibo.it/~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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

  40. Thorne, H.S.: Distributed control and constraint preconditioners. Technical Report RAL-TR-2010-016, Rutherford Appleton Laboratory (2010)

  41. Tröltzsch, F.: Optimal Control of Partial Differential Equations: Theory, Methods and Applications. Am. Math. Soc., Providence (2010). Translated by J. Sprekels

    MATH  Google Scholar 

  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)

    MathSciNet  Google Scholar 

  43. Zulehner, W.: Nonstandard norms and robust estimates for saddle point problems. SIAM. J. Matrix Anal. Appl. 32, 536 (2011)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We would like to thank the anonymous referees for helpful suggestions. We are grateful to Sue Thorne for providing us with the data on the distributed control problem of Sect. 3.1. We are indebted with Michele Benzi, Eldad Haber and Lauren Taralli for making their full code available, which allowed us to extract both the data and important information for the experiments of Sect. 4.1. We also thank Michele Benzi for helpful comments on an earlier version of this manuscript.

All reported timings were obtained with Matlab [22], using the computer facilities of the SINCEM Laboratory at CIRSA, Ravenna.

Author information

Authors and Affiliations

  1. Dipartimento di Matematica, Università di Bologna, Piazza di Porta S. Donato 5, 40127, Bologna, Italy

    V. Simoncini

  2. CIRSA, Ravenna, Italy

    V. Simoncini

Authors
  1. V. Simoncini
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to V. Simoncini.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Simoncini, V. Reduced order solution of structured linear systems arising in certain PDE-constrained optimization problems. Comput Optim Appl 53, 591–617 (2012). https://doi.org/10.1007/s10589-012-9464-0

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-012-9464-0

Keywords

Search

Navigation