{ "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", "
Curvature | \n", "Meaning | \n", "
---|---|
constant | \n", "$ f(x) $ independent of $ x $ | \n", "
affine | \n", "$ f(\\theta x + (1-\\theta)y) = \\theta f(x) + (1-\\theta)f(y), \\; \\forall x, \\; y,\\; \\theta \\in [0,1] $ | \n", "
convex | \n", "$ f(\\theta x + (1-\\theta)y) \\leq \\theta f(x) + (1-\\theta)f(y), \\; \\forall x, \\; y,\\; \\theta \\in [0,1] $ | \n", "
concave | \n", "$ f(\\theta x + (1-\\theta)y) \\geq \\theta f(x) + (1-\\theta)f(y), \\; \\forall x, \\; y,\\; \\theta \\in [0,1] $ | \n", "
unknown | \n", "DCP analysis cannot determine the curvature | \n", "