×

zbMATH — the first resource for mathematics

A multi-level ADMM algorithm for elliptic PDE-constrained optimization problems. (English) Zbl 07351826
Summary: In this paper, elliptic PDE-constrained optimization problems with box constraints on the control are considered. To numerically solve the problems, we apply the ‘optimize-discretize-optimize’ strategy. Specifically, the alternating direction method of multipliers (ADMM) algorithm is applied in function space first, and then, the standard piecewise linear finite-element approach is employed to discretize the subproblems in each iteration. Finally, some efficient numerical methods are applied to solve the discretized subproblems based on their structures. Motivated by the idea of the multi-level strategy, instead of fixing the mesh size before the computation process, we propose the strategy of gradually refining the grid. Moreover, the subproblems in each iteration are solved by appropriate inexact methods. Based on the strategies above, an efficient convergent multi-level ADMM (mADMM) algorithm is proposed. We present the convergence analysis and the iteration complexity results \(o(1/k)\) for the mADMM algorithm. Some numerical experiments are done and the numerical results show the high efficiency of the mADMM algorithm.
MSC:
65Nxx Numerical methods for partial differential equations, boundary value problems
49-XX Calculus of variations and optimal control; optimization
Software:
NewtonLib; iFEM; QSDPNAL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bai, Z.; Benzi, M.; Chen, F.; Wang, Z., Preconditioned MHSS iteration methods for a class of block two-by-two linear systems with applications to distributed control problems, IMA J Numer Anal, 33, 1, 343-369 (2013) · Zbl 1271.65100
[2] Brandt, A., Multi-level adaptive solutions to boundary-value problems, Math Comp, 31, 138, 333-390 (1977) · Zbl 0373.65054
[3] Casas E, Tröltzsch F (2002) Error estimates for linear-quadratic elliptic control problems. International Worksing Conference on Analysis and Optimization of Differential Systems. DBLP
[4] Chen L (2009) iFEM: An integrated finite element methods package in MATLAB. Technical Report. University of California at Irvine, Irvine
[5] Chen, Z.; Song, X.; Zhang, X.; Yu, B., A FE-ADMM algorithm for Lavrentiev-regularized state-constrained elliptic control problem, ESAIM Control Optim Calc Var, 25, 5 (2019) · Zbl 1437.49003
[6] Chen, L.; Sun, D.; Toh, KC, An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming, Math Program, 161, 1-2, 237-270 (2017) · Zbl 1356.90105
[7] Ciarlet PG (2002) The Finite Element Method for Elliptic Problems. Volume 40 of Classics in Applied Mathematics. Society for Industrial and Applied Mathematics, Philadelphia · Zbl 0999.65129
[8] Deuflhard, P., Newton methods for nonlinear problems: affine invariance and adaptive algorithms (2011), Berlin: Springer, Berlin · Zbl 1226.65043
[9] Ern, A.; Guermond, JL, Theory and practice of finite elements (2004), New York: Springer, New York
[10] Fazel, M.; Pong, TK; Sun, D.; Tseng, P., Hankel matrix rank minimization with applications to system identification and realization, SIAM J Matrix Anal Appl, 34, 3, 946-977 (2013) · Zbl 1302.90127
[11] Fortin M, Glowinski R (1983) On decomposition-coordination methods using an augmented Lagrangian. Augmented Lagrangian Methods: Applications to the Solution of Boundary Problems. Elsevier, Amsterdam · Zbl 0525.65045
[12] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput Math Appl, 2, 17-40 (1976) · Zbl 0352.65034
[13] Glowinski, R., Lectures on numerical methods for nonlinear variational problems (1980), Berlin: Springer, Berlin · Zbl 0456.65035
[14] Glowinski, R.; Marroco, A., 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, Analyse Numérique, 9, R2, 41-76 (1975) · Zbl 0368.65053
[15] Hackbusch, W., On the multi-grid method applied to difference equations, Computing, 20, 4, 291-306 (1978) · Zbl 0391.65045
[16] Hackbusch, W., Multi-grid methods and applications (1985), Berlin: Springer, Berlin · Zbl 0585.65030
[17] Han, D.; Sun, D.; Zhang, L., Linear rate convergence of the alternating direction method of multipliers for convex composite programming, Math Oper Res, 43, 2, 622-637 (2017) · Zbl 1440.90047
[18] Hinze, M.; Meyer, C., Variational discretization of Lavrentiev-regularized state constrained elliptic optimal control problems, Comput Optim Appl, 46, 3, 487-510 (2010) · Zbl 1207.49037
[19] Hinze, M.; Vierling, M., The semi-smooth Newton method for variationally discretized control constrained elliptic optimal control problems; implementation, convergence and globalization, Optim Methods Softw, 27, 6, 933-950 (2012) · Zbl 1244.49050
[20] Hinze, M.; Pinnau, R.; Ulbrich, M.; Ulbrich, S., Optimization with PDE constraints (2009), Berlin: Springer, Berlin · Zbl 1167.49001
[21] Kinderlehrer, D.; Stampacchia, G., an introduction to variational inequalities and their applications (1980), New York: Academic Press, New York · Zbl 0457.35001
[22] Li, X.; Sun, D.; Toh, KC, A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions, Math Program, 155, 1-2, 333-373 (2016) · Zbl 1342.90134
[23] Li, X.; Sun, D.; Toh, KC, QSDPNAL: A two-phase Newton-CG proximal augmented Lagrangian method for convex quadratic semidefinite programming problems, Math Program Comput, 10, 703-743 (2018) · Zbl 1411.90213
[24] Li, J.; Wang, X.; Zhang, K., An efficient alternating direction method of multipliers for optimal control problems constrained by random Helmholtz equations, Numer Algorith, 78, 1, 161-191 (2018) · Zbl 1388.93110
[25] Saad, Y.; Schultz, MH, GMRES: Ageneralized minimum residual algorithm for solving nonsymmetric linear systems, SIAM J Sci Stat Comput, 7, 3, 856-869 (1986) · Zbl 0599.65018
[26] Song X (2018) Some alternating direction iteration methods for solving PDE-constrained optimization problems. PhD thesis, Dalian University of Technology, Dalian
[27] Song, X.; Yu, B., A two phase strategy for control constrained elliptic optimal control problems, Numer Linear Algebra Appl, 25, e2138 (2018) · Zbl 06945798
[28] Song, X.; Yu, B.; Zhang, X.; Wang, Y., A FE-inexact heterogeneous ADMM algorithm for elliptic optimal control problems with \(L^1\)-control cost, J Syst Sci Complex, 31, 6, 1659-1697 (2017) · Zbl 1406.49021
[29] Sun, D.; Toh, KC; Yang, L., A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints, SIAM J Optim, 25, 2, 882-915 (2015) · Zbl 1328.90083
[30] Yang L, Li J, Sun D, Toh KC (2018) A fast globally linearly convergent algorithm for the computation of Wasserstein Barycenters. arXiv preprint arXiv:1809.04249
[31] Zhang, K.; Li, J.; Song, Y.; Wang, X., An alternating direction method of multipliers for elliptic equation constrained optimization problem, Sci China Math, 60, 2, 361-378 (2017) · Zbl 1365.90246
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.