Simulation

Simulation routines are explored in the Simulation page.

Simulation

alg_sim executes a given optimization algorithm, and stores the output in an alg_sim_out object.

class simulator.alg_sim

ALG_SIM algorithm simulator, execution of the algorithmic interconnection

Plots the procedure to solve \(0 \in \sum_{i=0}^s F_i(\beta^*)\)

Constructor Summary

alg_sim(sys, d, sampler)

ALG_SIM Construct an alg_sim object

Parameters:

• sys – system to simulate

• d – number of dimensions (multiplicity of kronecker lift)

• c – number of partitions of the dimension/coordinate blocks

• sampler – random sampler code used in the algorithm execution.

Property Summary

EQUALITY

Is an op_sim_equality object present? True if so.

c

number of partitions of dimension

d

number of dimensions (kronecker lift)

sampler

random sample routines

sys

system to simulate

Method Summary

sim(T)

SIM: simulate a trajectory execution

Parameters:

T – Number of steps in execution

Returns:

ssim (alg_sim_out) – struct that stores the algorithm execution. Each output is indexed by time

class simulator.alg_sim_out

ALG_SIM_OUT output of an alg_sim simulation routine

Constructor Summary

alg_sim_out()

ALG_SIM_OUT construct this container for output. This gets filled by alg_sim.

Property Summary

abs_ferr

l1 norm of error in function output

eq

Equality constraint error norm(Ez - b)

f

function values (if applicable)

ferr

error in function value

k

time index

mode

mode of the switched system

param

parameters used

res_w

optimality error norm(sum(w))

res_z

consensus error norm(z - average(z))

s

number of oracles (in bind)

sq_uerr

square of error in controller output

sq_werr

square of error in oracle output (subgradients)

sq_xcerr

square of error in state of network

sq_xnerr

square of error in state of network

sq_yerr

square of error in controller input

sq_zerr

square of error in oracle input (iterates)

u

controller output/system input

uerr

error in controller output

w

input to the operators

werr

error in oracle output (subgradients)

wp

performance input

xc

states of the controller

xcerr

error in state of network

xn

states of the network

xnerr

error in state of network

y

controller input/system output

yerr

error in controller input

z

output of the operators

zerr

error in oracle input (iterates)

zp

performance output

Random sampling is provided by specifying (anonymous) methods in alg_sim_sampler

class simulator.alg_sim_sampler

alg_sim_SAMPLER sampler for algorithm simulation random generation

Constructor Summary

alg_sim_sampler()

alg_sim_samplerconstruct a sampler

Property Summary

param

parameters at each time (transition rule)

param0

initial parameters

wp

performance input

x0

initial state

Operators

The operators are defined by op_sim classes. Each operator \(F\) has three core routines:

Evaluation	Name	Operation
Forward	fw	\(z \mapsto F(z)\),
Backward	bw	\(z \mapsto (I - \Dcl F)^{-1} (z)\)
Function	f	\(z \mapsto f(z)\)

At least one of fw and bw must be defined.

Function evaluation is supported if the operator \(F\) is the subdifferential of a function \(f\). When \(F\) is the psuedogradient of a game with multiple agents, \(f\) can be defined as the vector of payoff functions for each agent. If \(f\) is undefined, then f returns the empty set [].

class simulator.op_sim.op_sim

Bases: simulator.op_sim.op_sim_interface

OP_SIM an operator used for the purposes of simulation (algorithm execution).

Constructor Summary

op_sim(fw, bw, f)

OP_SIM operator used in algorithm simulation

Parameters:

• fw – forward evalution

• bw – backward evalution

• f – function evalution

Property Summary

bw_func

backward evaluation (e.g. proximal operator)

f_func

function value (or function values in a game)

fw_func

forward evaluation (e.g. gradient)

Method Summary

bw(k, D, v, param)

backwards evaluation of an oracle, generalization of a proximal evaluation with preconditioner D

Parameters:

• k (int) – time index

• D – prox parameter

• v – input to proximal oracle

• param – parameter structure for the operator

Returns:

z – the z such that z = (I - D F)^(-1)(v)

f(k, z, param)

function value evaluation, if the operator has a potential could also be a vector of function evaluations in a game.

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

f_out – f_out = f(z) if F = partial f.

fw(k, z, param)

forward evaluation of an oracle w = F(z)

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

w – the w such that w = F(z)

class simulator.op_sim.op_sim_box

Bases: simulator.op_sim.op_sim_interface

OP_SIM_BOX a projection onto a box this includes a hard \(L_\infty\) norm as a special case

