PaperlayerView exact revision on arXiv

Source-linked AI summary

Design of Optimal Sparse Feedback Gains via the Alternating Direction Method of Multipliers

Fu Lin, Makan Fardad, Mihailo R. Jovanović

arXiv:1111.6188v3math.OCeess.SY

TL;DR

The paper addresses sparse and block sparse feedback design for reducing distributed-system variance amplification while avoiding dense centralized gains. It uses ADMM with sparsity-promoting penalties to identify gain structures, then optimizes H2 performance under those structures. The resulting distributed controllers have performance comparable to the optimal centralized controller, with examples demonstrating the approach.

  • Problem

    Standard H2 design produces dense centralized feedback gains, motivating methods that identify sparse communication structures while minimizing distributed-system variance amplification.

  • Method

    ADMM alternates sparsity promotion and closed-loop performance optimization, using separable penalties and analytically solvable subproblems before optimizing gains under the identified structure.

  • Results

    The developed approach designs sparse and block sparse feedback gains with performance comparable to the optimal centralized controller.

  • Takeaways & Limitations

    The framework provides a flexible way to identify sparse or block sparse distributed-controller structures and improve their H2 performance through a second optimization step.

Abstract

from arXiv · show

We design sparse and block sparse feedback gains that minimize the variance amplification (i.e., the $H_2$ norm) of distributed systems. Our approach consists of two steps. First, we identify sparsity patterns of feedback gains by incorporating sparsity-promoting penalty functions into the optimal control problem, where the added terms penalize the number of communication links in the distributed controller. Second, we optimize feedback gains subject to structural constraints determined by the identified sparsity patterns. In the first step, the sparsity structure of feedback gains is identified using the alternating direction method of multipliers, which is a powerful algorithm well-suited to large optimization problems. This method alternates between promoting the sparsity of the controller and optimizing the closed-loop performance, which allows us to exploit the structure of the corresponding objective functions. In particular, we take advantage of the separability of the sparsity-promoting penalty functions to decompose the minimization problem into sub-problems that can be solved analytically. Several examples are provided to illustrate the effectiveness of the developed approach.

I. INTRODUCTION

The paper develops sparse and block sparse feedback gains for minimizing distributed-system variance amplification, using ADMM to identify structures and then optimize structured gains. The approach balances H2 performance against controller sparsity through separable penalty functions and analytically solvable subproblems.

  • The design targets sparse and block sparse feedback gains that minimize the variance amplification of distributed systems.
  • The procedure first identifies sparsity patterns by incorporating penalties for communication links into the optimal control problem.
  • Increasing the penalty weight traces a solution path from the centralized controller toward sparser gains until the desired performance–sparsity balance is reached.
  • The second step optimizes H2 performance subject to the identified feedback-gain structure.
  • ADMM alternates between promoting gain sparsity and optimizing closed-loop performance, while separable penalties yield analytically solvable subproblems.
  • The method accommodates sparsity and block sparsity, and its analytical subproblem solutions also apply to other distributed-control problems where sparsity is desired.

II. SPARSITY-PROMOTING OPTIMAL CONTROL PROBLEM

The paper formulates an unconstrained feedback-design problem that directly penalizes gain sparsity while retaining H2 control performance. This formulation seeks favorable communication structures without assuming them in advance.

  • The control problem uses state feedback, performance weights Q and R, and a closed-loop system whose H2 performance is represented through an observability Gramian.
  • The formulation seeks feedback gains with favorable communication structures without prior assumptions about the sparsity pattern.
  • Sparsity is incorporated directly into the objective function rather than imposed as a structural constraint on the feedback gain.
  • The cardinality function measures the number of nonzero elements in the gain matrix and promotes sparse feedback through the optimization problem.
  • A positive weight γ controls the sparsity emphasis: larger γ encourages a sparser gain, while γ = 0 yields the centralized standard-LQR solution.

2 P, where P is the unique positive definite

The section motivates sparsity-promoting optimization because cardinality-based feedback design is combinatorial, then describes convex and nonconvex surrogates, weighted schemes, and block-sparse extensions.

  • Sparsity promotion: Cardinality-based optimization is combinatorial, motivating tractable sparsity-promoting alternatives such as the ℓ1 norm.The ℓ1 norm is used as a replacement for the cardinality function in optimization problems where sparsity is desired.
  • Weighted penalties: Weighted ℓ1 penalties use non-negative weights that can be chosen inversely proportional to feedback-gain magnitudes.The specified weighting assigns 1/|Fij| to nonzero entries and 1/ε to zero entries, with 0 < ε ≪ 1.
  • Weighted penalties: With those inverse-magnitude weights, the weighted ℓ1 norm and the cardinality function of F coincide.The corresponding weighting scheme depends on the unknown feedback gain, so it cannot be implemented directly.
  • Penalty functions: The paper examines the nonconvex sum-of-logs function as a more aggressive sparsity-promoting penalty than convex ℓ1-based relaxations.Both the ℓ1 norm and weighted ℓ1 norm are convex relaxations of cardinality, while the sum-of-logs function is considered separately.
  • Block-sparse design: Block sparsity is obtained by partitioning F into submatrices and replacing elementwise magnitudes with Frobenius norms.This promotes sparsity at the submatrix level rather than within each block; weighted ℓ1 and sum-of-logs penalties can both be generalized this way.

