6.3 Conic Quadratic Optimization

The structure of a typical conic optimization problem is

\[\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, \\ & & & Fx+g & \in & \D, \end{array}\end{split}\]

(see Sec. 11 (Problem Formulation and Solutions) for detailed formulations). We recommend Sec. 6.2 (From Linear to Conic Optimization) for a tutorial on how problems of that form are represented in MOSEK and what data structures are relevant. Here we discuss how to set-up problems with the (rotated) quadratic cones.

MOSEK supports two types of quadratic cones, namely:

• Quadratic cone:

  \[\Q^n = \left\lbrace x \in \real^n: x_0 \geq \sqrt{\sum_{j=1}^{n-1} x_j^2} \right\rbrace.\]

• Rotated quadratic cone:

  \[\Qr^n = \left\lbrace x \in \real^n: 2 x_0 x_1 \geq \sum_{j=2}^{n-1} x_j^2,\quad x_0\geq 0,\quad x_1 \geq 0 \right\rbrace.\]

For example, consider the following constraint:

\[(x_4, x_0, x_2) \in \Q^3\]

which describes a convex cone in \(\real^3\) given by the inequality:

\[x_4 \geq \sqrt{x_0^2 + x_2^2}.\]

For other types of cones supported by MOSEK, see Sec. 13.6 (Supported domains) and the other tutorials in this chapter. Different cone types can appear together in one optimization problem.

6.3.1 Example CQO1

Consider the following conic quadratic problem which involves some linear constraints, a quadratic cone and a rotated quadratic cone.

(6.7)\[\begin{split}\begin{array} {lccc} \mbox{minimize} & x_4 + x_5 + x_6 & & \\ \mbox{subject to} & x_1+x_2+ 2 x_3 & = & 1, \\ & x_1,x_2,x_3 & \geq & 0, \\ & x_4 \geq \sqrt{x_1^2 + x_2^2}, & & \\ & 2 x_5 x_6 \geq x_3^2 & & \end{array}\end{split}\]

The two conic constraints can be expressed in the ACC form as shown in (6.8)

(6.8)\[\begin{split}\left[\begin{array}{cccccc}0&0&0&1&0&0\\1&0&0&0&0&0\\0&1&0&0&0&0\\0&0&0&0&1&0\\0&0&0&0&0&1\\0&0&1&0&0&0\end{array}\right] \left[\begin{array}{c}x_1\\x_2\\x_3\\x_4\\x_5\\x_6\end{array}\right] + \left[\begin{array}{c}0\\0\\0\\0\\0\\0\end{array}\right] \in \Q^3 \times \Q_r^3.\end{split}\]

Setting up the linear part

The linear parts (constraints, variables, objective) are set up exactly the same way as for linear problems, and we refer to Sec. 6.1 (Linear Optimization) for all the details. The same applies to technical aspects such as defining an optimization problem, retrieving the solution and so on.

Setting up the conic constraints

To define the conic constraints, we start by setting prob$F equal to the matrix shown in (6.8). Note that F will internally be converted to the sparse triplet form (dgTMatrix) but the user may directly construct it as such by setting giveCsparse=FALSE (or repr="T" for newer Matrix package versions) in the sparseMatrix call. The vector prob$g is set to zero. Lastly, the domains are specified as columns in a list-typed matrix called cones, with rows for each associated detail. In example (6.7) we have two conic constraints:

    # NOTE: The F matrix is internally stored in the sparse
    #       triplet form. Use 'giveCsparse' or 'repr' option 
    #       in the sparseMatrix() call to construct the F 
    #       matrix directly in the sparse triplet form. 
    prob$F     <- sparseMatrix(i=c(1, 2, 3, 4, 5, 6),
                               j=c(4, 1, 2, 5, 6, 3), 
                               x=c(1, 1, 1, 1, 1, 1),
                               dims = c(6,6))
    prob$g     <- c(1:6)*0
    prob$cones <- matrix(list(), nrow=3, ncol=2)
    rownames(prob$cones) <- c("type","dim","conepar")

    prob$cones[,1] <- list("QUAD", 3, NULL)
    prob$cones[,2] <- list("RQUAD",3, NULL)

The first row in prob$cones selects the "type" of cone, such as "MSK_DOMAIN_QUADRATIC_CONE" or "MSK_DOMAIN_RQUADRATIC_CONE" (note that QUAD, QUADRATIC_CONE and RQUAD, RQUADRATIC_CONE are valid aliases for each domain, respectively). The second row specifies the dimension ("dim") of each domain, here set to 3. The third row sets the parameters ("conepar") for parametric domains, but because the quadratic cones are not parameterized, we set this value as NULL.

Source code

Listing 6.4 Source code solving problem (6.7). Click here to download.

library("Rmosek")

cqo1 <- function()
{
    # Specify the non-conic part of the problem.
    prob <- list(sense="min")
    prob$c  <- c(0, 0, 0, 1, 1, 1)
    prob$A  <- Matrix(c(1, 1, 2, 0, 0, 0), nrow=1, sparse=TRUE)
    prob$bc <- rbind(blc=1, 
                     buc=1)
    prob$bx <- rbind(blx=c(rep(0,3), rep(-Inf,3)), 
                     bux=rep(Inf,6))
    
    # Specify the affine conic constraints.
    # NOTE: The F matrix is internally stored in the sparse
    #       triplet form. Use 'giveCsparse' or 'repr' option 
    #       in the sparseMatrix() call to construct the F 
    #       matrix directly in the sparse triplet form. 
    prob$F     <- sparseMatrix(i=c(1, 2, 3, 4, 5, 6),
                               j=c(4, 1, 2, 5, 6, 3), 
                               x=c(1, 1, 1, 1, 1, 1),
                               dims = c(6,6))
    prob$g     <- c(1:6)*0
    prob$cones <- matrix(list(), nrow=3, ncol=2)
    rownames(prob$cones) <- c("type","dim","conepar")

    prob$cones[,1] <- list("QUAD", 3, NULL)
    prob$cones[,2] <- list("RQUAD",3, NULL)
    
    #
    # Use cbind to extend this chunk of ACCs, if needed:
    #
    #    oldcones <- prob$cones
    #    prob$cones <- cbind(oldcones, newcones)
    #

    # Solve the problem
    r <- mosek(prob)

    # Return the solution
    stopifnot(identical(r$response$code, 0))
    r$sol
}

cqo1()