6.2 From Linear to Conic Optimization¶
In Sec. 6.1 (Linear Optimization) we demonstrated setting up the linear part of an optimization problem, namely the objective, linear bounds and linear (in)equalities. In this tutorial we show how to define conic constraints.
A single conic constraint in MOSEK is constructed in the following form
where
is the optimization variable vector of length , is a matrix of coefficients (problem data), where is the number of affine expressions (AFEs) in the conic constraint, is a vector of constants (problem data). Thus, the affine combination results in a -vector where each element is a scalar-valued AFE, is a conic domain of dimension , representing one of the cone types supported by MOSEK.
Constraints of this form are called affine conic constraints, or ACC for short. Therefore, in this section we show how to set up a problem of the form
where
Generalization of linear constraints
Conic constraints are a natural generalization of linear constraints to the general nonlinear case. For example, a typical linear constraint of the form
can also be written as membership in the cone of nonnegative real numbers (also called the positive orthant cone):
and that naturally generalizes to
for more complicated domains
6.2.1 Example AFFCO1¶
Consider the following simple optimization problem:
Adding auxiliary variables we convert this problem into an equivalent conic form:
Note that each of the vectors constrained to a cone is in a natural way an affine combination of the problem variables.
We first set up the linear part of the problem, including the number of variables, objective and all bounds precisely as in Sec. 6.1 (Linear Optimization). Affine conic constraints will be defined using the field cones
in the problem
structure. We construct the matrices
Below we set up the matrices and define the cone type as a "MSK_DOMAIN_QUADRATIC_CONE"
of length NULL
because it is a non-parametric cone (unlike the power cones).
# The quadratic cone
FQ <- rbind(c(0,0,0,0), c(1,0,0,0), c(0,1,0,0))
gQ <- c(1, -0.5, -0.6)
cQ <- matrix(list("QUAD", 3, NULL), nrow=3, ncol=1)
Next we demonstrate how to do the same for the second of the power cone constraints. Its affine representation is:
The power cone is defined by its type, length, and the additional parameter which is a vector of exponents
# The power cone for (x_1+x_2+0.1, 1, t_2) \in POW3^(1/4,3/4)
FP2 <- rbind(c(1,1,0,0), c(0,0,0,0), c(0,0,0,1))
gP2 <- c(0.1, 1, 0)
cP2 <- matrix(list("PPOW", 3, c(1.0, 3.0)), nrow=3, ncol=1)
Once affine conic descriptions of all cones are ready it remains to stack them vertically into the matrix
library("Rmosek")
affco1 <- function()
{
prob <- list(sense="max")
# Variables [x1; x2; t1; t2]
prob$c <- c(0, 0, 1, 1)
# Linear inequality x_1 - x_2 <= 1
prob$A <- Matrix(c(1, -1, 0, 0), nrow=1, sparse=TRUE)
prob$bc <- rbind(blc=-Inf, buc=1)
prob$bx <- rbind(blx=rep(-Inf,4), bux=rep(Inf,4))
# The quadratic cone
FQ <- rbind(c(0,0,0,0), c(1,0,0,0), c(0,1,0,0))
gQ <- c(1, -0.5, -0.6)
cQ <- matrix(list("QUAD", 3, NULL), nrow=3, ncol=1)
# The power cone for (x_1, 1, t_1) \in POW3^(1/3,2/3)
FP1 <- rbind(c(1,0,0,0), c(0,0,0,0), c(0,0,1,0))
gP1 <- c(0, 1, 0)
cP1 <- matrix(list("PPOW", 3, c(1/3, 2/3)), nrow=3, ncol=1)
# The power cone for (x_1+x_2+0.1, 1, t_2) \in POW3^(1/4,3/4)
FP2 <- rbind(c(1,1,0,0), c(0,0,0,0), c(0,0,0,1))
gP2 <- c(0.1, 1, 0)
cP2 <- matrix(list("PPOW", 3, c(1.0, 3.0)), nrow=3, ncol=1)
# All cones
prob$F <- rbind(FQ, FP1, FP2)
prob$g <- cbind(gQ, gP1, gP2)
prob$cones <- cbind(cQ, cP1, cP2)
rownames(prob$cones) <- c("type","dim","conepar")
r <- mosek(prob, list(soldetail=1))
stopifnot(identical(r$response$code, 0))
print(r$sol$itr$pobjval)
print(r$sol$itr$xx[1:2])
}
6.2.2 Example AFFCO2¶
Consider the following simple linear dynamical system. A point in
which can be cast into conic form as:
with variable vector
We assemble all conic constraints in the form
For the conic quadratic constraint this representation is
For the
where
firstHittingTime <- function(n, z, a, d)
{
prob <- list(sense="min")
# Variables [t, y1, ..., yn]
prob$A <- Matrix(nrow=0, ncol=n+1)
prob$bx<- rbind(rep(-Inf,n+1), rep(Inf,n+1))
prob$c <- c(1, rep(0, n))
# Quadratic cone
FQ <- Diagonal(n+1, c(0, z))
gQ <- c(d, rep(0, n))
# All exponential cones
FE <- sparseMatrix( c(seq(1,3*n,by=3), seq(3,3*n,by=3)),
c(2:(n+1), rep(1,n)),
x=c(rep(1,n), t(a)))
gE <- rep(c(0, 1, 0), n)
# Assemble input data
prob$F <- rbind(FQ, FE)
prob$g <- c(gQ, gE)
prob$cones <- cbind(matrix(list("QUAD", 1+n, NULL), nrow=3, ncol=1),
matrix(list("PEXP", 3, NULL), nrow=3, ncol=n))
rownames(prob$cones) <- c("type","dim","conepar")
# Solve
r <- mosek(prob, list(soldetail=1))
stopifnot(identical(r$response$code, 0))
r$sol$itr$xx[1]
}