×

An efficient duality-based approach for PDE-constrained sparse optimization. (English) Zbl 1388.49037

Summary: In this paper, Elliptic Optimal Control Problems (EOCP) involving the \(L^1\)-control cost (\(L^1\)-EOCP) is considered. To numerically discretize \(L^1\)-EOCP, the standard piecewise linear finite element is employed. However, different from the finite dimensional \(l^1\)-regularization optimization, the resulting discrete \(L^1\)-norm does not have a decoupled form. A common approach to overcome this difficulty is employing a nodal quadrature formula to approximately discretize the \(L^1\)-norm. It is clear that this technique will incur an additional error. To avoid the additional error, solving \(L^1\)-EOCP via its dual, which can be reformulated as a multi-block unconstrained convex composite minimization problem, is considered. Motivated by the success of the Accelerated Block Coordinate Descent (ABCD) method for solving large scale convex minimization problems in finite dimensional space, we consider extending this method to \(L^1\)-EOCP. Hence, an efficient inexact ABCD method is introduced for solving \(L^1\)-EOCP. The design of this method combines an inexact 2-block majorized ABCD and the recent advances in the inexact Symmetric Gauss-Seidel (SGS) technique for solving a multi-block convex composite quadratic programming whose objective contains a nonsmooth term involving only the first block. The proposed algorithm (called SGS-imABCD) is illustrated at two numerical examples. Numerical results not only confirm the finite element error estimates, but also show that our proposed algorithm is more efficient than (a) the IHADMM (inexact heterogeneous alternating direction method of multipliers), (b) the accelerated proximal gradient method.

MSC:

49N05 Linear optimal control problems
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
49M25 Discrete approximations in optimal control
68W15 Distributed algorithms
49M29 Numerical methods involving duality
93A15 Large-scale systems

Software:

