: Convex sets<a class="btn btn-sm" href="/UUID/EDB/2F0/?lang=eng"><span class="ttfamily"><small class="scriptsize">[2F0]</small></span></a>

15.1 Convex sets[2F0]

Definition 360

[16W]Given $x_ 1,\ldots x_ k∈ ℝ^ n$ , given $t_ 1,\ldots t_ k≥ 0$ with $t_ 1+\cdots + t_ k=1$, the sum

\[ x_ 1 t_ 1+\cdots + x_ k t_ k \]

is a convex combination of the points $x_ 1,\ldots x_ k$.

Remark 361

[23P]If $k=2$ then the convex combination is usually written as $(tx+(1-t)y)$ with $t∈ [0,1]$; the set of all these points is the segment that connects $x$ to $y$.

Definition 362

[16X] Let $C⊆ ℝ^ n$ be a set; it is called convex if

\[ ∀ t∈[0,1],~ ~ ∀ x,y∈ C, ~ ~ (tx+(1-t)y)∈ C \]

that is, if the segment connecting each $x,y∈ C$ is all inclusive in $C$.

(We note that $∅$ is a convex set, and that every vector subspace or affine subspace of $ℝ^ n$ is convex).

Convex sets enjoy a lot of interesting properties, this one below is just a small list.

Topology

E362

[16Y] Let $C⊆ ℝ^ n$ be a set; show that it is convex if and only if it contains every convex combination of its points, that is: for every $k≥ 1$, for every choice of $x_ 1,\ldots x_ k∈ C$ , for each choice $t_ 1,\ldots t_ k≥ 0$ with $t_ 1+\cdots + t_ k=1$, you have

\[ x_ 1 t_ 1+\cdots + x_ k t_ k ∈ C\quad . \]

E362

[16Z] Topics:simplex.

Given $x_ 0,\ldots x_ k∈ ℝ^ n$, let

\begin{equation} \left\{ ∑_{i=0}^ k x_ i t_ i : ∑_{i=0}^ k t_ i=1 ∀ i, t_ i≥ 0 \right\} \label{eq:simplesso} \end{equation}

363

the set of all possible combinations: prove that this set is convex.

When the vectors $x_ 1-x_ 0,x_ 2-x_ 0\ldots x_ k-x_ 0$ are linearly independent, the set defined above is a simplex of dimension $k$.

Show that, if $n=k$, then the simplex has a non-empty interior, equal to

\begin{equation} \left\{ ∑_{i=0}^ n x_ i t_ i : ∑_{i=0}^ n t_ i=1 ∀ i, t_ i> 0 \right\} \label{eq:interno_ simplesso} \end{equation}

364

E362

[170] Let $A⊂ ℝ^ n$ be a convex set containing at least two points, and $V$ the smallest affine space that contains $A$ (show that this concept is well defined); and, viewing $A$ as a subset of $V$, prove that $A$ has non-empty inner part. Hidden solution: [UNACCESSIBLE UUID ’171’]

E362

[172] If $A⊂ ℝ^ n$ is convex, $x∈ {{A}^\circ }$ and $y∈ A$ then the segment that links them is contained in ${{A}^\circ }$, except possibly for the extreme $y$, that is, $∀ t∈(0,1), t x+(1-t)y∈ {{A}^\circ }$. Hidden solution: [UNACCESSIBLE UUID ’173’]

E362

[174] Prerequisites:4,1.If $A⊂ ℝ^ n$ is convex, $x∈ {{A}^\circ }$ and $z∈ ∂ A$ then the segment that connects them is contained in ${{A}^\circ }$, except possibly for the extreme $z$ (i.e. $∀ t∈(0,1), tx+(1-t)z∈ {{A}^\circ }$). Hidden solution: [UNACCESSIBLE UUID ’175’]

E362

[176] Given $A⊂ ℝ^ n$ convex, show that its interior, as well as its closure, are still convex. Hidden solution: [UNACCESSIBLE UUID ’177’]

E362

[178] Prerequisites:286,5.Given $A⊂ ℝ^ n$ convex with non-empty interior, show that $\overline A= \overline{({{A}^\circ })}$ (the closure of the interior of $A$). Then find a simple example of $A$ for which $\overline A≠ \overline{({{A}^\circ })}$. Hidden solution: [UNACCESSIBLE UUID ’179’]

E362

[17B] Prerequisites:7.Difficulty:*.

Given $A⊂ ℝ^ n$ convex, show that ${{A}^\circ }={{\Big(\overline A\Big)}^\circ }$ (the inner part of the closure of $A$).

Using 3 it is easily shown that ${{A}^\circ }⊇ {{\Big(\overline A\Big)}^\circ }$; unfortunately this result is useful in one of the possible proofs of 3 (!); an alternative proof uses simplexes as neighbourhoods, cf 2. Hidden solution: [UNACCESSIBLE UUID ’17C’]

E362

[059]Suppose that $C_ i⊆ℝ^ n$ are convex sets, for $i∈\ I$: prove that

\[ ⋂_{i∈ I} C_ i \]

is convex.

Definition 365

[2G4]Let then $A⊆ℝ^ n$ be a non-empty set, the convex hull (or convex envelop) $co(A)$ of $A$ is the intersection of all convex sets containing $A$. Because of 9, $co(A)$ is the smallest convex sets containing $A$.

Projection, separation

E365

[17D] Topics:projection.Difficulty:*. Note:This is the well-known ”projection theorem”, which holds for $A$ convex closed in a Hilbert space; if $A⊂ ℝ^ n$ then the proof is simpler, and it’s a useful exercise..

