GRAPHSP – Customized algorithms for topology identification and optimal design of noisy networks

dmdsp-visual 

Sepideh Hassan-Moghaddam and Mihailo R. Jovanovic

May 2016

Matlab Files
Download all Matlab files

Paper
arXiv:1506.03437v2

Purpose

This website provides a Matlab implementation of customized algorithms for topology identification and optimal design of undirected consensus networks with additive stochastic disturbances. By introducing ell_1-regularization into the optimal control formulation aimed at minimizing the steady-state variance amplification, this problem can be cast as a semidefinite program. Standard interior-point (IP) method solvers can be used to compute the optimal solution for small- and medium-size networks. We derive a Lagrange dual and exploit structure of the optimality conditions for undirected networks to develop three customized algorithms that are well-suited for large problems. Our customized algorithms are based on:

  • the infeasible primal-dual IP method;

  • the proximal gradient method;

  • the proximal Newton method.

The proximal gradient algorithm is a simple first-order method that updates the controller graph Laplacian via convenient use of the soft-thresholding operator. In the IP method, the Newton direction is obtained using an inexact iterative procedure based on the preconditioned conjugate gradients and, in the proximal Newton method it is computed using cyclic coordinate descent over the set of active variables. We illustrate that all of our algorithms significantly outperform the general-purpose solvers and greedy strategies and that the proximal algorithms can solve the problems with more than million edges in the controller graph in a few minutes, on a PC. We also exploit structure of connected resistive networks to demonstrate how additional edges can be systematically added in order to minimize the {cal H}_2 norm of the closed-loop system.

Problem formulation

We consider a control problem for undirected consensus networks with n nodes

 	begin{array}{rcl} 	dot{psi} 	& !! = !! & 	-  L_p  , psi  ; + ;   u ; + ; d 	[0.15cm] 	zeta 	& !! = !! & 	left[    begin{array}{c}      Q^{1/2}       0     end{array}    right]     psi 	; + ;      left[  	begin{array}{c}      0       R^{1/2}     end{array}    right] u 	[0.35cm] 	u 	& !! = !! & 	- L_x , psi 	end{array}

where d and zeta denote disturbance input and performance output, psi is the state of the network, and u is the control input. Symmetric ntimes n matrices L_p and L_x are Laplacians of the plant and the controller, and matrices Q and R denote state and control weights in the optimal control problem. Upon closing the loop we obtain

 	begin{array}{rcl} 	dot{psi} 	& !! = !! & 	-  left( L_p  , +  ,  L_xright)  psi  ; + ;  d 	[0.15cm] 	zeta 	& !! = !! & 	left[    begin{array}{c}      Q^{1/2}       - R^{1/2} L_x     end{array}  right]  psi. 	end{array}

Our objective is to identify the optimal topology for L_x and to design the corresponding edge weights x in order to achieve the desired tradeoff between controller sparsity and network performance. The performance is quantified by the steady-state variance amplification of the stochastically-forced network (from the white-in-time input d to the performance output zeta which penalizes deviation from consensus and control effort).

To achieve consensus in the absence of disturbances, the closed-loop network has to be connected. This amounts to positive definiteness of the ‘‘strengthened’’ graph Laplacian of the closed-loop network

 	G 	; 	mathrel{mathop:}= 	; 	L_p 	; + ; 	L_x 	; + ; 	(1/n) , mathbf{1} mathbf{1}^T 	; 	= 	; 	G_p 	; + ; 	E , ensuremath{mathrm{diag}} left( x right) E^T 	; 	succ 	;     0

where L_x = E , ensuremath{mathrm{diag}} left( x right) E^T, E in mathbf{R}^{ntimes m} is the given incidence matrix of the controller graph, x in mathbf{R}^m is the vector of controller edge weights, and

 	G_p 	; mathrel{mathop:}= ; 	L_p   	; + ;  	(1/n) , mathbf{1} mathbf{1}^T.

Structural restrictions on the Laplacian matrices introduce an additional constraint on G,

 	G , mathbf{1} 	; = ; 	mathbf{1}.

Sparsity-promoting optimal control problem

The steady-state amplification of white-in-time disturbances is determined by the {cal H}_2 norm of stochastically-forced network,

     | H |_2^2     ; = ;     frac{1}{2}     langle {G^{-1},Q + L_x , R , L_x} rangle     ; =mathrel{mathop:} ;     frac{1}{2}     ,     J (G,x).

The objective function J can be expressed as

 	J ( G, x ) 	, = ,    	langle {G^{-1},Q_p} rangle 	, + ,     ensuremath{mathrm{diag}} 	left( 	E^{T} R , E 	right)^T 	! 	x 	, - ,      langle {R,L_p}rangle      , - ,     1

where

 	begin{array}{rcl} 	Q_p 	& 	!! 	mathrel{mathop:}= 	 !! 	 & 	Q     ; + ;     (1/n)     ,     mathbf{1} mathbf{1}^{T} 	; + ; 	L_p , R , L_p. 	end{array}

The problem of designing a controller graph that provides an optimal tradeoff between the {cal H}_2 performance of the closed-loop network and the controller sparsity can be formulated as

 	begin{array}{rl} 	{rm minimize} 	& 	langle{G^{-1},Q_p}rangle 	, + ;     ensuremath{mathrm{diag}} 	left( 	E^{T} R , E 	right)^T 	! 	x 	; + ; 	gamma ; | x |_1 	[0.25cm] 	{rm subject~to} 	&     G_p     ,  + ,     E , ensuremath{mathrm{diag}} , ( x ) , E^{T}     , succ , 0 	end{array}       hspace{1.cm}     {rm (SP)}

