A primal-dual optimization strategy for elliptic partial differential equations
Authors:
Dominique Zosso and Braxton Osting
Journal:
Quart. Appl. Math. 79 (2021), 175-200
MSC (2010):
Primary 65K10, 65N06; Secondary 49Q05, 35J20
DOI:
https://doi.org/10.1090/qam/1576
Published electronically:
October 6, 2020
MathSciNet review:
4188628
Full-text PDF
Abstract |
References |
Similar Articles |
Additional Information
Abstract: We consider a class of elliptic partial differential equations (PDE) that can be understood as the Euler–Lagrange equations of an associated convex optimization problem. Discretizing this optimization problem, we present a strategy for a numerical solution that is based on the popular primal-dual hybrid gradients (PDHG) approach: we reformulate the optimization as a saddle-point problem with a dual variable addressing the quadratic term, introduce the PDHG optimization steps, and analytically eliminate the dual variable. The resulting scheme resembles explicit gradient descent; however, the eliminated dual variable shows up as a boosting term that substantially accelerates the scheme. We introduce the proposed strategy for a simple Laplace problem and then illustrate the technique on a variety of more complicated and relevant PDE, both on Cartesian domains and graphs. The proposed numerical method is easily implementable, computationally efficient, and applicable to relevant computing tasks across science and engineering.
References
- Kenneth J. Arrow, Leonid Hurwicz, and Hirofumi Uzawa, Studies in linear and non-linear programming, Stanford Mathematical Studies in the Social Sciences, vol. II, Stanford University Press, Stanford, Calif., 1958. With contributions by H. B. Chenery, S. M. Johnson, S. Karlin, T. Marschak, R. M. Solow. MR 0108399
- Amir Beck and Marc Teboulle, Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Trans. Image Process. 18 (2009), no. 11, 2419–2434. MR 2722312, DOI https://doi.org/10.1109/TIP.2009.2028250
- Andrea L. Bertozzi and Arjuna Flenner, Diffuse interface models on graphs for classification of high dimensional data, Multiscale Model. Simul. 10 (2012), no. 3, 1090–1118. MR 3022033, DOI https://doi.org/10.1137/11083109X
- Dimitri P. Bertsekas, Convex optimization algorithms, Athena Scientific, Belmont, MA, 2015. MR 3558548
- Amit Bhaya and Eugenius Kaszkurewicz, Steepest descent with momentum for quadratic functions is a version of the conjugate gradient method., Neural networks: the official journal of the International Neural Network Society 17 (20041), no. 1, 65–71.
- Haïm Brezis and Moïse Sibony, Méthodes d’approximation et d’itération pour les opérateurs monotones, Arch. Rational MEch. Anal. 28 (1967/1968), 59–82 (French). MR 0220110, DOI https://doi.org/10.1007/BF00281564
- L. A. Caffarelli, The obstacle problem revisited, J. Fourier Anal. Appl. 4 (1998), no. 4-5, 383–402. MR 1658612, DOI https://doi.org/10.1007/BF02498216
- Antonin Chambolle and Thomas Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision 40 (2011), no. 1, 120–145. MR 2782122, DOI https://doi.org/10.1007/s10851-010-0251-1
- Damek Davis, Convergence rate analysis of primal-dual splitting schemes, SIAM J. Optim. 25 (2015), no. 3, 1912–1943. MR 3402786, DOI https://doi.org/10.1137/151003076
- John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra, Efficient projections onto the l1-ball for learning in high dimensions, Proceedings of the 25th international conference on machine learning - icml ’08, 20087, pp. 272–279.
- Ivar Ekeland and Roger Temam, Convex analysis and variational problems, North-Holland Publishing Co., Amsterdam-Oxford; American Elsevier Publishing Co., Inc., New York, 1976. Translated from the French; Studies in Mathematics and its Applications, Vol. 1. MR 0463994
- Ernie Esser, Xiaoqun Zhang, and Tony F. Chan, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sci. 3 (2010), no. 4, 1015–1046. MR 2763706, DOI https://doi.org/10.1137/09076934X
- Stanley J. Farlow, Partial differential equations for scientists and engineers, John Wiley & Sons, Inc., New York, 1982. MR 657763
- Avner Friedman, Variational principles and free-boundary problems, Pure and Applied Mathematics, John Wiley & Sons, Inc., New York, 1982. A Wiley-Interscience Publication. MR 679313
- Cristina Garcia-Cardona, Ekaterina Merkurjev, Andrea L. Bertozzi, Arjuna Flenner, and Allon G. Percus, Multiclass Data Segmentation Using Diffuse Interface Methods on Graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence 36 (20148), no. 8, 1600–1613.
- Arpita Ghosh, Stephen Boyd, and Amin Saberi, Minimizing effective resistance of a graph, SIAM Rev. 50 (2008), no. 1, 37–66. MR 2403057, DOI https://doi.org/10.1137/050645452
- Roland Glowinski, Variational methods for the numerical solution of nonlinear elliptic problems, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 86, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2015. MR 3450066
- Roland Glowinski and Stanley J. Osher (eds.), Splitting methods in communication, imaging, science, and engineering, Scientific Computation, Springer, Cham, 2016. MR 3587821
- Leo J. Grady and Jonathan R. Polimeni, Discrete calculus, Springer-Verlag London, Ltd., London, 2010. Applied analysis on graphs for computational science. MR 2676662
- James Hopwood Jeans, The Mathematical Theory of Electricity and Magnetism, Cambridge University Press, 1908.
- Nikos Komodakis and Jean-Christophe Pesquet, Playing with Duality: An overview of recent primal-dual approaches for solving large-scale optimization problems, IEEE Signal Processing Magazine 32 (201511), no. 6, 31–54.
- Gregory F. Lawler, Random walk and the heat equation, Student Mathematical Library, vol. 55, American Mathematical Society, Providence, RI, 2010. MR 2732325
- T. Lu, P. Neittaanmäki, and X.-C. Tai, A parallel splitting-up method for partial differential equations and its applications to Navier-Stokes equations, RAIRO Modél. Math. Anal. Numér. 26 (1992), no. 6, 673–708 (English, with English and French summaries). MR 1183413, DOI https://doi.org/10.1051/m2an/1992260606731
- Ekaterina Merkurjev, Cristina Garcia-Cardona, Andrea L. Bertozzi, Arjuna Flenner, and Allon G. Percus, Diffuse interface methods for multiclass segmentation of high-dimensional data, Appl. Math. Lett. 33 (2014), 29–34. MR 3193482, DOI https://doi.org/10.1016/j.aml.2014.02.008
- B. Merriman, J. K. Bence, and S. Osher, Diffusion generated motion by mean curvature, AMS Selected Letters, Crystal Grower’s Workshop (1993), 73–83.
- P. Neittaanmäki, M. Rudnicki, and A. Savini, Inverse Problems and Optimal Design in Electricity and Magnetism, Clarendon Press, 1996.
- Yu. E. Nesterov, A method for solving the convex programming problem with convergence rate $O(1/k^{2})$, Dokl. Akad. Nauk SSSR 269 (1983), no. 3, 543–547 (Russian). MR 701288
- B. T. Poljak, Some methods of speeding up the convergence of iterative methods, Ž. Vyčisl. Mat i Mat. Fiz. 4 (1964), 791–803 (Russian). MR 169403
- Ning Qian, On the momentum term in gradient descent learning algorithms, Neural Networks 12 (19991), no. 1, 145–151.
- Steven J. Ruuth and Brian T. R. Wetton, A simple scheme for volume-preserving motion by mean curvature, J. Sci. Comput. 19 (2003), no. 1-3, 373–384. Special issue in honor of the sixtieth birthday of Stanley Osher. MR 2028850, DOI https://doi.org/10.1023/A%3A1025368328471
- Daniel A. Spielman and Nikhil Srivastava, Graph sparsification by effective resistances, SIAM J. Comput. 40 (2011), no. 6, 1913–1926. MR 2863199, DOI https://doi.org/10.1137/080734029
- John C. Strikwerda, Finite difference schemes and partial differential equations, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2004. MR 2124284
- W Tobler, An Alternative Formulation for Spatial-Interaction Modeling, Environment and Planning A 15 (19835), no. 5, 693–703.
- Haiyan Wang, Feng Wang, and Kuai Xu, Modeling Information Diffusion in Online Social Networks with Partial Differential Equations (201310).
- N. N. Janenko, Implicit difference methods for the higher-dimensional heat equation, Izv. Vysš. Učebn. Zaved. Matematika 1961 (1961), no. 4 (23), 148–157 (Russian). MR 0152145
- Mingqiang Zhu and Tony Chan, An efficient primal-dual hybrid gradient algorithm for total variation image restoration, 2008.
- Mingqiang Zhu, Stephen J. Wright, and Tony F. Chan, Duality-based algorithms for total-variation-regularized image restoration, Comput. Optim. Appl. 47 (2010), no. 3, 377–400. MR 2746365, DOI https://doi.org/10.1007/s10589-008-9225-2
- Dominique Zosso, Braxton Osting, Mandy Xia, and Stanley J. Osher, An efficient primal-dual method for the obstacle problem, J. Sci. Comput. 73 (2017), no. 1, 416–437. MR 3704858, DOI https://doi.org/10.1007/s10915-017-0420-0
References
- Kenneth J. Arrow, Leonid Hurwicz, and Hirofumi Uzawa, Studies in linear and non-linear programming, With contributions by H. B. Chenery, S. M. Johnson, S. Karlin, T. Marschak, R. M. Solow. Stanford Mathematical Studies in the Social Sciences, vol. II, Stanford University Press, Stanford, Calif., 1958. MR 0108399
- Amir Beck and Marc Teboulle, Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Trans. Image Process. 18 (2009), no. 11, 2419–2434. MR 2722312, DOI https://doi.org/10.1109/TIP.2009.2028250
- Andrea L. Bertozzi and Arjuna Flenner, Diffuse interface models on graphs for classification of high dimensional data, Multiscale Model. Simul. 10 (2012), no. 3, 1090–1118. MR 3022033, DOI https://doi.org/10.1137/11083109X
- Dimitri P. Bertsekas, Convex optimization algorithms, Athena Scientific, Belmont, MA, 2015. MR 3558548
- Amit Bhaya and Eugenius Kaszkurewicz, Steepest descent with momentum for quadratic functions is a version of the conjugate gradient method., Neural networks: the official journal of the International Neural Network Society 17 (20041), no. 1, 65–71.
- Haïm Brezis and Moïse Sibony, Méthodes d’approximation et d’itération pour les opérateurs monotones, Arch. Rational MEch. Anal. 28 (1967/1968), 59–82 (French). MR 0220110, DOI https://doi.org/10.1007/BF00281564
- L. A. Caffarelli, The obstacle problem revisited, J. Fourier Anal. Appl. 4 (1998), no. 4-5, 383–402. MR 1658612, DOI https://doi.org/10.1007/BF02498216
- Antonin Chambolle and Thomas Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision 40 (2011), no. 1, 120–145. MR 2782122, DOI https://doi.org/10.1007/s10851-010-0251-1
- Damek Davis, Convergence rate analysis of primal-dual splitting schemes, SIAM J. Optim. 25 (2015), no. 3, 1912–1943. MR 3402786, DOI https://doi.org/10.1137/151003076
- John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra, Efficient projections onto the l1-ball for learning in high dimensions, Proceedings of the 25th international conference on machine learning - icml ’08, 20087, pp. 272–279.
- Ivar Ekeland and Roger Temam, Convex analysis and variational problems, Studies in Mathematics and its Applications, Vol. 1, North-Holland Publishing Co., Amsterdam-Oxford; American Elsevier Publishing Co., Inc., New York, 1976. Translated from the French. MR 0463994
- Ernie Esser, Xiaoqun Zhang, and Tony F. Chan, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sci. 3 (2010), no. 4, 1015–1046. MR 2763706, DOI https://doi.org/10.1137/09076934X
- Stanley J. Farlow, Partial differential equations for scientists and engineers, John Wiley & Sons, Inc., New York, 1982. MR 657763
- Avner Friedman, Variational principles and free-boundary problems, Pure and Applied Mathematics, John Wiley & Sons, Inc., New York, 1982. A Wiley-Interscience Publication. MR 679313
- Cristina Garcia-Cardona, Ekaterina Merkurjev, Andrea L. Bertozzi, Arjuna Flenner, and Allon G. Percus, Multiclass Data Segmentation Using Diffuse Interface Methods on Graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence 36 (20148), no. 8, 1600–1613.
- Arpita Ghosh, Stephen Boyd, and Amin Saberi, Minimizing effective resistance of a graph, SIAM Rev. 50 (2008), no. 1, 37–66. MR 2403057, DOI https://doi.org/10.1137/050645452
- Roland Glowinski, Variational methods for the numerical solution of nonlinear elliptic problems, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 86, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2015. MR 3450066
- Roland Glowinski and Stanley J. Osher (eds.), Splitting methods in communication, imaging, science, and engineering, Scientific Computation, Springer, Cham, 2016. MR 3587821
- Leo J. Grady and Jonathan R. Polimeni, Discrete calculus, Springer-Verlag London, Ltd., London, 2010. Applied analysis on graphs for computational science. MR 2676662
- James Hopwood Jeans, The Mathematical Theory of Electricity and Magnetism, Cambridge University Press, 1908.
- Nikos Komodakis and Jean-Christophe Pesquet, Playing with Duality: An overview of recent primal-dual approaches for solving large-scale optimization problems, IEEE Signal Processing Magazine 32 (201511), no. 6, 31–54.
- Gregory F. Lawler, Random walk and the heat equation, Student Mathematical Library, vol. 55, American Mathematical Society, Providence, RI, 2010. MR 2732325
- T. Lu, P. Neittaanmäki, and X.-C. Tai, A parallel splitting-up method for partial differential equations and its applications to Navier-Stokes equations, RAIRO Modél. Math. Anal. Numér. 26 (1992), no. 6, 673–708 (English, with English and French summaries). MR 1183413, DOI https://doi.org/10.1051/m2an/1992260606731
- Ekaterina Merkurjev, Cristina Garcia-Cardona, Andrea L. Bertozzi, Arjuna Flenner, and Allon G. Percus, Diffuse interface methods for multiclass segmentation of high-dimensional data, Appl. Math. Lett. 33 (2014), 29–34. MR 3193482, DOI https://doi.org/10.1016/j.aml.2014.02.008
- B. Merriman, J. K. Bence, and S. Osher, Diffusion generated motion by mean curvature, AMS Selected Letters, Crystal Grower’s Workshop (1993), 73–83.
- P. Neittaanmäki, M. Rudnicki, and A. Savini, Inverse Problems and Optimal Design in Electricity and Magnetism, Clarendon Press, 1996.
- Yu. E. Nesterov, A method for solving the convex programming problem with convergence rate $O(1/k^{2})$, Dokl. Akad. Nauk SSSR 269 (1983), no. 3, 543–547 (Russian). MR 701288
- B. T. Poljak, Some methods of speeding up the convergence of iterative methods, Ž. Vyčisl. Mat i Mat. Fiz. 4 (1964), 791–803 (Russian). MR 169403
- Ning Qian, On the momentum term in gradient descent learning algorithms, Neural Networks 12 (19991), no. 1, 145–151.
- Steven J. Ruuth and Brian T. R. Wetton, A simple scheme for volume-preserving motion by mean curvature, J. Sci. Comput. 19 (2003), no. 1-3, 373–384. Special issue in honor of the sixtieth birthday of Stanley Osher. MR 2028850, DOI https://doi.org/10.1023/A%3A1025368328471
- Daniel A. Spielman and Nikhil Srivastava, Graph sparsification by effective resistances, SIAM J. Comput. 40 (2011), no. 6, 1913–1926. MR 2863199, DOI https://doi.org/10.1137/080734029
- John C. Strikwerda, Finite difference schemes and partial differential equations, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2004. MR 2124284
- W Tobler, An Alternative Formulation for Spatial-Interaction Modeling, Environment and Planning A 15 (19835), no. 5, 693–703.
- Haiyan Wang, Feng Wang, and Kuai Xu, Modeling Information Diffusion in Online Social Networks with Partial Differential Equations (201310).
- N. N. Janenko, Implicit difference methods for the higher-dimensional heat equation, Izv. Vysš. Učebn. Zaved. Matematika 1961 (1961), no. 4 (23), 148–157 (Russian). MR 0152145
- Mingqiang Zhu and Tony Chan, An efficient primal-dual hybrid gradient algorithm for total variation image restoration, 2008.
- Mingqiang Zhu, Stephen J. Wright, and Tony F. Chan, Duality-based algorithms for total-variation-regularized image restoration, Comput. Optim. Appl. 47 (2010), no. 3, 377–400. MR 2746365, DOI https://doi.org/10.1007/s10589-008-9225-2
- Dominique Zosso, Braxton Osting, Mandy Xia, and Stanley J. Osher, An efficient primal-dual method for the obstacle problem, J. Sci. Comput. 73 (2017), no. 1, 416–437. MR 3704858, DOI https://doi.org/10.1007/s10915-017-0420-0
Similar Articles
Retrieve articles in Quarterly of Applied Mathematics
with MSC (2010):
65K10,
65N06,
49Q05,
35J20
Retrieve articles in all journals
with MSC (2010):
65K10,
65N06,
49Q05,
35J20
Additional Information
Dominique Zosso
Affiliation:
Department of Mathematical Sciences, Montana State University, Bozeman, Montana 59717-2400
MR Author ID:
939733
ORCID:
0000-0001-5685-4273
Email:
dominique.zosso@montana.edu
Braxton Osting
Affiliation:
Department of Mathematics, University of Utah, Salt Lake City, Utah 84112
MR Author ID:
876194
ORCID:
0000-0002-4123-9048
Email:
osting@math.utah.edu
Keywords:
Elliptic PDE,
convex optimization,
primal-dual hybrid gradients,
momentum method.
Received by editor(s):
March 9, 2020
Received by editor(s) in revised form:
May 27, 2020
Published electronically:
October 6, 2020
Additional Notes:
This work was supported by NSF DMS-1461138, UC Lab Fees Grant, the W. M. Keck Foundation, and a Simons Collaboration Grant for Mathematicians.
Article copyright:
© Copyright 2020
Brown University