Given $A⊂ ℝ^ n$ closed convex non-empty and $ z∈ ℝ^ n$, show that there is only one minimum point $x^*$ for the problem

\[ \min _{x∈ A} \| z-x\| ~ . \]

Show that $x^*$ is the minimum if and only if

\[ ∀ y∈ A , ⟨ z-x^*, y-x^* ⟩≤ 0 ~ ~ . \]

$x^*$ is called ”the projection of $z$ on $A$”.

$\includegraphics[width=0.9\linewidth ]{UUID/1/7/F/blob_zxx}$

(Note that this last condition is simply saying that the angle must be obtuse.)

Hidden solution: [UNACCESSIBLE UUID ’17G’]

E365

[17H] Topics:separation. Prerequisites:1.

Given $A⊂ {\mathbb {R}}^ n$ closed non-empty convex and $z∉ A$, let $x^*$ be defined as in the previous exercise 1; define $𝛿=\| z-x^*\| $, $v= (z-x^*)/𝛿$ and $a=⟨ v,x^*⟩$. Prove that $v,a$ and $v,a+𝛿$ define two parallel hyperplanes that strongly separate $z$ from $A$, in the sense that $⟨ z,v⟩=a+𝛿$ but $∀ x∈ A,⟨ x,v⟩≤ a$.

E365

[17J] Topics:separation. Difficulty:*.

This result applies in very general contexts, and is a consequence of Hahn–Banach theorem (which makes use of Zorn’s Lemma); if $A⊂ ℝ^ n$ it can be proven in an elementary way, I invite you to try.

Given $A⊂ ℝ^ n$ open convex non-empty and $ z∉ A$, show that there is a hyperplane $P$ separating $ z$ from $A$, that is, $z\in P$ while $A$ is entirely contained in one of the two closed half-spaces bounded by the hyperplane $P$. Equivalently, in analytical form, there exist $a∈ℝ,v∈ℝ^ n,v≠ 0$ such that $⟨ z,v⟩=a$ but $∀ x∈ A,⟨ x,v⟩{\lt}a$; and

\[ P = \{ y\in {\mathbb {R}}^ n : ⟨ y,v⟩=a \} ~ . \]

The hyperplane $P$ thus defined is called supporting hyperplane of $z$ for $A$.

There are (at least) two possible proofs. A possible proof is made by induction on $n$; we can assume without loss of generality that $ z=e_ 1=(1,0\dots 0),0∈ A, a=1$; keep in mind that the intersection of a convex open sets with $ℝ^{n-1}× \{ 0\} ⊂ℝ^ n$ is an open convex set in $ℝ^{n-1}$; this proof is complex but does not use any prerequisite. A second proof uses 6 and 2 if $z∉∂ A$; if $z∈∂ A$ it also uses 7 to find $(z_ n)⊂ {{(A^ c)}^\circ }$ with $z_ n→ z$ . Hidden solution: [UNACCESSIBLE UUID ’17K’]

E365

[17M] Prerequisites:3,2.If $A,B$ are disjoint convex, with $A$ open, show that there is a hyperplane separating $A$ and $B$, that is, there exist $v∈ℝ^ n,v≠ 0$ and $c∈ℝ$ such that

\begin{equation} ∀ x∈ A,⟨ x,v⟩< c \text{~ but ~ } ∀ y∈ B,⟨ y,v⟩≥ c ~ ;\label{eq:separa_ due_ convessi_ aperti} \end{equation}

366

moreover show that if also $B$ is open, then you can have strict separation (i.e. strict inequality in the last term in ??).

(Hint: given $A,B⊆ ℝ^ n$ convex nonempty, show that

\[ A-B{\stackrel{.}{=}}\{ x-y,x∈ A, y∈ B\} \]

is convex; show that if $A$ is open then $A-B$ is open, as in 2.) Hidden solution: [UNACCESSIBLE UUID ’17N’]

E365

[17P]Find an example of open convex sets $A,B⊂ℝ^ 2$ with $\overline A,\overline B$ disjoint, and such that there is a single hyperplane separating them (i.e. an ”unique” choice of $v,c$ that satisfies ??; ”unique”, up to multiplying $v,c$ by the same positive constant). Hidden solution: [UNACCESSIBLE UUID ’17Q’]

E365

[17R] Prerequisites:3.If $A⊂ ℝ^ n$ is convex, $x∈ {{A}^\circ }$ and $y∈∂ A$, then the straight line that connects them, continuing over $y$, stays out of $\overline A$ (i.e. $∀ t{\gt}1, ty+(1-t)x∉ \overline A$). Hidden solution: [UNACCESSIBLE UUID ’17S’]

E365

[17T] Topics:separation,support. Prerequisites: 3,3, 8.

Given $A⊂ ℝ^ n$ convex non-empty and $z∈ ∂ A$, prove that there exist $v∈ℝ^ n,a∈ℝ$ such that $⟨ z,v⟩= a$ and $∀ x∈ A,⟨ x,v⟩≤ a$. The hyperplane thus defined is called support hyperplane of $z$ for $A$. Hidden solution: [UNACCESSIBLE UUID ’17V’]

E365

[17W]Difficulty:*.Given a set $A⊂ ℝ^ 2$ bounded convex open nonempty, show that $∂ A$ is support of a closed simple arc (that is also Lipschitz continuous).

Hidden solution: [UNACCESSIBLE UUID ’17X’]