# Convex programming¶

A major application of RepLAB is symmetrizing convex problems to compute their optimum faster.

In particular, it supports:

## CommutantVar¶

class replab.CommutantVar(generators, sdpMatrix, sdpMatrixIsSym, matrixType, field)

Bases: `replab.Str`

Sdpvar matrices subject to symmetry constraints.

A general matrix invariant under a permutation group can be constructed with the method `fromPermutations`. `fromIndexMatrix` allows for the construction of a symmetry-invariant matrix with additional structure. Symmetry constraints can also be imposed on existing sdpvar object with the `fromSdpMatrix` constructor. If the provided SDP matrix is already known to be invariant under the group, then `fromSymSdpMatrix` can be used to only add the induced block structure onto this matrix.

The class implements basic algebra for invariant matrices, such as addition, trace, comparison, etc. These operations take precedence over matlab’s when combining a `CommutantVar` object with a matlab builtin type, such as a double matrix. Due to a bug in octave, correct precedence cannot be guaranteed when combining a `CommutantVar` object with another class object on the left, such as a sdpvar. Doing so typically results in an error. This can be avoided in two ways:

1. Always put the `CommutantVar` on the left of other class objects (e.g. write `M >= N` instead of `N <= M` if `M` is a `CommutantVar` and `N` a sdpvar object)

2. Embed the sdpvar object into a `CommutantVar` object with trivial symmetry: both `M >= N2` and `N2 >= M` are possible after defining `N2 = replab.CommutantVar.fromSdpMatrix(N, {[]})`

Warning: this object inherits from a handle object, therefore it is also a handle object. To copy this object and obtain two identical but independent objects, use the `copy` method.

See also `replab.CommutantVar.fromPermutations`,

### Own members

U_

Unitary operator block-diagonalizing the matrix

blocks

The sdp blocks corresponding to each irreducible representation

dim

matrix dimension

dimensions1

Dimensions of all irreducible representations

field

real or complex

fullBlockMatrix_

The combinations, lazy evaluated

linearConstraints

linear constraints imposed on the matrix

matrixType

full, symmetric of hermitian

multiplicities

Multipliticies of all irreducible representations

nComponents

Number of block components

sdpMatrix_

The provided or constructed sdpMatrix

types

Type of all irreducible representations

U(self)

Returns the block-diagonalizing unitary.

Returns

unitary

Return type

double matrix

Example

```>>> matrix = replab.CommutantVar.fromPermutations({[2 3 1]}, 'symmetric', 'real');
>>> matrix.U;
```

Overload of `replab.Str.additionalFields`

block(self, i)

Returns the desired block

Parameters

i (`integer`) – block component number

Returns

sdpvar block

Return type

sdpvar

Example

```>>> matrix = replab.CommutantVar.fromPermutations({[3 1 2]}, 'symmetric', 'real');
>>> matrix.block(2);
```

Block structure

Returns a 0-1-filled matrix showing the block structure of the matrix in the irreducible basis.

Returns

matrix

Return type

integer matrix

Example

```>>> matrix = replab.CommutantVar.fromPermutations({[2 3 1]}, 'symmetric', 'real');
```
compatibleWith(X, Y)

Compares the block structure

Checks whether the block structure of Y is compatible with that of X.

Parameters
Returns

integer – 0 if Y is not compatible with X 1 if Y has the block structure of X 2 if Y has the block structure of X and identical blocks in X correspond to identical blocks in Y

Return type

Measure of compatibility

Example

```>>> matrix1 = replab.CommutantVar.fromPermutations({[2 3 1]}, 'symmetric', 'real');
>>> matrix2 = replab.CommutantVar.fromPermutations({[2 1 3]}, 'symmetric', 'real');
>>> % both matrices have comparable block structures ...
>>> % ... but not in the same basis
>>> matrix1.compatibleWith(matrix2);
>>> % The following matrix has the correct structure in the right basis:
>>> matrix1.compatibleWith(M);
```
copy(rhs)