where the ell_1 norm of x,

 	| x |_1 	, mathrel{mathop:}= , 	sum_{l , = , 1}^{m} ;  |x_l|

is introduced as a proxy for inducing sparsity. In (SP), the positive definite matrix G in {bf R}^{n times n} and the vector of the edge weights x in {bf R}^m are optimization variables; the problem data is given by the positive regularization parameter gamma, the plant graph Laplacian L_p, the state and control weights Q and R, and the incidence matrix of the controller graph E.

Since minimization of the Lagrangian associated with (SP) does not lead to an explicit expression for the dual function, we introduce an auxiliary variable G and find the dual of. It is well-known that the consensus can be achieved even if some edge weights take negative values; e.g., see Xiao and Boyd ’04. By expressing the vector of the edge weights, x, as a difference between two non-negative vectors, x_+ and x_-,

     x     ;=;     x_+     ; - ;     x_-

the optimal control problem can be expressed as

 	!! 	begin{array}{rl} 	{rm minimize} 	& 	!! 	langle{G^{-1},Q_p}rangle 	, + , 	(gamma , mathbf{1} , + , {rm diag} left( E^{T} R , E right))^T x_{+} 	, + , 	(gamma , mathbf{1} , - , {rm diag} left( E^{T} R , E right))^T x_{-}	 	[0.25cm] 	{rm subject~to} 	& 	!!     G 	, - ,     G_p     ,  - ,     E , {rm diag} , ( x_+ , - , x_- ) , E^{T}     , = , 0     [.15cm]     &     !!     G , succ , 0,     ~~     x_{+} , geq ,0,     ~~     x_{-} , geq ,0 	end{array}     hspace{1.cm}     {rm (P)}

The Lagrange dual of the sparsity-promoting optimal control problem (P) is given by

 	begin{array}{rl} 	{rm maximize} 	& 	2 , {rm trace} 	left( 	( Q_p^{1/2} , Y , Q_p^{1/2})^{1/2} 	right) 	, - ; 	langle{Y,G_p} rangle     [0.25cm]     {rm subject~to} 	& 	|, {rm diag} left( E^{T} (Y ,-, R) , E right) |_{infty} 	, leq , gamma 	[0.15cm] 	& 	Y ; succ ; 0,     ~~   	 	Y , mathbf{1} ;=; mathbf{1} 	end{array}     hspace{1.cm}     {rm (D)}

where Y = Y^T in {bf R}^{n times n} is the dual variable associated with the equality constraint in (P).

Growing connected resistive networks

The problem of topology identification and optimal design of stochastically-forced networks has many interesting variations. An important class of problems is given by resistive networks in which all edge weights are restricted to be non-negative. Here, we study the problem of growing connected resistive networks. In this, the plant graph is connected and there are no joint edges between the plant and the controller graphs. In the absence of the sparsity-promoting term, the closed-loop network is given by a complete graph. Our objective is to add a small number of edges in order to optimally enhance the closed-loop performance.

The restriction on connected plant graphs implies positive definiteness of the strengthened graph Laplacian of the plant,

 	G_p 	; = ; 	L_p  ; + ; (1/n) , mathbf{1} mathbf{1}^T 	; succ ; 	0.

Thus,  G_p + E , {rm diag} , ( x ) , E^{T} is always positive definite for connected resistive networks. As done in problem (P), in order to determine the Lagrange dual of the optimization problem, we introduce an additional optimization variable G. The sparsity-promoting optimal control problem simplifies to

 	begin{array}{rl} 	{rm minimize} 	& 	langle{G^{-1},Q_p}rangle 	, + , 	( 	gamma , mathbf{1}     ,+,     {rm diag} 	left( 	E^{T} R , E 	right) 	)^T     x 	[0.25cm] 	{rm subject~to} 	&     G 	, - ,     G_p     ,  - ,     E , {rm diag} , (x) , E^{T}     , = , 0     [.15cm]     & 	x , geq , 0 	end{array}      hspace{1.cm}     {rm (P1)}

where the matrix G in {bf R}^{n times n} and the vector x in {bf R}^m are optimization variables. Non-negativity of the edge weights was used to write | x |_1 = sum_l x_l and to remove positive definite requirements on G.

The Lagrange dual of the sparsity-promoting optimal control problem {rm (P1)} is given by

 	begin{array}{rl} 	!!!! 	{rm maximize} 	& 	2 , {rm trace} 	left( 	( Q_p^{1/2} , Y , Q_p^{1/2})^{1/2} 	right) 	, - ; 	langle{Y,G_p}rangle     [0.25cm] 	!!!!     {rm subject~to} 	& 	{rm diag} left( E^{T} (Y ,-, R) , E right) 	; leq ; 	gamma , mathbf{1} 	[0.2cm] 	!!!! 	& 	Y ; succ ; 0,     	~~   	 	Y , mathbf{1} ;=; mathbf{1} 	end{array}     hspace{1.25cm}     {rm (D1)}

where Y is the dual variable associated with the equality constraint in {rm (P1)}.

Acknowledgements

This project is supported by the