15.3 Data Structures and Notation

We specify the notation and data structures used in the interface.

Problem definition

  • prob — describes an optimization problem.

  • accs — structure of affine conic constraints.

  • names — names of objects in the optimization problem.

  • barc, bara, barf — description of the semidefinite part.

Solutions

Other

15.3.1 Notation

The mathematical formulations of problem types solvable by MOSEK are discussed in full detail in Sec. 12 (Problem Formulation and Solutions). Here we summarize them in the context of the Optimization Toolbox for MATLAB API.

Linear problem

A linear problem has the form:

(15.1)\[\begin{split}\begin{array}{lccccl} \mbox{minimize} & & & c^T x+c^f & & \\ \mbox{subject to} & l^c & \leq & A x & \leq & u^c, \\ & l^x & \leq & x & \leq & u^x. \end{array}\end{split}\]

It has \(n\) variables and \(m\) linear constraints. See Sec. 12.1 (Linear Optimization).

Conic problem

A conic problem with affine conic constraints (ACC) is an extension of a linear problem and has the form:

(15.2)\[\begin{split}\begin{array}{lccccl} \mbox{minimize} & & & c^T x+ \langle \barC,\barX\rangle + c^f & & \\ \mbox{subject to} & l^c & \leq & A x + \langle \barA,\barX\rangle & \leq & u^c, \\ & l^x & \leq & x & \leq & u^x, \\ & & & Fx+\langle \barF,\barX\rangle +g & \in & \D, \\ & & & \barX & \in & \PSD, \end{array}\end{split}\]

where \(\D\) is a product of domains from Sec. 15.8 (Supported domains) and \(\PSD\) is a product of PSD cones meaning that \(\barX\) is a sequence of PSD matrix variables. The available conic domain types are listed in Sec. 15.8 (Supported domains).

Quadratic and quadratically constrained problems

A problem with quadratic objective or constraints has the form:

(15.3)\[\begin{split} \begin{array}{lccccl} \mbox{minimize} & & & \frac12 x^TQ^ox + c^T x+c^f & & \\ \mbox{subject to} & l^c & \leq & \frac12 x^TQ^cx+ A x & \leq & u^c, \\ & l^x & \leq & x & \leq & u^x. \end{array}\end{split}\]

It has \(n\) variables, and \(m\) constraints. The matrix \(Q^o=(q_{ij}^o)_{i=1,\ldots,n,j=1,\ldots,n}\) must be symmetric positive semidefinite. See also Sec. 12.4 (Quadratic and Quadratically Constrained Optimization). Each of the matrices \(Q^i=(q_{jk}^i)_{j=1,\ldots,n,k=1,\ldots,n}\) for \(j=1\ldots,m\) must be

  • negative semidefinite if \(-\infty < l_i^c\), \(u_i^c=+\infty\),

  • positive semidefinite if \(-\infty = l_i^c\), \(u_i^c<+\infty\),

  • zero otherwise.

Mixed-integer problems

All problems without semidefinite variables or domains may be integer-constrained, i.e., for some set \(\mathcal{J}\subseteq\{1,\ldots,n\}\) we require

(15.4)\[x_j \in\integral \mbox{ for all } j \in \mathcal{J}\]

Minimization vs. Maximization

The objective of every problem can be maximized rather than minimized without any change. In case of quadratic problems the matrix \(Q^o\) must be negative semidefinite.

Data specification in MATLAB

  • The linear constraint matrix \(A=(a_{ij})_{i=1\ldots,m,j=1,\ldots,n}\) must be a sparse matrix. The dimensions of \(A\) are used to determine the number of constraints \(m\) and the number of variables \(n\) in the problem.

  • The affine conic constraint matrix \(F=(f_{ij})_{i=1\ldots,k,j=1,\ldots,n}\) must be a sparse matrix. The dimensions of \(F\) are used to determine the total dimension of all conic domains in \(\D\).

  • The symmetric matrices \(Q^o\), \(Q^i\), \(\barC_j\), \(\barA_{ij}\), \(\barF_{ij}\) are specified in sparse triplet format discarding zero elements, and since they are symmetric, only the lower triangular parts should be specified. A generic matrix \(M\) specified in sparse triplet format is given by three arrays subi, subj and val of the same length such that

    \[M_{\mathtt{subi[t]},\mathtt{subj[t]}} = \mathtt{val[t]},\ \quad t=1,\ldots,\mathtt{len(val)}\]

  • For a specification of the domains \(\D\) see accs.

  • For a specification of the semidefinite part see barf, bara and barc.

