7.8 Library of basic functions

This section contains a library of small models of basic functions frequently appearing in optimization models. It is essentially an implementation of the mathematical models from the MOSEK Modeling Cookbook using Fusion API for C++. These short code snippets can be seen as illustrative examples, can be copy-pasted to other code, and can even be directly called when assembling optimization models as we show in Sec. 7.8.6 (Model assembly example) (although this may be more suitable for prototyping; also note that additional variables and constraints will be introduced and there is no error checking).

7.8.1 Variable and constraint management

Variable duplication

\(x=y\)

Listing 7.16 Duplicate variables. Click here to download.
// x = y
static void dup(Model::t M, Variable::t x, Variable::t y) {
  M->constraint(Expr::sub(x,y), Domain::equalsTo(0.0));
}

7.8.2 Linear operations

Absolute value

\(t\geq |x|\)

Listing 7.17 Absolute value. Click here to download.
// t >= |x|, where t, x have the same shape
static void abs(Model::t M, Variable::t t, Variable::t x) {
  M->constraint(Expr::add(t,x), Domain::greaterThan(0.0));
  M->constraint(Expr::sub(t,x), Domain::greaterThan(0.0));
}

1-norm

\(t\geq \sum_i |x_i|\)

Listing 7.18 \(1\)-norm. Click here to download.
// t >= sum( |x_i| ), x is a vector variable
static void norm1(Model::t M, Variable::t t, Variable::t x) {
  Variable::t u = M->variable(x->getShape(), Domain::unbounded());
  abs(M, u, x);
  M->constraint(Expr::sub(t, Expr::sum(u)), Domain::greaterThan(0.0));
}

7.8.3 Quadratic and power operations

Square

\(t\geq x^2\)

Listing 7.19 Square. Click here to download.
// t >= x^2
static void sq(Model::t M, Variable::t t, Variable::t x) {
  M->constraint(Expr::hstack(0.5, t, x), Domain::inRotatedQCone());
}

2-norm

\(t\geq \sqrt{\sum_i x_i^2}\)

Listing 7.20 \(2\)-norm. Click here to download.
// t >= sqrt(x_1^2 + ->->-> + x_n^2) where x is a vector
static void norm2(Model::t M, Variable::t t, Variable::t x) {
  M->constraint(Expr::vstack(t, x), Domain::inQCone());
}

Powers

\(t\geq |x|^p\), \(p>1\)

Listing 7.21 Power. Click here to download.
// t >= |x|^p (where p>1)
static void pow(Model::t M, Variable::t t, Variable::t x, double p) {
  M->constraint(Expr::hstack(t, 1, x), Domain::inPPowerCone(1.0/p));
}

\(t\geq 1/x^p,\ x>0\), \(p>0\)

Listing 7.22 Power reciprocal. Click here to download.
// t >= 1/|x|^p, x>0 (where p>0)
static void pow_inv(Model::t M, Variable::t t, Variable::t x, double p) {
  M->constraint(Expr::hstack(t, x, 1), Domain::inPPowerCone(1.0/(1.0+p)));
}

p-norm

\(t\geq (\sum_i |x_i|^p)^{1/p}\), \(p>1\)

Listing 7.23 \(p\)-norm. Click here to download.
// t >= \|x\|_p (where p>1), x is a vector variable
static void pnorm(Model::t M, Variable::t t, Variable::t x, double p) {
  int n = (int) x->getSize();
  Variable::t r = M->variable(n);
  M->constraint(Expr::sub(t, Expr::sum(r)), Domain::equalsTo(0.0));
  M->constraint(Expr::hstack(Var::repeat(t,n), r, x), Domain::inPPowerCone(1.0-1.0/p));
}

Geometric mean

\(t\leq (x_1\cdot\cdots\cdot x_n)^{1/n}\), \(x_i>0\)

Listing 7.24 Geometric mean. Click here to download.
// |t| <= (x_1->->->x_n)^(1/n), x_i>=0, x is a vector variable of length >= 1
static void geo_mean(Model::t M, Variable::t t, Variable::t x) {
  int n = (int) x->getSize();
  if (n==1) {
      abs(M, x, t);
  }
  else {
      Variable::t t2 = M->variable();
      M->constraint(Expr::hstack(t2, x->index(n-1), t), Domain::inPPowerCone(1.0-1.0/n));
      geo_mean(M, t2, x->slice(0,n-1));
  }
}

7.8.4 Exponentials and logarithms

log

\(t\leq \log{x},\ x>0\)

Listing 7.25 Logarithm. Click here to download.
// t <= log(x), x>=0
static void log(Model::t M, Variable::t t, Variable::t x) {
  M->constraint(Expr::hstack(x, 1, t), Domain::inPExpCone());
}

exp

\(t\geq e^{x}\)

Listing 7.26 Exponential. Click here to download.
// t >= exp(x)
static void exp(Model::t M, Variable::t t, Variable::t x) {
  M->constraint(Expr::hstack(t, 1, x), Domain::inPExpCone());
}

Entropy

\(t\geq x\log{x},\ x>0\)

