17.2 Data Structures and Notation

The data structures employed by MOSEK are discussed in this section, along with the used notation.

The data structures and types used are the following:

17.2.1 Notation

MOSEK solves linear, quadratic, quadratically constrained, and conic optimization problems. The simplest of those is a linear problem, which is posed in MOSEK as

\[\begin{split}\begin{array} {lccccll} \mbox{minimize} & & & \sum_{j=1}^n c_j x_j + c^f & & & \\ \mbox{subject to} & l_i^c & \leq & \sum_{j=1}^n a_{ij} x_j & \leq & u_i^c, & i = 1, \ldots, m,\\ & l_j^x & \leq & x_j & \leq & u_j^x, & j = 1, \ldots, n. \end{array}\end{split}\]

An extension is a linear conic problem where the variables can belong to quadratic or semidefinite cones. A conic problem in MOSEK has the form

\[\begin{split}\begin{array} {lccccll} \mbox{minimize} & & & \sum_{j=1}^n c_j x_j + \sum_{j=1}^p \left\langle \barC_j, \barX_j \right\rangle + c^f & & & \\ \mbox{subject to} & l_i^c & \leq & \sum_{j=1}^n a_{ij} x_j + \sum_{j=1}^p \left\langle \barA_{ij}, \barX_j\right\rangle & \leq & u_i^c, & i = 1, \ldots, m,\\ & l_j^x & \leq & x_j & \leq & u_j^x, & j = 1, \ldots, n,\\ & & & x \in \K, \barX_j \in \PSD^{r_j}, & & & j = 1, \ldots, p \end{array}\end{split}\]

where the conic constraint

(1)\[x \in \K\]

means that a partitioning of \(x\) belongs to a set of quadratic cones (elaborated below). Further, the problem has \(p\) symmetric positive semidefinite variables \(\barX_j\in \PSD^{r_j}\) of dimension \(r_j\) with symmetric coefficient matrices \(\barC_j\in \Symm^{r_j}\) and \(\barA_{i,j}\in \Symm^{r_j}\).

Alternatively, MOSEK can solve convex quadratically constrained quadratic problems

\[\begin{split}\begin{array} {lrcccll} \mbox{minimize} & & & \half \sum_{i=1}^n\sum_{j=1}^nq^o_{ij}x_i x_j + \sum_{j=1}^nc_j x_j + c^f & & & \\ \mbox{subject to} & l_i^c & \leq & \half \sum_{j=1}^n\sum_{k=1}^nq^i_{jk}x_j x_k + \sum_{j=1}^n a_{ij} x_j & \leq & u_i^c, & i=1,\ldots ,m, \\ & l_j^x & \leq & x & \leq & u_j^x, & j=1,\ldots ,n. \end{array}\end{split}\]

The matrix

\[\begin{split}Q^o = \left[ \begin{array} {ccc} q_{11}^o & \cdots & q_{1n}^o \\ \vdots & \cdots & \vdots \\ q_{n1}^{0} & \cdots & q_{nn}^o \end{array} \right]\end{split}\]

must be symmetric positive semidefinite and the matrix

\[\begin{split}Q^i = \left[ \begin{array} {ccc} q_{11}^i & \cdots & q_{1n}^i \\ \vdots & \cdots & \vdots \\ q_{n1}^i & \cdots & q_{nn}^i \end{array} \right]\end{split}\]

must be either symmetric negative semidefinite with the \(i\)th constraint

\[l_i^c \leq \half \sum_{j=1}^n\sum_{k=1}^nq^i_{j,k} x_j x_k + \sum_{j=1}^n a_{i,j} x_j,\]

or \(Q^i\) must be symmetric positive semidefinite with the \(i\)th constraint

\[\half \sum_{j=1}^n\sum_{k=1}^n q^i_{j,k} x_j x_k + \sum_{j=1}^n a_{i,j} x_j \leq u_i^c.\]

Note that the if the quadratic terms \(Q^i\) are absent, the problem reduces to a standard quadratic optimization problem.

Finally, some variables may be integer-constrained, i.e.,

(2)\[x_j \mbox{ integer-constrained for all } j \in \mathcal{j}\]

where \(x_j\) (and possibly \(\barX_j\)) are the decision variables and all the other quantities are the parameters of the problem and they are presented below:

  • Since \(Q^o\) and \(Q^i\) are symmetric, only the lower triangular part should be specified.
  • The coefficients \(c_j\) are coefficients for the linear term \(c_j x_j\) in the objective.
  • \(c^f\) is a constant term in the objective, i.e., independent of all variables.
  • The constraint matrix \(A\) is given by