Constructor Summary

op_sim_box(BOX)

OP_SIM_BOX Constructor for box constraint

Property Summary

BOX

size of the box

Method Summary

bw(k, D, v, param)

backwards evaluation of an oracle, generalization of a proximal evaluation with preconditioner D

Parameters:

• k (int) – time index

• D – prox parameter

• v – input to proximal oracle

• param – parameter structure for the operator

Returns:

z – the z such that z = (I + D F)^(-1)(v)

f(k, z, param)

primal residual for the equality constraint

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

f_out – f_out = norm(Ez - b)

fw(k, z, param)

forward evaluation of the procedure oracle w = E’(E z- b)

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

w – the \(w\) such that \(w = F(z)\)

class simulator.op_sim.op_sim_equality

Bases: simulator.op_sim.op_sim_interface

OP_SIM_EQUALITY an affine mapping used to enforce an equality constraint \(Ez = b\)

implemented as \(z \mapsto E^\top (Ez - b)\) with E full row rank

Constructor Summary

op_sim_equality(E, b)

OP_SIM_EQUALITY Constructor for equatlity constraint

Property Summary

E

Matrix in the equality constraint

b

function value (or function values in a game)

Method Summary

bw(k, D, v, param)

backwards evaluation of an oracle, generalization of a proximal evaluation with preconditioner D

Parameters:

• k (int) – time index

• D – prox parameter

• v – input to proximal oracle

• param – parameter structure for the operator

Returns:

z – the z such that z = (I - D F)^(-1)(v)

f(k, z, param)

primal residual for the equality constraint

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

f_out – f_out = norm(Ez - b)

fw(k, z, param)

forward evaluation of the procedure oracle w = E’(E z- b)

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

w – the w such that w = F(z)

class simulator.op_sim.op_sim_interface

OP_SIM_INTERFACE functions to evaluate algorithm trajectories

Constructor Summary

op_sim_interface()

OP_SIM_INTERFACE blank constructor

Method Summary

blocksize(v)

BLOCKSIZE compute the coordinate lift/size of blocks used for backward evaluations

Parameters:

v – point to perform backward evaluation

Returns:

dl – size of coordinate blocks

class simulator.op_sim.op_sim_l1_hard

Bases: simulator.op_sim.op_sim_interface

OP_SIM_l1_hard a projection onto an L1 ball

Constructor Summary

op_sim_l1_hard(tau)

OP_SIM_L1_hard constructor for l1 norm ball

operations used in the evaluation of the operator

Parameters:

tau – radius

Property Summary

tau

radius of L1 norm ball

Method Summary

bw(k, D, v, param)

backwards evaluation of an oracle, generalization of a proximal evaluation with preconditioner D

Parameters:

• k (int) – time index

• D – prox parameter

• v – input to proximal oracle

• param – parameter structure for the operator

Returns:

z – the z such that z = (I + D F)^(-1)(v)

f(k, z, param)

primal residual for the equality constraint

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

f_out – f_out = norm(Ez - b)

fw(k, z, param)

forward evaluation of the procedure oracle w = E’(E z- b)

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

w – the w such that w = F(z)

class simulator.op_sim.op_sim_LQ_game

Bases: simulator.op_sim.op_sim_interface

OP_SIM_LQ_GAME pseudogradient of a linear quadratic game

Agent payoffs are \(J_i(x) = \frac{1}{2}x^\top Q_i x + b_i^\top x + e_i\). The goal is to find a (generalized variational) Nash equilibrium of the game.

Constructor Summary

op_sim_LQ_game(Q, b, e, n)

OP_SIM_LQ_GAME constructor for the pseudogradient

operations used in the evaluation of the operator

Parameters:

• Q (cell) – each agent’s quadratic term

• b (cell) – each agent’s linear term

• c (cell) – each agent’s constant term

• n (int) – number of inputs per agent, sum(n) = length(b)

Property Summary

Q

quadratic term (cell)

Q_all

matrix term in pseudogradient

b

linear term (cell)

b_all

linear term in pseudogradient

e

constant term (cell)

n

partition of agents

Method Summary

bw(k, D, v, param)

backwards evaluation of an pseudogradient, generalization of a proximal evaluation with preconditioner D

Parameters:

• k (int) – time index

• D – prox parameter

• v – input to proximal oracle

• param – parameter structure for the operator

Returns:

z – the z such that z = (I + D F)^(-1)(v)

coco()

cocoercivity property of the game

f(k, z, param)

payoff functions of the game

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