Copies a `CommutantVar` object

Creates an identical but independent copy of rhs. Modifying the copy does not modify the original object. This is useful internally.

Arg:

rhs (`CommutantVar`): object to be copied

Returns

result

Return type

`CommutantVar`

end(self, k, n)

Returns the last index

Returns the last index in an indexing expression such as self(1,2:end) or self(end).

Parameters
• k – dimension

• n – number of dimensions on which the indexing is done

Returns

result

Return type

double

eq(X, Y)

Equality constraint

The constraint is imposed through a series of equality constraint for each block. If X or Y includes linear constraints, they are also added to the result.

Parameters
Returns

constraint

Return type

constraint

Example

```>>> matrix = replab.CommutantVar.fromPermutations({[2 3 1]}, 'symmetric', 'real');
>>> F = [matrix == 0];
>>> matrix = replab.CommutantVar.fromSdpMatrix(sdpvar(3), {[2 3 1]});
>>> F = [matrix == 0];
```
static fromIndexMatrix(indexMatrix, generators, matrixType, field)

An invariant matrix with additional constraints.

Creates a `CommutantVar` matrix with additional structure. The produced sdpvar matrix:

• is invariant under the permutation group

• satisfies the structure imposed by the index matrix: two matrix elements with same index are equal to each other

This is obtained by first performing an exact Reynolds simplification of the matrix of indices so that it is invariant under the group.

Note: at the moment, only positive indices are supported.

Parameters
• indexMatrix (`integer (*,*)`) – matrix with integer values corresponding to the label of the variable at each element. The actual index values are irrelevant.

• generators (`permutation`) – a list of generators under which the matrix remains unchanged

• matrixType (`charstring`) – one of the following: ‘full’ : no particular structure ‘symmetric’ : transpose-invariant matrix ‘hermitian’ : hermitian matrix

• field (`charstring`) – matrix elements are either ‘real’ or ‘complex’

Returns

result

Return type

`CommutantVar`

Example

```>>> indexMatrix = [1 1 3 4; 1 5 6 30; 3 6 10 11; 4 30 11 15];
>>> matrix = replab.CommutantVar.fromIndexMatrix(indexMatrix, {[4 1 2 3]}, 'symmetric', 'real');
```
static fromPermutations(generators, matrixType, field)

A matrix invariant under joint permutations of lines and columns.

Creates a `CommutantVar` matrix that is invariant under joint permutations of its lines and columns by the provided generators.

Parameters
• generators (`permutation`) – list of generators under which the matrix is to remain unchanged

• matrixType (`charstring`) – one of the following: ‘full’ : no particular structure ‘symmetric’ : transpose-invariant matrix ‘hermitian’ : hermitian matrix

• field (`charstring`) – matrix elements are either ‘real’ or ‘complex’

Returns

result

Return type

`CommutantVar`

Example

```>>> matrix = replab.CommutantVar.fromPermutations({[3 1 2]}, 'symmetric', 'real');
```
static fromSdpMatrix(sdpMatrix, generators)

An sdpvar matrix with symmetry constraints

Imposes symmetry constraints onto an existing SDP matrix. This creates a `CommutantVar` matrix which satisfies both:

• the structure encoded into sdpMatrix

• invariance under joint permutations of its lines and columns by the provided generators.

The type of matrix (full/symmetric/hermitian) as well as the field (real/complex) is inferred from the provided matrix.

Parameters
• sdpMatrix (`sdpvar`) – the SDP matrix on which to impose permutation invariance

• generators (`permutation`) – a list of generators under which the matrix is to remain unchanged

Returns

result

Return type

`CommutantVar`

Example

```>>> sdpMatrix = sdpvar(3);
>>> matrix = replab.CommutantVar.fromSdpMatrix(sdpMatrix, {[3 1 2]});
```
static fromSymSdpMatrix(sdpMatrix, generators)

An invariant sdpvar matrix with symmetry constraints