\[\begin{split}A = \left[ \begin{array} {ccc} a_{11} & \cdots & a_{1n} \\ \vdots & \cdots & \vdots \\ a_{m1} & \cdots & a_{mn} \end{array} \right].\end{split}\]

In MOSEK it is assumed that \(A\) is a sparse matrix, i.e. most of the coefficients in \(A\) are zero. Therefore, only non-zeros elements in \(A\) are stored and worked with. This usually saves a lot of storage and speeds up the computations.

  • The symmetric matrices \(\barC_j\) are coefficient matrices for the linear term \(\mathrm{tr}(\barC_j \barX_j)\) in the objective for semidefinite problems. The matrices are specified in triplet format discarding zero elements, and since they are symmetric, only the lower triangular parts should be specified.

  • The constraint matrices \(\barA_{ij}\) are symmetric matrices used in the constraints

    \[l_i^c \leq \sum_{j=1}^n a_{ij} x_j + \sum_{j=1}^p \left\langle \barA_{ij}, \barX_j\right\rangle \leq u_i^c, \quad i = 1, \ldots, m,\]

    for semidefinite problems. The matrices are specifed in triplet format discard zero elements, and since they are symmetric only the lower triangulars should be specified.

    • \(l^c\) specifies the lower bounds of the constraints.
    • \(u^c\) specifies the upper bounds of the constraints.
    • \(l^x\) specifies the lower bounds on the variables \(x\).
    • \(u^x\) specifies the upper bounds on the variables \(x\).
  • In conic problems, a partitioning of \(x\) belongs to a set of free variables and quadratic cones. Let

    \[x^t \in \real^{n^t}, \quad t=1,\ldots ,k\]

    be vectors comprised of disjoint subsets of the decision variables \(x\) (each decision variable is a field of exactly one \(x^t\)), e.g.,

    \[\begin{split}x^1 = \left[ \begin{array}{c} x_1 \\ x_4 \\ x_7 \end{array} \right] \mbox{ and } x^2 = \left[ \begin{array} {c} x_6 \\ x_5 \\ x_3 \\ x_2 \end{array} \right].\end{split}\]

    Next, define

    \[\K := \left\lbrace x \in \real^n: \quad x^t \in \K_t,\quad t=1,\ldots ,k \right\rbrace\]

    where \(\K_t\) must have one of the following forms

  • Free variables:

    \[\K_t = \{ x \in \real^{n^t} \}.\]
  • Quadratic cones:

    \[\K_t = \left\lbrace x \in \real^{n^{t}}: x_1 \geq \sqrt{\sum_{j=2}^{n^t} x_j^2} \right\rbrace.\]
  • Rotated quadratic cones:

    \[\K_t = \left\lbrace x \in \real^{n^t}: 2 x_1 x_2 \geq \sum_{j=3}^{n^t} x_j^2,\quad x_1,x_2 \geq 0 \right\rbrace.\]

The parameters of the optimization problem are stored using one or more subfields of the prob structure using the naming convention in Table 17.1.

Table 17.1 The relation between fields and problem parameters
Field name Type Dimension Optional Problem parameter
qosubi int length(qoval) Yes \(q_{ij}^o\)
qosubj int length(qoval) Yes \(q_{ij}^o\)
qoval double length(qoval) Yes \(q_{ij}^o\)
c double \(n\) Yes \(c_j\)
qcsubk int length(qcval) Yes \(q_{ij}^p\)
qcsubi int length(qcval) Yes \(q_{ij}^p\)
qcsubj int length(qcval) Yes \(q_{ij}^p\)
qcval double length(qcval) Yes \(q_{ij}^p\)
a Sparse matrix \(m ×n\) No \(a_{ij}\)
bardim int \(p\) Yes \(r_j\)
barc MATLAB struct   Yes \(\barC_j\)
bara MATLAB struct   Yes \(\barA_{ij}\)
blc double \(m\) Yes \(l_k^c\)
buc double \(m\) Yes \(u_k^c\)
blx double \(n\) Yes \(l_k^x\)
bux double \(n\) Yes \(u_k^x\)
ints MATLAB struct \(|\mathcal{j}|\) Yes \(\mathcal{j}\)
cones MATLAB cell \(k\) Yes \(\K\)