B. Sparsity-promoting optimal control problem

The paper formulates sparsity-promoting optimal control to trace the trade-off between closed-loop H2 performance and feedback-gain sparsity, then uses ADMM to identify patterns and solves a structured H2 problem.

  • B. Sparsity-promoting optimal control problem: The optimal control problem combines the squared closed-loop H2 norm J with a sparsity-promoting penalty g weighted by γ.Replacing the cardinality function with convex or other penalty functions yields relaxations of the combinatorial design problem.
  • B. Sparsity-promoting optimal control problem: As γ varies from 0 to +∞, solutions trace a trade-off path between H2 performance and feedback-gain sparsity.Increasing γ promotes sparser solutions; γ=0 gives the centralized-feedback solution.
  • B. Sparsity-promoting optimal control problem: For convex problems, standard results establish convergence of ADMM to a global minimizer; for nonconvex problems, such convergence is unavailable, although experiments suggest effectiveness.Nonconvexity arises because stabilizing gains are generally nonconvex and J need not be convex in F.
  • B. Sparsity-promoting optimal control problem: ADMM introduces G and the constraint F−G=0 to decouple the H2 objective J from the sparsity penalty g.The resulting iterations alternate F-minimization, G-minimization, and dual-variable updates.
  • B. Sparsity-promoting optimal control problem: Separability of g decomposes G-minimization into scalar subproblems, enabling analytical solutions for weighted ℓ1, sum-of-logs, and cardinality penalties.The H2 term is not componentwise separable, whereas its differentiability supports descent algorithms for F-minimization.

1) Weighted ℓ1 norm:

The weighted ℓ1 penalty produces an analytical soft-thresholding update that shrinks entries toward zero and sets sufficiently small entries exactly to zero.

  • 1) Weighted ℓ1 norm:: The weighted ℓ1 G-minimization solution is given by a soft-thresholding operator.Each entry is moved toward zero according to its weight and the ratio γ/ρ.
  • 1) Weighted ℓ1 norm:: Entries are set to zero when |Vij| ≤ (γ/ρ)Wij, so increasing γ or Wij, or decreasing ρ, promotes more aggressive sparsification.The threshold determines whether an entry survives the update.

2) Cardinality function:

The paper extends analytical ADMM updates to cardinality and block-sparse penalties, and uses descent methods to solve the differentiable feedback-gain subproblem while maintaining stability.

  • 2) Cardinality function:: For the cardinality penalty, the G-minimization solution is characterized by a truncation operator.The update compares retaining an entry with setting it to zero.
  • 2) Cardinality function:: In block-sparse design, scalar absolute values are replaced by Frobenius norms of the corresponding blocks in the minimization formulas.This adapts the analytical updates to block-level sparsity.
  • 2) Cardinality function:: The Anderson–Moore method solves the F-minimization problem by alternating Lyapunov-equation solves for Gramians with a Sylvester-equation solve for the gain.Each iteration requires two Lyapunov equations and one Sylvester equation.
  • 2) Cardinality function:: The difference between consecutive Anderson–Moore iterates is a descent direction, allowing line search to guarantee closed-loop stability and convergence to a stationary point.The method starts from a stabilizing feedback gain.
  • 2) Cardinality function:: Because J is infinite outside the stabilizing set and grows toward its boundary, decreasing objective values preserve stabilizing gains.This stability argument applies to the descent sequence generated for the F-subproblem.

C. Solving the structured H2 problem

After ADMM identifies a sparsity pattern, the paper fixes that structure and solves the structured H2 problem to obtain an optimized sparse feedback gain.

  • C. Solving the structured H2 problem: The identified sparsity pattern is fixed as a structural subspace S before solving the structured H2 problem.The resulting gain belongs to S and can improve the performance of the sparse gain returned by ADMM.
  • C. Solving the structured H2 problem: The sparse feedback gains obtained by ADMM are stabilizing, which facilitates descent-based solution of the structured H2 problem.This stability property supports the subsequent structured optimization stage.
  • C. Solving the structured H2 problem: Starting from an initial gain in S, updates Fi+1=Fi+si F̃i generate a decreasing sequence of the objective function J.The Newton direction is obtained from a second-order approximation within the structural subspace.
  • C. Solving the structured H2 problem: The structural identity matrix IS characterizes which feedback-gain entries are free variables and enforces F◦IS=F for F∈S.Entrywise multiplication imposes the structural constraint.
  • C. Solving the structured H2 problem: Newton directions can be computed with conjugate gradients without explicitly forming or inverting the large Hessian matrix.Negative-curvature tests and Armijo line searches can support descent and generate decreasing objective values.

