1
$\begingroup$

For $\alpha\in\mathbb{R}^{n}$ and a set $A\in\mathbb{R}^{n}$ hold: $$\inf\{\langle\alpha,a\rangle: a\in A\}=\inf\{\langle\alpha,a\rangle: a\in conv(A)\}=\inf\{\langle\alpha,a\rangle: a\in clo(conv(A))\}$$. By conv we mean convex hull and by clo closure. Why is this true and the infimums are equal?

$\endgroup$
  • $\begingroup$ I cant think of an example where this isnt $-\infty$ $\endgroup$ – MONODA43 Oct 17 at 22:09
2
$\begingroup$

Let the three sets be $S_1, S_2, S_3$ respectively. We immediately have $\inf S_1 \ge \inf S_2 \ge \inf S_3$ so it remains to check the two reverse inequalities.

Hints:

  • For the first inequality, it suffices to show that for any $a' \in \text{conv}(A)$, there exists $a \in A$ such that $\langle \alpha, a \rangle \le \langle \alpha, a'\rangle$. (In plain words, going from $A$ to $\text{conv}(A)$ doesn't help make the inner product smaller.)
  • For the second inequality, the idea is that any element of $\text{clo}(\text{conv}(A))$ can be approximated by an element of $\text{conv}(A)$. Since the function $a \mapsto \langle \alpha, a \rangle$ is continuous and linear, you can quantify how much this approximation affects the value of the inner product, and show that in the end it is negligible.

Solution for the second inequality

Let $B = \text{conv}(A)$. We already know $(\inf S_3)$ is a lower bound for $S_2$ so it suffices to show it is the greatest lower bound. To do this, it suffices to show that for any fixed $\epsilon > 0$ we are able to find $a \in B$ such that $\langle \alpha, a \rangle \le (\inf S_3) + \epsilon$. To find such an $a$, consider $a' \in \text{clo}(B)$ such that $\langle \alpha, a' \rangle \le (\inf S_3) + \epsilon / 2$. Since $a'$ is in the closure of $B$, there exists $a \in B$ such that $\|a-a'\| < \frac{\epsilon}{2\|\alpha\|}$. Then, using the Cauchy-Schwarz inequality, $$\langle \alpha, a\rangle = \langle \alpha, a' \rangle + \langle \alpha, a - 'a \rangle \le (\inf S_3) + \frac{\epsilon}{2} + \|\alpha\| \frac{\epsilon}{2\|\alpha\|} = (\inf S_3) + \epsilon.$$

Solution for the first inequality

Any $a' \in \text{conv}(A)$ can be written as $c_1 a_1 + \cdots + c_n a_n$ for $a_1, \ldots, a_n \in A$ and $c_1, \ldots, c_n \ge 0$ summing to $1$. WLOG let $\langle \alpha, a_1 \rangle \ge \cdots \ge \langle \alpha, a_n \rangle$. Then $$\langle \alpha, a' \rangle = c_1 \langle \alpha, a_1 \rangle + \cdots + c_n \langle \alpha, a_n \rangle \ge \langle \alpha, a_n \rangle.$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot. Just one more question $\inf S_{1}\ge \inf S_{2}\ge \inf S_{3}$ follows from $A\subset conv(A)\subset clo(conv(A))$? $\endgroup$ – Laura Oct 18 at 7:27
  • $\begingroup$ @Laura Yes that's right $\endgroup$ – angryavian Oct 18 at 17:56
  • $\begingroup$ How does showing $\langle \alpha, a \rangle \le (\inf S_3) + \epsilon$ imply that $S_3$ is a lower bound for $S_2$? As far as I can tell this just shows that $S_2$ can be arbitrarily close to $S_3$. $\endgroup$ – MONODA43 Oct 18 at 20:00
  • 1
    $\begingroup$ @MONODA43 Sorry I wrote something incorrect, which I've fixed. We actually already know $\inf S_3$ is a lower bound; the goal is to show it is the greatest lower bound. Showing existence of $a$ such that $\langle \alpha, a \rangle \le (\inf S_3) + \epsilon$ suffices, since if for some $\epsilon$ this isn't possible, then you could obtain a larger lower bound. See Theorem 2 on this page for more detail. $\endgroup$ – angryavian Oct 18 at 20:29

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.