Listing 7.27 Entropy. Click here to download.
// t >= x * log(x), x>=0
static void ent(Model::t M, Variable::t t, Variable::t x) {
  M->constraint(Expr::hstack(1, x, Expr::neg(t)), Domain::inPExpCone());
}

Relative entropy

\(t\geq x\log{x/y},\ x,y>0\)

Listing 7.28 Relative entropy. Click here to download.
// t >= x * log(x/y), x,y>=0
static void relent(Model::t M, Variable::t t, Variable::t x, Variable::t y) {
  M->constraint(Expr::hstack(y, x, Expr::neg(t)), Domain::inPExpCone());
}

Log-sum-exp

\(\log{\sum_i e^{x_i}}\leq t\)

Listing 7.29 Log-sum-exp. Click here to download.
// log( sum_i(exp(x_i)) ) <= t, where x is a vector
static void logsumexp(Model::t M, Variable::t t, Variable::t x) {
  int n = (int) x->getSize();
  Variable::t u = M->variable(n);
  M->constraint(Expr::hstack(u, Expr::constTerm(n, 1.0), Expr::sub(x, Var::repeat(t, n))), Domain::inPExpCone());
  M->constraint(Expr::sum(u), Domain::lessThan(1.0));
}

7.8.5 Integer Modeling

Semicontinuous variable

\(x\in\{0\}\cup[a,b]\), \(b>a>0\)

Listing 7.30 Semicontinuous variable. Click here to download.
// x = 0 or a <= x <= b
static void semicontinuous(Model::t M, Variable::t x, double a, double b) {
  Variable::t u = M->variable(x->getShape(), Domain::binary());
  M->constraint(Expr::sub(x, Expr::mul(a, u)), Domain::greaterThan(0.0));
  M->constraint(Expr::sub(x, Expr::mul(b, u)), Domain::lessThan(0.0));
}

Indicator variable

\(x\neq 0 \implies t=1\). We assume \(x\) is a priori normalized so \(|x_i|\leq 1\).

Listing 7.31 Indicator variable. Click here to download.
// x!=0 implies t=1. Assumes that |x|<=1 in advance.
static void indicator(Model::t M, Variable::t t, Variable::t x) {
  M->constraint(t, Domain::inRange(0,1));
  t->makeInteger();
  abs(M, t, x);
}

Logical OR

At least one of the conditions is true.

Listing 7.32 Logical OR. Click here to download.
// x OR y, where x, y are binary
static void logic_or(Model::t M, Variable::t x, Variable::t y) {
  M->constraint(Expr::add(x, y), Domain::greaterThan(1.0));
}
// x_1 OR ->->-> OR x_n, where x is a binary vector
static void logic_or_vect(Model::t M, Variable::t x) {
  M->constraint(Expr::sum(x), Domain::greaterThan(1.0));
}

Logical NAND

At most one of the conditions is true (also known as SOS1).

Listing 7.33 Logical NAND. Click here to download.
// at most one of x_1,->->->,x_n, where x is a binary vector (SOS1 constraint)
static void logic_sos1(Model::t M, Variable::t x) {
  M->constraint(Expr::sum(x), Domain::lessThan(1.0));
}
// NOT(x AND y), where x, y are binary
static void logic_nand(Model::t M, Variable::t x, Variable::t y) {
  M->constraint(Expr::add(x, y), Domain::lessThan(1.0));
}

Cardinality bound

At most \(k\) of the continuous variables are nonzero. We assume \(x\) is a priori normalized so \(|x_i|\leq 1\).

Listing 7.34 Cardinality bound. Click here to download.
// At most k of entries in x are nonzero, assuming in advance |x_i|<=1.
static void card(Model::t M, Variable::t x, int k) {
  Variable::t t = M->variable(x->getShape(), Domain::binary());
  abs(M, t, x);
  M->constraint(Expr::sum(t), Domain::lessThan(k));
}

7.8.6 Model assembly example

We now demonstrate how to quickly build a simple optimization model for the problem

(7.19)\[\begin{split}\begin{array}{rl} \maximize & -\sqrt{x^2 + y^2} + \log{y} - x^{1.5}, \\ \st & x\geq y+3, \end{array}\end{split}\]

or equivalently

\[\begin{split}\begin{array}{rl} \maximize & -t_0+t_1-t_2, \\ \st & x\geq y+3, \\ & t_0\geq\sqrt{x^2+y^2}, \\ & t_1\leq\log{y}, \\ & t_2\geq x^{1.5}. \end{array}\end{split}\]
Listing 7.35 Modeling (7.19). Click here to download.
static void testExample() {
  Model::t M = new Model();
  Variable::t x = M->variable();
  Variable::t y = M->variable();
  Variable::t t = M->variable(3);

  M->constraint(Expr::sub(x, y), Domain::greaterThan(3.0));
  norm2(M, t->index(0), Var::vstack(x,y));
  log  (M, t->index(1), y);
  pow  (M, t->index(2), x, 1.5);

  M->objective(ObjectiveSense::Maximize, Expr::dot(t, new_array_ptr<double,1>({-1,1,-1})));