Block-diagonalizes an existing SDP matrix which is already invariant under the group generators. The type of matrix (full/symmetric/hermitian) as well as the field (real/complex) is inferred from the provided matrix.

Parameters
• sdpMatrix (`sdpvar`) – the SDP matrix to block diagonlize

• generators (`permutation`) – a list of generators under which the matrix remains unchanged

Returns

result

Return type

`CommutantVar`

Example

```>>> x = sdpvar;
>>> y = sdpvar;
>>> sdpMatrix = [x y y; y x y; y y x];
>>> matrix = replab.CommutantVar.fromSymSdpMatrix(sdpMatrix, {[3 1 2]});
```
fullBlockMatrix(self)

Returns the full matrix in its block-diagonal form.

Returns

sdpvar matrix in block diagonal form

Return type

sdpvar matrix

Example

```>>> matrix = replab.CommutantVar.fromPermutations({[2 3 1]}, 'symmetric', 'real');
>>> % see(matrix.fullBlockMatrix); TODO: correct
```
fullMatrix(self)

Constructs the invariant matrix in the natural basis.

Returns

sdpvar matrix

Return type

sdpvar matrix

Example

```>>> matrix = replab.CommutantVar.fromPermutations({[2 3 1]}, 'symmetric', 'real');
>>> % see(matrix.fullMatrix); TODO: correct
```
ge(X, Y)

Greater or equal semi-definite constraint.

The constraint on the matrices are imposed through a series of constraint for each block. If X or Y includes linear constraints, they are also added to the result.

Parameters
Returns

constraint

Return type

constraint

Example

```>>> matrix = replab.CommutantVar.fromPermutations({[2 3 1]}, 'symmetric', 'real');
>>> F = [matrix >= 0];
>>> matrix = replab.CommutantVar.fromSdpMatrix(sdpvar(3), {[2 3 1]});
>>> F = [matrix >= 0];
```
getBaseMatrix(self, index)

Matrix of coefficient for a given sdp variable index

Returns the coefficients contributing the the SDP variable with given index.

Parameters

index (`integer`) – index of the sdp variable (or 0 for the constant term)

Returns

the matrix of coefficients

Return type

double matrix

getVariables(self)

Lists sdp variables used by the object

Returns the Yalmip indices of the SDP variable used by the object. If the object includes linear constraints, variables from the constraints are also counted.

Returns

vector of indices

Return type

integer row vector

Example

```>>> matrix1 = replab.CommutantVar.fromPermutations({[2 3 1]}, 'symmetric', 'real');
>>> matrix1.getVariables;
>>> matrix2 = replab.CommutantVar.fromSdpMatrix(sdpvar(3), {[2 3 1]});
>>> matrix2.getVariables;
>>> x = sdpvar;
>>> sdpMatrix = [1 x x; x 1 x; x x 1];
>>> matrix3 = replab.CommutantVar.fromSymSdpMatrix(sdpMatrix, {[2 3 1]});
>>> matrix3.getVariables;
```
gt(X, Y)

Greater than constraint.

Parameters
Returns

constraint

Return type

constraint

Returns

description of the object

Return type

charstring

hiddenFields(self)

Overload of `replab.Str.hiddenFields`

replab.Str.hiddenFields

ishermitian(self)

Tells whether the matrix is invariant under complex transposition

Returns

true iff the matrix is invariant under complex transposition

Return type

bool

Example

```>>> matrix = replab.CommutantVar.fromPermutations({[3 1 2]}, 'hermitian', 'complex');
>>> ishermitian(matrix);
```
isreal(self)

Tells whether the matrix is real

Returns

true iff the matrix is real

Return type

bool

Example

```>>> matrix = replab.CommutantVar.fromPermutations({[3 1 2]}, 'symmetric', 'real');
>>> isreal(matrix);
```
issymmetric(self)

Tells whether the matrix is invariant under transposition

Returns

true iff the matrix is invariant under transposition

Return type

