×

Optimal-order preconditioners for linear systems arising in the semismooth Newton solution of a class of control-constrained problems. (English) Zbl 1348.65100

Summary: In this paper we present a new multigrid preconditioner for the linear systems arising in the semismooth Newton method solution of certain control-constrained, quadratic distributed optimal control problems. Using a piecewise constant discretization of the control space, each semismooth Newton iteration essentially requires inverting a principal submatrix of the matrix entering the normal equations of the associated unconstrained optimal control problem, the rows (and columns) of the submatrix representing the constraints deemed inactive at the current iteration. Previously developed multigrid preconditioners for the aforementioned submatrices were based on constructing a sequence of conforming coarser spaces and proved to be of suboptimal quality for the class of problems considered. Instead, the multigrid preconditioner introduced in this work uses nonconforming coarse spaces, and it is shown that, under reasonable geometric assumptions on the constraints that are deemed inactive, the preconditioner approximates the inverse of the desired submatrix to optimal order. The preconditioner is tested numerically on a classical elliptic-constrained optimal control problem and further on a constrained image-deblurring problem.

MSC:

65K10 Numerical optimization and variational techniques
49M15 Newton-type methods
49J20 Existence theories for optimal control problems involving partial differential equations
49M27 Decomposition methods
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] S. Beuchler, C. Pechstein, and D. Wachsmuth, {\it Boundary concentrated finite elements for optimal boundary control problems of elliptic PDEs}, Comput. Optim. Appl., 51 (2012), pp. 883-908. · Zbl 1257.49027
[2] G. Biros and G. Doǧan, {\it A multilevel algorithm for inverse problems with elliptic PDE constraints}, Inverse Problems, 24 (2008), 034010. · Zbl 1187.35273
[3] A. Borz\`\i and K. Kunisch, {\it A multigrid scheme for elliptic constrained optimal control problems}, Comput. Optim. Appl., 31 (2005), pp. 309-333. · Zbl 1081.49022
[4] A. Borzi and V. Schulz, {\it Multigrid methods for PDE optimization}, SIAM Rev., 51 (2009), pp. 361-395, http://dx.doi.org/10.1137/060671590 doi:10.1137/060671590. · Zbl 1167.35354
[5] D. Braess, {\it Finite Elements: Theory, Fast Solvers, and Applications in Elasticity Theory}, 3rd ed., translated from the German by Larry L. Schumaker, Cambridge University Press, Cambridge, UK, 2007. · Zbl 1180.65146
[6] S. C. Brenner and L. R. Scott, {\it The Mathematical Theory of Finite Element Methods}, 3rd ed., Texts in Appl. Math. 15, Springer, New York, 2008. · Zbl 1135.65042
[7] A. Drăgănescu, {\it Multigrid preconditioning of linear systems for semi-smooth Newton methods applied to optimization problems constrained by smoothing operators}, Optim. Methods Softw., 29 (2014), pp. 786-818, http://dx.doi.org/10.1080/10556788.2013.854356 doi:10.1080/10556788.2013.854356. · Zbl 1308.65104
[8] A. Drăgănescu and T. F. Dupont, {\it Optimal order multilevel preconditioners for regularized ill-posed problems}, Math. Comp., 77 (2008), pp. 2001-2038. · Zbl 1198.65188
[9] A. Drăgănescu and A. M. Soane, {\it Multigrid solution of a distributed optimal control problem constrained by the Stokes equations}, Appl. Math. Comput., 219 (2013), pp. 5622-5634. · Zbl 1280.49045
[10] A. Drăgănescu and C. Petra, {\it Multigrid preconditioning of linear systems for interior point methods applied to a class of box-constrained optimal control problems}, SIAM J. Numer. Anal., 50 (2012), pp. 328-353, http://dx.doi.org/10.1137/100786502 doi:10.1137/100786502. · Zbl 1247.65081
[11] M. Hanke and C. R. Vogel, {\it Two-level preconditioners for regularized inverse problems. I. Theory}, Numer. Math., 83 (1999), pp. 385-402. · Zbl 0941.65056
[12] R. Herzog and E. Sachs, {\it Preconditioned conjugate gradient method for optimal control problems with control and state constraints}, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2291-2317, http://dx.doi.org/10.1137/090779127 doi:10.1137/090779127. · Zbl 1209.49038
[13] M. Hintermüller, K. Ito, and K. Kunisch, {\it The primal-dual active set strategy as a semismooth Newton method}, SIAM J. Optim., 13 (2002), pp. 865-888, http://dx.doi.org/10.1137/S1052623401383558 doi:10.1137/S1052623401383558. · Zbl 1080.90074
[14] M. Hintermüller and M. Ulbrich, {\it A mesh-independence result for semismooth Newton methods}, Math. Program., 101 (2004), pp. 151-184. · Zbl 1079.65065
[15] R. H. W. Hoppe and R. Kornhuber, {\it Adaptive multilevel methods for obstacle problems}, SIAM J. Numer. Anal., 31 (1994), pp. 301-323, http://dx.doi.org/10.1137/0731016 doi:10.1137/0731016. · Zbl 0806.65064
[16] B. Kaltenbacher, {\it V-cycle convergence of some multigrid methods for ill-posed problems}, Math. Comp., 72 (2003), pp. 1711-1730. · Zbl 1035.65056
[17] J. T. King, {\it Multilevel algorithms for ill-posed problems}, Numer. Math., 61 (1992), pp. 311-334. · Zbl 0768.65091
[18] O. Lass, M. Vallejos, A. Borzi, and C. C. Douglas, {\it Implementation and analysis of multigrid schemes with finite elements for elliptic optimal control problems}, Computing, 84 (2009), pp. 27-48. · Zbl 1162.65360
[19] M. Porcelli, V. Simoncini, and M. Tani, {\it Preconditioning of active-set Newton methods for PDE-constrained optimal control problems}, SIAM J. Sci. Comput., 37 (2015), pp. S472-S502, http://dx.doi.org/10.1137/140975711 doi:10.1137/140975711. · Zbl 1325.65066
[20] A. Rieder, {\it A wavelet multilevel method for ill-posed problems stabilized by Tikhonov regularization}, Numer. Math., 75 (1997), pp. 501-522. · Zbl 0878.65039
[21] W. Rudin, {\it Functional Analysis}, 2nd ed., International Series in Pure and Applied Mathematics, McGraw-Hill, New York, 1991. · Zbl 0867.46001
[22] J. Schöberl, R. Simon, and W. Zulehner, {\it A robust multigrid method for elliptic optimal control problems}, SIAM J. Numer. Anal., 49 (2011), pp. 1482-1503, http://dx.doi.org/10.1137/100783285 doi:10.1137/100783285. · Zbl 1230.65072
[23] S. Takacs and W. Zulehner, {\it Convergence analysis of multigrid methods with collective point smoothers for optimal control problems}, Comput. Vis. Sci., 14 (2011), pp. 131-141. · Zbl 1250.65086
[24] S. Takacs and W. Zulehner, {\it Convergence analysis of all-at-once multigrid methods for elliptic control problems under partial elliptic regularity}, SIAM J. Numer. Anal., 51 (2013), pp. 1853-1874, http://dx.doi.org/10.1137/120880884 doi:10.1137/120880884. · Zbl 1281.65096
[25] M. Ulbrich, {\it Semismooth Newton Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces}, MOS-SIAM Ser. Optim. 11, SIAM, Philadelphia, 2011. · Zbl 1235.49001
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.