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 Python. 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
def dup(M, x, 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
def abs(M, 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 expression
def norm1(M, t, x):
    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
def sq(M, 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
def norm2(M, 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)
def pow(M, t, x, 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)
def pow_inv(M, t, x, 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 expression
def pnorm(M, t, x, p):
    n = int(x.getSize())
    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 expression of length >= 1
def geo_mean(M, t, x):
    n = int(x.getSize())
    if n==1:
        abs(M, x, t)
    else:
        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
def log(M, 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)
def exp(M, 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
def ent(M, 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
def relent(M, t, x, 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
def logsumexp(M, t, x):
    n = int(x.getSize())
    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
def semicontinuous(M, x, a, b):
    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.
def indicator(M, 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
def logic_or(M, x, y):
    M.constraint(Expr.add(x, y), Domain.greaterThan(1.0))
# x_1 OR ... OR x_n, where x is a binary vector
def logic_or_vect(M, 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)
def logic_sos1(M, x):
    M.constraint(Expr.sum(x), Domain.lessThan(1.0))
# NOT(x AND y), where x, y are binary
def logic_nand(M, x, 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.
def card(M, x, k):
    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.
def testExample():
    M = Model()
    x = M.variable()
    y = M.variable()
    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, [-1,1,-1]))