bool

Example

```>>> matrix = replab.CommutantVar.fromPermutations({[3 1 2]}, 'symmetric', 'real');
>>> issymmetric(matrix);
```
ldivide(X, Y)

Element-wise left division operator

This is to be used only for division by a scalar. Use fullMatrix otherwise.

Parameters
Returns

result

Return type

`CommutantVar`

le(X, Y)

Lesser or equal semi-definite constraint.

The constraint on the matrices are imposed through a series of constraint for each block. If X or Y includes linear constraints, they are also added to the result.

Parameters
Returns

constraint

Return type

constraint

Example

```>>> matrix = replab.CommutantVar.fromPermutations({[2 3 1]}, 'symmetric', 'real');
>>> F = [matrix <= 0];
>>> matrix = replab.CommutantVar.fromSdpMatrix(sdpvar(3), {[2 3 1]});
>>> F = [matrix <= 0];
```
lt(X, Y)

Lesser than constraint.

Parameters
Returns

constraint

Return type

constraint

minus(X, Y)

Substraction operator

Parameters
Returns

result

Return type

`CommutantVar`

mldivide(X, Y)

Matrix left division operator

This is to be used only for division by a scalar. Use fullMatrix otherwise.

Parameters
Returns

result

Return type

`CommutantVar`

mrdivide(X, Y)

Matrix right division operator

This is to be used only for division by a scalar. Use fullMatrix otherwise.

Parameters
Returns

result

Return type

`CommutantVar`

mtimes(X, Y)

Matrix multiplication

This is to be used only for division by a scalar. Use fullMatrix otherwise.

Parameters
Returns

result

Return type

`CommutantVar`

nbVars(self)

Returns the number of SDP variable used be the object.

Returns

number of SDP variables

Return type

integer

Example

```>>> matrix1 = replab.CommutantVar.fromPermutations({[2 3 1]}, 'symmetric', 'real');
>>> matrix1.nbVars;
>>> matrix2 = replab.CommutantVar.fromSdpMatrix(sdpvar(3), {[2 3 1]});
>>> matrix2.nbVars;
>>> x = sdpvar;
>>> sdpMatrix = [1 x x; x 1 x; x x 1];
>>> matrix3 = replab.CommutantVar.fromSymSdpMatrix(sdpMatrix, {[2 3 1]});
>>> matrix3.nbVars;
```
numel(self)

Number of elements

Returns the number of objects (i.e. 1). To obtain the number of elements in the matrix, use prod(size(self)) instead.

Returns

1

Return type

integer

Example

```>>> matrix = replab.CommutantVar.fromPermutations({[3 1 2]}, 'symmetric', 'real');
>>> numel(matrix);
```
plus(X, Y)

Parameters
Returns

result

Return type

`CommutantVar`

rdivide(X, Y)

Element-wise right division operator

This is to be used only for division by a scalar. Use fullMatrix otherwise.

Parameters
Returns

result

Return type

`CommutantVar`

see(self)

Displays internal structure of variables

Displays internal info about the structure of the matrix in full form.

`sdpvar.see`

size(self, d)

Returns the matrix size

Parameters

d (`integer, optional`) – specific dimension

Returns

• s1 (integer) – The dimension array, or first dimension if s2 is also requested

• s2 (integer) – The second dimension (optional)

Example

```>>> matrix = replab.CommutantVar.fromPermutations({[3 1 2]}, 'symmetric', 'real');
>>> size(matrix);
```
str(self)

Nice string representation

Returns

result

Return type

charstring

subsref(self, varargin)

This function is called when using the syntax ‘()’ to extract one part of a matrix.

Parameters

varargin – as usual

Returns

depends on usage

Return type

depends on the usage

Example

```>>> matrix = replab.CommutantVar.fromPermutations({[2 3 1]}, 'symmetric', 'real');
>>> matrix(1);
```
times(X, Y)

Element-wise multiplication

This is to be used only for multiplication by a scalar. Use fullMatrix otherwise.

