Skip to main content
SpringerLink
Log in

Fast iterative solvers for an optimal transport problem

  • Published:
Advances in Computational Mathematics Aims and scope Submit manuscript

Abstract

Optimal transport problems pose many challenges when considering their numerical treatment. We investigate the solution of a PDE-constrained optimisation problem subject to a particular transport equation arising from the modelling of image metamorphosis. We present the nonlinear optimisation problem, and discuss the discretisation and treatment of the nonlinearity via a Gauss–Newton scheme. We then derive preconditioners that can be used to solve the linear systems at the heart of the (Gauss–)Newton method.

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

Similar content being viewed by others

References

  1. Villani, C.: Optimal Transport: Old and New, vol. 338. Springer Science & Business Media, Berlin (2008)

    Google Scholar 

  2. Kuzmin, D.: A Guide to Numerical Methods for Transport Equations, Friedrich-Alexander-Universität Erlangen–Nürnberg, http://www.mathematik.uni-dortmund.de/~kuzmin/Transport.pdf (2010)

  3. Leveque, R.J.: Numerical Methods for Conservation Laws, 2nd edn. Birkhäuser, Basel (1992)

    Book  MATH  Google Scholar 

  4. Ito, K., Kunisch, K.: Lagrange Multiplier Approach to Variational Problems and Applications, vol. 15 of Advances in Design and Control, Society for Industrial and Applied Mathematics. Philadelphia, PA (2008)

    Google Scholar 

  5. Tröltzsch, F.: Optimal Control of Partial Differential Equations: Theory, Methods and Applications, American Mathematical Society (2010)

  6. 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 

  7. Kantorovich, L.V.: On a problem of Monge. J. Math. Sci. 133(4), 1383–1383 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  8. Kantorovitch, L.V.: On the translocation of masses. Manag. Sci. 5(1), 1–4 (1958)

    Article  MathSciNet  MATH  Google Scholar 

  9. Benamou, J. -D., Brenier, Y.: A computational fluid mechanics solution to the Monge–Kantorovich mass transfer problem. Numer. Math. 84(3), 375–393 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  10. Andreev, R., Scherzer, O., Zulehner, W.: Simultaneous optical flow and source estimation: space time discretization and preconditioning. Appl. Numer. Math. 96, 72–81 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  11. Borzi, A., Ito, K., Kunisch, K.: Optimal control formulation for determining optical flow. SIAM J. Sci. Comput. 24(3), 818–847 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  12. Bruhn, A., Weickert, J., Schnörr, C.: Lucas/Kanade meets Horn/Schunck: combining local and global optic flow methods. Int. J. Comput. Vis. 61(3), 211–231 (2005)

    Article  Google Scholar 

  13. Haber, E., Modersitzki, J.: A multilevel method for image registration. SIAM J. Sci. Comput. 27(5), 1594–1607 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  14. Horn, B.K.P., Schunck, B.G.: Determining optical flow. Artif. Intell. 17 (1–3), 185–203 (1981)

    Article  Google Scholar 

  15. Mang, A., Biros, G.: An inexact Newton–Krylov algorithm for constrained diffeomorphic image registration. SIAM J. Imaging Sci. 8(2), 1030–1069 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  16. Mang, A., Ruthotto, L.: A Lagrangian Gauss–Newton–Krylov solver for mass- and intensity-preserving diffeomorphic image registration. SIAM J. Sci. Comput. 39 (5), B860–B885 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  17. Haber, E., Ascher, U.M., Oldenburg, D.: On optimization techniques for solving nonlinear inverse problems. Inverse Probl. 16(5), 1263–1280 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  18. Axelsson, O., Farouq, S., Neytcheva, M.: Comparison of preconditioned Krylov subspace iteration methods for PDE-constrained optimization problems. Numer. Algorithm. 73(3), 631–663 (2016)

    Article  MATH  Google Scholar 

  19. Pearson, J.W., Stoll, M., Wathen, A.J.: Regularization-robust preconditioners for time-dependent PDE-constrained optimization problems. SIAM J. Matrix Anal. Appl. 33(4), 1126–1152 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  20. Pearson, J.W., Wathen, A.J.: Fast iterative solvers for convection–diffusion control problems. Electron. Trans. Numer. Anal. 40, 294–310 (2013)

    MathSciNet  MATH  Google Scholar 

  21. Zulehner, W.: Non-standard norms and robust estimates for saddle point problems. SIAM J. Matrix Anal. Appl. 32, 536–560 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  22. Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer Series in Operations Research and Financial Engineering, Springer, New York (2006)

    MATH  Google Scholar 

  23. Kuznetsov, Y.A.: Efficient iterative solvers for elliptic finite element problems on nonmatching grids. Russ. J. Numer. Anal. Math. Model. 10, 187–211 (1995)

    MathSciNet  MATH  Google Scholar 

  24. Murphy, M.F., Golub, G.H., Wathen, A.J.: A note on preconditioning for indefinite linear systems. SIAM J. Sci. Comput. 21(6), 1969–1972 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  25. Ipsen, I.C.F.: A note on preconditioning non-symmetric matrices. SIAM J. Sci. Comput. 23(3), 1050–1051 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  26. Pearson, J.W., Stoll, M.: Fast iterative solution of reaction–diffusion control problems arising from chemical processes. SIAM J. Sci. Comput. 35, B987–B1009 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  27. Pearson, J.W., Wathen, A.J.: A new approximation of the Schur complement in preconditioners for PDE-constrained optimization. Numer. Linear Algebra Appl. 19, 816–829 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  28. Benner, P., Dolgov, S., Onwunta, A., Stoll, M.: Low-rank solvers for unsteady Stokes–Brinkman optimal control problem with random data. Comput. Methods Appl. Mech. Eng. 304, 26–54 (2016)

    Article  MathSciNet  Google Scholar 

  29. Saad, Y., Schultz, M.H.: GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Comput. 7(3), 856–869 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  30. Borzi, A., Ito, K., Kunisch, K.: An optimal control approach to optical flow computation. Int. J. Numer. Methods Fluids 40(1–2), 231–240 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  31. Black, M.J., Jepson, A.D.: Eigentracking: robust matching and tracking of articulated objects using a view-based representation. Int. J. Comput. Vis. 26(1), 63–84 (1998)

    Article  Google Scholar 

Download references

Acknowledgments

The authors would like to thank two anonymous referees for their helpful comments and suggestions. JWP gratefully acknowledges support from the Engineering and Physical Sciences (EPSRC) Fellowship EP/M018857/2.

Author information

Authors and Affiliations

  1. Faculty of Mathematics, Technische Universität Chemnitz, Reichenhainer Straße 41, 09126, Chemnitz, Germany

    Roland Herzog & Martin Stoll

  2. School of Mathematics, The University of Edinburgh, James Clerk Maxwell Building, The King’s Buildings, Peter Guthrie Tait Road, Edinburgh, EH9 3FD, UK

    John W. Pearson

Authors
  1. Roland Herzog
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. John W. Pearson
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Martin Stoll
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Martin Stoll.

Additional information

Communicated by: Lothar Reichel

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Herzog, R., Pearson, J.W. & Stoll, M. Fast iterative solvers for an optimal transport problem. Adv Comput Math 45, 495–517 (2019). https://doi.org/10.1007/s10444-018-9625-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10444-018-9625-5

Keywords

Mathematics Subject Classification (2010)

Search

Navigation