Abstract
In this paper, elliptic optimal control problems involving the $L^1$-control cost ($L^1$-EOCP) are considered. To numerically discretize $L^1$-EOCP, the standard piecewise linear finite element is employed. However, unlike finite-dimensional $l^1$-regularization, 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, which incurs an additional error. To avoid this, we solve $L^1$-EOCP via its dual, reformulated as a multi-block unconstrained convex composite minimization problem. We introduce an efficient inexact accelerated block coordinate descent (sGS-imABCD) method. Numerical results confirm the finite element error estimates and demonstrate that our algorithm is more efficient than the inexact heterogeneous ADMM (ihADMM) and the accelerated proximal gradient (APG) method.
Introduction
In many engineering and physics applications, the goal is to control a system governed by Partial Differential Equations (PDEs) using a minimal number of actuators. This is known as sparse optimization. Mathematically, sparsity is promoted by adding an $L^1$-norm penalty to the control variable in the cost function. However, solving these problems numerically presents two major hurdles: discretization errors from standard quadrature methods and the massive computational scale of high-dimensional PDE constraints.
The sGS-imABCD Algorithm
The authors propose a "First discretize, then optimize" approach, solving the dual problem to avoid the pitfalls of primal discretization. The core contribution is the sGS-imABCD (inexact symmetric Gauss-Seidel based majorized Accelerated Block Coordinate Descent) method.
Key components of the algorithm include:
- Duality-Based Formulation: By transforming the primal problem into its dual, the authors handle the non-smooth $L^1$ term without needing error-prone nodal quadrature approximations.
- Inexact Solves: The algorithm uses "inexact" criteria for internal subproblems, saving significant computation time in early iterations.
- Symmetric Gauss-Seidel (sGS) Technique: This decomposes multi-block quadratic subproblems into manageable chunks while maintaining convergence guarantees.
- Efficient Preconditioning: A PMHSS preconditioner within a GMRES solver is used to handle the resulting saddle-point linear systems.
Key Insights: Sparsity and Structure
A crucial aspect of $L^1$-regularized control is the resulting structure of the optimal control variable. The $L^1$ penalty induces a "dead zone" where the control is exactly zero, leading to sparsity.
As shown in the figure above, the optimal control $u$ remains zero when the adjoint-related variable $p$ is within the interval $[-\beta, \beta]$. Outside this range, the control increases linearly until it hits the box constraints defined by $a$ and $b$. The sGS-imABCD method efficiently navigates this non-smooth structure by working in the dual space.
Other key insights include:
- Mesh Independence: The number of iterations required for convergence remains nearly constant even as the mesh is refined, ensuring high scalability.
- Iteration Complexity: The method achieves an $O(1/k^2)$ iteration complexity, the theoretical gold standard for first-order accelerated methods.
Numerical Results
The sGS-imABCD method was evaluated against ihADMM and APG on benchmark elliptic problems.
- Speed: In a mesh with approximately 260,000 degrees of freedom, sGS-imABCD converged in just 9 iterations (~312 seconds), significantly faster than ihADMM (54 iterations, ~915s) and APG (18 iterations, ~859s).
- Accuracy: Directly solving the dual problem yielded lower errors compared to primal methods using quadrature approximations.
- Robustness: The algorithm remained efficient across various regularization parameters, though it showed more sensitivity to the PDE scaling ($\alpha$) than the sparsity penalty ($\beta$).
Conclusion
By leveraging duality and inexact block coordinate descent, the sGS-imABCD algorithm provides a robust and efficient framework for solving large-scale PDE-constrained sparse optimization problems. It avoids the accuracy trade-offs of traditional quadrature methods while delivering superior performance compared to existing first-order solvers.
Summary updated