{ "metadata": { "name": "" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Disciplined Convex Programming" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Disciplined convex programming (DCP) is a system for constructing mathematical expressions with known curvature from a given library of base functions. CVXPY uses DCP to ensure that the specified optimization problems are convex.\n", "\n", "This section of the tutorial explains the rules of DCP and how they are applied by CVXPY.\n", "\n", "Visit [dcp.stanford.edu](http://dcp.stanford.edu) for a\n", "more interactive introduction to DCP." ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Expressions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Expressions in CVXPY are formed from variables, parameters, numerical constants such as Python floats and Numpy matrices, the standard arithmetic operators `+, -, *, /`, and a library of [functions](/functions). Here are some examples of CVXPY expressions:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "from cvxpy import *\n", "\n", "# Create variables and parameters.\n", "x, y = Variable(), Variable()\n", "a, b = Parameter(), Parameter()\n", "\n", "# Examples of CVXPY expressions.\n", "3.69 + b/3\n", "x - 4*a\n", "sqrt(x) - min(y, x - a)\n", "max(2.66 - sqrt(y), square(x + 2*y))" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stderr", "text": [ "/Users/stevend2/anaconda/envs/cvxpy/lib/python2.7/site-packages/ecos-1.0.3-py2.7-macosx-10.5-x86_64.egg/_ecos.py:3: UserWarning: Module cvxpy was already imported from /Users/stevend2/anaconda/envs/cvxpy/lib/python2.7/site-packages/cvxpy-0.1-py2.7.egg/cvxpy/__init__.pyc, but /Users/stevend2/PythonProjects/cvxpy/examples/notebooks is being added to sys.path\n" ] }, { "metadata": {}, "output_type": "pyout", "prompt_number": 2, "text": [ "max(2.66 + -sqrt(var2), square(var1 + 2 * var2))" ] } ], "prompt_number": 2 }, { "cell_type": "markdown", "metadata": {}, "source": [ "Expressions can be scalars, vectors, or matrices. The dimensions of an expression are stored as `expr.size`. CVXPY will raise an exception if an expression is used in a way that doesn't make sense given its dimensions, for example adding matrices of different size." ] }, { "cell_type": "code", "collapsed": false, "input": [ "import numpy\n", "\n", "X = Variable(5, 4)\n", "A = numpy.ones((3, 5))\n", "\n", "# Use expr.size to get the dimensions.\n", "print \"dimensions of X:\", X.size\n", "print \"dimensions of sum(X):\", sum(X).size\n", "print \"dimensions of A*X:\", (A*X).size\n", "\n", "# ValueError raised for invalid dimensions.\n", "try:\n", " A + X\n", "except ValueError, e:\n", " print e" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "dimensions of X: (5, 4)\n", "dimensions of sum(X): (1, 1)\n", "dimensions of A*X: (3, 4)\n", "Incompatible dimensions (3, 5) (5, 4)\n" ] } ], "prompt_number": 3 }, { "cell_type": "markdown", "metadata": {}, "source": [ "CVXPY uses DCP analysis to determine the sign and curvature of each expression." ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Sign" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Each (sub)expression is flagged as _positive_ (non-negative), _negative_ (non-positive), _zero_, or _unknown_.\n", "\n", "The signs of larger expressions are determined from the signs of their subexpressions. For example, the sign of the expression expr1*expr2 is\n", "\n", "* Zero if either expression has sign zero.\n", "* Positive if expr1 and expr2 have the same (known) sign.\n", "* Negative if expr1 and expr2 have opposite (known) signs.\n", "* Unknown if either expression has unknown sign.\n", "\n", "The sign given to an expression is always correct. But DCP sign analysis may flag an expression as unknown sign when the sign could be figured out through more complex analysis. For instance, `x*x` is positive but has unknown sign by the rules above." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The sign of an expression is stored as `expr.sign`. A vector or matrix expression may have entries with different signs, in which case `expr.sign` is a Numpy 2D array containing the signs of all the entries." ] }, { "cell_type": "code", "collapsed": false, "input": [ "x = Variable()\n", "a = Parameter(nonpos=True)\n", "c = numpy.array([1, -1])\n", "\n", "print \"sign of x:\", x.sign\n", "print \"sign of a:\", a.sign\n", "print \"sign of square(x)\", square(x).sign\n", "print \"sign of c*a\"\n", "print (c*a).sign" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "sign of x: UNKNOWN\n", "sign of a: NEGATIVE\n", "sign of square(x) POSITIVE\n", "sign of c*a\n", "[['NEGATIVE']\n", " ['POSITIVE']]\n" ] } ], "prompt_number": 4 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Curvature" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Each (sub)expression is flagged as one of the following curvatures\n", "\n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "\n", " \n", " \n", "\n", "
CurvatureMeaning
constant$ f(x) $ independent of $ x $
affine$ f(\\theta x + (1-\\theta)y) = \\theta f(x) + (1-\\theta)f(y), \\; \\forall x, \\; y,\\; \\theta \\in [0,1] $
convex$ f(\\theta x + (1-\\theta)y) \\leq \\theta f(x) + (1-\\theta)f(y), \\; \\forall x, \\; y,\\; \\theta \\in [0,1] $
concave$ f(\\theta x + (1-\\theta)y) \\geq \\theta f(x) + (1-\\theta)f(y), \\; \\forall x, \\; y,\\; \\theta \\in [0,1] $
unknownDCP analysis cannot determine the curvature
\n", "using the curvature rules given below. As with sign analysis, the conclusion is always correct, but the simple analysis can flag expressions as unknown even when they are convex or concave. Note that any constant expression is also affine, and any affine expression is convex and concave." ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Curvature Rules" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "DCP analysis is based on applying a general composition theorem from convex analysis to each (sub)expression.\n", "\n", "$f(expr_1, expr_2, ..., expr_n)$ is convex if $\\text{ } f$ is a convex function and for each $expr_{i}$ one of the following conditions holds:\n", "\n", "* $f$ is increasing in argument i and $expr_{i}$ is convex.\n", "* $f$ is decreasing in argument i and $expr_{i}$ is concave.\n", "* $expr_{i}$ is affine or constant.\n", "\n", "$f(expr_1, expr_2, ..., expr_n)$ is concave if $\\text{ } f$ is a 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 concave.\n", "* $f$ is decreasing in argument i and $expr_{i}$ is convex.\n", "* $expr_{i}$ is affine or constant.\n", "\n", "$f(expr_1, expr_2, ..., expr_n)$ is affine if $\\text{ } f$ is an affine function function and each $expr_{i}$ is 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", "Whether a function is increasing or decreasing in an argument may depend on the sign of the argument. For instance, `square` is increasing for positive arguments and decreasing for negative arguments." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The curvature of an expression is stored as `expr.curvature`. A vector or matrix expression may have entries with different curvatures, in which case `expr.curvature` is a Numpy 2D array containing the curvatures of all the entries." ] }, { "cell_type": "code", "collapsed": false, "input": [ "x = Variable()\n", "a = Parameter(nonneg=True)\n", "c = numpy.array([1, -1])\n", "\n", "print \"curvature of x:\", x.curvature\n", "print \"curvature of a:\", a.curvature\n", "print \"curvature of square(x)\", square(x).curvature\n", "print \"curvature of c*square(x)\"\n", "print (c*square(x)).curvature" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "curvature of x: AFFINE\n", "curvature of a: CONSTANT\n", "curvature of square(x) CONVEX\n", "curvature of c*square(x)\n", "[['CONVEX']\n", " ['CONCAVE']]\n" ] } ], "prompt_number": 5 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Infix Operators" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The infix operators `+, -, *, /` are treated exactly like functions. The infix operators `+` and `-` are affine, so the rules above are used to flag the curvature. For example, `expr1 + expr2` is flagged as convex if `expr1` and `expr2` are convex.\n", "\n", "`expr1*expr2` is allowed only when one of the expressions is constant. If both expressions are non-constant, CVXPY will raise an exception. `expr1/expr2` is allowed only when `expr2` is a scalar constant. The curvature rules above apply. For example, `expr1/expr2` is convex when `expr1` is concave and `expr2` is negative and constant." ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Example 1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "DCP analysis breaks expressions down into subexpressions. The tree visualization below shows how this works for the expression `2*square(x) + 3`. Each subexpression is shown in a blue box. We mark its curvature on the left and its sign on the right.\n", "\n", "\"sqrt(1" ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Example 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We'll walk through the application of the DCP rules to the expression `sqrt(1 + square(x))`.\n", "\n", "\"sqrt(1\n", "\n", "The variable `x` has affine curvature and unknown sign. The `square` function is convex and non-monotone for arguments of unknown sign. It can take the affine expression `x` as an argument; the result `square(x)` is convex.\n", "\n", "The arithmetic operator `+` is affine and increasing, so the composition `1 + square(x)` is convex by the curvature rule for convex functions. The function `sqrt` is concave and increasing, which means it can only take a concave argument. Since `1 + square(x)` is convex, `sqrt(1 + square(x))` violates the DCP rules and cannot be verified as convex.\n", "\n", "In fact, `sqrt(1 + square(x))` is a convex function of `x`, but the DCP rules are not able to verify convexity. If the expression is written as `norm(vstack(1, x), 2)`, the L2 norm of the vector $[1,x]$, which has the same value as `sqrt(1 + square(x))`, then it will be certified as convex using the DCP rules." ] }, { "cell_type": "code", "collapsed": false, "input": [ "print \"curvature of sqrt(1 + square(x))\", sqrt(1 + square(x)).curvature\n", "print \"curvature of norm(vstack(1, x), 2)\", norm(vstack(1, x), 2).curvature" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "curvature of sqrt(1 + square(x)) UNKNOWN\n", "curvature of norm(vstack(1, x), 2) CONVEX\n" ] } ], "prompt_number": 6 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "DCP Problems" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A problem is constructed from an objective and a list of constraints. If a problem follows the DCP rules, it is guaranteed to be convex and solvable by CVXPY. The DCP rules require that the problem objective have one of two forms:\n", "\n", "* Minimize(convex)\n", "* Maximize(concave)\n", "\n", "The only valid constraints under the DCP rules are\n", "\n", "* affine == affine\n", "* convex <= concave\n", "* concave >= convex\n", "\n", "You can check that a problem, constraint, or objective satisfies the DCP rules by calling `object.is_dcp()`. Here are some examples of DCP and non-DCP problems:" ] }, { "cell_type": "code", "collapsed": false, "input": [ "x = Variable()\n", "y = Variable()\n", "\n", "# DCP problems.\n", "prob1 = Problem(Minimize(square(x - y)), [x + y >= 0])\n", "prob2 = Problem(Maximize(sqrt(x - y)), \n", " [2*x - 3 == y,\n", " square(x) <= 2])\n", "\n", "print \"prob1 is DCP:\", prob1.is_dcp()\n", "print \"prob2 is DCP:\", prob2.is_dcp()\n", "\n", "# Non-DCP problems.\n", "prob3 = Problem(Maximize(square(x))) # Non-DCP objective.\n", "\n", "print \"prob3 is DCP:\", prob3.is_dcp()\n", "print \"Maximize(square(x)) is DCP:\", Maximize(square(x)).is_dcp()\n", "\n", "prob4 = Problem(Minimize(square(x)), [sqrt(x) <= 2]) # Non-DCP constraint.\n", "\n", "print \"prob4 is DCP:\", prob4.is_dcp()\n", "print \"sqrt(x) <= 2 is DCP:\", (sqrt(x) <= 2).is_dcp()" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "prob1 is DCP: True\n", "prob2 is DCP: True\n", "prob3 is DCP: False\n", "Maximize(square(x)) is DCP: False\n", "prob4 is DCP: False\n", "sqrt(x) <= 2 is DCP: False\n" ] } ], "prompt_number": 14 }, { "cell_type": "markdown", "metadata": {}, "source": [ "CVXPY will raise an exception if you call `problem.solve()` on a non-DCP problem." ] }, { "cell_type": "code", "collapsed": false, "input": [ "# ValueError raised for invalid dimensions.\n", "prob = Problem(Minimize(sqrt(x)))\n", "\n", "try:\n", " prob.solve()\n", "except Exception as e:\n", " print e" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Problem does not follow DCP rules.\n" ] } ], "prompt_number": 16 } ], "metadata": {} } ] }