{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (3 x 10 = 30) Which of the following sets are convex? In each case, give detailed reasons for your answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(a) Solution set of quadratic inequality, i.e., $\\{x \\in \\mathbb{R}^{n} \\:\\mid\\: x^{\\top}Ax + b^{\\top}x + c \\leq 0, \\quad A\\in\\mathbb{S}^{n}_{+}, \\quad b\\in\\mathbb{R}^{n}, \\quad c\\in\\mathbb{R} \\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "Convex. We will prove this using the following property: a set is convex if and only if its intersection with an arbitrary line $\\{\\widehat{x}+tv \\:\\mid\\: t\\in \\mathbb{R}\\}$ is convex. \n",
    "\n",
    "We have\n",
    "$$ (\\widehat{x}+tv)^{\\top}A(\\widehat{x}+tv) \\:+\\: b^{\\top}(\\widehat{x}+tv) \\:+\\: c = \\alpha t^{2} + \\beta t + \\gamma, $$\n",
    "where\n",
    "$$ \\alpha = v^{\\top}Av, \\qquad \\beta = b^{\\top}v + 2\\widehat{x}^{\\top}Av, \\qquad \\gamma = c + b^{\\top}\\widehat{x} + \\widehat{x}^{\\top}A \\widehat{x}.$$\n",
    "\n",
    "The intersection of our set of interest with the line defined by $\\widehat{x}$ and $v$, is the set\n",
    "$$ \\{\\widehat{x} + tv \\:\\mid\\: \\alpha t^{2} + \\beta t + \\gamma \\:\\leq\\: 0\\}, $$\n",
    "which is convex if $\\alpha \\geq 0$. This is true for any vector $v$ if $v^{\\top}Av\\geq 0$, i.e., when $A \\in \\mathbb{S}^{n}_{+}$, which is what we have. Hence our set of interest is convex."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(b) Hyperbolic set, i.e., $\\{x \\in \\mathbb{R}^{n}_{+} \\: \\mid \\: \\displaystyle\\prod_{i=1}^{n}x_{i} \\geq 1\\}.$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "Convex. Let $x, y \\in \\mathbb{R}^{n}_{+}$ such that $\\displaystyle\\prod_{i=1}^{n}x_{i} \\geq 1$, and $\\displaystyle\\prod_{i=1}^{n}y_{i} \\geq 1$. Using the inequality \n",
    "$$ a^{\\theta}b^{1-\\theta} \\leq \\theta a + (1-\\theta) b, \\quad a, b \\geq 0, \\quad 0 \\leq \\theta \\leq 1,$$\n",
    "we have\n",
    "$$ \\displaystyle\\prod_{i=1}^{n} \\left(\\theta x_{i} + (1-\\theta)y_{i}\\right) \\geq \\displaystyle\\prod_{i=1}^{n} x_{i}^{\\theta}y_{i}^{1-\\theta} = \\left(\\displaystyle\\prod_{i=1}^{n}x_{i}\\right)^{\\theta}\\left(\\displaystyle\\prod_{i=1}^{n}y_{i}\\right)^{1-\\theta} \\geq 1.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(c) A slab, i.e., $\\{x \\in \\mathbb{R}^{n} \\:\\mid\\: \\alpha \\leq a^{\\top}x \\leq \\beta, \\quad a\\in\\mathbb{R}^{n}, \\quad \\alpha,\\beta\\in\\mathbb{R}\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution: \n",
    "Convex (in fact, a polyhedron) since it is an intersection of 2 halfspaces."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(d) A rectangle, i.e., $\\{x\\in \\mathbb{R}^{n}\\:\\mid\\: \\alpha \\leq x \\leq \\beta, \\quad \\alpha,\\beta\\in\\mathbb{R}^{n}, \\quad \\text{vector inequality is elementwise}\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution: \n",
    "Convex (in fact, a polyhedron) since it is an intersection of finite number of halfspaces."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(e) A wedge, i.e., $\\{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}\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution: \n",
    "Convex (in fact, a polyhedron) since it is an intersection of 2 halfspaces. It is a cone for $b_{1} = b_{2} = 0$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(f) Set of points closer to a given point than a given set, i.e., $\\{x\\in\\mathbb{R}^{n} \\:\\mid\\: \\parallel x - x_{0}\\parallel_{2} \\:\\leq\\: \\parallel x - y\\parallel_{2}, \\quad \\forall\\:y\\in\\mathcal{S}\\subseteq\\mathbb{R}^{n}, \\quad x_{0}\\in\\mathbb{R}^{n}\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution: \n",
    "Convex because the set can be expressed as\n",
    "$$\\bigcap_{y\\in\\mathcal{S}}\\{x\\in\\mathbb{R}^{n} \\:\\mid\\: \\parallel x - x_{0}\\parallel_{2} \\:\\leq\\: \\parallel x - y\\parallel_{2}\\},$$\n",
    "i.e., an intersection of halfspaces. Notice that for fixed $y\\in\\mathbb{R}^{n}$, the set $\\{x\\in\\mathbb{R}^{n} \\:\\mid\\: \\parallel x - x_{0}\\parallel_{2} \\:\\leq\\: \\parallel x - y\\parallel_{2}\\}$ is a halfspace."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(g) Set of points closer to one set than another, i.e., $\\{x\\in\\mathbb{R}^{n} \\:\\mid\\: {\\rm{dist}}(x,\\mathcal{S})\\leq {\\rm{dist}}(x,\\mathcal{T}), \\quad \\mathcal{S},\\mathcal{T}\\subseteq\\mathbb{R}^{n}\\},\\quad$and$\\quad{\\rm{dist}}(x,\\mathcal{S}) := \\inf\\{\\parallel x - z \\parallel_{2} \\:\\mid\\: z\\in\\mathcal{S}\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "In general, this set is not convex. As counterexample, consider $n=1$ with $\\mathcal{S} = \\{-1,1\\}$, and $\\mathcal{T}=\\{0\\}$. Then\n",
    "$$\\{x\\in\\mathbb{R} \\:\\mid\\: {\\rm{dist}}(x,\\mathcal{S})\\leq {\\rm{dist}}(x,\\mathcal{T}), \\quad \\mathcal{S},\\mathcal{T}\\subseteq\\mathbb{R}^{n}\\} = \\{x \\leq -1/2\\} \\cup \\{x \\geq 1/2\\},$$\n",
    "which is not convex."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(h) Subtraction from a convex set, i.e., $\\{x\\in\\mathbb{R}^{n} \\:\\mid\\: x +\\mathcal{S}_{2} \\subseteq \\mathcal{S}_{1}, \\quad \\mathcal{S}_{1},\\mathcal{S}_{2}\\subseteq\\mathbb{R}^{n}, \\quad \\mathcal{S}_{1}\\,\\text{convex}\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "This set is convex. Notice that $x + \\mathcal{S}_{2} \\subseteq \\mathcal{S}_{1}$ if $x + y \\in \\mathcal{S}_{1}$ for all $y\\in\\mathcal{S}_{2}$. Therefore, \n",
    "$$ \\{x\\in\\mathbb{R}^{n} \\:\\mid\\: x +\\mathcal{S}_{2}\\} = \\bigcap_{y\\in\\mathcal{S}_{2}} \\{x \\:\\mid\\: x + y \\in \\mathcal{S}_{1}\\} = \\bigcap_{y\\in\\mathcal{S}_{2}} \\left(\\mathcal{S}_{1} - y\\right),$$\n",
    "the intersection of convex sets $(\\mathcal{S}_{1} - y)$, hence convex."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(i) Set of points whose distance to a given point ($a\\in\\mathbb{R}^{n}$) does not exceed a fixed fraction ($0\\leq \\theta\\leq 1$) of the distance to another given point ($b\\in\\mathbb{R}^{n}$), i.e., $\\{x\\in\\mathbb{R}^{n} \\:\\mid\\: \\parallel x - a \\parallel_{2} \\:\\leq\\: \\theta\\parallel x - b \\parallel_{2}, \\quad a\\neq b\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "Convex. Notice that\n",
    "$$ \\{x \\:\\mid\\: \\parallel x - a \\parallel_{2} \\:\\leq\\: \\theta\\parallel x - b \\parallel_{2}\\}\n",
    "= \\{x \\:\\mid\\: \\parallel x - a \\parallel_{2}^{2} \\:\\leq\\: \\theta^{2}\\parallel x - b \\parallel_{2}^{2}\\}\n",
    "=  \\{x \\:\\mid\\: (1-\\theta^{2})x^{\\top}x -2(a-\\theta^{2}b)^{\\top}x + (a^{\\top}a -\\theta^{2}b^{\\top}b) \\:\\leq\\: 0 \\}.$$\n",
    "If $\\theta=1$, then the above set is a halfspace. If $\\theta < 1$, then it is a ball\n",
    "$$ \\{x\\in\\mathbb{R}^{n} \\:\\mid\\: (x-x_{0})^{\\top}(x-x_{0}) \\leq r^{2}\\},$$\n",
    "with center $x_{0}$ and radius $r$, given by\n",
    "$$ x_{0} = \\displaystyle\\frac{a-\\theta^{2}b}{1-\\theta^{2}}, \\qquad r = \\left(\\displaystyle\\frac{\\theta^{2}\\parallel b \\parallel_{2}^{2} - \\parallel a \\parallel_{2}^{2}}{1 - \\theta^{2}} \\:-\\: \\parallel x_{0} \\parallel_{2}^{2}\\right)^{1/2}. $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(j) Expansion of a convex set by $a\\geq 0$, i.e., $\\{x\\in\\mathbb{R}^{n} \\:\\mid\\: {\\rm{dist}}(x,\\mathcal{S})\\leq a, \\quad \\mathcal{S}\\,\\text{convex}\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "#### Solution:\n",
    "Convex. Let $\\mathcal{S}_{a} := \\{x\\in\\mathbb{R}^{n} \\:\\mid\\: {\\rm{dist}}(x,\\mathcal{S})\\leq a, \\; \\mathcal{S}\\,\\text{convex}\\}$, and consider two points $x_{1}, x_{2} \\in \\mathcal{S}_{a}$. For $0 \\leq \\theta \\leq 1$,\n",
    "\n",
    "$$ {\\rm{dist}}\\left(\\theta x_{1} + (1-\\theta)x_{2},\\mathcal{S}\\right) = \\underset{y\\in\\mathcal{S}}{\\inf}\\:\\parallel \\theta x_{1} + (1-\\theta)x_{2} - y \\parallel_{2} \\:=\\: \\underset{y_{1}, y_{2}\\in\\mathcal{S}}{\\inf}\\:\\parallel \\theta x_{1} + (1-\\theta)x_{2} - \\theta y_{1} - (1-\\theta)y_{2} \\parallel_{2} \\\\\n",
    "= \\underset{y_{1}, y_{2}\\in\\mathcal{S}}{\\inf}\\:\\parallel \\theta (x_{1} - y_{1}) + (1-\\theta)(x_{2}-y_{2}) \\parallel_{2} \\:\\leq\\: \\underset{y_{1}, y_{2}\\in\\mathcal{S}}{\\inf}\\: \\left(\\theta\\parallel x_{1} - y_{1} \\parallel_{2} + (1-\\theta)\\parallel x_{2}-y_{2} \\parallel_{2}\\right) \\\\\n",
    "= \\theta\\:\\underset{y_{1}\\in\\mathcal{S}}{\\inf}\\:\\parallel x_{1} - y_{1} \\parallel_{2} \\:+\\: (1-\\theta)\\:\\underset{y_{2}\\in\\mathcal{S}}{\\inf}\\:\\parallel x_{2} - y_{2} \\parallel_{2} \\,\\leq\\: a.$$\n",
    "Thus, $\\theta x_{1} + (1-\\theta)x_{2} \\in \\mathcal{S}_{a}$, proving convexity."
   ]
  },
  {
   "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
}