The parameters of the optimization problem are stored using one or more subfields of the prob structure using the naming convention in Table 15.1. Only a is obligatory. All other fields are optional depending on what problem type is defined.

Table 15.1 The relation between fields and problem parameters

Field name

Type

Dimension

Problem parameters

a

sparse matrix

\(m \times n\)

\(a_{ij}\)

c

double[]

\(n\)

\(c_j\)

cfix

double

\(1\)

\(c^f\)

blc

double[]

\(m\)

\(l_i^c\)

buc

double[]

\(m\)

\(u_i^c\)

blx

double[]

\(n\)

\(l_j^x\)

bux

double[]

\(n\)

\(u_j^x\)

ints.subs

int[]

\(|\mathcal{J}|\)

\(\mathcal{J}\)

cones

cones

\(\K\)

f

sparse matrix

\(k\times n\)

\(F\)

g

double[]

\(k\)

\(g\)

bardim

int[]

\(s\)

\(r_j\)

barc

barc

\(\barC_j\)

bara

bara

\(\barA_{ij}\)

barf

barf

\(\barF_{ij}\)

qosubi

int[]

len(qoval)

\(q_{ij}^o\), sparse rep.

qosubj

int[]

len(qoval)

\(q_{ij}^o\), sparse rep.

qoval

double[]

len(qoval)

\(q_{ij}^o\), sparse rep.

qcsubk

int[]

len(qcval)

\(q_{ij}^k\), sparse rep.

qcsubi

int[]

len(qcval)

\(q_{ij}^k\), sparse rep.

qcsubj

int[]

len(qcval)

\(q_{ij}^k\), sparse rep.

qcval

double[]

len(qcval)

\(q_{ij}^k\), sparse rep.

The int type indicates that the field must contain an integer value, double indicates any real number. This distinction is only a convenience for the reader — all actual data structures in MATLAB are ordinary matrices/arrays of floating-point numbers.

The sparse representation of quadratic terms is:

(15.5)\[\begin{split}\begin{array}{l} q_{\mathtt{qosubi(t)},\mathtt{qoval(t)} }^o = \mathtt{qoval(t)},\quad t=1,2,\ldots ,\mathtt{length(qoval)}, \\ q_{\mathtt{qcsubi(t)},\mathtt{qcsubj(t)}}^{\mathtt{qcsubk(t)}} = \mathtt{qcval(t)},\quad t=1,2,\ldots ,\mathtt{length(qcval)}. \end{array}\end{split}\]

Since \(Q^o\), \(Q^i\) are by assumption symmetric, all elements are assumed to belong to the lower triangular part. If an element is specified multiple times, the different elements are added together.

15.3.2 Data Types and Structures

prob

The prob data structure is used to communicate an optimization problem to MOSEK or for MOSEK to return an optimization problem to the user. It defines an optimization problem using a number of subfields. Most of the fields are optional, depending on what problem type is being solved.

