Previous Articles    

ERROR ESTIMATES FOR SPARSE OPTIMAL CONTROL PROBLEMS BY PIECEWISE LINEAR FINITE ELEMENT APPROXIMATION

Xiaoliang Song1, Bo Chen2, Bo Yu3   

  1. 1. Dalian University of Technology, Dalian 116024, China;
    2. Department of Mathematics, National University of Singapore, 10 Lower Kent Ridge Road, Singapore;
    3. School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China
  • Received:2017-09-04 Revised:2017-09-04 Online:2021-05-15 Published:2021-04-12
  • Contact: Bo Yu,Email:yubo@dlut.edu.cn
  • Supported by:
    The authors would like to thank Prof. Defeng Sun at The Hong Kong Polytechnic University and Prof. Kim-Chuan Toh at National University of Singapore for their valuable suggestions that led to improvement in this paper.

Xiaoliang Song, Bo Chen, Bo Yu. ERROR ESTIMATES FOR SPARSE OPTIMAL CONTROL PROBLEMS BY PIECEWISE LINEAR FINITE ELEMENT APPROXIMATION[J]. Journal of Computational Mathematics, 2021, 39(3): 471-492.

Optimization problems with L1-control cost functional subject to an elliptic partial differential equation (PDE) are considered. However, different from the finite dimensional l1-regularization optimization, the resulting discretized L1-norm does not have a decoupled form when the standard piecewise linear finite element is employed to discretize the continuous problem. A common approach to overcome this difficulty is employing a nodal quadrature formula to approximately discretize the L1-norm. In this paper, a new discretized scheme for the L1-norm is presented. Compared to the new discretized scheme for L1-norm with the nodal quadrature formula, the advantages of our new discretized scheme can be demonstrated in terms of the order of approximation. Moreover, finite element error estimates results for the primal problem with the new discretized scheme for the L1-norm are provided, which confirms that this approximation scheme will not change the order of error estimates. To solve the new discretized problem, a symmetric Gauss-Seidel based majorized accelerated block coordinate descent(sGS-mABCD) method is introduced to solve it via its dual. The proposed sGS-mABCD algorithm is illustrated at two numerical examples. Numerical results not only confirm the finite element error estimates, but also show that our proposed algorithm is efficient.

CLC Number: 

