Build the system

Build the system#

Algorithms to solve inclusion problems \(0 \in \sum_{i=1}^s F(\beta^*)\) are modeled using a generalized plant framework. The system (algorithmic interconnection) is specified by the operators \(F\), the network, and the controller. The system is mathematically described by

\[\begin{split}\begin{align*} \text{Operator}: & & w_k & \in F(z_k), \\ \text{Network}: & & \mat{c}{x^N_{k+1} \hl z_k \\ z_{p k} \\ y_k} &= \mat{c|cc}{A & B_z & B_{z_p} & B_u \hl C_z & D_{zd} & D_{z w_p} & D_{zu} \\ C_{z_p} & D_{z_p d} & D_{z_p w_p} & D_{z_p u} \\ C_y & D_{yd} & D_{y w_p} & D_{yu}} \mat{c}{x_k^N \hl w_k \\ w_{pk} \\ u_k}, \\ \text{Controller}: & & \mat{c}{x^c_{k+1} \hl u_k} &= \mat{c|c}{\Ac & \Bc \hl \Cc & \Dc } \mat{c}{x^c_k \hl y_k}, \end{align*}\end{split}\]

where the specific signals are

State

Plant input

Plant output

\(x^N\)

Network

\(z\)

Input to operators

\(w\)

Output from operators

\(x^c\)

Controller

\(z_p\)

Performance output

\(w_p\)

Performance input

\(y\)

Output to controller

\(u\)

Input from controller

The system is programmatically described by an opt_system object:

1sys = opt_system(operators, network, controller)

Operators#

The operators argument in the system is an \(s\)-length cell array {op1, op2, op3, ...}.

Operators for simulation#

In simulation, operators{i} is the specific operator \(F_i\) used in the inclusion problem. An operator may implement the following methods:

Evaluation

Name

Operation

Forward

fw()

\(z \mapsto F_i(z)\),

Backward (with parameter \(\mathcal{W} \succ 0\))

bw()

\(z \mapsto (I - \mathcal{W} F_i)^{-1} (z)\)

Function

f()

\(z \mapsto f_i(z)\)

Supported operators for simulation include

Operator

Class Name

Description

Custom

op_sim

Implemented by anonymous functions

Quadratic

op_sim_quad

Quadratic function \(\frac{1}{2} (x - x^*)^\top M (x - x^*)\)

Least squares

op_sim_lsq

Quadratic function \(\frac{1}{2} \norm{Ax - b}^2_2\)

\(L_\infty\) (hard)

op_sim_box

Indicator function of \(L_\infty\) ball

\(L_1\) (hard)

op_sim_l1_hard

Indicator function of \(L_1\) ball

Linear quadratic game

op_sim_lq_game

Pseudogradient of game, with agent payoffs \(f_j = \frac{1}{2} x^\top Q_j x + b^\top x_j + e_j\)

Operators classes#

In analysis and synthesis, operators{i} is the operator class for which operator \(F_i\) is a member.

The two categories of operator classes are general set-valued maps and subdifferentials.

Set-valued maps#

A general set-valued map is specified by op_gen. Fields of op_gen define constraints satisfied by all \(w_1 \in F_i (z_1), w_2 \in F_i(z_2)\).

Field name

Parameter

Description

monotone

\(\mu \in \R\)

\(\langle w_1 - w_2, z_1 - z_2 \rangle \geq \mu \norm{z_1 - z_2}^2_2\)

cocoercive

\(\beta > 0\)

\(\langle w_1 - w_2, z_1 - z_2 \rangle \geq \beta \norm{w_1 - w_2}^2_2\)

lipschitz

\(L > 0\)

\(\norm{w_1 - w_2}_2 \leq L \norm{z_1 - z_2}_2\)

inverse_lipschitz

\(R > 0\)

\(\norm{z_1 - z_2}_2 \leq R \norm{w_1 - w_2}_2\)

Setting the monotone field to \(\mu \in \R\) is a description that \(F_i - \mu \ \text{Id}\) is maximal monotone. Strong monotonicity is described by \(\mu>0\), and hypo (weak) monotonicity is described by \(\mu < 0\).

Subdifferentials#

The supported subdifferentials are based on properties of proper, closed, convex (p.c.c.) functions. A p.c.c. function \(f\) satisfies the properties

Proper

\(f(x) > -\infty\) everywhere and there is \(x\) with \(f(x) < \infty\)