QSDPNAL; iFEM
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Stadler, G.: Elliptic optimal control problems with \[L^1\] L1-control cost and applications for the placement of control devices. Comput. Optim. Appl. 44, 159-181 (2009) · Zbl 1185.49031 · doi:10.1007/s10589-007-9150-9
[2] Hinze, M.: A variational discretization concept in control constrained optimization: the linear-quadratic case. Comput. Optim. Appl. 30, 45-61 (2005) · Zbl 1074.65069 · doi:10.1007/s10589-005-4559-5
[3] Falk, R.S.: Approximation of a class of optimal control problems with order of convergence estimates. J. Math. Anal. Appl. 44, 28-47 (1973) · Zbl 0268.49036 · doi:10.1016/0022-247X(73)90022-X
[4] Geveci, T.: On the approximation of the solution of an optimal control problem problem governed by an elliptic equation. RAIRO-Analyse numérique 13, 313-328 (1979) · Zbl 0426.65067 · doi:10.1051/m2an/1979130403131
[5] Rösch, A.: Error estimates for linear-quadratic control problems with control constraints. Optim. Methods Softw. 21, 121-134 (2006) · Zbl 1085.49042 · doi:10.1080/10556780500094945
[6] Casas, E., Tröltzsch, F.: Error estimates for linear-quadratic elliptic control problems. In: IFIP TC7/WG7.2 International working conference on analysis and optimization of differential systems, September 10-14, 2002, Constanta, Romania, pp. 89-100 (2002) · Zbl 1027.65088
[7] Meyer, C., Rösch, A.: Superconvergence properties of optimal control problems. SIAM J. Control Optim. 43, 970-985 (2004) · Zbl 1071.49023 · doi:10.1137/S0363012903431608
[8] Casas, E.: Using piecewise linear functions in the numerical approximation of semilinear elliptic control problems. Adv. Comput. Math. 26, 137-153 (2007) · Zbl 1118.65069 · doi:10.1007/s10444-004-4142-0
[9] Wachsmuth, G., Wachsmuth, D.: Convergence and regularisation results for optimal control problems with sparsity functional. ESAIM Control Optim. Calc. Var. 17, 858-886 (2011) · Zbl 1228.49032 · doi:10.1051/cocv/2010027
[10] Casas, E., Herzog, R., Wachsmuth, G.: Approximation of sparse controls in semilinear equations by piecewise linear functions. Numer. Math. 122, 645-669 (2012) · Zbl 1284.65074 · doi:10.1007/s00211-012-0475-7
[11] Casas, E., Herzog, R., Wachsmuth, G.: Optimality conditions and error analysis of semilinear elliptic control problems with \[L^1\] L1 cost functional. SIAM J. Optim. 22, 795-820 (2012) · Zbl 1278.49026 · doi:10.1137/110834366
[12] Clason, C., Kunisch, K.: A duality-based approach to elliptic control problems in non-reflexive Banach spaces. ESAIM Control Optim. Calc. Var. 17, 243-266 (2011) · Zbl 1213.49041 · doi:10.1051/cocv/2010003
[13] Casas, E., Clason, C., Kunisch, K.: Approximation of elliptic control problems in measure spaces with sparse solutions. SIAM J. Control Optim. 50, 1735-1752 (2012) · Zbl 1343.49048 · doi:10.1137/110843216
[14] Collis, S.S., Heinkenschloss M.: Analysis of the streamline upwind/Petrov Galerkin method applied to the solution of optimal control problems. CAAM TR02-01 (2002) · Zbl 1033.49039
[15] Bergounioux, M., Ito, K., Kunisch, K.: Primal-dual strategy for constrained optimal control problems. SIAM J. Control Optim. 37, 1176-1194 (1999) · Zbl 0937.49017 · doi:10.1137/S0363012997328609
[16] Ulbrich, M.: 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) · Zbl 1393.49022
[17] Ulbrich, M.: Semismooth Newton methods for operator equations in function spaces. SIAM J. Optim. 13, 805-842 (2003) · Zbl 1033.49039 · doi:10.1137/S1052623400371569
[18] Hinze, M., Pinnau, R., Ulbrich, M., Ulbrich, S.: Optimization with PDE Constraints, vol. 23. Springer, Berlin (2008) · Zbl 1167.49001
[19] Hintermüller, M., Ulbrich, M.: A mesh-independence result for semismooth Newton methods. Math. Program. 101, 151-184 (2004) · Zbl 1079.65065 · doi:10.1007/s10107-004-0540-9
[20] Porcelli, M., Simoncini, V., Stoll, M.: Preconditioning PDE-constrained optimization with \[L^1\] L1-sparsity and control constraints. Comput. Math. Appl. 74, 1059-1075 (2017) · Zbl 1393.49022 · doi:10.1016/j.camwa.2017.04.033
[21] Herzog, R., Ekkehard, S.: Preconditioned conjugate gradient method for optimal control problems with control and state constraints. SIAM J. Matrix Anal. Appl. 31, 2291-2317 (2010) · Zbl 1209.49038 · doi:10.1137/090779127
[22] Blumensath, T., Davies, M.E.: Iterative thresholding for sparse approximations. J. Fourier Anal. Appl. 14, 629-654 (2008) · Zbl 1175.94060 · doi:10.1007/s00041-008-9035-z
[23] Jiang, K., Sun, D.F., Toh, K.C.: An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP. SIAM J. Optim. 22, 1042-1064 (2012) · Zbl 1401.90120 · doi:10.1137/110847081
[24] Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183-202 (2009) · Zbl 1175.94009 · doi:10.1137/080716542
[25] Toh, K.C., Yun, S.: An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Pac. J. Optim. 6, 615-640 (2010) · Zbl 1205.90218
[26] Fazel, M., Pong, T.K., Sun, D.F., Tseng, P.: Hankel matrix rank minimization with applications to system identification and realization. SIAM J. Matrix Anal. Appl. 34, 946-977 (2013) · Zbl 1302.90127 · doi:10.1137/110853996
[27] Chen, L. Sun, D.F., Toh, K.C.: An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming. Math. Program. 161, 237-270 (2017) · Zbl 1356.90105
[28] Li, X.D., Sun, D.F., Toh, K.C.: A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions. Math. Program. 155, 333-373 (2016) · Zbl 1342.90134 · doi:10.1007/s10107-014-0850-5
[29] Li, X.D., Sun, D.F., Toh, K.C.: QSDPNAL: a two-phase Newton-CG proximal augmented Lagrangian method for convex quadratic semidefinite programming problems. arXiv:1512.08872 (2015) · Zbl 0268.49036
[30] Song, X.L., Yu, B., Wang, Y.Y., Zhang, X.Z.: An inexact heterogeneous ADMM algorithm for elliptic optimal control problems with \[L^1\] L1-control cost. arXiv:1709.01067 (2017) · Zbl 1074.65069
[31] Schindele, A., Borzì, A.: Proximal methods for elliptic optimal control problems with sparsity cost functional. Appl. Math. 7, 967-992 (2016) · doi:10.4236/am.2016.79086
[32] Chambolle, A., Dossa, C.: A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions. https://hal.archives-ouvertes.fr/hal-01099182 (2015) · Zbl 1085.49042
[33] Sun, D.F., Toh, K.C., Yang, L.Q.: An efficient inexact ABCD method for least squares semidefinite programming. SIAM J. Optim. 26, 1072-1100 (2016) · Zbl 1346.90658 · doi:10.1137/15M1021799
[34] Cui, Y.: Large scale composite optimization problems with coupled objective functions: theory, algorithms and applications. Ph.D. thesis, National University of Singapore (2016) · Zbl 1071.49023
[35] Kinderlehrer, D., Stampacchia, G.: An Introduction to Variational Inequalities and their Applications, vol. 31. SIAM, Philadelphia (1980) · Zbl 0457.35001
[36] Hiriart-Urruty, J.-B., Strodiot, J.-J., Nguyen, V.H.: Generalized Hessian matrix and second-order optimality conditions for problems with \[C^{1,1}\] C1,1 data. Appl. Math. Optim. 11, 43-56 (1984) · Zbl 0542.49011 · doi:10.1007/BF01442169
[37] Wathen, A.J.: Realistic eigenvalue bounds for the Galerkin mass matrix. IMA J. Numer. Anal. 7, 449-457 (1987) · Zbl 0648.65076 · doi:10.1093/imanum/7.4.449
[38] Li, X.D.: A two-phase augented Lagrangian method for convex composite quadratic programming. Ph.D. thesis, National University of Singapore (2015) · Zbl 1175.94060
[39] Rees, T., Dollar, H.S., Wathen, A.J.: Optimal solvers for PDE-constrained optimization. SIAM J. Sci. Comput. 32, 271-298 (2010) · Zbl 1208.49035 · doi:10.1137/080727154
[40] Rees, T., Wathen, A.J.: Chebyshev semi-iteration in preconditioning for problems including the mass matrix. Electron. Trans. Numer Anal. 34, 125-135 (2009) · Zbl 1189.65065
[41] Bai, Z.Z., Benzi, M., Chen, F., Wang, Z.Q.: 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, 343-369 (2013) · Zbl 1271.65100 · doi:10.1093/imanum/drs001
[42] Elman, H.C., Silvester, D.J., Wathen, A.J.: Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics. Oxford University Press, Oxford (2014) · Zbl 1304.76002 · doi:10.1093/acprof:oso/9780199678792.001.0001
[43] Song, X., Chen, B., Yu, B.: Error estimates for sparse optimal control problems by piecewise linear finite element approximation. arXiv:1709.09539 (2017)
[44] Chen, L.: iFEM: an integrated finite element methods package in MATLAB. Technical report, Department of Mathematics, University of California at Irvine, Irvine (2008) · Zbl 1175.94009
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.