Primal-dual gap estimators for a posteriori error analysis of nonsmooth minimization problems

Bartels, Sören; Milicevic, Marijo

ESAIM: Mathematical Modelling and Numerical Analysis , Tome 54 (2020) no. 5, pp. 1635-1660.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

The primal-dual gap is a natural upper bound for the energy error and, for uniformly convex minimization problems, also for the error in the energy norm. This feature can be used to construct reliable primal-dual gap error estimators for which the constant in the reliability estimate equals one for the energy error and equals the uniform convexity constant for the error in the energy norm. In particular, it defines a reliable upper bound for any functions that are feasible for the primal and the associated dual problem. The abstract a posteriori error estimate based on the primal-dual gap is provided in this article, and the abstract theory is applied to the nonlinear Laplace problem and the Rudin–Osher–Fatemi image denoising problem. The discretization of the primal and dual problems with conforming, low-order finite element spaces is addressed. The primal-dual gap error estimator is used to define an adaptive finite element scheme and numerical experiments are presented, which illustrate the accurate, local mesh refinement in a neighborhood of the singularities, the reliability of the primal-dual gap error estimator and the moderate overestimation of the error.

[1] M. Ainsworth and J.T. Oden, A posteriori error estimation in finite element analysis. Comput. Methods Appl. Mech. Eng. 142 (1997) 1–88. | DOI | MR | Zbl

[2] C. Atkinson and C.R. Champion, Some boundary-value problems for the equation ${(\nabla .(\left|\nabla \phi \right|}^N\nabla \phi )=0)$. Q. J. Mech. Appl. Math. 37 (1984) 401–419. | DOI | MR | Zbl

[3] C. Atkinson and C.W. Jones, Similarity solutions in some nonlinear diffusion problems and in boundary-layer flow of a pseudo plastic fluid. Q. J. Mech. Appl. Math. 27 (1974) 193–211. | DOI | Zbl

[4] G. Aubert and P. Kornprobst, Mathematical problems in image processing, 2nd edition. In: Vol. 147 of Applied Mathematical Sciences. Springer (2006). | DOI | MR | Zbl

[5] I. Babuška and W.C. Rheinboldt, Error estimates for adaptive finite element computations. SIAM J. Numer. Anal. 15 (1978) 736–754. | DOI | MR | Zbl

[6] J. Baranger and K. Najib, Numerical analysis of quasi-newtonian flow obeying the power low or the carreau flow. Numer. Math. 58 (1990) 35–49. | MR | Zbl

[7] J.W. Barrett and W.B. Liu, Finite element approximation of the $p$-Laplacian. Math. Comput. 61 (1993) 523–537. | MR | Zbl

[8] S. Bartels, Error control and adaptivity for a variational model problem defined on functions of bounded variation. Math. Comput. 84 (2015) 1217–1240. | DOI | MR

[9] S. Bartels, Numerical methods for nonlinear partial differential equations. In: Vol. 47 of Springer Series in Computational Mathematics. Springer (2015). | DOI | MR | Zbl

[10] S. Bartels, M. Milicevic, Alternating direction method of multipliers with variable step sizes Preprint (2017). | arXiv

[11] S. Bartels, P. Schön, Adaptive approximation of the monge-kantorovich problem via primal-dual gap estimates, ESAIM: M2AN 51 (2017) 2237–2261. | DOI | Numdam | MR

[12] S. Bartels, R.H. Nochetto and A.J. Salgado, Discrete total variation flows without regularization. SIAM J. Numer. Anal. 52 (2014) 363–385. | DOI | MR | Zbl

[13] L. Belenki, L. Diening and C. Kreuzer, Optimality of an adaptive finite element method for the $p$-Laplacian equation. IMA J. Numer. Anal. 32 (2012) 484–510. | DOI | MR | Zbl

[14] D. Boffi, F. Brezzi and M. Fortin, Mixed finite element methods and applications. In: Vol. 44 of Springer Series in Computational Mathematics. Springer (2013). | MR | Zbl