Parameters
Returns

result

Return type

`CommutantVar`

trace(self)

Trace operator

Returns

trace

Return type

sdpvar

Example

```>>> matrix = replab.CommutantVar.fromPermutations({[2 3 1]}, 'symmetric', 'real');
>>> trace(matrix);
```
uminus(self)

Unary minus operator

Returns

result

Return type

`CommutantVar`

value(self)

Returns the current numerical value of the object.

Returns

numerical value taken by the object

Return type

double matrix

`sdpvar.value`

## SedumiData¶

class replab.SedumiData(At, b, c, K, G, rho)

A block-diagonalizing preprocessor for SDPs in SeDuMi format.

The problem data is stored in (At, b, c, K) according to the SeDuMi documentation, with size(At, 2) the number of dual variables.

We only support a single SDP block, and no other cones (so K.f = K.l = 0, K.q = K.r = [] and K.s = s).

We provide the symmetry group acting on the SDP block X, such that rho(g) * X * rho(g)’ = X for all elements g in the group G.

The finite group G and its representation rho are jointly written as follows.

Without loss of generality, a finite group can be represented by permutations. Then G is a (row) cell array containing the N generators of this permutation group.

### Own members

At

Data matrix of size n x m

Type

double

G

cell array of generators as permutations

Type

cell(1,*) of permutation

K

Cone specification (Sedumi data)

Type

struct

b

Constraint right hand side (Sedumi data)

Type

double

c

Primal objective (Sedumi data)

Type

double

m

Number of dual variables

Type

integer

rep

group representation commuting with the SDP block

Type

`Rep`

rho

Cell array of generator images defining the representation

Type

cell(1,*) of double(*,*)

s

Size of single SDP block present

Type

integer

## equivar¶

class replab.equivar(equivariant, varargin)

Bases: `replab.Obj`

Describes an equivariant YALMIP matrix variable (experimental)

The variable is defined over an equivariant space `equivariant`; it corresponds to a matrix `X` invariant under the action of a representation `repR` acting on the row space, and a representation `repC` acting on the column space: `repR.image(g) * X == X * repC.image(g)`.

Internally, the variable will be parameterized using the irreducible decomposition of both `equivariant.repR` and `equivariant.repC`, which is given by `.equivariant.decomposition`, of type `IrreducibleEquivariant`, which provides us a minimal parameterization of the different blocks.

### Own members

blocks

Matrix blocks

Type

cell(*,*) of double(*,*,*) or sdpvar(*,*,*)

equivariant

Equivariant space corresponding to this matrix

Type

`Equivariant`

double(self)

Returns the explicit double floating-point matrix corresponding to this equivar

Raises

`An error if the matrix is of type "sdpvar"`

Returns

Matrix

Return type

double(*,*)

equivar(equivariant, varargin)

Constructs an equivariant YALMIP matrix variable

There are two possibilities:

• if one of the `value` or `blocks` arguments is given, this is initialized using the argument contents,

• if none of these keyword arguments is provided, the variable is free, and all its degrees of freedom will be initialized using YALMIP variables.

Parameters
• equivariant (`Equivariant`) – Equivariant space over which this variable is defined

• value – Variable value (in the original space)

• blocks – Variable value in the minimal parameter space

Kwtype value

double(*,*) or sdpvar(*,*)

Kwtype blocks

cell(*,*) of double(*,*) or sdpvar(*,*)

issdp(self)

Returns the YALMIP constraint that this equivar is semidefinite positive

This expands the SDP constraint in the block-diagonal basis

Returns:

repC(self)

Returns the representation acting on the column space

Returns

Representation

Return type

`Rep`

repR(self)

Returns the representation acting on the row space

Returns

Representation

Return type

`Rep`

sdpvar(self)

Returns the explicit matrix corresponding to this equivar in the non-symmetry-adapted basis

Returns

Matrix

Return type

double(*,*) or sdpvar(*,*)