In Table 17.1 all the parameters are listed with their corresponding type. The int type indicates that the field must contain an integer value, double indicates a real number. The relationship between \(Q^o\) and \(Q^p\) and the subfields of the prob structure is as follows:

  • The quadratic terms in the objective:

    (3)\[q_{\mathtt{qosubi(t)},\mathtt{qoval(t)} }^o = \mathtt{qoval(t)},\quad t=1,2,\ldots ,\mathtt{length(qoval)}.\]

    Since \(Q^o\) by assumption is 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.

  • The quadratic terms in the constraints:

    (4)\[q_{\mathtt{qcsubi(t)},\mathtt{qcsubj(t)}}^{\mathtt{qcsubk(t)}} = \mathtt{qcval(t)},\quad t=1,2,\ldots ,\mathtt{length(qcval)}.\]

    Since \(Q^p\) by assumption is 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.

17.2.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.

Fields:
 
  • names (string) – A structure which contains the problem name, the name of the objective, and so forth.
  • qosubi (int[]) – \(i\) subscript for element \(q_{ij}^o\) in \(Q^o\). See (3).
  • qosubj (int[]) – \(j\) subscript for element \(q_{ij}^o\) in \(Q^o\). See (3).
  • qoval (double[]) – Numerical value for element \(q_{ij}^o\) in \(Q^o\). See (3).
  • qcsubk (int[]) – \(k\) subscript for element \(q_{ij}^p\) in \(Q^p\). See (4)
  • qcsubi (int[]) – \(i\) subscript for element \(q_{ij}^p\) in \(Q^p\). See (4)
  • qcsubj (double[]) – \(j\) subscript for element \(q_{ij}^p\) in \(Q^p\). See (4)
  • qcval (double[]) – Numerical value for element \(q_{ij}^p\) in \(Q^p\). See (4)
  • c (double[]) – Linear term in the objective.
  • a (double[][]) – The constraint matrix. It must be a sparse matrix having the number of rows and columns equivalent to the number of constraints and variables in the problem. 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.
  • 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\).
  • 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}\).
  • 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\).
  • ints (struct) –

    A structure which has the subfields

    • .sub A one-dimensional array containing the indexes of the integer-constrained variables. ints.sub is identical to the set \(\mathcal{j}\) in (2).
    • .pri A one dimensional array of the same length as ints.sub. The ints.pri(k) is the branching priority assigned to variable index ints.sub(k).
  • cones (cones) – A structure defining the conic constraints (1).
  • sol (solver_solutions) – A structure containing a guess on the optimal solution which some of the optimizers in MOSEK may exploit.
  • primalrepair (struct) –

    A structure used for primal feasibility repair which can optimally contain either of the subfields:

    • .wlc Weights for lower bounds on constraints.
    • .wuc Weights for upper bounds on constraints.
    • .wlx Weights for lower bounds on variables.
    • .wlc Weights for upper bounds on variables.

    If either of the subfields is missing, it assumed to be a vector with value 1 of appropriate dimension.

  • prisen (prisen) – A structure which has the subfields:
res
Fields:
 
  • sol (solver_solutions) – A structure holding available solutions (if any)
  • info (struct) – A structure containing the task information database which contains various task related information such as the number of iterations used to solve the problem. However, this field is only defined if info appeared in the cmd command when mosekopt is invoked.
  • param (list) – A structure which contain the complete MOSEK parameter database. However, this field is defined only if the param command is present in cmd when mosekopt is invoked.
  • prob (prob) – Contains the problem data if the problem data was read from a file.
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.
  • barvar (cell) – a cell array where names.barvar{j} contains the name of the \(j\)th semidefinite variable.
  • cone (cell) – a cell array where names.cone{t} contains the name of the \(t\)th conic constraint.
cones

A MATLAB structure representing details about cones.

For example the quadratic cone

\[x_5 \geq \sqrt{ {x_3}^2 + {x_1}^2}\]

and rotated quadratic cone

\[2 x_6 x_4 \geq x_2^2 + x_7^2\]

would be specified using the two arrays

cones.type   = [0, 1];
cones.sub    = [5, 3, 1, 6, 4, 2, 7];
cones.subptr = [1, 4];
Fields:
 
  • type (list) – An array with the cone types for each cone; "MSK_CT_QUAD" or "MSK_CT_RQUAD", indicating if the cone is a quadratic cone or a rotated quadratic cone.
  • sub (int[]) – An array of variable indexes specifying which variables are fields of the cones. The array is a concatenation of index lists of all the cones.
  • subptr (int[]) – An array of pointers into cones.sub indicating the beginning of the different cone index-sets.
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[]) – Subscripts of nonzeros elements.
  • subl (int[]) – 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)},\]
