# Proving that the optimal solution of an LP is a point on the convex hull

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$.
• The inequality shows that the optimal objective value is at least $w$, but you know $w$ is attained by at least one of the $x_i$, so ... – Robert Israel Mar 16 '18 at 5:56
• I'm sorry but I still don't get what you are up to. Your above inequality only references the indices ${1,...,N}$, so the $N+1$ seems to be missing. – 3nondatur Mar 16 '18 at 6:06
• What $N+1$? I'm not using induction. Well, you could adapt this to an induction-style proof if you really want to. Every point of $\text{conv}(x_1,\ldots, x_{N+1})$ is $\lambda y + (1-\lambda) x_{N+1}$ where $0 \le \lambda \le 1$ and $y \in \text{conv}(x_1, \ldots, x_N)$. – Robert Israel Mar 16 '18 at 6:50