Fields

  • names (names) – A structure which contains the names of the problem, variables, constraints and so on.

  • a (double[][]) – The linear constraint matrix. It is obligatory, and its dimensions define the number of variables and constraints. It must be a sparse matrix. This field should always be defined, even if the problem does not have any constraints. In that case a sparse matrix having zero rows and the correct number of columns is the appropriate definition of the field.

  • c (double[]) – Linear term in the objective.

  • cfix (double) – Fixed term in the objective.

  • blc (double[]) – Lower bounds of the constraints. \(-\infty\) denotes an infinite lower bound. If the field is not defined or blc==[], then all the lower bounds are assumed to be equal to \(-\infty\).

  • buc (double[]) – Upper bounds of the constraints. \(\infty\) denotes an infinite upper bound. If the field is not defined or buc==[], then all the upper bounds are assumed to be equal to \(\infty\).

  • blx (double[]) – Lower bounds on the variables. \(-\infty\) denotes an infinite lower bound. If the field is not defined or blx==[], then all the lower bounds are assumed to be equal to \(-\infty\).

  • bux (double[]) – Upper bounds on the variables. \(\infty\) denotes an infinite upper bound. If the field is not defined or bux==[], then all the upper bounds are assumed to be equal to \(\infty\).

  • bardim (int[]) – A list with the dimensions of the semidefinite variables.

  • barc (barc) – A structure for specifying \(\barC_j\).

  • bara (bara) – A structure for specifying \(\barA_{ij}\).

  • qosubi (int[]) – \(i\) subscripts in the sparse specification of \(q_{ij}^o\) in \(Q^o\). See (15.5).

  • qosubj (int[]) – \(j\) subscripts in the sparse specification of \(q_{ij}^o\) in \(Q^o\). See (15.5).

  • qoval (double[]) – Numerical values in the sparse specification of \(q_{ij}^o\) in \(Q^o\). See (15.5).

  • qcsubk (int[]) – \(k\) subscripts in the sparse specification of \(q_{ij}^k\) in \(Q^k\). See (15.5)

  • qcsubi (int[]) – \(i\) subscripts in the sparse specification of \(q_{ij}^k\) in \(Q^k\). See (15.5)

  • qcsubj (double[]) – \(j\) subscripts in the sparse specification of \(q_{ij}^k\) in \(Q^k\). See (15.5)

  • qcval (double[]) – Numerical values in the sparse specification of \(q_{ij}^k\) in \(Q^k\). See (15.5)

  • accs (accs) – A structure defining the structural data (list of domains) for affine conic constraints (ACC), see (15.2).

  • f (double[][]) – The matrix of affine conic constraints. It must be a sparse matrix.

  • g (double[]) – The constant term of affine conic constraints. If not present or g==[] it is assumed \(g=0\).

  • barf (barf) – A structure for specifying \(\barF_{ij}\).

  • cones (cones) – Deprecated.

  • ints.sub (int[]) – A list of indexes of integer-constrained variables. ints.sub is identical to the set \(\mathcal{j}\) in (15.4).

  • sol (solver_solutions) – A structure containing a guess on the optimal solution which some of the optimizers in MOSEK may exploit.

  • primlarepair (primal_repair) – Specification of primal feasibility repair. See Sec. 14.2.1.1 (Using the automatic repair tool).

  • prisen (prisen) – Request sensitivity analysis. See Sec. 14.3 (Sensitivity Analysis).

  • duasen (duasen) – Request sensitivity analysis. See Sec. 14.3 (Sensitivity Analysis).

res

Contains a response from mosekopt.

Fields
solver_solutions

It contains informations about initial/final solutions. Availability of solutions depends on the problem/algorithm type, see Sec. 7.1.2 (Available solutions).

Fields
solution

Stores information about one solution. See Sec. 7.1.2 (Available solutions).

Fields

  • prosta (string) – Problem status (prosta).

  • solsta (string) – Solution status (solsta).

  • skc (string[]) – Linear constraint status keys (stakey).

  • skx (string[]) – Variable status keys (stakey).

  • skn (string[]) – Conic constraint status keys (stakey, not in basic solution).

  • xc (double[]) – Constraint activities, i.e., \(x_c = Ax\) where \(x\) is the optimal solution.

  • xx (double[]) – The optimal \(x\) solution.

  • barx (list) – Semidefinite variable solution (not in basic solution).

  • y (double[]) – Identical to sol.slc-sol.suc (not in integer solution).

  • slc (double[]) – Dual variable for constraint lower bounds (not in integer solution).

  • suc (double[]) – Dual variable for constraint upper bounds (not in integer solution).

  • slx (double[]) – Dual variable for variable lower bounds (not in integer solution).

  • sux (double[]) – Dual variable for variable upper bounds (not in integer solution).

  • snx (double[]) – Dual variable of conic constraints (not in basic or integer solution).

  • doty (double[]) – Dual variables of affine conic constraints (not in basic or integer solution).

  • bars (list) – Dual variable of semidefinite domains (not in basic or integer solution).

  • pobjval (double) – The primal objective value.

  • dobjval (double) – The dual objective value (not in integer solution).

names

This structure is used to store all the names of individual items in the optimization problem such as the constraints and the variables.

Fields

  • name (string) – contains the problem name.

  • obj (string) – contains the name of the objective.

  • con (cell) – a cell array where names.con{i} contains the name of the \(i\)-th constraint.

  • var (cell) – a cell array where names.var{j} contains the name of the \(j\)-th variable.

  • acc (cell) – a cell array where names.acc{j} contains the name of the \(j\)-th affine conic constraint.

  • cone (cell) – Deprecated.

  • barvar (cell) – a cell array where names.barvar{j} contains the name of the \(j\)-th semidefinite variable.

