{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "%matplotlib inline\n", "import numpy as np;\n", "from matplotlib import pyplot as plt" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\LaTeX \\text{ commands here}\n", "\\newcommand{\\R}{\\mathbb{R}}\n", "\\newcommand{\\im}{\\text{im}\\,}\n", "\\newcommand{\\norm}[1]{||#1||}\n", "\\newcommand{\\inner}[1]{\\langle #1 \\rangle}\n", "\\newcommand{\\span}{\\mathrm{span}}\n", "\\newcommand{\\proj}{\\mathrm{proj}}\n", "\\newcommand{\\E}{\\mathbb{E}}\n", "$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "
\n", "\n", "**Georgia Tech, CS 4540**\n", "\n", "# L13: Linear Programming Introduction\n", "\n", "Jake Abernethy & Benjamin Bray\n", "\n", "*Thursday, October 3, 2019*" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Quick Review: SGD and OCO" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Random functions\n", "\n", "In many fields, especially Machine Learning, we deal with functions that have randomized inputs. For example, assume we have some distribution $D$, we often consider functions of the form\n", "$$ \n", "F(\\theta) := \\E_{\\xi \\sim D} [f(\\theta;\\xi)].\n", "$$\n", "Here, $\\theta$ are the parameters we want to optimize, and $\\xi$ is some random input, such as a datapoint. But we'd like to optimize $\\theta$ \"on average\", i.e. in expectation over a random sample of $\\xi \\sim D$. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Stochastic Gradient Descent\n", "\n", "We can optimize functions, defined through expectations above, using *randomized gradients*. \n", "\n", "- Initialize $\\theta_1$\n", "- For $t=1,2, \\ldots, T$:\n", " + Sample $\\xi_t \\sim D$\n", " + $\\theta_{t+1} = \\Pi_K(\\theta_t - \\eta_t \\nabla f(\\theta_t; \\xi_t))$\n", "- Output: $\\bar \\theta_T := \\frac 1 T \\sum_{t=1}^T \\theta_t$\n", "\n", "**Theorem** (Hazan book): As long as $f(\\cdot;\\xi)$ is convex, $\\|\\nabla f(\\cdot; \\cdot) \\| \\leq G$ and $\\text{diam}(K) \\leq D$, then we have\n", "$$\\E[F(\\bar \\theta_T)] - \\min_{\\theta \\in K} F(\\theta) \\leq \\frac{3GD}{2\\sqrt{T}}$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## SGD versus standard GD\n", "\n", "Let $F(\\theta) := \\frac 1 n \\sum_{i=1}^n f(\\theta; \\xi_i)$ be some objective function, defined as an average over samples $\\xi_1, \\ldots \\xi_n$. Consider two algorithms for minimizing $F$:\n", "\n", "1. Run (average-iterate) Gradient Descent on $F$, for $n$ steps\n", "2. Run SGD on $F$, by sampling a random $\\xi_i$ on each round, for $n$ steps\n", "\n", "#### Problem\n", "\n", "1. What is the convergence guarantee for each algorithm? (I'm only interested in the $T$-dependence!)\n", "1. What is the computational complexity of each? Which is better?\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# New material: Linear Programming\n", "\n", "*Note*: this is material for HW4 and will NOT be on the midterm!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Reading\n", "\n", "* Tim Roughgarden, Stanford CS261, [\"Lecture 7: Linear Programming\"](http://theory.stanford.edu/~tim/w16/l/l7.pdf)\n", "* Thomas S. Ferguson, [\"Linear Programming: A Concise Introduction\"](https://www.math.ucla.edu/~tom/LP.pdf)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Notation: Elementwise Inequalities\n", "\n", "For vectors $u,v \\in \\R^m$, define **elementwise** inequalities as:\n", "$$\n", "\\begin{align}\n", "u \\leq v &\\iff u_i \\leq b_i & (i=1,\\dots,m)\n", "\\end{align}\n", "$$\n", "Similarly, let $x \\in \\R^n$ and $b \\in \\R^m$. If $A \\in \\R^{m \\times n}$ is a matrix with rows $a_1^T, \\dots, a_m^T \\in \\R^{1 \\times n}$, then\n", "$$\n", "\\begin{align}\n", "A x \\leq b\n", "&\\iff a_i^T x \\leq b_i & (i=1,\\dots,m) \\\\\n", "\\end{align}\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Recall: Linear Programs\n", "\n", "A **linear program** consists of:\n", "\n", "* **Decision variables** $x = (x_1,\\dots,x_n) \\in \\R^d$\n", "* **Linear constraints** of the form $(a^T x \\leq b)$, $(a^Tx \\geq b)$, or $(a^T x = b)$\n", " * Here, $a \\in \\R^d$ is a vector and $b \\in \\R$ is a scalar\n", "* A **linear objective function** $c^T x$ which we want to maximize (or minimize).\n", "\n", "The reading contained the following example:\n", "\n", "
\n", "$$\n", "\\begin{align}\n", "\\max_{x_1, x_2} &\\quad x_1 + x_2 \\\\\n", "\\text{such that}\n", "&\\quad x_1 \\geq 0 \\\\\n", "&\\quad x_2 \\geq 0 \\\\\n", "&\\quad 2 x_1 + x_2 \\leq 1 \\\\\n", "&\\quad x_1 + 2 x_2 \\leq 1\n", "\\end{align}\n", "$$\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Warm-Up: Geometry of Linear Programs\n", "\n", "
\n", "Warm-Up: The feasible region of a linear program is the set of all $x \\in \\R^d$ which satisfy the linear constraints. Argue that the feasible region is a convex set.\n", "
\n", "\n", "![](images/l6-lpexample.png)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Solution: Feasible Region is Convex (1)\n", "\n", "Remember that a **hyperplane** is a level set of the linear functional $f(x) = a^T x$ for some $a \\in \\R^n$, and a **half-space** is the region on either side of a hyperplane:\n", "$$\n", "\\begin{align}\n", "\\text{hyperplane:} \\quad& \\{ x \\in \\R^n \\mid a^T x = b \\} \\\\\n", "\\text{half-space:} \\quad& \\{ x \\in \\R^n \\mid a^T x \\leq b \\}\n", "\\end{align}\n", "$$\n", "\n", "The feasible regions is a **polytope** or **polyhedron**, since it's an intersection of half-spaces. This means it's also convex!\n", "\n", "![hyperplane](images/l6-hyperplane.png)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Problem: Activity Analysis\n", "\n", "
\n", "Problem: Express the following scenario as a linear program:\n", "\n", "* A company has $m$ different resources which can be used to manufacture $n$ different products.\n", "* The company has $r_i$ units of resource $i=1,\\dots,m$ available.\n", "* The company earns a profit $c_j$ per unit of product $j=1,\\dots,n$.\n", "* The company expends $a_{ij}$ units of resource $i$ to manufacture one unit of product $j$.\n", "\n", "Using the resources available, how much of each product should be manufactured to maximize profits?\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Solution: Activity Analysis (1)\n", "\n", "For convenience, define\n", "* $x = (x_1,\\dots,x_n) \\in \\R^n$ is the amount of each product manufactured\n", "* $r = (r_1,\\dots,r_m) \\in \\R^m$ is the supply of each resource\n", "* $c = (c_1,\\dots,c_n) \\in \\R^n$ is the profit generated by each product\n", "* $A = [a_{ij}] \\in \\R^{m \\times n}$ represents the manufacturing costs\n", "\n", "Notice that:\n", "\n", "* The $i$th row of $A$ (let's call it $a_i^T \\in \\R^{1 \\times n}$) lists the amount of resource $i$ that each product uses. \n", "* The $j$th column of $A$ lists the amount of each resource needed to produce product $j$." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Solution: Activity Analysis (2)\n", "\n", "The **total profit** earned from production plan $x = (x_1,\\dots,x_n) \\in \\R^n$ is\n", "$$\n", "c^T x = c_1 x_1 + c_2 x_2 + \\cdots + c_n x_n\n", "$$\n", "In doing so, we expend the following amount of each resource $j=1,\\dots,m$:\n", "$$\n", "a_i^T x = a_{i1} x_1 + a_{i2} x_2 + \\cdots + a_{in} x_n\n", "$$\n", "We only have $r_i$ units of resource $i$, so we need to enforce $\\boxed{a_i^T x \\leq r_i}$. We also can't produce a negative amount of any product, so $\\boxed{x \\geq 0}$.\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Solution: Activity Analysis (3)\n", "\n", "Written more compactly, the linear program we want to solve is:\n", "\n", "
\n", "$$\n", "\\begin{align}\n", "\\max_{x \\in \\R^n} &\\quad c^T x \\\\\n", "\\text{such that} &\\quad a_i^T x \\leq r_i & (i = 1,\\dots,m) \\\\\n", " &\\quad x \\geq 0\n", "\\end{align}\n", "$$\n", "
\n", "\n", "> Notice that we can rewrite the constraints as $Ax \\leq r$." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "### Extra: Transportation \n", "\n", "
\n", "Problem: Express the following scenario as a linear program:\n", "\n", "* We want to ship coal from $M$ coal mines to $N$ factories.\n", "* Each mine $i=1,\\dots,M$ contains $m_i$ units of coal.\n", "* Each factory $j=1,\\dots,N$ needs $n_j$ units of coal to operate.\n", "* It costs $c_{ij}$ dollars to ship one unit of coal from mine $i$ to factory $j$.\n", "\n", "Our goal is to meet the needs of all the factories at minimum transportation cost.\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Linear Programs in Standard Form\n", "\n", "The **standard form** of a linear program for $c,x \\in \\R^n$, $b \\in \\R^m$ and $A \\in \\R^{m \\times n}$ is\n", "\n", "
\n", "\\begin{align}\n", "\\max_{x \\in \\R^d} &\\quad c^T x \\\\\n", "\\text{such that} &\\quad Ax \\leq b & \\text{(only $\\leq$ constraints)} \\\\\n", " &\\quad x \\geq 0 & \\text{(variables nonnegative)}\n", "\\end{align}\n", "
\n", "\n", "> We will show that every linear program can be converted to standard form! Only $\\leq$ constraints and nonnegative variables are necessary." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Problem: Inequalities to Standard Form\n", "\n", "
\n", "Problem: Argue that every linear program can be written using only $\\leq$ constraints. As an example, rewrite the following linear program using only constraints of the form $(a^T x \\leq b)$.\n", "$$\n", "\\begin{align}\n", "\\max_{x \\in \\R^n} &\\quad c^T x \\\\\n", "\\text{such that}\n", "&\\quad a^T x \\geq \\alpha \\\\\n", "&\\quad b^T x = \\beta \\\\\n", "\\end{align}\n", "$$\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Solution: Inequalities in Standard Form\n", "\n", "The following linear program is equivalent, but all the constraints are now $\\leq$:\n", "\n", "$$\n", "\\begin{align}\n", "\\max_{x \\in \\R^n} &\\quad c^T x \\\\\n", "\\text{such that}\n", "\\quad-& a^T x \\leq -\\alpha \\\\\n", "\\quad & b^T x \\leq \\beta \\\\\n", "\\quad-& b^T x \\leq \\beta \\\\\n", "\\end{align}\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Problem: Nonnegative Decision Variables\n", "\n", "
\n", "Problem: Argue that any linear program can be rewritten to have only nonnegative decision variables (possibly by adding/removing variables and constraints). For example,\n", "\n", "$$\n", "\\begin{align}\n", "\\max_{x \\in \\R^2} \\quad & x_1 - x_2 \\\\\n", "\\text{such that} \\quad & x_1 + x_2 \\leq 1 \\\\\n", " \\quad-& x_1 + x_2 \\leq 1\n", "\\end{align}\n", "$$\n", "
\n", "\n", "> *Hint:* Any $x \\in \\R$ can be written as $x = a - b$ where $a,b \\geq 0$." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Solution: Nonnegative Decision Variables\n", "\n", "Split each unconstrained decision variable into two nonnegative decision variables:\n", "$$\n", "\\begin{align}\n", "x_1 &= y_1 - y_2 &(y_1,y_2 \\geq 0)\\\\\n", "x_2 &= y_3 - y_4 &(y_3,y_4 \\geq 0)\\\\\n", "\\end{align}\n", "$$\n", "\n", "Let $y = (y_1,y_2,y_3,y_4)$. Replace $x_1$ and $x_2$ with the expressions above to obtain:\n", "$$\n", "\\begin{align}\n", "\\max_{x \\in \\R^2} \\quad& (y_1 - y_2) - (y_3 - y_4) \\\\\n", "\\text{such that}\n", "\\quad & (y_1 - y_2) + (y_3 - y_4) \\leq 1 \\\\\n", "\\quad-& (y_1 - y_2) + (y_3 - y_4) \\leq 1 \\\\\n", "\\quad & y \\geq 0\n", "\\end{align}\n", "$$\n", "\n", "> By finding an optimal solution for the linear program for $y$, we can reconstruct an optimal solution for $x$'s linear program!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Conclusion: Standard Form\n", "\n", "The previous two problems show that any linear program can be converted to standard form! From now on, we'll assume every linear program is written in this form.\n", "\n", "
\n", "\\begin{align}\n", "\\max_{x \\in \\R^d} &\\quad c^T x \\\\\n", "\\text{such that} &\\quad Ax \\leq b & \\text{(only $\\leq$ constraints)} \\\\\n", " &\\quad x \\geq 0 & \\text{(variables nonnegative)}\n", "\\end{align}\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Farkas Lemma\n", "\n", "We will work towards proving the following Lemma:\n", "\n", "
\n", "Lemma. (Farkas) Let $A \\in \\R^{m \\times n}$ and $b \\in \\R^m$. Then exactly one of the following two statements is true:\n", "\n", "1. There exists $x \\in \\R^n$ such that $Ax = b$ and $x \\geq 0$.\n", "2. There exists $y \\in \\R^m$ such that $y^T A \\geq 0$ and $b^T y < 0$.\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Problem: Farkas Lemma, Part 1\n", "\n", "
\n", "Problem: Prove that \n", "$$\n", "(\\exists\\, x \\geq 0 \\text{ s.t. } Ax = b) \\iff b \\in \\mathrm{cone}(a_1, \\dots, a_n)\n", "$$\n", "where $\\mathrm{cone}\\{ a_1, \\dots, a_n \\}$ is the set of all conic combinations of the columns of $A$.\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Solution: Farkas Lemma, Part 1\n", "\n", "* $(\\implies)$ Suppose there is $x \\geq 0$ such that $A x = b$ and $x \\geq 0$. Since $A x$ is a linear combination of the columns of $A$ with coefficients from $x$, which has nonnegative entries, $A x = b \\in \\mathrm{cone}\\{ a_1,\\dots,a_n \\}$ by definition.\n", "* $(\\impliedby)$ Similarly, if $b \\in \\mathrm{cone}(a_1,\\dots,a_n)$, then there are coefficients $x_1,\\dots,x_n \\geq 0$ such that $b = \\sum_{k=1}^n x_1 a_1 \\in \\R^m$. Assemble the coefficients into a vector $x = (x_1,\\dots,x_n) \\in \\R^n$. Then $A x = b$." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Problem: Farkas Lemma, Part 2\n", "\n", "
\n", "Problem: (not 1 implies 2) Show that:\n", "\n", "* If there does not exist $x \\geq 0$ such that $Ax = b$...\n", "* then there exists $y \\in \\R^m$ such that $y^T A \\geq 0$ and $b^T y < 0$.\n", "
\n", "\n", "> *Hint:* Use the separating hyperplane theorem, where one set is $\\mathrm{cone}(a_1,\\dots,a_k)$." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Problem: Farkas Lemma, Part 2\n", "\n", "* Assume there is no $x \\geq 0$ such that $Ax = b$. By the previous problem, then $b \\notin \\mathrm{cone}(a_1,\\dots,a_n)$.\n", "* Notice that $y^T A = [ y^T a_1, y^T a_2, \\dots, y^T a_n ] \\in \\R^{1 \\times n}$. So, $y^T A \\geq 0$ is equivalent to:\n", "$$\n", "y^T A \\geq 0\n", "\\iff\n", "y^T a_j \\geq 0 \\quad \\forall\\, j=1,\\dots,n\n", "$$\n", "* Interpret $y$ as the normal vector to a hyperplane. So, we want to show that there is a hyperplane which separates $b \\in \\R^m$ from the columns of $A$.\n", "* By assumption, $b$ is disjoint from $\\mathrm{cone}(a_1,\\dots,a_n)$ and they are both closed sets. Use the separating hyperplane theorem to find $y \\in \\R^m$ separating $b$ from the cone. Since the columns of $A$ belong to the cone, we are done!" ] } ], "metadata": { "celltoolbar": "Slideshow", "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.3" } }, "nbformat": 4, "nbformat_minor": 4 }