0
$\begingroup$

$A \subset \mathbb{R}^n$, $P, Q \in \mathbb{R}^n$, $Conv$ is the convex hull operator, defined as

$$ Conv(\{ a_1, a_2, ..., a_n \}) = \left \{ \ \Sigma \ a_i \lambda_i \mid \lambda_i \in \mathbb{R}, \Sigma \ \lambda_i = 1, \lambda_i \geq 0 \right \} $$

The assertion seems reasonable enough, and I got this far:

Let $A = \{a_1, a_2, \ldots, a_n \}$

$$ p = \sum a_i \lambda_i + (1 - \lambda) q $$

Where $\lambda = \sum \lambda_i$, and $\lambda > 0$, since $p \notin \text{Conv}(A)$.

Similarly,

$$ q = \sum a_i \delta_i + (1 - \delta) p $$

where $\delta = \sum \delta_i$, $\delta > 0$.

Now, I considered $p + q$:

$$ p + q = \sum (\lambda_i + \delta_i) a_i + (1 - \lambda)q + (1 - \delta) p \\ \lambda p + \delta q = \sum(\lambda_i + \delta_i) a_i \\ \frac{\lambda p + \delta q}{\lambda + \delta} = \sum\frac{(\lambda_i + \delta_i)}{\lambda + \delta} a_i $$

This tells us that the point that divides the line segment $p q$ in the ratio $\lambda \ : \delta$ lies in the convex hull of $A$, as $\sum\frac{(\lambda_i + \delta_i)}{\lambda + \delta} = 1$, and $\frac{(\lambda_i + \delta_i)}{\lambda + \delta} \geq 0$, and is well defined since $\lambda > 0, \delta > 0$.

But, now what? I was hoping to show that such a point must converge onto $p$ or $q$, but I've been having no such luck in proving this. I wanted to write $\lambda : \delta = k : 1$ and then proceed to solve, but it seemed far too messy for such a cute problem.

$\endgroup$
  • $\begingroup$ According what wrote here you should have written $0 \leq \lambda < 1$ and $ 0 \leq \delta < 1 $. So you should correct rest of your solution! it is incorrect ! $\endgroup$ – Red shoes May 22 '17 at 9:25
1
$\begingroup$

Since $p \notin Conv(A)$ , $$ext [Conv(A \cup \{p\})] = ext(A) \cup \{p\}$$similarly$$ext [Conv(A \cup \{q\})] = ext(A) \cup\{q\}$$

now taking into account the assumptions shows that$$Conv(A \cup \{p\})= Conv(A \cup\{q\}) $$ Therefore $$ext(A) \cup \{p\} = ext(A) \cup \{q\}$$ which implies $p=q$ (since $p,q \notin ext(A) ).$

$\endgroup$
  • $\begingroup$ Could you expand on "now taking into account the assumptions.."? I'm not sure how you got there $\endgroup$ – Siddharth Bhat May 22 '17 at 9:14
  • $\begingroup$ @SiddharthBhat LHS contains both $A$ and $q$ so it does contain RHS, similarly RHS contains LHS. $\endgroup$ – Red shoes May 22 '17 at 9:22

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.