[1] G. Stadler, Elliptic optimal control problems with L1-control cost and applications for the placement of control devices. Comp. Optim. Appls., 44(2009), 159-181.
[2] G. Wachsmuth and D. Wachsmuth, Convergence and regularisation results for optimal control problems with sparsity functional. ESAIM Control Optim. Calc. Var., 17(2011), 858-886.
[3] E. Casas, R. Herzog, G. Wachsmuth, Approximation of sparse controls in semilinear equations by piecewise linear functions. Numer. Math., 122(2012), 645-669.
[4] E. Casas, R. Herzog, G, Wachsmuth, Optimality conditions and error analysis of semilinear elliptic control problems with L1 cost functional. SIAM J. Optim., 22(2012), 795-820.
[5] M. Ulbrich, Nonsmooth Newton-like methods for variational inequalities and constrained optimization problems in function spaces. Habilitation thesis, Fakultät für Mathematik, Technische Universität München, 2002.
[6] M. Ulbrich, Semismooth Newton methods for operator equations in function spaces. SIAM J. Optim., 13(2003), 805-842.
[7] M. Hinze, R. Pinnau, M. Ulbrich, S. Ulbrich, Optimization with PDE Constraints. Springer Science and Business Media, 23(2008).
[8] T. Blumensath, M.E. Davies, Iterative Thresholding for Sparse Approximations. J. Fourier Anal. Appl., 14(2008), 629-654.
[9] K. Jiang, D.F. Sun, K.C. Toh, An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP. SIAM J. Optim., 22(2012), 1042-1064.
[10] A. Beck, M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci., 2(2009), 183-202.
[11] K.C. Toh, S. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Pac. J. Optim., 6(2010), 615-640.
[12] M. Fazel, T.K. Pong, D.F. Sun, P. Tseng, Hankel matrix rank minimization with applications to system identification and realization. SIAM J. Matrix Anal. Appl., 34(2013), 946-977.
[13] Q. Fan, Y.L. Jiao and X.L. Lu, A primal dual active set algorithm with continuation for compressed sensing, IEEE Trans. Signal Process., 62:(2014), 6276-6285.
[14] L. Chen, D.F. Sun, K.C. Toh, An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming. Math. Program., (2015), 1-34.
[15] Y.L. Jiao, B. Jin and X.L. Lu, A primal dual active set with continuation algorithm for the l0-regularized optimization problem, Appl. Comput. Harmon. Anal., 39(2015), 400-426.
[16] X.D. Li, D.F. Sun, K.C. Toh, A Schur complement based semi-proximal ADMM for con-vex quadratic conic programming and extensions. Math. Program., 155(2016), 333-373.
[17] X.L. Song, B. Yu, Y.Y. Wang, X.Z. Zhang, An inexact heterogeneous ADMM algorithm for elliptic optimal control problems with L1-control cost.arXiv preprint arXiv:1610.00306, 2016.
[18] A. Schindele, A. Borzì, Proximal methods for elliptic optimal control problems with sparsity cost functional. Appl. Math., 7(2016), 967-992.
[19] X.L. Song, B. Chen, B. Yu, An efficient duality-based approach for PDE-constrained sparse optimization. Comput Optim Appl., 69(2018), 461-500.
[20] X. L. Song, B. Chen, B. Yu:Mesh Independence of an Accelerated Block Coordinate Descent Method for Sparse Optimal Control Problems, arXiv:1610.00308, 2017.
[21] Y. Cui, Large scale composite optimization problems with coupled objective functions:theory, algorithms and applications. PhD thesis, National University of Singapore, 2016.
[22] X.D. Li, D.F. Sun, K.C. Toh, A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications. arXiv:1703.06629, 2017
[23] A.J. Wathen, Realistic eigenvalue bounds for the Galerkin mass matrix. IMA J. Numer. Anal., 7(1987), 449-457.
[24] P.G. Ciarlet, The finite element method for elliptic problems. Society for Industrial and Applied Mathematics, 2002.
[25] H.C. Elman, D.J. Silvester and A.J. Wathen, Finite elements and fast iterative solvers:with applications in incompressible fluid dynamics. Oxford University Press (UK), 2014.
[26] C. Carstensen, Quasi-interpolation and a posteriori error analysis in finite element methods. ESAIM:Math. Model. Numer. Anal., 33(1999), 1187-1202.
[27] D. Kinderlehrer and G. Stampacchia, An introduction to variational inequalities and their applications, vol. 31, Siam, 1980.
[1] Kaibo Hu, Ragnar Winther. WELL-CONDITIONED FRAMES FOR HIGH ORDER FINITE ELEMENT METHODS [J]. Journal of Computational Mathematics, 2021, 39(3): 333-357.
[2] Xiaodi Zhang, Weiying Zheng. MONOLITHIC MULTIGRID FOR REDUCED MAGNETOHYDRODYNAMIC EQUATIONS [J]. Journal of Computational Mathematics, 2021, 39(3): 453-470.
[3] Xiaocui Li, Xu You. MIXED FINITE ELEMENT METHODS FOR FRACTIONAL NAVIER-STOKES EQUATIONS [J]. Journal of Computational Mathematics, 2021, 39(1): 130-146.
[4] Michael Holst, Yuwen Li, Adam Mihalik, Ryan Szypowski. CONVERGENCE AND OPTIMALITY OF ADAPTIVE MIXED METHODS FOR POISSON'S EQUATION IN THE FEEC FRAMEWORK [J]. Journal of Computational Mathematics, 2020, 38(5): 748-767.
[5] Qilong Zhai, Xiaozhe Hu, Ran Zhang. THE SHIFTED-INVERSE POWER WEAK GALERKIN METHOD FOR EIGENVALUE PROBLEMS [J]. Journal of Computational Mathematics, 2020, 38(4): 606-623.
[6] Weifeng Zhang, Shuo Zhang. ORDER REDUCED METHODS FOR QUAD-CURL EQUATIONS WITH NAVIER TYPE BOUNDARY CONDITIONS [J]. Journal of Computational Mathematics, 2020, 38(4): 565-579.
[7] Juncai He, Lin Li, Jinchao Xu, Chunyue Zheng. RELU DEEP NEURAL NETWORKS AND LINEAR FINITE ELEMENTS [J]. Journal of Computational Mathematics, 2020, 38(3): 502-527.
[8] Jie Chen, Zhengkang He, Shuyu Sun, Shimin Guo, Zhangxin Chen. EFFICIENT LINEAR SCHEMES WITH UNCONDITIONAL ENERGY STABILITY FOR THE PHASE FIELD MODEL OF SOLID-STATE DEWETTING PROBLEMS [J]. Journal of Computational Mathematics, 2020, 38(3): 452-468.
[9] Li Cai, Ye Sun, Feifei Jing, Yiqiang Li, Xiaoqin Shen, Yufeng Nie. A FULLY DISCRETE IMPLICIT-EXPLICIT FINITE ELEMENT METHOD FOR SOLVING THE FITZHUGH-NAGUMO MODEL [J]. Journal of Computational Mathematics, 2020, 38(3): 469-486.
[10] Huoyuan Duan, Roger C. E. Tan. ERROR ANALYSIS OF A STABILIZED FINITE ELEMENT METHOD FOR THE GENERALIZED STOKES PROBLEM [J]. Journal of Computational Mathematics, 2020, 38(2): 254-290.
[11] Nikolaus von Daniels, Michael Hinze. VARIATIONAL DISCRETIZATION OF A CONTROL-CONSTRAINED PARABOLIC BANG-BANG OPTIMAL CONTROL PROBLEM [J]. Journal of Computational Mathematics, 2020, 38(1): 14-40.
[12] Carsten Carstensen, Sophie Puttkammer. HOW TO PROVE THE DISCRETE RELIABILITY FOR NONCONFORMING FINITE ELEMENT METHODS [J]. Journal of Computational Mathematics, 2020, 38(1): 142-175.
[13] Yu Du, Haijun Wu, Zhimin Zhang. SUPERCONVERGENCE ANALYSIS OF THE POLYNOMIAL PRESERVING RECOVERY FOR ELLIPTIC PROBLEMS WITH ROBIN BOUNDARY CONDITIONS [J]. Journal of Computational Mathematics, 2020, 38(1): 223-238.
[14] Weijie Huang, Zhiping Li. A MIXED FINITE ELEMENT METHOD FOR MULTI-CAVITY COMPUTATION IN INCOMPRESSIBLE NONLINEAR ELASTICITY [J]. Journal of Computational Mathematics, 2019, 37(5): 609-628.
[15] Li Guo, Hengguang Li, Yang Yang. INTERIOR ESTIMATES OF SEMIDISCRETE FINITE ELEMENT METHODS FOR PARABOLIC PROBLEMS WITH DISTRIBUTIONAL DATA [J]. Journal of Computational Mathematics, 2019, 37(4): 458-474.
Viewed
Full text


Abstract