6.3 Conic Quadratic Optimization

Conic optimization is a generalization of linear optimization, allowing constraints of the type

\[x^t \in \K_t,\]

where \(x^t\) is a subset of the problem variables and \(\K_t\) is a convex cone. Since the set \(\real^n\) of real numbers is also a convex cone, we can simply write a compound conic constraint \(x\in \K\) where \(\K=\K_1\times\cdots\times\K_l\) is a product of smaller cones and \(x\) is the full problem variable.

MOSEK can solve conic quadratic optimization problems of the form

\[\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, \\ & & & x \in \K, & & \end{array}\end{split}\]

where the domain restriction, \(x \in \K\), implies that all variables are partitioned into convex cones

\[x = (x^0, x^1, \ldots , x^{p-1}),\quad \mbox{with } x^t \in \K_t \subseteq \real^{n_t}.\]

In this tutorial we describe how to use the two types of quadratic cones defined as:

  • 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 other types of cones supported by MOSEK see Sec. 6.4 (Power Cone Optimization), Sec. 6.5 (Conic Exponential Optimization), Sec. 6.6 (Semidefinite Optimization). Different cone types can appear together in one optimization problem.

For example, the following constraint:

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

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

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

Furthermore, each variable may belong to one cone at most. The constraint \(x_i - x_j = 0\) would however allow \(x_i\) and \(x_j\) to belong to different cones with same effect.

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.5)\[\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}\]

Setting up the linear part

The linear parts (constraints, variables, objective) are set up using exactly the same methods 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 task, retrieving the solution and so on.

Setting up the conic constraints

The conic constraints are specified as columns in a list-typed matrix called cones, with rows for each associated detail. In example (6.5) we have two conic constraints:

    NUMCONES <- 2
    prob$cones <- matrix(list(), nrow=2, ncol=NUMCONES)
    rownames(prob$cones) <- c("type","sub")

    prob$cones[,1] <- list("QUAD", c(4, 1, 2))
    prob$cones[,2] <- list("RQUAD", c(5, 6, 3))

The first row selects the type of cone, such as quadratic "MSK_CT_QUAD" or rotated quadratic "MSK_CT_RQUAD", noting that the prefix MSK_CT_ is optional. The second row selects the vector of variables constrained to the cone, identified by index (counting from one in the R language).

Source code

Listing 6.3 Source code solving problem (6.5). 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 cones.
    NUMCONES <- 2
    prob$cones <- matrix(list(), nrow=2, ncol=NUMCONES)
    rownames(prob$cones) <- c("type","sub")

    prob$cones[,1] <- list("QUAD", c(4, 1, 2))
    prob$cones[,2] <- list("RQUAD", c(5, 6, 3))
    
    #
    # Use cbind to extend this chunk of cones 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()