0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I'm sorry, but I don't get how this is connected to my problem above. $\endgroup$ – 3nondatur Mar 16 '18 at 2:30
  • $\begingroup$ 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 ... $\endgroup$ – Robert Israel Mar 16 '18 at 5:56
  • $\begingroup$ 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. $\endgroup$ – 3nondatur Mar 16 '18 at 6:06
  • $\begingroup$ 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)$. $\endgroup$ – Robert Israel Mar 16 '18 at 6:50
  • $\begingroup$ Ah, now I understand what you mean. $\endgroup$ – 3nondatur Mar 16 '18 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.