Can we describe the conic hull of a set with this formula?

483 Views Asked by At

Can we describe the conic hull of a set with this formula:

\begin{equation*} \text{Conic} \space C = \{\textbf x=\textbf x_0+ \theta \textbf{v} | \textbf x_0 = \textbf 0_n , \textbf{v} \in \text{conv} \space C , \theta\in \ \mathbb R_{+}\} \end{equation*}

where $\text{conv} \space C$ is the covex hull of the set $C$.


Definition of conic hull:

$\text{Conic} \space C = \{\Sigma_{i=1}^{k}\theta_i x_i | x_i \in C, \theta_i\in\mathbb R_+\}$

it is the set of conic combinations of some points of $C$.


My proof:

$K = \{\theta \textbf v| \textbf v \in \text{conv} \space C, \theta \in \mathbb R_+ \} = \text{conic C}$

For proving this: we should show $K \subseteq \text{conic C}$ and $\text{conic C} \subseteq K$.

a. $K \subseteq \text{conic C}$:

suppose $\textbf{x} \in K$, then: $\textbf{x} = \theta \textbf{v}$ where $\textbf{v} \in \text{conv} \space C$, $\theta \in \mathbb R_+$ $\Rightarrow$ $\textbf{v} = \sum_{i} {\theta_i} x_i$, $x_i \in C$, $\Rightarrow$ $\frac{x}{\theta} = \sum_{i} {\theta_i}x_i$ $\Rightarrow$ $x = \sum_{i} {\alpha_i x_i}$ where ${\alpha_i} = \theta_i \theta$ $\in \mathbb R_+$ $\Rightarrow$ $\textbf{x} \in \text{conic C}$.

b. $\text{conic C} \subseteq K$:

suppose $\textbf{x} \in \text{conic C}$, then: $\textbf{x} = \sum_i{\theta}_i x_i$, where $x_i \in C$, $\theta_i \in \mathbb R_+$ $\Rightarrow$ $\frac{{\textbf{x}}}{\theta} = \sum_i{\frac{\theta_{i}}{\theta}}{x_i} $ where $\theta = \sum_i{\theta_i}$ $\Rightarrow$ $\frac{{\textbf{x}}}{\theta} = \sum_i{\lambda_{i}}{x_i} $ where $\sum_i {\lambda_{i}} = 1$ $\Rightarrow$ $\textbf{x} = \theta \textbf{v}$ where $\textbf{v} = \sum_i{\lambda_{i}}{x_i} \in \text{conv} \space C$.

Hence: $K = \text{conic C}$.

1

There are 1 best solutions below

1
On BEST ANSWER

Let $C \in \mathbb{R}^n$ and define:

$$\text{Co}(C)=\{\theta\cdot v\in \mathbb{R}^n\,|\,v \in \text{conv}(C), \theta \in \mathbb{R}_+\}$$

$\text{$(1)$: $\text{Co}(C)\subset \text{Conic}(C)$}$

Let $x=\theta\cdot v\in \text{Co}(C)$, where $v \in \text{conv}(C)$ and $\theta \in \mathbb{R}_+$. Since $v \in \text{conv}(C)$, there must be some $n \in \mathbb{N}$ and $\alpha_i \geq0,v_i \in C$ with

$$\sum_{i=1}^n\alpha_i\cdot v_i=v\\ \sum_{i=1}^n\alpha_i=1$$

Then $x=\sum_{i=1}^n\underbrace{(\theta\cdot \alpha_i)}_{\in \mathbb{R}_+}\cdot v_i$ and hence lies in $\text{Conic}(C)$.

$\text{$(2)$: $\text{Conic}(C)\subset \text{Co}(C)$}$

Indeed, let $x=\sum_{i=1}^k\theta_i\cdot x_i \in \text{Conic}(C)$, where $x_i \in C$ and $\theta_i\in\mathbb{R}_+$. Let $\theta=\sum_{i=1}^k\theta_i$. If $\theta=0$, then all $\theta_i$ are zero and $x=0$, so $x$ lies in $\text{Co}(C)$.

Now, suppose $\theta>0$ and let $\alpha_i=\frac{\theta_i}{\theta}$. Then $\alpha_i\geq0$ and $\sum_{i=1}^k \alpha_i=1$. Then $v=\sum_{i=1}^k\alpha_i\cdot x_i$ lies in $\text{conv}(C)$. Finally, it suffices to check that $x=\theta\cdot v$ to conclude that $x \in \text{Co}(C)$.


Together, inclusions $(1)$ and $(2)$ imply that $\text{Co}(C)=\text{Conic}(C)$, so the answer is yes.