#!/usr/bin/env python
# coding: utf-8

# # (Text exercises 2.21, 2.24, 2.25) Separating and supporting hyperplanes

# ## The set of separating hyperplanes
# (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}$).

# ## Explicitly write convex set as intersection of halfspaces
# 
# (5 points) Express the closed convex set $\{x \in \mathbb{R}^{2}_{+} \:\mid\: x_{1}x_{2} \geq 1\}$ as an intersection of halfspaces.

# ## Explicit computation of supporting hyperplanes
# 
# (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.

# ## Inner and outer polyhedral approximations
# (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
# 
# $$ \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\}. $$
# 
# Prove that $\mathcal{P}_{\text{inner}} \subseteq \mathcal{X} \subseteq \mathcal{P}_{\text{outer}}$. Draw a picture illustrating this.

# In[ ]: