{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 1 [55 points] Convex sets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (a) [5 x 5 = 25 points] Prove or disprove set convexity\n",
    "\n",
    "For each of the following, **state clearly if the set is convex or not**. Then **prove your statement**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(i) Rectangle: (vector inequality is to be understood elementwise)\n",
    "\n",
    "$$\\{x\\in\\mathbb{R}^{n} \\mid \\alpha \\leq x \\leq \\beta, \\quad \\alpha,\\beta\\in\\mathbb{R}^{n}\\}.$$ \n",
    "\n",
    "\n",
    "(ii) Wedge: \n",
    "\n",
    "$$\\{x\\in\\mathbb{R}^{n} \\mid a_{1}^{\\top}x \\leq b_{1}, \\quad a_{2}^{\\top}x \\leq b_{2}, \\quad a_{1},a_{2}\\in\\mathbb{R}^{n}, \\quad b_{1},b_{2}\\in\\mathbb{R}\\}.$$\n",
    "\n",
    "(iii) Set of points closer to a given point than a given set: \n",
    "\n",
    "$$\\{x\\in\\mathbb{R}^{n} \\mid \\| x - x_{0}\\|_{2} \\:\\leq\\: \\| x - y\\|_{2}, \\quad \\forall\\: y\\in\\mathcal{S}\\subseteq\\mathbb{R}^{n}, \\quad x_{0}\\in\\mathbb{R}^{n}\\}.$$ \n",
    "\n",
    "(iv) Set of points closer to one set than another:\n",
    "\n",
    "$$\\{x\\in\\mathbb{R}^{n} \\mid \\text{dist}\\left(x,\\mathcal{A}\\right)\\leq \\text{dist}\\left(x,\\mathcal{B}\\right), \\quad \\mathcal{A},\\mathcal{B}\\subset\\mathbb{R}^{n}\\}, \\quad \\text{dist}\\left(x,\\mathcal{A}\\right):= \\underset{a\\in\\mathcal{A}}{\\inf}\\|x-a\\|_{2}.$$\n",
    "\n",
    "(v) The set:\n",
    "$$\\{c\\in\\mathbb{R}^{n+1} \\mid c_{0} + c_{n} = 1, \\big|c_{0} + c_{1}x + c_{2}x^{2} + ... + c_{n}x^{n}\\big| \\leq 1 \\;\\text{for}\\; 2020\\leq x\\leq 2021\\}.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (b) [10 + 10 + 10 = 30 points] Support function\n",
    "\n",
    "The support function of a compact convex set $\\mathcal{X}\\subset\\mathbb{R}^{n}$ is defined as\n",
    "\n",
    "$$h(y)  := \\sup_{x\\in\\mathcal{X}}\\:\\{x^{\\top}y \\:\\mid y\\in\\mathbb{R}^{n}\\},$$\n",
    "\n",
    "which can be geometrically interpreted as the perpendicular distance from the origin to the supporting hyperplane of $\\mathcal{X}$. Therefore, the support function uniquely determines a convex set."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(i) Suppose two compact convex sets $\\mathcal{X}_{1},\\mathcal{X}_{2}\\subset\\mathbb{R}^{n}$ have support functions $h_1(\\cdot)$ and $h_2(\\cdot)$, respectively. **Derive** the support function $h(\\cdot)$ for the set sum/Minkowski sum $\\mathcal{X}_{1}+\\mathcal{X}_{2}$ (which is a convex set, see Lec. 6, p. 4). In other words, express $h(\\cdot)$ in terms of $h_{1}(\\cdot)$ and $h_2(\\cdot)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(ii) **Prove that** $h(y+z) \\leq h(y) + h(z)$ for any compact convex set $\\mathcal{X}\\subset\\mathbb{R}^{n}$, and any $y,z\\in\\mathbb{R}^{n}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(iii) **Derive** the support function $h(y)$ for the Euclidean ball $\\mathcal{B}(0,r)\\subset\\mathbb{R}^{n}$ (see Lec. 5, p. 12) with center at origin and radius $r>0$. (Hint: [Cauchy-Schwarz inequality](https://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 2 [3 x 15 = 45 points] Convex functions\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For each of the following, **state clearly if the function is convex or concave or both or neither**. Then **prove your statement**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(i) $f(x,t) = \\log\\left(\\dfrac{1}{t^{2} - x^{\\top}x}\\right)$ over ${\\rm{\\mathbf{dom}}}(f) = \\{(x,t) \\in \\mathbb{R}^{n} \\times \\mathbb{R} \\:\\mid\\: \\parallel x\\parallel_{2} \\:<\\: t\\}$.\n",
    "\n",
    "(ii) $f(p,q) = \\displaystyle\\sum_{i=1}^{n} p_{i}\\log\\left(\\displaystyle\\frac{p_{i}}{q_{i}}\\right)$ over ${\\rm{\\mathbf{dom}}}(f) = \\{(p,q)\\in\\mathbb{R}_{\\geq 0}^{n}\\times\\mathbb{R}_{\\geq 0}^{n} \\:\\mid\\: \\mathbf{1}^{\\top}p = \\mathbf{1}^{\\top}q = 1\\}$.\n",
    "\n",
    "(iii) $f(x) = \\dfrac{1}{x}\\displaystyle\\int_{0}^{x}\\!g(t)\\:{\\mathrm{d}}t$ over ${\\rm{\\mathbf{dom}}}(f) = \\mathbb{R}_{>0}$, where $g:\\mathbb{R}\\mapsto\\mathbb{R}$ is convex and differentiable."
   ]
  }
 ],
 "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.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}