Edit on GitHub

Smoothed Spectral Abscissa (SSA)

This package computes the smoothed spectral abscissa (SSA) of square matrices, and the associated gradient, as described in:

The Smoothed Spectral Abscissa for Robust Stability Optimization , J Vanbiervliet et al , 2009. DOI: 10.1137/070704034

The SSA is a smooth upper bound to the spectral abscissa of a matrix, that is, the highest real part of the eigenvalues.

The current version implements only the "simplified" version of SSA, i.e. the one where input and output transformations are identity matrices.

Definition of SSA

Consider a square real matrix $A$, that regulates a dynamical system as follows: $\text{d} \mathbf{x}/\text{d}t = A\,\mathbf{x}$. The stability of the dynamical system can be assessed using the following quantity:

\[f(A,s) := \int_0^{\infty} \text{d}t \;\left\| \exp\left( \left(A-sI\right)t \right)\right\|^2\]

where $\left\| M \right\|^2 := \text{trace}\left(M \,M^\top \right)$.

For a given $\varepsilon$, the SSA can be denoted as $\tilde{\alpha}_\varepsilon(A)$. By definition, it satisfies the following equality:

\[f(A,\tilde{\alpha}_\varepsilon(A)) = \frac{1}{\varepsilon}\]

The SSA is an upper bound to the spectral abscissa (SA) of $A$. If matrix $A$ is modified so that its SSA is below 0, the SA of $A$ will also be negative, which guarantees the stability of the associated linear dynamics.

Usage

This module does not export functions in the global scope. It is therefore convenient to shorten the module name as follows:

using SmoothedSpectralAbscissa ; const SSA=SmoothedSpectralAbscissa

It then becomes possible to use the shorter notation SSA.foo in place of SmoothedSpectralAbscissa.foo.

The functions below compute the SSA (and its gradient) for a matrix $A$.

SmoothedSpectralAbscissa.ssa — Function
ssa(A,ssa_eps=nothing) -> ssa_val

Computes the smoothed spectral abscissa (SSA) of matrix A (with identity input-output weighting matrices). If ssa_eps is not specified, the default value is set by default_eps_ssa(A)

Arguments

  • A::Matrix{<:Real}: A square matrix
  • ssa_eps::Union{Nothing,R}=nothing The $\varepsilon$ parameter associated with the SSA computation. If not specified, it is set by default_eps_ssa(A)
  • io_matrices=SmoothedSpectralAbscissa.IOIdentity : input and output matrix. WARNING for now the only option is identity.

Returns

  • ssa_val<:Real: this is the $\tilde{\alpha}_\varepsilon(A)$
source
SmoothedSpectralAbscissa.ssa_withgradient — Function
  ssa_withgradient(A,ssa_eps) -> (ssa_val,gradient_matrix)

Computes the Smoothed Spectral Abscissa (SSA) of matrix A and also its gradient with respect to each element of A. If ssa_eps is not specified, the default value is set by default_eps_ssa(A)

In case you need to call the SSA iteratively (e.g. gradient-based optimization), please consider pre-allocating memory and using ssa_simple!(...).

Arguments

  • A::Matrix{<:Real}: A square matrix
  • ssa_eps::Union{Nothing,R}=nothing The $\varepsilon$ parameter associated with the SSA computation. If not specified, it is set by default_eps_ssa(A)
  • io_matrices=SmoothedSpectralAbscissa.IOIdentity : input and output matrix. WARNING for now the only option is identity.

Returns

  • ssa_val<:Real: this is the $\tilde{\alpha}_\varepsilon(A)$
  • gradient_matrix::Matrix{<:Real}: the gradient of the SSA w.r.t. each entry of matrix A
source

Examples

  1. Comparison of SA and SSA
  2. Stability-optimized linear systems
  3. Optimization of excitatory/inhibitory recurrent neural network

Advanced Interface

When the SSA is used as optimization objective, it is convenient to use the advanced interface to avoid memory reallocation. The memory is pre-allocated in an object of type SSA.SSAlloc, which can then be used to call the SSA.ssa_simple(...) function multiple times.

SmoothedSpectralAbscissa.SSAAlloc — Type
    SSAAlloc(n::Integer) -> SSAAlloc

Memory allocation to avoid re-allocating space for repeated SSA computations.

Arguments

  • n::Integer: the size of the matrix (or matrices) on which the SSA will be computed
source
    SSAAlloc(A::Matrix) -> SSAAlloc

Memory allocation to avoid re-allocating space for repeated SSA computations. This corresponds to SSAAlloc(size(A,1))

source

Once the space is allocated, the SSA and its gradient can be computed by the following function.

SmoothedSpectralAbscissa.ssa! — Function
ssa!(A,grad,PQ,ssa_eps=nothing ;
    io_matrices=SmoothedSpectralAbscissa.IOIdentity,
    optim_method=SmoothedSpectralAbscissa.OptimOrder2) -> ssa_value

Computes the smoothed spectral abscissa (SSA) of matrix A and its gradient (optionally). If ssa_eps is not specified, the default value is set by default_eps_ssa(A)

Arguments

  • A::Matrix{<:Real}: A square matrix
  • grad::Union{Nothing,Matrix{<:Real}}: nothing skips the gradient computation. To compute the gradient, provide a matrix grad of the same size as A. The matrix will be rewritten in-place with entries $\frac{\partial\; \tilde{\alpha}_\varepsilon(A)}{\partial\; A_{i,j}}$
  • alloc::SSAAlloc : Pre-allocated matrices for iterative computations. Can be generated by SSAAlloc(A)
  • ssa_eps::Union{Nothing,R}=nothing The $\varepsilon$ parameter associated with the SSA computation. If not specified, it is set by default_eps_ssa(A)
  • io_matrices=SmoothedSpectralAbscissa.IOIdentity : input and output matrix. WARNING for now the only option is identity.
  • optim_method=SmoothedSpectralAbscissa.OptimOrder2 : root finding algorithm. Two methods implemented: OptimOrder2 and OptimNewton.

Returns

  • ssa_value<:Real: this is $\tilde{\alpha}_\varepsilon(A)$
source

Index