{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (Text exercises 2.21, 2.24, 2.25) Separating and supporting hyperplanes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The set of separating hyperplanes\n",
    "(10 points) Consider two disjoint sets $\\mathcal{C},\\mathcal{D} \\subseteq \\mathbb{R}^{n}$, they need not be convex. Consider the set of $(a,b)\\in\\mathbb{R}^{n+1}$ for which $a^{\\top}x \\leq b$, $\\forall\\:x\\in\\mathcal{C}$, and $a^{\\top}x \\geq b$, $\\forall\\:x\\in\\mathcal{D}$. Show that this set is a convex cone (which is the singleton $\\{0\\}$ if there is no hyperplane that separates $\\mathcal{C}$ and $\\mathcal{D}$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Explicitly write convex set as intersection of halfspaces\n",
    "\n",
    "(5 points) Express the closed convex set $\\{x \\in \\mathbb{R}^{2}_{+} \\:\\mid\\: x_{1}x_{2} \\geq 1\\}$ as an intersection of halfspaces."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Explicit computation of supporting hyperplanes\n",
    "\n",
    "(5 points) Let $\\mathcal{C}=\\{x\\in\\mathbb{R}^{n} \\:\\mid\\: \\parallel x \\parallel_{\\infty} \\:\\leq\\: 1\\}$, the $\\ell_{\\infty}$-norm unit ball in $\\mathbb{R}^{n}$, and let $\\widehat{x}$ be a point in the boundary of $\\mathcal{C}$. Identify the supporting hyperplanes of $\\mathcal{C}$ at $\\widehat{x}$ explicitly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Inner and outer polyhedral approximations\n",
    "(5 + 5 = 10 points) Let $\\mathcal{X} \\subseteq \\mathbb{R}^{n}$ be a closed convex set, and suppose that $x_{1}, ..., x_{K}$ are on the boundary of $\\mathcal{X}$. Suppose that for each $i\\in\\{1,...,K\\}$, the equation $a_{i}^{\\top}(x-x_{i}) = 0$ defines a supporting hyperplane for $\\mathcal{X}$ at $x_{i}$, i.e., $\\mathcal{X} \\subseteq \\{x \\in \\mathbb{R}^{n} \\:\\mid\\: a_{i}^{\\top}(x-x_{i}) \\leq 0\\}$. Now consider two polyhedra\n",
    "\n",
    "$$ \\mathcal{P}_{\\text{inner}} = {\\rm{conv}}\\{x_{1}, ..., x_{K}\\}, \\quad \\mathcal{P}_{\\text{outer}} = \\{x \\in \\mathbb{R}^{n} \\:\\mid\\: a_{i}^{\\top}(x-x_{i}) \\leq 0,\\; i=1,...,K\\}. $$\n",
    "\n",
    "Prove that $\\mathcal{P}_{\\text{inner}} \\subseteq \\mathcal{X} \\subseteq \\mathcal{P}_{\\text{outer}}$. Draw a picture illustrating this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}