{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "![MOSEK ApS](https://www.mosek.com/static/images/branding/webgraphmoseklogocolor.png )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# *Fusion:* Object-Oriented API for Conic Optimization\n", "\n", "*Fusion* is an Object-Oriented API specifically designed for Conic Optimization with **MOSEK**. In version 9 of **MOSEK** *Fusion* is available for Python, C#, Java and C++.\n", "\n", "*Fusion* makes it easy to assemble optimization models from conic blocks without going through the nitty-gritty of converting the optimization problem into matrix form - *Fusion* takes care of that part. It makes it easy to add and remove constraints and experiment with the model, making prototyping of complex models very quick. It provides linear expressions, linear algebra operations and cones.\n", "\n", "This is a quick demonstration of the main capabilities of *Fusion*. More details may be found in the documentation for the respective APIs. In particular section 6 of each Fusion API manual contains a lot more modeling techniques.\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from mosek.fusion import *\n", "import numpy as np\n", "import sys" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Problem formulation in *Fusion*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Fusion solves optimization problems of the form\n", "$$\n", "\\begin{array}{rll}\n", "\\mbox{minimize/maximize} & c^T x & \\\\\n", "\\mbox{subject to} & A^i x + b^i & \\in & K^i, & \\forall i, \\\\\n", "\\end{array}\n", "$$\n", "\n", "where $K^i$ are convex cones. The possible cones $K^i$ are \n", "\n", "* $\\{0\\}$ - the zero cone. This expresses simply a linear equality constraint $Ax+b=0$.\n", "* $\\mathbb{R}_+$ - positive orthant. This expresses simply a linear inequality constraint $Ax+b\\geq 0$.\n", "* $\\mathcal{Q}$ - quadratic cone, $x_1\\geq \\sqrt{x_2^2+\\cdots+x_n^2}$ where $n$ is the length of the cone.\n", "* $\\mathcal{Q_r}$ - rotated quadratic cone, $2x_1x_2\\geq x_3^2+\\cdots+x_n^2$, $x_1,x_2\\geq 0$.\n", "* $K_\\mathrm{exp}$ - the exponential cone $x_1\\geq x_2\\exp(x_3/x_2)$, useful in particular in entropy ptoblems.\n", "* $\\mathcal{P}_\\alpha$ - the three-dimensional power cone $x_1^\\alpha x_2^{1-\\alpha}\\geq |x_3|$, where $0<\\alpha<1$.\n", "* $\\mathbb{S}_+$ - the cone of positive semidefinite matrices.\n", "\n", "That allows for expressing linear, conic quadratic (SOCP), semidefinite, relative entropy, $p$-norm and many other types of problems.\n", "\n", "# Linear expressions\n", "\n", "Linear expressions are represented by the class Expression, of which Variable (that is an optimization variable in the model) is a special case. Linear expressions are constructed in an intuitive way. For example if $A,b$ are constant data matrices then we can form $Ax+b$ as follows:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[10]\n" ] } ], "source": [ "# Fix some dimensions and constant data for the example\n", "m, n = 10, 6\n", "A = np.random.uniform(-1.0, 1.0, [m,n])\n", "b = np.random.uniform(-1.0, 1.0, [m])\n", "\n", "# Construct a model with a variable of length n\n", "M = Model(\"example model\")\n", "x = M.variable(n)\n", "\n", "# Construct Ax+b\n", "e = Expr.add(Expr.mul(A,x), b)\n", "\n", "# Check we have the right dimension\n", "print(e.getShape())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Conic constraints\n", "\n", "We can now solve the unconstrained linear regression problem, that is minimize $\\|Ax+b\\|_2$. This will require a new variable $t$ such that the compound vector $(t,Ax+b)$ belongs to the quadratic cone (i.e. $t\\geq \\|Ax+b\\|_2$). The compound vector is created as a stack from existing expressions of compatible shapes. " ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[-0.2564764 0.07487066 -0.48852686 -0.27069618 -0.0116702 0.25069298]\n" ] } ], "source": [ "# Add scalar variable and conic quadratic constraint t >= \\|Ax+b\\|_2\n", "t = M.variable()\n", "M.constraint(Expr.vstack(t, e), Domain.inQCone())\n", "\n", "# Let t be the objective we minimize\n", "M.objective(ObjectiveSense.Minimize, t)\n", "\n", "# Solve and print solution\n", "M.solve()\n", "print(x.level())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Suppose we want to further restrict $x$, say $f^Tx\\geq 1$ where $f$ is a given vector." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0.14362664 0.24217444 0.12789172 0.16422602 0.14601391 0.7520208 ]\n" ] } ], "source": [ "f = np.random.uniform(0.0, 1.0, [n])\n", "\n", "# f^T dot x >= 1\n", "M.constraint(Expr.dot(f,x), Domain.greaterThan(1.0))\n", "\n", "M.solve()\n", "print(x.level())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Matrix notation\n", "\n", "Now suppose we want change the objective to\n", "\n", "$$\n", "\\mbox{minimize}\\quad \\|Ax + b\\|_2 + \\sum_{j=1}^n \\lambda_i e^{x_i}\n", "$$\n", "where $\\lambda$ are positive coefficients. This can be rewritten as\n", "\n", "$$\n", "\\begin{array}{lll}\n", "\\mbox{minimize} & t + \\lambda^T w & \\\\\n", "\\mbox{subject to} & (t, Ax+b) \\in \\mathcal{Q}, & \\\\\n", " & (w_i, 1, x_i) \\in K_\\mathrm{exp}.\n", "\\end{array}\n", "$$\n", "\n", "(Indeed, the last set of constraints is just $w_i\\geq e^{x_i}$). We only need to define the last set of constraints and this can be achieved in one go by stacking them in a matrix as follows:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "w = M.variable(n)\n", "\n", "M.constraint(Expr.hstack(w, Expr.constTerm(n, 1.0), x), Domain.inPExpCone());" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The horizontal stack above creates an expression of shape $n \\times 3$ which looks as follows\n", "\n", "$$\n", "\\left[\n", "\\begin{array}{cc}\n", "w_1 & 1 & x_1 \\\\\n", "w_2 & 1 & x_2 \\\\\n", ". & . & . \\\\\n", "w_n & 1 & x_n \\\\\n", "\\end{array}\n", "\\right]\n", "$$\n", "\n", "and the conic constraint is just a short way of writing that *every row of that matrix belongs to the exponential cone*, which is exactly what we need.\n", "\n", "We can now solve it, this time with log on screen." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Problem\n", " Name : example model \n", " Objective sense : min \n", " Type : CONIC (conic optimization problem)\n", " Constraints : 30 \n", " Cones : 7 \n", " Scalar variables : 42 \n", " Matrix variables : 0 \n", " Integer variables : 0 \n", "\n", "Optimizer started.\n", "Optimizer terminated. Time: 0.01 \n", "\n", "\n", "Interior-point solution summary\n", " Problem status : PRIMAL_AND_DUAL_FEASIBLE\n", " Solution status : OPTIMAL\n", " Primal. obj: 6.7324024340e+00 nrm: 2e+00 Viol. con: 5e-09 var: 0e+00 cones: 0e+00 \n", " Dual. obj: 6.7324024122e+00 nrm: 2e+00 Viol. con: 2e-16 var: 2e-09 cones: 0e+00 \n", "[-0.19956778 0.51106456 -0.04114955 0.0643022 0.38081815 0.6162572 ]\n" ] } ], "source": [ "lamb = np.random.uniform(0.0, 1.0, [n])\n", "\n", "M.setLogHandler(sys.stdout)\n", "\n", "# Objective = t + lambda dot w\n", "M.objective(ObjectiveSense.Minimize, Expr.add(t, Expr.dot(lamb,w)))\n", "M.solve()\n", "print(x.level())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Semidefinite variables\n", "\n", "An $n\\times n$ semidefinite variable can be defined with:" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[5 5]\n" ] } ], "source": [ "n = 5\n", "M = Model(\"semidefinite model\")\n", "X = M.variable(Domain.inPSDCone(n))\n", "print(X.getShape())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "and it can be used like any variable of this shape. For example we can solve the very simple illustrative problem of maximizing the sum of elements of $X$ subject to a fixed diagonal." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1.56287696 1.46813819 1.82873238 1.83024594 1.47063414] \n", "\n", "[[1.56287696 1.5147671 1.69058679 1.69128626 1.51605416]\n", " [1.5147671 1.46813819 1.63854565 1.63922358 1.46938563]\n", " [1.69058679 1.63854565 1.82873238 1.829489 1.63993788]\n", " [1.69128626 1.63922358 1.829489 1.83024594 1.64061639]\n", " [1.51605416 1.46938563 1.63993788 1.64061639 1.47063414]]\n" ] } ], "source": [ "diag = np.random.uniform(1.0, 2.0, n)\n", "print(diag, \"\\n\")\n", "\n", "# Fixed diagonal\n", "M.constraint(X.diag(), Domain.equalsTo(diag))\n", "\n", "# Objective = sum of elements of X\n", "M.objective(ObjectiveSense.Maximize, Expr.sum(X))\n", "\n", "# Solve\n", "M.solve()\n", "print(np.reshape(X.level(), [5,5]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# A cheatsheet to building expressions\n", "\n" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[]\n", "[6 6]\n", "[10 6]\n" ] } ], "source": [ "n = 6\n", "m = 10\n", "a = np.random.uniform(0.0, 1.0, [n])\n", "A = np.random.uniform(0.0, 1.0, [m,n])\n", "\n", "M = Model('demo model')\n", " \n", "x = M.variable('x', n, Domain.unbounded())\n", "y = M.variable('y', n, Domain.greaterThan(0.0))\n", "z = M.variable('z', n, Domain.inRange(-1.0, 1.0))\n", "\n", "# Multi-dimensional variable\n", "X = M.variable('X', [n,n])\n", "\n", "# Binary version\n", "e0 = Expr.add(x,1.0) # x+1.0 (element-wise)\n", "e1 = Expr.add(x,y) # x+y\n", "e2 = Expr.add(a,y) # a+y\n", "e3 = Expr.sub(x,y) # x-y \n", "e4 = Expr.add(Expr.add(x,y),z) # x+y+z\n", "\n", "# List version\n", "e5 = Expr.add([x, y, z]) # x+y+z\n", "\n", "# Multiplication \n", "e6 = Expr.mul(7.0,x) # 7.0*x \n", "e7 = Expr.mulElm(a,x) # a *. x, element wise multiplication\n", "\n", "# Inner and outer products\n", "e8 = Expr.dot(a,x) # a'*x\n", "print(e8.getShape())\n", "\n", "e9 = Expr.outer(a,x) # a*x' Outer product \n", "print(e9.getShape())\n", "\n", "# Reduction type operations\n", "e10 = Expr.sum(x)\n", "\n", "# Matrix multiplication\n", "e11 = Expr.mul(A, X) # AX\n", "print(e11.getShape())" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "
This work is licensed under a Creative Commons Attribution 4.0 International License. The **MOSEK** logo and name are trademarks of Mosek ApS. The code is provided as-is. Compatibility with future release of **MOSEK** or the Fusion API are not guaranteed. For more information contact our [support](mailto:support@mosek.com). " ] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.4" } }, "nbformat": 4, "nbformat_minor": 1 }