{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DGP fundamentals\n",
    "\n",
    "This notebook will introduce you to the fundamentals of **disciplined geometric programming** (**DGP**), which lets you formulate and solve *log-log convex programs* (LLCPs) in CVXPY.\n",
    "\n",
    "LLCPs are problems that become convex after the variables, objective functions, and constraint functions are replaced with their logs, an operation that we refer to as a log-log transformation. LLCPs generalize geometric programming."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import cvxpy as cp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Log-log curvature\n",
    "\n",
    "Just as every Expression in CVXPY has a curvature (constant, affine, convex, concave, or unknown), every Expression also has a log-log curvature.\n",
    "\n",
    "A function $f : D \\subseteq \\mathbf{R}^{n}_{++} \\to \\mathbf{R}$ is said to be **log-log convex** if the function $F(u)=\\log f(e^u)$, with domain $\\{u \\in \\mathbf{R}^n : e^u \\in D\\}$, is convex (where $\\mathbf{R}^{n}_{++}$ denotes the set of positive reals and the logarithm and exponential are meant elementwise); the function $F$ is called the log-log transformation of $f$. The function $f$ is **log-log concave** if $F$ is concave, and it is **log-log affine** if $F$ is affine.\n",
    "\n",
    "Notice that if a function has log-log curvature, then its domain and range can only include positive numbers.\n",
    "\n",
    "The log-log curvature of an `Expression` can be accessed via its `.log_log_curvature` attribute. For an `Expression` to have known log-log curvature, all of the `Constant`s, `Variable`s, and `Parameter`s it refers to must be elementwise positive."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0 LOG-LOG CONSTANT\n",
      "[1. 2.] LOG-LOG CONSTANT\n",
      "[1. 0.] UNKNOWN\n",
      "-2.0 UNKNOWN\n"
     ]
    }
   ],
   "source": [
    "# Only elementwise positive constants are allowed in DGP.\n",
    "c = cp.Constant(1.0)\n",
    "print(c, c.log_log_curvature)\n",
    "\n",
    "c = cp.Constant([1.0, 2.0])\n",
    "print(c, c.log_log_curvature)\n",
    "\n",
    "c = cp.Constant([1.0, 0.0])\n",
    "print(c, c.log_log_curvature)\n",
    "\n",
    "c = cp.Constant(-2.0)\n",
    "print(c, c.log_log_curvature)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "var0 LOG-LOG AFFINE\n",
      "var1 UNKNOWN\n",
      "param2 LOG-LOG CONSTANT\n",
      "param3 UNKNOWN\n"
     ]
    }
   ],
   "source": [
    "# Variables and parameters must be positive, ie, they must be constructed with the option `pos=True`\n",
    "v = cp.Variable(pos=True)\n",
    "print(v, v.log_log_curvature)\n",
    "\n",
    "v = cp.Variable()\n",
    "print(v, v.log_log_curvature)\n",
    "\n",
    "p = cp.Parameter(pos=True)\n",
    "print(p, p.log_log_curvature)\n",
    "\n",
    "p = cp.Parameter()\n",
    "print(p, p.log_log_curvature)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Functions from geometric programming\n",
    "\n",
    "A function $f(x)$ is log-log affine if and only if it is given by\n",
    "\n",
    "$$\n",
    "f(x) = cx_1^{a_1}x_2^{a_2} \\ldots x_n^{a_n},\n",
    "$$\n",
    "\n",
    "where $c > 0$ and the $a_i$ are real numbers. In the context of geometric programming, such a function is called\n",
    "a monomial."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.0 * power(x[0], 1/2) * power(x[1], 2) * power(x[2], 9/5) : LOG-LOG AFFINE\n"
     ]
    }
   ],
   "source": [
    "x = cp.Variable(shape=(3,), pos=True, name=\"x\")\n",
    "c = 2.0\n",
    "a = [0.5, 2.0, 1.8]\n",
    "\n",
    "monomial = c * x[0] ** a[0] * x[1] ** a[1] * x[2] ** a[2]\n",
    "# Monomials are not convex.\n",
    "assert not monomial.is_convex()\n",
    "\n",
    "# They are, however, log-log affine.\n",
    "print(monomial, \":\", monomial.log_log_curvature)\n",
    "assert monomial.is_log_log_affine()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A sum of monomial functions is log-log convex; in the context of geometric programming, such a function is called a posynomial. There are functions that are not posynomials that are still log-log convex."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.0 : LOG-LOG CONSTANT\n",
      "2.0 * x * y : LOG-LOG AFFINE\n",
      "2.0 * x * y + power(x, 3/2) * power(y, -1) : LOG-LOG CONVEX\n",
      "power(2.0 * x * y + power(x, 3/2) * power(y, -1), -1) : LOG-LOG CONCAVE\n",
      "power(2.0 * x * y + power(x, 3/2) * power(y, -1), -1) + 2.0 * x * y + power(x, 3/2) * power(y, -1) : UNKNOWN\n"
     ]
    }
   ],
   "source": [
    "x = cp.Variable(pos=True, name=\"x\")\n",
    "y = cp.Variable(pos=True, name=\"y\")\n",
    "\n",
    "constant = cp.Constant(2.0)\n",
    "monomial = constant * x * y\n",
    "posynomial = monomial + (x ** 1.5) * (y ** -1)\n",
    "reciprocal = posynomial ** -1\n",
    "unknown = reciprocal + posynomial\n",
    "\n",
    "print(constant, \":\", constant.log_log_curvature)\n",
    "print(monomial, \":\", monomial.log_log_curvature)\n",
    "print(posynomial, \":\", posynomial.log_log_curvature)\n",
    "print(reciprocal, \":\", reciprocal.log_log_curvature)\n",
    "print(unknown, \":\", unknown.log_log_curvature)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. Log-log curvature ruleset\n",
    "\n",
    "CVXPY has a library of atomic functions with known log-log curvature and monotonicity. It uses this information to\n",
    "tag every `Expression`, i.e., every composition of atomic functions, with a log-log curvature. In particular, \n",
    "\n",
    "A function $f(expr_1,expr_2,...,expr_n)$ is log-log convex if  $f$ is a log-log convex function and for each expri one of the following conditions holds:\n",
    "\n",
    "$f$ is increasing in argument i and $expr_i$ is log-log convex.\n",
    "$f$ is decreasing in argument $i$ and $expr_i$ is log-log concave.\n",
    "$expr_i$ is log-log affine.\n",
    "A function $f(expr_1,expr_2,...,expr_n)$ is log-log concave if  $f$ is a log-log concave function and for each $expr_i$ one of the following conditions holds:\n",
    "\n",
    "$f$ is increasing in argument $i$ and $expr_i$ is log-log concave.\n",
    "$f$ is decreasing in argument $i$ and $expr_i$ is log-log convex.\n",
    "$expr_i$ is log-log affine.\n",
    "A function $f(expr_1,expr_2,...,expr_n)$ is log-log affine if $f$ is an log-log affine function and each $expr_i$ is log-log affine.\n",
    "\n",
    "If none of the three rules apply, the expression $f(expr_1,expr_2,...,expr_n)$ is marked as having unknown curvature.\n",
    "\n",
    "If an Expression satisfies the composition rule, we colloquially say that the `Expression` “is DGP.” You can check whether an `Expression` is DGP by calling the method `is_dgp()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.0 * x * y is dgp? True\n",
      "2.0 * x * y + power(x, 3/2) * power(y, -1) is dgp? True\n"
     ]
    }
   ],
   "source": [
    "x = cp.Variable(pos=True, name=\"x\")\n",
    "y = cp.Variable(pos=True, name=\"y\")\n",
    "\n",
    "monomial = 2.0 * x * y\n",
    "posynomial = monomial + (x ** 1.5) * (y ** -1)\n",
    "\n",
    "print(monomial, \"is dgp?\", monomial.is_dgp())\n",
    "print(posynomial, \"is dgp?\", posynomial.is_dgp())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. DGP problems\n",
    "\n",
    "An LLCP is an optimization problem of the form\n",
    "\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{array}{ll}\n",
    "\\mbox{minimize} & f_0(x) \\\\\n",
    "\\mbox{subject to} & f_i(x) \\leq \\tilde{f_i}, \\quad i=1, \\ldots, m\\\\\n",
    "& g_i(x) = \\tilde{g_i}, \\quad i=1, \\ldots, p,\n",
    "\\end{array}\n",
    "\\end{equation}\n",
    "$$\n",
    "\n",
    "where the functions $f_i$ are log-log convex, $\\tilde{f_i}$ are log-log concave, and the functions $g_i$ and $\\tilde{g_i}$ are log-log affine. An optimization problem with constraints of the above form in which the goal is to maximize a log-log concave function is also an LLCP.\n",
    "\n",
    "A problem is DGP if additionally all the functions are DGP. You can check whether a CVXPY `Problem` is DGP by calling\n",
    "its `.is_dgp()` method.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "maximize x * y * z\n",
      "subject to 4.0 * x * y * z + 2.0 * x * z <= 10.0\n",
      "           x <= 2.0 * y\n",
      "           y <= 2.0 * x\n",
      "           1.0 <= z\n",
      "Is this problem DGP? True\n"
     ]
    }
   ],
   "source": [
    "x = cp.Variable(pos=True, name=\"x\")\n",
    "y = cp.Variable(pos=True, name=\"y\")\n",
    "z = cp.Variable(pos=True, name=\"z\")\n",
    "\n",
    "objective_fn = x * y * z\n",
    "constraints = [\n",
    "  4 * x * y * z + 2 * x * z <= 10, x <= 2*y, y <= 2*x, z >= 1]\n",
    "assert objective_fn.is_log_log_concave()\n",
    "assert all(constraint.is_dgp() for constraint in constraints)\n",
    "problem = cp.Problem(cp.Maximize(objective_fn), constraints)\n",
    "\n",
    "print(problem)\n",
    "print(\"Is this problem DGP?\", problem.is_dgp())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solving DGP problems\n",
    "\n",
    "You can solve a DGP `Problem` by calling its `solve` method with `gp=True`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal value: 1.9999999926890524\n",
      "x : 0.9999999989968756\n",
      "y : 1.9999999529045318\n",
      "z : 1.000000020895385\n",
      "Dual values:  [1.1111111199586956, 1.94877846244994e-09, 0.1111111217156332, 0.11111112214962586]\n"
     ]
    }
   ],
   "source": [
    "problem.solve(gp=True)\n",
    "print(\"Optimal value:\", problem.value)\n",
    "print(x, \":\", x.value)\n",
    "print(y, \":\", y.value)\n",
    "print(z, \":\", z.value)\n",
    "print(\"Dual values: \", list(c.dual_value for c in constraints))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you forget to supply `gp=True`, an error will be raised."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Problem does not follow DCP rules. However, the problem does follow DGP rules. Consider calling this function with `gp=True`.\n"
     ]
    }
   ],
   "source": [
    "try:\n",
    "    problem.solve()\n",
    "except cp.DCPError as e:\n",
    "    print(e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4. Next steps\n",
    "\n",
    "## Atoms\n",
    "CVXPY has a large library of log-log convex functions, including common functions like $\\exp$, $\\log$, and the difference between two numbers. Check out the tutorial on our website for the full list of atoms: https://www.cvxpy.org/tutorial/dgp/index.html\n",
    "\n",
    "## References\n",
    "For a reference on DGP, consult the following paper: https://web.stanford.edu/~boyd/papers/dgp.html"
   ]
  }
 ],
 "metadata": {
  "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.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}