f_out – f_out = [J_1, J_2, …, J_n]

fw(k, z, param)

forward evaluation of the pseudogradient map

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

w – the w such that w = F(z)

lipschitz()

lipschitz constant of the game

monotone()

montonocity constant of the game

class simulator.op_sim.op_sim_lsq

Bases: simulator.op_sim.op_sim_interface

OP_SIM_LSQ a least squares cost for algorithm simulation

\(f = (1/2) ||A z - b||_2^2\)

Constructor Summary

op_sim_lsq(A, b)

OP_SIM_LSQ Constructor form a quadratic function

Parameters:

• A – a rectangular matrix

• b – the reference vector

Property Summary

A

matrix in least squares

b

vector in least squares

Method Summary

bw(k, D, v, param)

backwards evaluation of an oracle, generalization of a proximal evaluation with preconditioner D

Parameters:

• k (int) – time index

• D – prox parameter

• v – input to proximal oracle

• param – parameter structure for the operator

Returns:

z – the z such that z = (I + D F)^(-1)(v)

f(k, z, param)

function value evaluation, if the operator has a potential could also be a vector of function evaluations in a game.

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

f_out – f_out = f(z) if F = partial f.

fw(k, z, param)

forward evaluation of an oracle w = F(z)

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

w – the w such that w = F(z)

class simulator.op_sim.op_sim_quad

Bases: simulator.op_sim.op_sim_interface

OP_SIM_QUAD a quadratic function for algorithm simulation

\(f = (1/2) (z-z^*)' M (z-z^*)\)

Constructor Summary

op_sim_quad(M, bstar)

OP_SIM_QUAD Constructor form a quadratic function

Parameters:

• M – a symmetric matrix defining the quadratic form

• bstar – critical point to the unconstrained quadratic minimization problem is a function of k.

Property Summary

M

quadratic matrix

bstar

critical point to the unconstrained quadratic minimization problem

Method Summary

bw(k, D, v, param)

backwards evaluation of an oracle, generalization of a proximal evaluation with preconditioner D

Parameters:

• k (int) – time index

• D – prox parameter

• v – input to proximal oracle

• param – parameter structure for the operator

Returns:

z – the z such that z = (I + D F)^(-1)(v)

f(k, z, param)

function value evaluation, if the operator has a potential could also be a vector of function evaluations in a game.

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

f_out – f_out = f(z) if F = partial f.

fw(k, z, param)

forward evaluation of an oracle w = F(z)

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

w – the w such that w = F(z)

class simulator.op_sim.op_tv

Bases: simulator.op_sim.op_sim_interface

OP_TV total variation norm (2d)

Constructor Summary

op_tv(lam_tv, m, n)

OP_TV_BOX constructor for l1 norm ball operations used in the evaluation of the operator

Property Summary

lam_tv

regularization for total variation

m

horizontal dimension

n

vertical dimension

Method Summary

bw(k, D, v, param)

backwards evaluation of an oracle, generalization of a proximal evaluation with preconditioner D

Parameters:

• k (int) – time index

• D – prox parameter

• v – input to proximal oracle

• param – parameter structure for the operator

Returns:

z – the z such that z = (I - D F)^(-1)(v)

f(k, z, param)

total variation penalty. Ignores the box constraint in function evaluation

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

f_out – f_out = TV(z)

fw(k, z, param)

forward evaluation of the procedure oracle w = E’(E z- b)

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

w – the w such that w = F(z)

class simulator.op_sim.op_tv_box

Bases: simulator.op_sim.op_sim_interface

OP_TV_BOX total variation and box constraint

Constructor Summary

op_tv_box(BOX, lam_tv, m, n)

OP_TV_BOX constructor for l1 norm ball operations used in the evaluation of the operator

Property Summary

BOX

size of box [0, BOX]

lam_tv

regularization for total variation

m

horizontal dimension

n

vertical dimension

Method Summary

bw(k, D, v, param)

backwards evaluation of an oracle, generalization of a proximal evaluation with preconditioner D

Parameters:

• k (int) – time index

• D – prox parameter

• v – input to proximal oracle

• param – parameter structure for the operator

Returns:

z – the z such that z = (I - D F)^(-1)(v)

f(k, z, param)

total variation penalty. Ignores the box constraint in function evaluation

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

f_out – f_out = TV(z)

fw(k, z, param)

forward evaluation of the procedure oracle w = E’(E z- b)

Parameters:

• k (int) – time index

• z – input to oracle

• param – parameter structure for the operator

Returns:

w – the w such that w = F(z)