15.3 Data Structures and Notation

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

Problem definition

  • prob — describes an optimization problem.

  • cones — description of cones.

  • names — names of objects in the optimization problem.

  • barc, bara — description of the semidefinite part.

Solutions

Other

15.3.1 Notation

Linear problem

A linear problem has the form:

(15.1)\[\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}\]

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

Conic problem

A conic problem is an extension of a linear problem and has the form:

(15.2)\[\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}\]

It has \(n\) variables, \(m\) linear constraints, a cone \(\K\) (see below) and \(p\geq 0\) semidefinite variables. See also Sec. 12.2 (Conic Optimization) (or Sec. 12.3 (Semidefinite Optimization) for SDP). The conic constraint

\[x \in \K\]

means that a partitioning of \(x\) belongs to a set of cones \(\K=\K_1\times\ldots\times\K_s\), which can be one of:

  • Quadratic cone

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

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

    \[\EXP = \left\lbrace x \in \real^{3}: x_1\geq x_2\exp(x_3/x_2),\quad x_1,x_2 \geq 0 \right\rbrace\]

    as well as its dual

    \[\EXP^* = \left\lbrace x \in \real^{3}: x_1 \geq -x_3 e^{-1}\exp(x_2/x_3), \quad x_3\leq 0,x_1 \geq 0 \right\rbrace.\]
  • Primal power cone (with parameter \(0< \alpha< 1\))

    \[\POW^{\alpha,1-\alpha}_n = \left\lbrace x \in \real^{n}: x_1^\alpha x_2^{1-\alpha}\geq \sqrt{\sum_{j=3}^{n} x_j^2},\quad x_1,x_2 \geq 0 \right\rbrace\]

    as well as its dual

    \[(\POW^{\alpha,1-\alpha}_n )^* = \left\lbrace x \in \real^{n}: \left(\frac{x_1}{\alpha}\right)^\alpha \left(\frac{x_2}{1-\alpha}\right)^{1-\alpha} \geq \sqrt{\sum_{j=3}^{n} x^2_j}, \quad x_1, x_2 \geq 0 \right\rbrace.\]
  • The set \(\real^n\).

  • The zero cone \(\{(0,\ldots,0)\}\).

Membership in the trivial cones does not have to be specified.

Conic problem with affine conic constraints

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

(15.3)\[\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,\\ & & & Fx+g \in \K, & & & \\ & & & \barX_j \in \PSD^{r_j}, & & & j = 1, \ldots, p \end{array}\end{split}\]

It has \(n\) variables, \(m\) linear constraints, a cone \(\K\) (see below) and \(p\geq 0\) semidefinite variables. See also Sec. 12.5 (Affine Conic Constraints).

The conic constraint

\[Fx+g \in \K\]

where \(F\in\real^{k\times n}\) and \(g\in\real^k\) means that an affine combination of \(x\) belongs to a product of cones \(\K=\K_1\times\ldots\times\K_s\) of total length (dimension) \(k\). The available cone types are the same as above.

Quadratic and quadratically constrained problems

A problem with quadratic objective or constraints has the form:

(15.4)\[\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}\]

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 may be integer-constrained, i.e., for some set \(\mathcal{J}\subseteq\{1,\ldots,n\}\) we require

(15.5)\[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 symmetric matrices \(Q^o\), \(Q^i\), \(\barC_j\) and \(\barA_{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 cones \(\K\) see cones.

  • For a specification of the semidefinite part see 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[]

\(p\)

\(r_j\)

barc

barc

\(\barC_j\)

bara

bara

\(\barA_{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.6)\[\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.6).

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

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

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

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

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

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

  • 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\).

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

  • cones (cones) – A structure defining either the conic constraints in (15.2) or the affine conic constraints in (15.3).

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

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

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

cones

Represents either conic constraints or affine conic constraints.

Conic constraints. For conic constraints \(x\in \K\), where \(\K=\K_1\times\cdots\times\K_s\), cones is a structure containing three or four fields:

  • type (list) — An array with the cone type for each cone; see conetype.

  • sub (int[]) — A concatenation of index lists of all the cones.

  • subptr (int[]) — An array of pointers indicating the beginning of consecutive cones in sub.

  • conepar (double[]) — An array of cone parameters; for a power cone this is the exponent \(\alpha\), for other cone types the value is irrelevant. If the problem contains no power cones this field is not required.

The arrays type and subptr (and conepar if present) must have the same length \(s\). For every \(j=1,\ldots,s\) the vector \(x_{\mathtt{sub[subptr[j]:(subptr[j+1]-1)]}}\) belongs to a cone of type \(\mathtt{type[j]}\) with parameter \(\mathtt{conepar[j]}\). For example for the two cones

\[x_5 \geq \sqrt{ x_3^2 + x_1^2},\quad x_6^{0.3} x_4^{0.7} \geq \sqrt{x_2^2 + x_7^2}\]

the description could be:

cones.type   = [res.symbcon.MSK_CT_QUAD, res.symbcon.MSK_CT_PPOW];
cones.sub    = [5, 3, 1, 6, 4, 2, 7];
cones.subptr = [1, 4];
cones.conepar= [0.0, 0.3];

Affine conic constraints. For affine conic constraints \(Fx+g\in \K\), where \(\K=\K_1\times\cdots\times\K_s\), cones is a list consisting of \(s\) concatenated cone descriptions. If a cone requires no additional parameters (quadratic, rotated quadratic, exponential, zero) then its description is

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

where \(\mathrm{type}\) is the type (conetype) and \(\mathrm{len}\) is the length (dimension). The length must be present. If a cone requires additional parameters (power cones) then its description has the form

\[[\mathrm{type}, \mathrm{len}, k, a_1, \ldots, a_k]\]

where \(k\geq 1\) is an integer and \(a_1,\ldots,a_k\in \real\) are the additional parameters. For the power cone it is required that \(k=2\) and then a power cone with parameter \(\alpha=a_1/(a_1+a_2)\) is constructed. For example \(\Q^5\times \POW_4^{0.4}\) could be defined as

cones = [res.symbcon.MSK_CT_QUAD 5 res.symbcon.MSK_CT_PPOW, 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.

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.