## equiop¶

class replab.equiop(group, source, target, sourceInjection, targetInjection)

Bases: `replab.Obj`

Describes a linear or affine map between equivariant spaces (experimental)

Formally, in MATLAB, both scalars and vectors are matrices, with one or two dimensions equal to one. Thus, `replab..equiop` describes maps between those different types of objects.

The map is defined between two spaces:

both of which must be defined over related groups, which describe the symmetries.

This `replab.equiop` is equivariant over a given `group`, and this group must be a subgroup of both `source.group` and `target.group`. The subgroup inclusion is characterized by the injection maps `sourceInjection` and `targetInjection`. These must satisfy:

• `sourceInjection.source == group`

• `sourceInjection.target == source.group`

• `targetInjection.source == group`

• `targetInjection.target == target.group`.

### Own members

group

Map equivariant group

Type

`CompactGroup`

source

Source equivariant space

Type

`Equivariant`

sourceInjection

Morphism from `group` to `source.group`

Type

`Morphism`

target

Target equivariant space

Type

`Equivariant`

targetInjection

Morphism from `group` to `target.group`

Type

`Morphism`

andThen(self, applyLast)

Composition of equivariant operators, the argument applied last

Parameters

applyLast (`replab.equiop`) – Morphism to apply second

Returns

The composition of equiops

Return type

`replab.equiop`

apply(self, X)

Computes the application of the operator to a matrix

The syntax `E.apply(X)` is equivalent to the call `E(X)`.

This method works on three argument types:

• when called on a `double` matrix, it directly applies the function and factorizes the output,

• when called on an `sdpvar` matrix, it decomposes the sdpvar and applies the user function on the components of the affine combination,

• when called on an `equivar` matrix, it computes the corresponding `sdpvar`, and applies the user function on the components as well.

In all cases it returns an `equivar` matrix.

Parameters

X (double(*,*) or sdpvar(*,*) or `equivar`) – Input matrix

Returns

Map output

Return type

`equivar`

compose(self, applyFirst)

Composition of equivariant operators, the argument applied first

Parameters

applyFirst (`replab.equiop`) – Morphism to apply first

Returns

The composition of equiops

Return type

`replab.equiop`

static generic(source, target, f, varargin)

Constructs an `replab.equiop` from a user-provided function

The user-provided function is always called on arguments of type `double`; when it is applied on variables containing sdpvars, the argument will be expanded on a linear combination of optimization variables, and the user-defined function will be called using basis matrices of type `double`.

The user-defined function may or may not support the use of sparse arguments (for example, if it uses `reshape/permute` internally). The `supportsSparse` parameter may be set accordingly.

The user-provided function must be equivariant over a group, and this group must be a subgroup of both `source.group` and `target.group`. The subgroup inclusion is characterized by the injection maps `sourceInjection` and `targetInjection`, which must satisfy `group = sourceInjection.source = targetInjection.source`.

In the case one or both of `sourceInjection` and `targetInjection` are missing, they are set to the identity isomorphism of `source.group` and `target.group` respectively.

Parameters
• source (`Equivariant`) – Source equivariant space

• target (`Equivariant`) – Target equivariant space

• f (`function_handle`) – User-defined linear or affine map

• sourceInjection – An injection from the equiop group to `source.group`

• targetInjection – An injection from the equiop group to `target.group`

• supportsSparse – Whether the user-defined function `f` may be applied on sparse matrices, default: `false`

Kwtype sourceInjection

`Morphism`, optional

Kwtype targetInjection

`Morphism`, optional

Kwtype supportsSparse

logical, optional

Returns

Super-operator between equivariant spaces

Return type

`replab.equiop`

restrict(self, injection)

Restricts the equiop to be equivariant under a subgroup of its symmetry group

Parameters

injection (`Morphism`) – Morphism from the subgroup to `group`

subsref(self, s)

MATLAB subscripted reference

Allows the use of an `replab.equiop` as if it were a function handle