[15] S.C. Brenner and L.R. Scott, The mathematical theory of finite element methods, 3rd edition. In: Vol. 15 of Texts in Applied Mathematics. Springer (2008). | DOI | MR | Zbl

[16] C. Carstensen and R. Klose, A posteriori finite element error control for the $p$-Laplace problem. SIAM J. Sci. Comput. 25 (2003) 792–814. | DOI | MR | Zbl

[17] C. Carstensen, W.B. Liu and N.N. Yan, A posteriori FE error control for $p$-Laplacian by gradient recovery in quasi-norm. Math. Comput. 75 (2006) 1599–1616. | DOI | MR | Zbl

[18] S.-S. Chow, Finite element error estimates for non-linear elliptic equations of monotone type. Numer. Math. 54 (1989) 373–393. | DOI | MR | Zbl

[19] P.G. Ciarlet, The Finite Element Method for Elliptic Problems. Society for Industrial and Applied Mathematics (2002). | DOI | MR

[20] L. Diening and M. Růžička, Interpolation operators in orlicz–sobolev spaces. Numer. Math. 107 (2007) 107–129. | DOI | MR | Zbl

[21] L. Diening and C. Kreuzer, Linear convergence of an adaptive finite element method for the $p$-Laplacian equation. SIAM J. Numer. Anal. 46 (2008) 614–638. | DOI | MR | Zbl

[22] C. Ebmeyer, Nonlinear elliptic problems with $p$-structure under mixed boundary value conditions in polyhedral domains. Adv. Differ. Equ. 6 (2001) 873–895. | MR | Zbl

[23] C. Ebmeyer, Mixed boundary value problems for nonlinear elliptic systems with $p$-structure in polyhedral domains. Math. Nachr. 236 (2002) 91–108. | DOI | MR | Zbl

[24] C. Ebmeyer, Global regularity in Sobolev spaces for elliptic problems with $p$-structure on bounded domains, edited by J.F. Rodrigues, G. Seregin, J.M. Urbano. in: Trends in Partial Differential Equations of Mathematical Physics. Birkhäuser Basel, Basel (2005) 81–89. | DOI | MR | Zbl

[25] C. Ebmeyer, W.B. Liu, Quasi-norm interpolation error estimates for the piecewise linear finite element approximation of $p$-Laplacian problems. Numer. Math. 100 (2005) 233–258. | DOI | MR | Zbl

[26] C. Ebmeyer, W.B. Liu and M. Steinhauer, Global regularity in fractional order sobolev spaces for the $p$-Laplace equation on polyhedral domains. Z. Anal. Anwend. 24 (2005) 353–374. | DOI | MR | Zbl

[27] I. Ekeland and R. Témam, Convex Analysis and Variational Problems. Society for Industrial and Applied Mathematics (1999). | DOI | MR | Zbl

[28] L. El Alaoui, A. Ern and M. Vohralk, Guaranteed and robust a posteriori error estimates and balancing discretization and linearization errors for monotone nonlinear problems. Special Issue on Modeling Error Estimation and Adaptive Modeling. Comput. Methods Appl. Mech. Eng. 200 (2011) 2782–2795. | DOI | MR | Zbl

[29] A. Ern and M. Vohralk, Adaptive inexact newton methods with a posteriori stopping criteria for nonlinear diffusion PDEs. SIAM J. Sci. Comput. 35 (2013) A1761–A1791. | DOI | MR | Zbl

[30] D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. App. 2 (1976) 17–40. | Zbl

[31] R. Glowinski and A. Marroco, Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de Dirichlet non linéaires. RAIRO Anal. Numer. 9 (1975) 41–76. | Numdam | MR | Zbl

[32] M. Hintermüller and M. Rincon-Camacho, An adaptive finite element method in $L^2$-TV-based image denoising. Inverse Prob. Imaging 8 (2014) 685–711. | DOI | MR | Zbl

