LQRSP – Sparsity-Promoting Linear Quadratic Regulator

lqrsp.m is a Matlab function for the design of sparse and block sparse state-feedback gains that minimize the variance amplification (i.e., the ${cal H}_2$ norm) of distributed systems. Our long-term objective is to develop a toolbox for sparse feedback synthesis. This will allow users to identify control configurations that strike a balance between the performance and the sparsity of the controller and to examine the influence of different control configurations on the performance of distributed systems.

Problem formulation

where

is the exogenous input signal and

is the performance output. The matrix

is a state feedback gain, Q = Q^T geq 0

and

are the state and control performance weights, and the closed-loop system is given by

in which the closed-loop ${cal H}_2$ norm

is augmented by a function {rm{bf card}}

that counts the number of nonzero elements in the feedback gain matrix

. For example,

As the parameter gamma

varies over [0, +infty)

, the solution traces the optimal trade-off path between the quadratic performance and the feedback gain sparsity.

After a desired level of sparsity is achieved, we fix the sparsity structure {cal S}

and find the optimal structured feedback gain

Relaxations of cardinality function

In addition to the cardinality function, we also consider several sparsity-promoting relaxations including

To illustrate the sparsity-promoting properties of these relaxations, let us consider the problem of finding the sparsest feedback gain that provides a given level of performance sigma > 0

. Convex ( ell_1

and weighted ell_1

norm) and non-convex (sum-of-logs) relaxations of the cardinality function lead to

The solution of the relaxed problem is the intersection of the constraint set {cal C} = { F ,|, J(F) leq sigma }

and the smallest sub-level set of

that touches {cal C}

Alternating direction method of multipliers (ADMM)

ADMM is a simple but powerful algorithm well-suited to large optimization problems. It blends the separability of the dual decomposition with the superior convergence of the method of multipliers. In the sparsity-promoting linear quadratic regulator problem, we use ADMM as the general purpose algorithm that

Sketch of the algorithm

Solution to the G-minimization problem

Since all of the above mentioned sparsity-promoting penalty functions can be written as a summation of componentwise functions, we can decompose the

-minimization problem into sub-problems expressed in terms of the individual elements of

where $V = (1/rho) Lambda^k + F^{k+1}.$ This separability of the

-minimization problem facilitates development of element-wise analytical solutions.

For sum-of-logs function, the solution to the

-minimization sub-problem depends on the parameters {gamma

. For example, the solution of

with

resembles the shrinkage operator for small values of gamma

(e.g.,

), and it resembles the truncation operator for large values of gamma

(e.g.,

Solution to the F-minimization problem

The necessary conditions for the optimality of the

-minimization problem are given by the three coupled nonlinear equations in the unknowns matrices

, and

For a fixed

, the first two equations are Lyapunov equations for the closed-loop controllability and observability gramians

and

, respectively; for fixed

and

, the third equation is a Sylvester equation for

. This structure of the necessary conditions for the optimality motivates the following iterative scheme

We have shown that the difference between the feedback gains in two consecutive steps provides a descent direction. This observation in conjunction with standard line search has allowed us to establish convergence of the iterative scheme.

Polishing

The necessary conditions for the optimality of the structured linear quadratic regulator problem are given by

where

denotes the entry-wise multiplication of two matrices, and $I_{cal S}$ is the structural identity. For example,

We have used Newton's method and employed the conjugate gradient scheme to compute the Newton direction efficiently.

Extension: Block sparsity

In many problems it is of interest to design feedback gains that have block sparse structure. In view of this, we have also considered the optimal control problem that promotes sparsity of the feedback gain at the level of the submatrices instead of at the level of the individual elements.

where $F_{ij} in R^{n_i times m_j}$ and | cdot |_F

is the Frobenius norm. We have also examined the following relaxations

Description of lqrsp.m

and the input options and returns the gamma

-parameterized family of solutions to both the sparsity-promoting optimal control problem (SP) and the structured ${cal H}_2$ problem (SH2). Input options allows users to specify the following parameters

help lqrsp

  Sparsity-Promoting Linear Quadratic Regulator

  Written by Fu Lin, January 2012

  Description:

  The sparsity-promoting linear quadratic regulator problem is solved using
  the alternating direction method of multipliers (ADMM)

        minimize J(F) + gamma * g(F)             (SP)

  where J is the closed-loop H2 norm, g is a sparsity-promoting penalty
  function, and gamma is the parameter that emphasizes the importance of
  sparsity.

  After the sparsity pattern has been identified, the structured H2 problem
  is solved

        minimize    J(F)
                                                                 (SH2)
        subject to  F belongs to identified sparsity pattern

  Syntax:

  solpath = lqrsp(A,B1,B2,Q,R,options)

  Inputs:

  (I)  State-space representation matrices {A,B1,B2,Q,R};

  (II) Options

      a) options.method specifies the sparsity-promoting penalty function g

         options.method = 'card'     --> cardinality function,
                        = 'l1'       --> l1 norm,
                        = 'wl1'      --> weighted l1 norm,
                        = 'slog'     --> sum-of-logs function,
                        = 'blkcard'  --> block cardinality function,
                        = 'blkl1'    --> sum of Frobenius norms,
                        = 'blkwl1'   --> weighted sum of Frobenius norms,
                        = 'blkslog'  --> block sum-of-logs function;

      b) options.gamval         --> range of gamma values;
      c) options.rho            --> augmented Lagrangian parameter;
      d) options.maxiter        --> maximum number of ADMM iterations;
      e) options.blksize        --> size of block sub-matrices of F;
      f) options.reweightedIter --> number of iterations for the reweighted
                                    update scheme.

  The default values of these fields are

  options.method         = 'wl1';
  options.gamval         = logspace(-4,1,50);
  options.rho            = 100;
  options.maxiter        = 1000;
  options.blksize        = [1 1];
  options.reweightedIter = 3.

  Output:

  solpath -- the solution path parameterized by gamma -- is a structure
  that contains:

  (1) solpath.F    --> feedback gains resulting from the control problem
                       (SP);
  (2) solpath.Fopt --> feedback gains resulting from the structured control
                       problem (SH2);
  (3) solpath.J    --> quadratic performance of the solutions to (SP);
  (4) solpath.Jopt --> optimal quadratic performance of the solutions to
                       (SH2);
  (5) solpath.nnz  --> number of nonzero elements (blocks) of optimal
                       sparse (block sparse) feedback gains;
  (6) solpath.gam  --> values of sparsity-promoting parameter gamma.

  Reference:

  F. Lin, M. Fardad, and M. R. Jovanovic
  ``Design of optimal sparse feedback gains via the alternating direction method of multipliers'' 
  IEEE Trans. Automat. Control, vol. 58, no. 9, pp. 2426-2431, September 2013.

  Additional information:

  http://www.umn.edu/~mihailo/software/lqrsp/

Acknowledgements

We would like to thank Stephen Boyd for encouraging us to develop this software.