SparsityPromoting Linear Quadratic Regulator
Introduction
lqrsp.m is a Matlab function for the design of sparse and block sparse
statefeedback gains that minimize the variance amplification (i.e., the norm)
of distributed systems. Our longterm 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.
The design procedure consists of two steps:
Identification of sparsity patterns by incorporating sparsitypromoting penalty functions
into the optimal control problem.
Optimization of feedback gains subject to structural constraints determined by the
identified sparsity patterns.
Problem formulation
Consider the following control problem
where is the exogenous input signal and is the performance output.
The matrix is a state feedback gain, and
are the state and control performance weights, and the closedloop system is given by
We study the sparsitypromoting optimal control problem
in which the closedloop norm is augmented by a function that
counts the number of nonzero elements in the feedback gain matrix . For example,
As the parameter varies over , the solution traces the optimal
tradeoff path between the quadratic performance and the feedback gain sparsity.

An example of control architectures resulting from the sparsitypromoting optimal control problem.
For the optimal controller
is obtained from the positive definite solution of the algebraic Riccati equation
Control architectures for depend on system's interconnections.

After a desired level of sparsity is achieved,
we fix the sparsity structure and find the optimal structured feedback
gain .
Relaxations of cardinality function
In addition to the cardinality function, we also consider several sparsitypromoting relaxations including
To illustrate the sparsitypromoting properties of these relaxations, let us consider the problem
of finding the sparsest feedback gain that provides a given level of performance .
Convex ( and weighted norm) and nonconvex (sumoflogs) relaxations of
the cardinality function lead to
The solution of the relaxed problem is the intersection of the constraint set
and the smallest sublevel set of that touches .
Alternating direction method of multipliers (ADMM)
ADMM is a simple but powerful algorithm wellsuited to large optimization problems. It blends the
separability of the dual decomposition with the superior convergence of the method of multipliers.
In the sparsitypromoting linear quadratic regulator problem, we use ADMM as the general purpose algorithm that
identifies sparsity patterns
provides good initial condition for structured design.
The algorithm consists of four steps:
Sketch of the algorithm
Solution to the Gminimization problem
Since all of the above mentioned sparsitypromoting penalty functions can be written as a
summation of componentwise functions, we can decompose the minimization problem into
subproblems expressed in terms of the individual elements of ,
where
This separability of the minimization problem facilitates development of elementwise analytical
solutions.
For sumoflogs function, the solution to the minimization subproblem
depends on the parameters , , . For example,
the solution of
with , resembles the shrinkage operator for
small values of (e.g., ), and it resembles the truncation operator
for large values of (e.g., ).
Solution to the Fminimization 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 closedloop 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 entrywise multiplication of two matrices, and 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.
The function that counts the number of nonzero submatrices is given by
where and is the Frobenius norm.
We have also examined the following relaxations

An example of a block sparse feedback gain with
submatrices of size
Additional information is provided in the block sparsity example.

Description of lqrsp.m
Matlab Syntax
>> solpath = lqrsp(A,B1,B2,Q,R,options);
Our Matlab function lqrsp.m takes the matrices
and the input options and returns the parameterized family of solutions to both the
sparsitypromoting optimal control problem (SP) and the structured problem (SH2).
Input options allows users to specify the following parameters
sparsitypromoting penalty function: , ,
or one of the relaxations with ;
values of and ;
maximum number of ADMM iterations;
maximum number of reweighted iterations (if weighted or weighted sum of
Frobenius norms is used);
block size of the submatrix
(if block sparsity is desired).
The parameterized output solpath is a structure that contains
solpath.F – feedback gains resulting from the control problem (SP);
solpath.Fopt – feedback gains resulting from the structured control problem (SH2);
solpath.J – quadratic performance of the solutions to (SP);
solpath.Jopt – optimal quadratic performance of the solutions to (SH2);
solpath.nnz – number of nonzero elements (blocks) of optimal sparse (block sparse)
feedback gains;
solpath.gam – values of sparsitypromoting parameter .
help lqrsp
SparsityPromoting Linear Quadratic Regulator
Written by Fu Lin, January 2012
Description:
The sparsitypromoting 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 closedloop H2 norm, g is a sparsitypromoting 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) Statespace representation matrices {A,B1,B2,Q,R};
(II) Options
a) options.method specifies the sparsitypromoting penalty function g
options.method = 'card' > cardinality function,
= 'l1' > l1 norm,
= 'wl1' > weighted l1 norm,
= 'slog' > sumoflogs function,
= 'blkcard' > block cardinality function,
= 'blkl1' > sum of Frobenius norms,
= 'blkwl1' > weighted sum of Frobenius norms,
= 'blkslog' > block sumoflogs 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 submatrices 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 sparsitypromoting 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. 24262431, 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.
This project is supported in part by the National Science Foundation under
