A Fast Algorithm for Sparse Controller Design

Matt Wytock, J. Zico KolterarXiv 2013 · OpenReview

TL;DR

This paper introduces a significantly faster algorithm for designing sparse controllers for large-scale linear systems. By combining a proximal Newton method with a coordinate descent active set approach and efficient Lyapunov equation solvers, their method achieves orders-of-magnitude speedups over existing techniques, enabling practical sparse controller design for systems previously considered intractable.

What Problem Does This Paper Address?

Designing optimal control laws for large-scale systems often requires controllers that are "sparse," meaning each control input only depends on a limited subset of the system's states. This is crucial for practical implementation, especially in systems like the electrical grid where full state feedback is infeasible. While methods exist to find sparse controllers by minimizing a quadratic cost function with an $\ell_1$ penalty (encouraging sparsity), these methods often struggle to scale to systems with thousands of states. Existing approaches typically rely on semidefinite programming (which scales poorly) or first-order methods (which require many iterations). This paper addresses the critical need for a computationally efficient algorithm that can handle large-scale sparse controller design problems.

Methods

The core contribution is a novel algorithm called Newton-CD (Newton Coordinate Descent). It's based on the "Newton-Lasso" or "proximal Newton" framework, which iteratively approximates the smooth part of the objective function with a quadratic and then minimizes this approximation along with the $\ell_1$ penalty.

Key innovations include:

  • Coordinate Descent Active Set: Instead of optimizing over all controller parameters at each step, the algorithm intelligently focuses on a small "active set" of parameters that are either non-zero or violate optimality conditions. This significantly reduces the computational burden.
  • Efficient Lyapunov Equation Solvers: A major bottleneck in sparse control is solving Lyapunov equations, which typically take $O(n^3)$ time. The authors leverage eigendecomposition, fast multipole methods, and the Autonne-Kagaki factorization to solve these equations and related matrix products in $O(n)$ time per coordinate update.
  • Caching and Precomputation: Extensive use of precomputed matrix products and cached values within the inner loop of the coordinate descent further accelerates the process.
  • Fallback for Non-Convexity: Since the objective function is not convex, the algorithm includes a fallback to a quasi-Newton coordinate descent method to ensure convergence guarantees, especially in the early stages.

Datasets

The paper evaluates its algorithm on two types of systems:

  • Synthetic Mass-Spring System: A standard benchmark for decentralized control, described by the displacement of $N$ masses connected in a line. The authors use systems with $N=50$ and $N=500$ states.
  • Real Power Networks: The authors use examples from the Power Systems Toolbox, including the IEEE 14 Bus, NE 39 Bus, GE 68 Bus, NPCC 140 Bus, and IEEE 145 Bus systems. They also create a larger $N=500$ state system by modifying the PST 48 machine system.

Key Insights and Ideas

  • Sparsity Scales with System Size: For both synthetic and real-world power systems, larger systems tend to require controllers with more sparsity to achieve near-optimal performance. This is a crucial observation for designing practical controllers for complex networks.
  • Newton-CD's Efficiency is Game-Changing: The combination of an active set strategy and fast Lyapunov solvers dramatically reduces the computational cost of each Newton step, making it orders of magnitude faster than previous methods. This opens the door to solving problems that were previously computationally infeasible.
  • Active Set is Key for Sparsity: The coordinate descent active set approach is particularly effective when the solution is sparse, as it avoids unnecessary computations on zeroed-out controller gains.
  • Lyapunov Equations are the Bottleneck: The paper clearly identifies the $O(n^3)$ complexity of Lyapunov equations as the primary computational hurdle for sparse controller design and provides an elegant solution to mitigate it.

Key Results

  • Orders-of-Magnitude Speedup: The Newton-CD algorithm is shown to be several orders of magnitude faster than existing methods like ADMM and ISTA. For instance, on a large power system example ($N=500$), Newton-CD converges to high accuracy in under 11 minutes, while ADMM takes over 2 hours to reach a much lower accuracy.
  • High Accuracy Achieved: The algorithm consistently converges to solutions with high numerical precision, often reaching accuracies of $10^{-8}$ or better.
  • Practical Scalability: The method successfully scales to systems with thousands of states, demonstrating its practical utility for large-scale control problems.
  • Comparable Performance to LQR: For many systems, sparse controllers designed by Newton-CD achieve performance very close to the full LQR controller, often within 0.1% of the optimal LQR cost, with significantly fewer controller gains.

Limitations and Future Work

  • Lyapunov Complexity Remains: While the authors significantly reduce the cost of solving Lyapunov equations, their $O(n^3)$ complexity still poses a fundamental limit for extremely large systems (beyond thousands of nodes).
  • Decomposition Methods: The authors suggest that decomposition methods, which solve smaller, independent subproblems, are a promising direction for tackling even larger systems.
  • Initial Controller Stability: While the paper addresses initial controller stability through soft-thresholding the LQR solution, ensuring stability remains a critical aspect.
  • Non-Convexity Handling: The fallback mechanism for non-convexity is effective but suggests that further research into robustly handling non-convex objectives in sparse control could be beneficial.

Summary updated

Abstract

We consider the task of designing sparse control laws for large-scale systems by directly minimizing an infinite horizon quadratic cost with an $\ell_1$ penalty on the feedback controller gains. Our focus is on an improved algorithm that allows us to scale to large systems (i.e. those where sparsity is most useful) with convergence times that are several orders of magnitude faster than existing algorithms. In particular, we develop an efficient proximal Newton method which minimizes per-iteration cost with a coordinate descent active set approach and fast numerical solutions to the Lyapunov equations. Experimentally we demonstrate the appeal of this approach on synthetic examples and real power networks significantly larger than those previously considered in the literature.
BibTeX
@misc{wytock2013fast,
  author = {Matt Wytock and J. Zico Kolter},
  title = {{A Fast Algorithm for Sparse Controller Design}},
  year = {2013},
  eprint = {1312.4892},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1312.4892},
}
Figure