cones

Deprecated. Represents structural information for old style cones. Use accs instead. If necessary consult the manual for version 9.

accs

Represents structural information about affine conic constraints (ACC). The numerical data is contained in prob.f, prob.g and barf.

For a problem with \(s\) affine conic constraints \(Fx+\langle\barF,\barX\rangle +g\in \D\), where \(\D=\D_1\times\cdots\times\D_s\), accs is a list consisting of \(s\) concatenated conic domain descriptions. For a list of domains see Sec. 15.8 (Supported domains).

If a domain definition requires no additional parameters (quadratic, rotated quadratic, exponential, geometric mean, linear) then its description is

\[[\mathrm{type}, \mathrm{len}]\]

where \(\mathrm{type}\) is the type (domaintype) and \(\mathrm{len}\) is the length (dimension). The length must be present.

Any additional parameters defining the domain should follow. Currently this is only the case for the power cones, whose description has the form

\[[\mathrm{type}, \mathrm{len}, n_l, \alpha_1, \ldots, \alpha_{n_l}]\]

where \(n_l\) is integer and \(\alpha_1,\ldots,\alpha_{n_l}\in \real\) are the additional parameters.

Example. Suppose we have two affine conic constraints: one with a quadratic cone of dimension 5 and one with a power cone \(\POW_4^{(40,60)}\). Then \(\D = \Q^5\times \POW_4^{(40,60)}\). We specify this data as

prob.accs = [res.symbcon.MSK_DOMAIN_QUADRATIC_CONE 5 res.symbcon.MSK_DOMAIN_PRIMAL_POWER_CONE, 4, 2, 40.0, 60.0 ];
barc

Together with field bardim this structure specifies the symmetric matrices \(\barC_j\) in the objective for semidefinite problems.

The symmetric matrices are specified in block-triplet format as

\[[\barC_{\mathtt{barc.subj(t)}}]_{\mathtt{barc.subk(t)},\mathtt{barc.subl(t)}} = \mathtt{barc.val(t)},\quad t=1,2,\ldots ,\mathtt{length(barc.subj)}.\]

Only the lower triangular parts of \(\barC_j\) are specified, i.e., it is required that

\[\mathtt{barc.subk(t)} \geq \mathtt{barc.subl(t)},\quad t=1,2,\ldots ,\mathtt{length(barc.subk)},\]

and that

\[1 \leq \mathtt{barc.subk(t)} \leq \mathtt{bardim(barc.subj(t))}, \quad t=1,2,\ldots ,\mathtt{length(barc.subj)}.,\]

All the structure fields must be arrays of the same length.

Fields

  • subj (int[]) – Semidefinite variable indices \(j\).

  • subk (int[]) – \(k\) subscripts of nonzeros elements.

  • subl (int[]) – \(l\) subscripts of nonzeros elements.

  • val (double) – Numerical values.

bara

Together with the field bardim this structure specifies the symmetric matrices \(\barA_{ij}\) in the constraints of semidefinite problems.

The symmetric matrices are specified in block-triplet format as

\[[\barA_{\mathtt{bara.subi(t)},\mathtt{bara.subj(t)}}]_{\mathtt{bara.subk(t)},\mathtt{bara.subl(t)}} = \mathtt{bara.val(t)},\quad t=1,2,\ldots ,\mathtt{length(bara.subi)}.\]

Only the lower triangular parts of \(\barA_{ij}\) are specified, i.e., it is required that

\[\mathtt{bara.subk(t)} \geq \mathtt{bara.subl(t)},\quad t=1,2,\ldots ,\mathtt{length(bara.subk)},\]

and that

\[1 \leq \mathtt{bara.subk(t)} \leq \mathtt{bardim(bara.subj(t))}, \quad t=1,2,\ldots ,\mathtt{length(bara.subj)},\]

All the structure fields must be arrays of the same length.

Fields

  • subi (int[]) – Constraint indices \(i\).

  • subj (int[]) – Semidefinite variable indices \(j\).

  • subk (int[]) – \(k\) subscripts of nonzeros elements.

  • subl (int[]) – \(l\) subscripts of nonzeros elements.

  • val (double[]) – Numerical values.

barf