Fields:
 
  • subi (int) – Constraint indices \(i\).
  • subj (int) – Semidefinite variable indices \(j\).
  • subk (int[]) – Subscripts of nonzeros elements.
  • subl (int[]) – Subscripts of nonzeros elements.
  • val (double[]) – Numerical values.
solver_solutions

A structure used to store one or more solutions to an optimization problem. The structure has one subfield for each possible solution type.

Fields:
 
  • itr (solution) – Interior (point) solution computed by the interior-point optimizer.
  • bas (solution) – Basic solution computed by the simplex optimizers and basis identification procedure.
  • int (solution) – Integer solution computed by the mixed-integer optimizer.
solution

Stores information about a solution returned by the solve.

The fields .skn and .snx cannot occur in the .bas and .int solutions. In addition the fields .y, .slc, .suc, .slx, and .sux cannot occur in the .int solution since integer problems does not have a well-defined dual problem, and hence no dual solution.

Fields:
 
  • prosta (prosta) – Problem status.
  • solsta (solsta) – Solution status.
  • skc (stakey) – Enumraint status keys.
  • skx (stakey) – Variable status keys.
  • skn (stakey) – Conic status keys.
  • xc (double[]) – Constraint activities, i.e., \(x_c = Ax\) where \(x\) is the optimal solution.
  • xx (double[]) – The optimal \(x\) solution.
  • barx (list) – The optimal solution of \(\barX_j, \quad j=1, 2, \ldots, \mathtt{length(bardim)}\).
  • bars (list) – The optimal solution of \(\barS_j, \quad j=1, 2, \ldots, \mathtt{length(bardim)}\).
  • y (double[]) – Identical to sol.slc-sol.suc.
  • slc (double[]) – Dual solution corresponding to the lower constraint bounds.
  • suc (double[]) – Dual solution corresponding to the upper constraint bounds.
  • slx (double[]) – Dual solution corresponding to the lower variable bounds.
  • sux (double[]) – Dual solution corresponding to the upper variable bounds.
  • snx (double[]) – Dual solution corresponding to the conic constraint.
  • pobjval (double) – The primal objective value.
prisen

Results of the primal sensitivity analysis.

Fields:
 
  • cons (cprisen) – Constraints shadow prices.
  • var (vprisen) – Variable shadow prices
  • sub (int[]) – Index of variables where coefficients are analysed for sensitivity.
cprisen

A structure holding information about constraint shadow prices.

Fields:
 
  • 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.
vprisen

A structure holding information about variable shadow prices.

Fields:
 
  • lr_bl (double) – Left value \(\beta_1\) in the linearity interval for a lower bound on a variable
  • rr_bl (double) – Right value \(\beta_2\) in the linearity interval for a lower bound on a variable
  • ls_bl (double) – Left shadow price \(s_l\) for a lower bound on a variable
  • rs_bl (double) – Right shadow price \(s_r\) for a lower bound on a variable
  • lr_bu (double) – Left value \(\beta_1\) in the linearity interval for an upper bound on a variable
  • rr_bu (double) – Right value \(\beta_2\) in the linearity interval for an upper bound on a variable
  • ls_bu (double) – Left shadow price \(s_l\) for an upper bound on a variable
  • rs_bu (double) – Right shadow price \(s_r\) for an upper bound on a variable.
duasen

Results of dual the sensitivity analysis.

Fields:
 
  • 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
info

info is a MATLAB structure containing a subfield for each item in the MOSEK optimization task database, e.g., the info.dinfitem.bi_time field specifies the amount of time spent in the basis identification in the last optimization. See dinfitem and iinfitem for all the items in the task information database are listed.

symbcon

A MATLAB structure containing a subfield for each MOSEK symbolic constant, e.g., the field symbcon.dinfitem.bi_time specifies the value of the symbolic constant "MSK_DINF_BI_TIME". In Section 17.6 allthe symbolic constants are listed.

callback

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

Fields:
 
  • loghandle (struct) – A data structure or just [].
  • log (string) –

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

    function myfunc(handle,str)
    

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

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

    The name of a user-defined function which must accept three input arguments,

    function myfunc(handle,where,info)
    

    where handle will be identical to callback.iterhandle when myfunc is called, where indicates the current progress of the colver and info is the current information database. See info for further details.