Closed

The set \(\{x \mid f(x) \leq \gamma\}\) is closed for all \(\gamma \in \R\)

Convex

\(f( \alpha x + (1-\alpha)y) \leq \alpha f(x) + (1-\alpha) f(y)\) for all \(\alpha \in [0, 1]\) and \((x, y)\).

The subdifferential of a p.c.c. function \(f\) at \(x\) is the set

\[\begin{align*} \partial f(x) = \{g \mid f(y) - f(x) \geq \langle g, y-x \rangle \; \forall y \} \end{align*}\]

Indicator functions of closed, convex sets are p.c.c.

Given constants \(-\infty < m < L \leq \infty\), the set \(S_{m, L}\) is the set of functions such that

  1. \(f - \frac{m}{2}\norm{\cdot}_2^2\) is p.c.c

  2. \(\frac{L}{2} \norm{\cdot} - f\) is p.c.c. if \(L < \infty\).

\(S_{0, \infty}\) is the set of p.c.c. functions. If \(m > 0\), then every \(f \in S_{m, \infty}\) is strongly convex. If \(0 < m < L < \infty\), then every \(f \in S_{m, L}\) has \(L\)-Lipschitz gradients (is \(L\)-smooth).

The subdifferential of p.c.c. functions is extended to subdifferentials of functions \(f \in S_{m, L}\) by

\[\begin{align*} \partial f(x) := \partial \left(f - \frac{m}{2}\norm{x}_2^2\right) + m x. \end{align*}\]

Operators arising from subdifferentials are described using the classes

op_pcc

Subdifferentials of p.c.c. functions

op_sml(m, L)

Subdifferentials of \(S_{m, L}\)

op_quad(m, L)

Gradients of quadratics in \(S_{m, L}\)

Tip

op_pcc is an alias for op_sml(0, inf).

Network and controller#

In simulation and analysis, the controller is a discrete-time state space system of type ss.
The controller field is ignored in synthesis, and can therefore be set to controller = [].

The declaration network = [] is used if there are no network dynamics. If network dynamics are present, then the network is described by a genplant object (see genplant documentation for more details). The attribute P of a genplant is a discrete-time state space system of type ss.

The genplant attributes (nz, nzp, ny, nw, nwp, nu) count dimensions of the respective input and output partitions.

An example genplant declaration for a two-operator problem with one performance input and output channel is

1D = [0, 0, 1, 1, 0;
2     0, 0, 1, 0, 1;
3     1, 1, 0, 0, 0;
4     1, 0, 0, 0, 0;
5     0, 1, 0, 0, 0];
6
7n = struct('nz', 2, 'nzp', 1, 'nw', 2, ...
8'nw', 2, 'nwp', 1, 'nu', 2);     
9p = genplant(ss(D), n);

genplant can also be called without the n argument, letting the dimensions such as \(p.nw\) be set later.

The Templates page documents commands to generates common network structures. One such network structure is bridge_channel_delay, which adds time delays before and after each operator \(\{F_i\}_{i =1}^s\).

Two-operator example#

The operator class for a composite optimization problem

\[\beta^* \in \argmin_\beta f_1(\beta) + \mathbf{I}_{\norm{\cdot}_1 \leq \tau}(\beta),\]

with \(f_1 \in S_{1, 10}\) can be specified using

1op1 = op_sml(1, 10);
2op2 = op_pcc();
3operator_class = {op1, op2};

Systems for synthesis with and without network dynamics are

1%add 2-step time delays before and after \partial f1
2delay2 = bridge_channel_delay([2, 0], [2, 0]);
3sys_delay = opt_system(operator_class, delay2, []);
4
5%no network dynamics
6sys_no_network = opt_system(operator_class, [], []);

Systems for analysis of a projected gradient descent algorithm over the same networks are

 1%the controller describing projected gradient descent
 2gamma = 2/11;
 3
 4Ac = 1;
 5Bc = [-gamma, -gamma];
 6Cc = [1; 1];
 7Dc = [0, 0; 
 8     -gamma, -gamma];
 9Ts = 1; %sample time     
10
11K = ss(Ac, Bc, Cc, Dc, 1);
12
13sys_pgd_delay = opt_system(operator_class, delay2, K);
14sys_pgd_no_network = opt_system(operator_class, [], K);

Extensions#

The system description can be extended in three main capacities:

These extensions are explored in subsequent sections.