Together with the field bardim this structure specifies the symmetric matrices \(\barF_{ij}\) in the affine expressions appearing in affine conic constraints.

The symmetric matrices are specified in block-triplet format as

\[[\barF_{\mathtt{barf.subi(t)},\mathtt{barf.subj(t)}}]_{\mathtt{barf.subk(t)},\mathtt{barf.subl(t)}} = \mathtt{barf.val(t)},\quad t=1,2,\ldots ,\mathtt{length(barf.subi)}.\]

Only the lower triangular parts of \(\barF_{ij}\) are specified, i.e., it is required that

\[\mathtt{barf.subk(t)} \geq \mathtt{barf.subl(t)},\quad t=1,2,\ldots ,\mathtt{length(barf.subk)},\]

and that

\[1 \leq \mathtt{barf.subk(t)} \leq \mathtt{bardim(barf.subj(t))}, \quad t=1,2,\ldots ,\mathtt{length(barf.subj)},\]

All the structure fields must be arrays of the same length.

Fields

  • subi (int[]) – Indices \(i\) defining the affine row in the affine conic constraints specification.

  • subj (int[]) – Semidefinite variable indices \(j\).

  • subk (int[]) – \(k\) subscripts of nonzeros elements.

  • subl (int[]) – \(l\) subscripts of nonzeros elements.

  • val (double[]) – Numerical values.

primal_repair

A structure holding data for primal feasibility repair. If either of the subfields is missing, it assumed to be a vector with value 1 of appropriate dimension. See Sec. 14.2.1.1 (Using the automatic repair tool).

Fields

  • wlc (double[]) – Weights for lower bounds on constraints.

  • wuc (double[]) – Weights for upper bounds on constraints.

  • wlx (double[]) – Weights for lower bounds on variables.

  • wux (double[]) – Weights for upper bounds on variables.

prisen

A structure holding information about primal sensitivity analysis. See Sec. 14.3 (Sensitivity Analysis).

Fields
prisen_data

A structure holding information about shadow prices of constraints or variables.

Fields

  • subl (int[]) – Indices of variables/constraints to be analyzed for lower bounds.

  • subu (int[]) – Indices of variables/constraints to be analyzed for upper bounds.

  • lr_bl (double[]) – Left value \(\beta_1\) in the linearity interval for a lower bound.

  • rr_bl (double[]) – Right value \(\beta_2\) in the linearity interval for a lower bound.

  • ls_bl (double[]) – Left shadow price \(s_l\) for a lower bound.

  • rs_bl (double[]) – Right shadow price \(s_r\) for a lower bound.

  • lr_bu (double[]) – Left value \(\beta_1\) in the linearity interval for an upper bound.

  • rr_bu (double[]) – Right value \(\beta_2\) in the linearity interval for an upper bound.

  • ls_bu (double[]) – Left shadow price \(s_l\) for an upper bound.

  • rs_bu (double[]) – Right shadow price \(s_r\) for an upper bound.

duasen

A structure holding information about dual sensitivity analysis. See Sec. 14.3 (Sensitivity Analysis).

Fields

  • sub (int[]) – Indices of variables to be analyzed.

  • lr_c (double) – Left value \(\beta_1\) in linearity interval for an objective coefficient

  • rr_c (double) – Right value \(\beta_2\) in linearity interval for an objective coefficient

  • ls_c (double) – Left shadow price \(s_l\) for an objective coefficient

  • rs_c (double) – Right shadow price \(s_r\) for an objective coefficient

callback

A structure containing callback information (all subfields are optional).

Fields

  • loghandle (struct) – A data structure or just [].

  • log (string) –

    Log handler. The name of a user-defined function which must accept two input arguments, e.g.,

    function myprint(handle,str)

    where handle will be identical to callback.handle when myfunc is called, and str is a string of text from the log.

  • iterhandle (struct) – A data structure or just [].

  • iter (string) –

    Progress callback handler. The name of a user-defined function which must accept three input arguments,

    function [r] = callback_handler(handle,where,info)

    where handle will be identical to callback.iterhandle when the handler is called, where indicates the current progress of the solver (callback) and info is the current information items list. See Sec. 7.6 (Progress and data callback) for further details.

optserver

A structure containing information about the OptServer which should be used for remote optimization.

Fields

host (string) – URL of the OptServer in the form http://server:port or https://server:port.