Source-linked AI summary
An ADMM Algorithm for a Class of Total Variation Regularized Estimation Problems
Bo Wahlberg, Stephen Boyd, Mariette Annergren, Yang Wang
TL;DR
The paper addresses large convex estimation problems whose objectives separate across variable blocks and consecutive differences. It derives an ADMM method with parallel block updates and efficient projection, applying it to mean and variance filtering. In a numerical example, the implementation is approximately 10000 times faster than generic optimization packages while producing the same estimates.
Problem
Large variable counts make these structured convex optimization problems difficult to handle efficiently with generic solvers.
Method
The paper derives a distributed ADMM algorithm that separately optimizes variable blocks and efficiently projects onto difference-consistency constraints.
Results
Approximately 10000 times faster: the C ADMM implementation took 2.2 milliseconds versus approximately 20 seconds for CVX while producing the same estimates.
Takeaways & Limitations
The method solves ℓ1 mean and variance filtering problems many orders of magnitude faster than generic solvers such as SeDuMi or SDPT3.
Takeaways & Limitations
The regularization parameter ρ lacks a formal optimality justification; for ℓ1 mean filtering, the authors report that ρ ≈ λ works well.
Abstract
from arXiv · showhide
We present an alternating augmented Lagrangian method for convex optimization problems where the cost function is the sum of two terms, one that is separable in the variable blocks, and a second that is separable in the difference between consecutive variable blocks. Examples of such problems include Fused Lasso estimation, total variation denoising, and multi-period portfolio optimization with transaction costs. In each iteration of our method, the first step involves separately optimizing over each variable block, which can be carried out in parallel. The second step is not separable in the variables, but can be carried out very efficiently. We apply the algorithm to segmentation of data based on changes inmean (l_1 mean filtering) or changes in variance (l_1 variance filtering). In a numerical example, we show that our implementation is around 10000 times faster compared with the generic optimization solver SDPT3.
1. INTRODUCTION
The paper targets large convex estimation problems with block-separable and consecutive-difference-separable objectives, developing a scalable ADMM algorithm for applications including filtering and portfolio optimization.
- Problem setting: The objective combines a term separable across variable blocks with a term separable across differences between consecutive blocks.This structure covers Fused Lasso, total variation denoising, ARX segmentation, and transaction-cost portfolio optimization.
- Motivation: Large numbers of variables can make these problems inefficient for generic optimization solvers.The paper motivates exploiting problem structure rather than relying on general-purpose methods.
- Approach: The proposed scalable algorithm uses the distributed Alternating Direction Method of Multipliers.ADMM is related to Bregman iterative algorithms, Douglas-Rachford splitting, and proximal point methods.
- Applications: The method is applied to ℓ1 mean and variance filtering for segmenting changes in signal behavior.These problems support applications in financial and biological data analysis and can preprocess data before parametric modeling.
- Evaluation: The paper evaluates the method through numerical examples after deriving the algorithm and applying it to mean and variance filtering.The paper’s organization separates ADMM review, algorithm derivation, applications, numerical examples, and conclusions.
2. ALTERNATING DIRECTION METHOD OF MULTIPLIERS (ADMM)
ADMM reformulates a convex constrained problem with an indicator function and alternates minimization over primal variables with a dual update. Under mild assumptions it converges, but its iteration count depends strongly on the penalty parameter ρ.
- Problem reformulation: A convex constrained problem is rewritten as minimizing f(x) plus the indicator function I_C(z), subject to x = z.The indicator is zero on C and infinite outside C, thereby encoding the constraint.
- Augmented Lagrangian: The augmented Lagrangian adds a quadratic penalty for x − z + u, where u is the scaled dual variable and ρ > 0 is the penalty parameter.The scaled dual variable satisfies u = (1/ρ)y.
- Iteration: Each ADMM iteration alternates minimization over x and z, followed by updating the dual variable u.The z-update is expressed as Euclidean projection onto C.
- Convergence: Under mild assumptions on f and C, the iterates converge to a solution, with f(x^k) → p⋆ and x^k − z^k → 0.These are the stated convergence properties as k → ∞.
- Convergence: A well-chosen ρ can achieve useful accuracy within a few tens of iterations, whereas poor choices may require many iterations.The paper points to heuristics for choosing ρ but does not establish a universal optimal choice.
- Stopping criterion: Termination uses primal and dual residuals compared against application-dependent absolute-plus-relative tolerances.The tolerances include ε_abs and ε_rel.
3. PROBLEM FORMULATION AND METHOD
The paper casts difference-regularized estimation in ADMM form, exploiting separability for parallel block updates and a structured projection with linear computational cost O(Nn).
- 3.1 Optimization problem: The method is derived for a convex optimization problem with block variables x_i and difference variables r_i satisfying r_i = x_{i+1} − x_i.The functions Φ_i and Ψ_i are convex, and the objective separates across x_i and r_i.
- 3.1 Optimization problem: ADMM introduces auxiliary variables z and s with consensus constraints x_i = z_i and r_i = s_i, together with scaled dual variables u and t.The splitting separates the original objective terms from the difference constraints.
- 3.2 Distributed optimization method: Each iteration begins with 2N − 1 separate minimizations because the objective is separable in x_i and r_i.These updates can be carried out in parallel, and many applications admit analytical solutions.
- 3.2 Distributed optimization method: The second step projects the updated primal variables onto the difference-consistency constraint set C.For this constraint set, the projection is designed to be extremely efficient.
- 3.2 Distributed optimization method: Dual-variable updates can be performed independently in parallel for each variable block.This preserves the distributed structure after the projection step.
- 3.3 Projection: The projection reduces to solving (I + D^T D)z = w + D^T v and then setting s = Dz.The matrix I + D^T D is block tridiagonal, enabling a block-banded Cholesky factorization.
- 3.3 Projection: The projection requires O(Nn) flops and, after precomputing diagonal inverses, only multiplication, addition, and subtraction.The method avoids division during the projection itself.
4. EXAMPLES
The examples apply the structured convex formulation and ADMM to piecewise-constant mean, covariance, and joint mean–covariance estimation, with fused penalties on consecutive differences.
- ℓ1 mean filtering: ℓ1 mean filtering estimates an unknown piecewise-constant mean from observations when the covariance matrix is known.
- ℓ1 mean filtering: The Fused Group Lasso formulation estimates mean vectors by constraining auxiliary differences to equal consecutive differences between the optimization variables.
- ℓ1 variance filtering: ℓ1 variance filtering estimates a piecewise-constant sequence of covariance matrices by using inverse covariances as the optimization variables.
- ℓ1 variance filtering: The variance-filtering formulation uses matrix variables and consecutive-difference constraints, with estimates obtained by inverting the optimal inverse-covariance variables.
- Joint filtering: For joint mean and covariance estimation, the method imposes consecutive-difference constraints on both mean and inverse-covariance variables.
- Joint filtering: The joint updates lack analytical formulas in the described treatment, so they require semidefinite programs.
5. NUMERICAL EXAMPLE
A one-dimensional ℓ1 mean-filtering instance demonstrates residual convergence and mean estimation. The custom ADMM implementation matches CVX estimates while requiring substantially less computation time.
- The experiment solves ℓ1 mean filtering with n = 1, Σ = 1, and N = 400 using the standard Fused Lasso method.
- Figure 1 plots primal residual ep as a solid line and dual residual ed as a dashed line.
- Figure 2 compares estimated means, true means, and measurements using solid lines, dashed lines, and crosses, respectively.
- 20 seconds versus 2.2 milliseconds: CVX took approximately 20 seconds, while the C implementation produced the same estimates in 2.2 milliseconds.
- Approximately 10000 times faster: the ADMM algorithm outperformed generic optimization packages on the same ℓ1 mean-filtering problem.
6. CONCLUSIONS
The paper derives an efficient, scalable distributed method for structured convex problems in control and estimation, with numerical examples showing much faster solution than generic solvers.
- The method exploits problem structure through distributed optimization, with updates typically using linear equations, matrix multiplication, or thresholding.
- Numerical examples show ℓ1 mean and variance filtering solved many orders of magnitude faster than generic solvers such as SeDuMi or SDPT3.
- The regularization parameter ρ is the method’s only tuning parameter, but selecting an optimal value is not straightforward.
- For the ℓ1 mean-filtering example, setting ρ ≈ λ worked well, but the paper provides no formal justification.
1.3. Optimization Methods and Software, 11(1):545–581,
The cited reference is a 1999 work by Toh, Sturm, and related authors, listed in the paper’s bibliography.
- The passage identifies the publication year as 1999.
- The citation includes the author name B. Wahlberg.
- The cited work concerns ℓ1 mean and variance filtering and appeared in the Proceedings of the Forty-Fifth Asilomar Conference.