D. Convergence of ADMM

For convex problems, ADMM converges to the global minimizer under standard results, while for the weighted ℓ1 formulation it converges to a critical point when convergence occurs. For nonconvex problems, convergence is not established, although computational experience suggests sufficiently large ρ can work well.

  • For convex problems, standard results guarantee ADMM convergence to the global minimizer.
  • For nonconvex problems, convergence results are unavailable.The paper notes that extensive computational experience nevertheless suggests good performance when ρ is sufficiently large.
  • The quadratic penalty term with sufficiently large ρ locally convexifies the objective function.
  • For the weighted ℓ1 formulation, any convergent ADMM sequence reaches a critical point of (SP).At a convergent point, the limiting variables satisfy the necessary optimality conditions.

IV. EXAMPLES

Three examples illustrate the proposed approach, producing localized sparse controllers. In the mass-spring example, increasing the sparsity penalty removes feedback diagonals, while about 2% nonzero elements yields H2 performance about 8% worse than the centralized controller.

  • IV. EXAMPLES: The three examples produce localized controllers after their sparsity structures are identified.The paper provides MATLAB source code and additional information for these examples.
  • A. Mass-spring system: In the mass-spring system, increasing γ decreases the number of nonzero sub- and super-diagonals in both position and velocity gains.At larger γ values, both gains eventually become diagonal.
  • A. Mass-spring system: The position and velocity gain diagonals are nearly constant except near boundary masses.The centralized gains’ diagonals are almost identical to those obtained at γ = 10^-4.
  • A. Mass-spring system: The procedure first identifies sparsity patterns and then solves a structured H2 problem for the corresponding optimal structured controllers.The mass-spring example uses a weighted ℓ1 sparsity-promoting penalty with iteratively chosen weights.
  • A. Mass-spring system: 2% nonzero elements yields H2 performance only 7.8% worse than the centralized gain Fc.The paper also describes this degradation as about 8% worse in the mass-spring comparison.

B. Network with 100 unstable nodes

For 100 unstable-node networks, increasing the sparsity penalty localizes communication graphs and exposes an H2-performance–sparsity trade-off. Block-sparse designs can reduce communication links while retaining nearly identical H2 performance to elementwise-sparse designs.

  • Network setup: The network contains 100 randomly distributed nodes, each modeled as an unstable second-order system coupled through distance-dependent interactions.The nodes are uniformly distributed in a 10 × 10 square, and coupling decays exponentially with Euclidean distance.
  • Sparse feedback design: As γ increases, the communication graphs obtained with a weighted ℓ1 penalty become progressively more localized.The localized graphs are shown for different γ values in Figs. 3a–3c.
  • Performance–sparsity trade-off: With about 8% of the centralized gain’s nonzero elements, the sparse gain’s H2 performance is about 28% worse than the centralized gain’s.Figure 3d presents the corresponding optimal trade-off curve between H2 performance degradation and feedback-gain sparsity.
  • Stability: The approach gradually modifies the feedback gain while increasing zero elements, helping preserve closed-loop stability compared with truncating the centralized controller.The sparse gains obtained by ADMM are stabilizing, whereas truncating the centralized controller can produce a non-stabilizing matrix.
  • Block sparsity: For the five-system example, block-sparse and sparse gains have the same number of nonzero elements and less than 1% H2-performance difference, but block sparsity uses fewer nonzero blocks.The block-sparse gain has two identically zero rows, so subsystems 1 and 2 do not need actuation and the resulting communication graph has fewer links.

V. CONCLUDING REMARKS

The paper presents a two-step framework that identifies sparse feedback structures with ADMM and then polishes the gains under those structural constraints. It targets H2-optimal sparse and block-sparse state feedback and can extend beyond H2 performance indices.

  • Scope: The framework designs sparse and block-sparse state feedback gains that optimize H2 performance.The paper’s stated focus is variance amplification measured by the H2 norm.
  • Design procedure: The design procedure first identifies a sparse structure and then optimizes the feedback gain subject to the identified structural constraints.The identification step uses ADMM, while the polishing step solves the constrained minimum-variance problem.
  • ADMM framework: ADMM alternates sparsity promotion and closed-loop performance optimization, with separable penalty terms enabling analytically solvable subproblems.This supports sparsity-promoting optimal control problems of the form (SP).
  • Extensions: The G-minimization step is independent of the assigned performance index, allowing the ADMM framework to support alternative performance indices.The paper states that analytical solutions to the relevant subproblems facilitate this flexibility.
  • Future work: The paper proposes extending the framework to observer-based sparse optimal feedback design, while results on classes of convex optimal control problems are deferred.These extensions and results are identified as future work rather than completed contributions.
Loading 1111.6188v3…