[33] K. Kunisch and M. Hintermüller, Total bounded variation regularization as a bilaterally constrained optimization problem. SIAM J. Appl. Math. 64 (2004) 1311–1333. | DOI | MR | Zbl

[34] W.B. Liu and J.W. Barrett, A further remark on the regularity of the solutions of the $p$-Laplacian and its applications to their finite element approximation. Nonlinear Anal. Theory Methods Appl. 21 (1993) 379–387. | DOI | MR | Zbl

[35] W.B. Liu and J.W. Barrett, A remark on the regularity of the solutions of the $p$-Laplacian and its application to their finite element approximation. J. Math. Anal. App. 178 (1993) 470–487. | DOI | MR | Zbl

[36] W.B. Liu and N.N. Yan, Quasi-norm a priori and a posteriori error estimates for the nonconforming approximation of $p$-Laplacian. Numer. Math. 89 (2001) 341–378. | DOI | MR | Zbl

[37] W.B. Liu and N.N. Yan, Quasi-norm local error estimators for $p$-Laplacian. SIAM J. Numer. Anal. 39 (2001) 100–127. | DOI | MR | Zbl

[38] W.B. Liu and N.N. Yan, On quasi-norm interpolation error estimation and a posteriori error estimates for $p$-Laplacian. SIAM J. Numer. Anal. 40 (2002) 1870–1895. | DOI | MR | Zbl

[39] M. Milicevic, Finite element discretization and iterative solution of total variation regularized minimization problems and application to the simulation of rate-independent damage evolutions. Ph.D. thesis, Albert-Ludwigs-Universität Freiburg (2019).

[40] R.H. Nochetto, K.G. Siebert and A. Veeser, Theory of adaptive finite element methods: an introduction, edited by R. Devore and A. Kunoth. In: Multiscale, Nonlinear and Adaptive Approximation. Springer, Berlin Heidelberg, Berlin, Heidelberg (2009) 409–542. | DOI | Zbl

[41] J.R. Philip, $n$-diffusion. Aust. J. Phys. 14 (1961) 1–13. | DOI | MR | Zbl

[42] S.I. Repin, A posteriori error estimates for approximate solutions to variational problems with strongly convex functionals. J. Math. Sci. 97 (1999) 4311–4328. | DOI | MR

[43] S.I. Repin, A posteriori error estimates for approximate solutions of variational problems with functionals of power growth. J. Math. Sci. 101 (2000) 3531–3538. | DOI | MR | Zbl

[44] S.I. Repin, A posteriori error estimation for nonlinear variational problems by duality theory. J. Math. Sci. 99 (2000) 927–935. | DOI | MR | Zbl

[45] S.I. Repin, A posteriori error estimation for variational problems with uniformly convex functionals. Math. Comput. 69 (2000) 481–500. | DOI | MR | Zbl

[46] S.I. Repin and L.S. Xanthis, A posteriori error estimation for elasto-plastic problems based on duality theory. Comput. Methods Appl. Mech. Eng. 138 (1996) 317–339. | DOI | MR | Zbl

[47] S.I. Repin and L.S. Xanthis, A posteriori error estimation for nonlinear variational problems. C.R. Acad. Sci. – Ser. I Math. 324 (1997) 1169–1174. | MR | Zbl

[48] L.I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms. Phys. D: Nonlinear Phenom. 60 (1992) 259–268. | DOI | MR | Zbl

[49] R. Stevenson, Optimality of a standard adaptive finite element method. Found. Comput. Math. 7 (2007) 245–269. | DOI | MR | Zbl

[50] M. Thomas, Quasistatic damage evolution with spatial BV-regularization. Discrete Contin. Dyn. Syst. – S 6 (2013) 235–255. | MR | Zbl

[51] A. Veeser, Convergent adaptive finite elements for the nonlinear Laplacian. Numer. Math. 92 (2002) 743–770. | DOI | MR | Zbl

[52] R. Verfürth, A Posteriori Error Estimation Techniques for Finite Element Methods. Oxford University Press (2013). | DOI | MR | Zbl