I'm currently struggeling with the following exercise:
Let $N \in \mathbb{N}$ and $x_1, ..., x_N \in \mathbb{R}^n$. Further let $c \in \mathbb{R}^n$. Prove by induction that there exists an $i \in \{1, ..., N \}$, such that $x_i$ is a solution to the following optimization problem:
$min_{x \in \mathbb{R}^n} c^Tx \ \ \ with \ \ \ x \in conv(x_1, ...,x_N)$
I tried the following:
I.B.: $N=1$
In this case the claim is clear.
I.H.:
There exists an $i \in \{1, ..., N \}$, such that $x_i$ is a solution to the following optimization problem:
$min_{x \in \mathbb{R}^n} c^Tx \ \ \ with \ \ \ x \in conv(x_1, ...,x_N)$
I.S.: $N \rightarrow N+1$
Let $x_1, ..., x_{N+1}$ be arbitrary points in $\mathbb{R}^n$ and let $\overline{x}$ be a solution for
$min_{x \in \mathbb{R}^n} c^Tx \ \ \ with \ \ \ x \in conv(x_1, ...,x_N)$
Since we are working with a convex hull we may consider a $\mathbb{\lambda} \in [0,1]^{N+1}$ such that
$\overline{x} = \sum_{i=1}^{N+1} \mathbb{\lambda}_ix_i \ \ \ \ and \ \ \ \ \sum_{i=1}^{N+1} \mathbb{\lambda}_i = 1$
If $\mathbb{\lambda}_{N+1} = 1$ the claim is clear. Else we may write:
$\overline{x} = (1-\mathbb{\lambda}_{N+1})*y + \mathbb{\lambda}_{N+1}*x_{N+1}$ $ \ \ \ where \ \ \ y = \sum_{i=1}^{N} \frac{\mathbb{\lambda}_i}{\sum_{j=1}^{N} \mathbb{\lambda}_i} x_i$
Now we should probably show that $\widetilde{x}$ or $x_{N+1}$ is optimal, but I don't know how to do that.
Could you help me wiht that?
Let $w = \min(c^T x_i: \; i=1\ldots N)$. If $x = \sum_i \lambda_i x_i \in \text{conv}(x_1,\ldots,x_N)$ with $\lambda_i \ge 0$, $\sum_i \lambda_i = 1$, then $c^T x = \sum_i \lambda_i c^T x_i \ge \sum_i \lambda_i w = w$.