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

# # (3 x 10 = 30) Which of the following sets are convex? In each case, give detailed reasons for your answer.

# (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} \}$.

# #### Solution:
# 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. 
# 
# We have
# $$ (\widehat{x}+tv)^{\top}A(\widehat{x}+tv) \:+\: b^{\top}(\widehat{x}+tv) \:+\: c = \alpha t^{2} + \beta t + \gamma, $$
# where
# $$ \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}.$$
# 
# The intersection of our set of interest with the line defined by $\widehat{x}$ and $v$, is the set
# $$ \{\widehat{x} + tv \:\mid\: \alpha t^{2} + \beta t + \gamma \:\leq\: 0\}, $$
# 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.

# (b) Hyperbolic set, i.e., $\{x \in \mathbb{R}^{n}_{+} \: \mid \: \displaystyle\prod_{i=1}^{n}x_{i} \geq 1\}.$

# #### Solution:
# 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 
# $$ a^{\theta}b^{1-\theta} \leq \theta a + (1-\theta) b, \quad a, b \geq 0, \quad 0 \leq \theta \leq 1,$$
# we have
# $$ \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.$$

# (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}\}$.

# #### Solution: 
# Convex (in fact, a polyhedron) since it is an intersection of 2 halfspaces.

# (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}\}$.

# #### Solution: 
# Convex (in fact, a polyhedron) since it is an intersection of finite number of halfspaces.

# (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}\}$.

# #### Solution: 
# Convex (in fact, a polyhedron) since it is an intersection of 2 halfspaces. It is a cone for $b_{1} = b_{2} = 0$.

# (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}\}$.

# #### Solution: 
# Convex because the set can be expressed as
# $$\bigcap_{y\in\mathcal{S}}\{x\in\mathbb{R}^{n} \:\mid\: \parallel x - x_{0}\parallel_{2} \:\leq\: \parallel x - y\parallel_{2}\},$$
# 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.

# (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}\}$.

# #### Solution:
# In general, this set is not convex. As counterexample, consider $n=1$ with $\mathcal{S} = \{-1,1\}$, and $\mathcal{T}=\{0\}$. Then
# $$\{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\},$$
# which is not convex.

# (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}\}$.

# #### Solution:
# 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, 
# $$ \{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),$$
# the intersection of convex sets $(\mathcal{S}_{1} - y)$, hence convex.

# (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\}$.

# #### Solution:
# Convex. Notice that
# $$ \{x \:\mid\: \parallel x - a \parallel_{2} \:\leq\: \theta\parallel x - b \parallel_{2}\}
# = \{x \:\mid\: \parallel x - a \parallel_{2}^{2} \:\leq\: \theta^{2}\parallel x - b \parallel_{2}^{2}\}
# =  \{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 \}.$$
# If $\theta=1$, then the above set is a halfspace. If $\theta < 1$, then it is a ball
# $$ \{x\in\mathbb{R}^{n} \:\mid\: (x-x_{0})^{\top}(x-x_{0}) \leq r^{2}\},$$
# with center $x_{0}$ and radius $r$, given by
# $$ 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}. $$

# (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}\}$.

# #### Solution:
# 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$,
# 
# $$ {\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} \\
# = \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) \\
# = \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.$$
# Thus, $\theta x_{1} + (1-\theta)x_{2} \in \mathcal{S}_{a}$, proving convexity.

# In[ ]: