In this paper, elliptic optimal control problems with $L^1$-control cost and box constraints on the control are considered. To numerically solve the optimal control problems, we use the First optimize, then discretize approach. We focus on the inexact alternating direction method of multipliers (iADMM) and employ the standard piecewise linear finite element approach to discretize the subproblems in each iteration. However, in general, solving the subproblems is expensive, especially when the discretization is at a fine level. Motivated by the efficiency of the multigrid method for solving large-scale problems, we combine the multigrid strategy with the iADMM algorithm. Instead of fixing the mesh size before the computation process, we propose the strategy of gradually refining the grid. Moreover, to overcome the difficulty whereby the $L^1$-norm does not have a decoupled form, we apply nodal quadrature formulas to approximately discretize the $L^1$-norm and $L^2$-norm. Based on these strategies, an efficient multilevel heterogeneous ADMM (mhADMM) algorithm is proposed. The total error of the mhADMM consists of two parts: the discretization error resulting from the finite-element discretization and the iteration error resulting from solving the discretized subproblems. Both errors can be regarded as the error of inexactly solving infinite-dimensional subproblems. Thus, the mhADMM can be regarded as the iADMM in function space. Furthermore, theoretical results on the global convergence, as well as the iteration complexity results $o(1/k)$ for the mhADMM, are given. Numerical results show the efficiency of the mhADMM algorithm.

This paper focuses on the two-block composite convex optimization problems prevalent in signal recovery, image processing and related fields. Although Alternating Block Coordinate Descent (ABCD) is simple to implement and low in computational cost, its objective function often oscillates during iterations. We propose monotone ABCD (MABCD) to guarantee the monotonic descent of the objective. On this basis, an inexact variant iMABCD is presented, which allows inexact subproblem solutions to lower computational overhead and adaptation to realistic application scenarios. Rigorous theoretical analysis of numerical experiments demonstrates that both algorithms attain the $O(1/k^2)$ convergence rate. The monotonic constraint effectively removes undesirable iterative fluctuations and stabilizes the optimization process, while the inexact updating rule greatly improves practical applicability.

In this paper, we propose an efficient numerical algorithm for solving large-scale ill-posed linear inverse problems encountered in image restoration. To boost computational efficiency, we extend the structured fast iterative shrinkage-thresholding algorithm (sFISTA) for addressing the corresponding $l_1$-regularized minimization problem, and further introduce the over-relaxation technique to accelerate the algorithm. The proposed algorithm is termed structured over-relaxed monotone FISTA (sOMFISTA). The convergence analysis of sOMFISTA is also conducted. The algorithmic framework of sOMFISTA is universally applicable to any non-smooth convex regularization term, exhibiting remarkable flexibility. Extensive numerical experiments are carried out to systematically validate the superiority in efficiency and performance of the proposed sOMFISTA.