The Eigenspace

BibliographyComments
/Part 7: Notes/Chapter 13: Convex and Nonlinear Analysis

13.1 Notations

[1]

Definition 13.1.1 (Convex Set).label A set $c\suf\R^{n}$ is convex if it satisfies at least one of the following

  • $c=\emp$

  • $\fall x,y\in c,\lam\in[0,1]$ we have $\lam x+(1-\lam)y\in c$

Example 13.1.2 (Convex Sets).label

  1. (1)

    $(a,b),[a,b),(-\infty,b]$ are convex

  2. (2)

    A disc, ball, half space are all convex

  3. (3)

    The union of convex sets is normally not convex

Lemma 13.1.3 (Half Space).label Let $a\in \R^{n}\del \curl{0},c\in\R$ then the half space

\begin{align*}H=\curl{x\in\R^n:\inner{a}{x}\leq c}\end{align*}

is convex.

Proof. Let $x,y\in H,\lam\in[0,1]$ then $\inner{a}{x},\inner{a}{y}\leq c$. By linearity of inner product

\begin{align*}\inner{a}{\lam x+(1-\lam)y}=\lam\inner{a}{x}+(1-\lam)\inner{a}{y}\leq \lam c+(1-\lam)c=c\end{align*}

$\square$

Lemma 13.1.4 (Convex Intersection).label Let $\curl{C_\al}_{\al\in A}\suf 2^{\R^n}$ be a collection of convex sets then $A=\caps{}{\al\in A}C_{\al}$ is convex.

Proof. Obvious.$\square$

Definition 13.1.5 (Convex Combination).label Let $x_{1},...,x_{m}\in\R^{n}$ then a convex combination of them is any point of the form

\begin{align*}\sums{m}{i=1}\lam_{i} x_{i}&&\lam_{i}\geq 0,\fall i\end{align*}

Theorem 13.1.6 (Convex Criteria).label Let $c\suf\R^{n}$ then the following are equivalent

  1. (1)

    $c$ is convex

  2. (2)

    $\fall m\geq 2\in\Z,\curl{x_i}_{1}^{m}\in c$ and for each $\lam_{1},...,\lam_{m}\geq0$ such that $\sums{m }{i=1}\lam_{i}=1$ we have $\sums{m }{i=1}\lam_{i}x_{i}\in C$

Proof. The proof is by induction on $m$ with base case given by convexity. Let $\curl{x_i }_{1}^{m+1}\in c$, $\lam_{1},...,\lam_{m+1}\geq 0$ such that $\sums{m+1 }{i=1}\lam_{i}=1$. WLOG $\lam_{i}\nin \curl{0,1}$ for each $i$. Observe $s\define \sums{m }{i=1}\lam_{i}\in (0,1)$ so

\begin{align*}\sums{m+1 }{i=1}\lam_{i}x_{i}=s \sums{m }{i=1}\frac{\lam_{i}}{s}x_{i}+\lam_{m+1}x_{m+1}\end{align*}

Since $\sums{m }{i=1}\frac{\lam_{i}}{s}=1$, by induction hypothesis $s \sums{m }{i=1}\frac{\lam_{i}}{s}x_{i}\in c$ hence $\sums{m+1 }{i=1}\lam_{i}x_{i}\in c$ as well.$\square$

Definition 13.1.7 (Affine Combination ).label An affine combination of points $x_{1},...,x_{m}\in\R^{n}$ is $\sums{m }{i=1}\lam_{i}x_{i}$ for $\lam_{i}\in\R,\sums{m }{i=1}\lam_{i}=1$

Definition 13.1.8 (Affine Hull).label Let $c\suf \R^{n}$ be nonempty then the affine hull of $c$, denoted $Aff(c)$, is the set of all affine combination of points of $c$. $Aff(c)$ is the smallest affine set containing $c$ so we define $\dim(c)\define \dim(Aff(c))$

Definition 13.1.9 (Relative Interior).label Let $c\suf\R^{n}$ be nonempty then the relative interior of $c$ is

\begin{align*}Reint(c)\define \curl{x\in c:\exists r>0,B(x,r)\cap Aff(c)\suf c}\end{align*}

which can be viewed as taking interior inside $Aff(c)$ viewed as a subspace.

Definition 13.1.10 (Convex Hull).label Let $c\suf\R^{n}$ be nonempty then the convex hull of $c$ is

\begin{align*}Conv(c)\define \caps{}{}\curl{C_\al:C_\al\text{ convex, }C_\al\supf C}\end{align*}

Theorem 13.1.11 (Convex Properties).label Let $c\suf\R^{n}$ be nonempty then

  1. (1)

    $Conv(c)$ is the smallest convex set containing $c$

  2. (2)

    $c$ is convex if and only if $Conv(c)=c$

  3. (3)

    $Conv(c)=\curl{\sums{m}{i=1}\lam_ix_i:\curl{\lam_i}_1^m\suf[0,1],\curl{x_i}_1^m\suf c,\sums{m }{i=1}\lam_i=1}$

Proof.

  1. (1)

    Follows from Lemma 13.1.4

  2. (2)

    We note $c\suf c$ so if $c$ is convex then $Conv(c)\suf c$ hence $Conv(c)=c$. Conversely $Conv(c)$ is convex.

  3. (3)

    Check

$\square$

Definition 13.1.12 (Affinely Independent).label We say $\curl{v_0,...,v_k}\suf\R^{n}$ is affinely independent if $v_{1}-v_{0},...,v_{k}-v_{0}$ are linearly independent. This is independent of the ordering. We call $Conv(\curl{v_0,v_1,...,v_k})$ a $K$-simplex

Definition 13.1.13 (Polytope).label A polytope is the convex hull of a finite set of points. A polyhedron is a finite intersection of half spaces

Definition 13.1.14 (Norm in $\R^{n}$).label A norm in $\R^{n}$ is $\norm{\cd}{}:\R^{n}\to[0,\infty)$ such that

  1. (1)

    $\norm{x}{}=0\iff x=0$

  2. (2)

    $\norm{\lam x}{}=\abs{\lam}\norm{x}{}$ for all $\lam\in\R$

  3. (3)

    $\norm{x+y}{}\leq\norm{x}{}+\norm{y}{}$

Proposition 13.1.15 (Convexity of Ball).label For any $\norm{\cd}{}$ on $\R^{n}$ and any $r>0$ the closed ball $B_{\norm{\cd}{}}(0,r)=\curl{x\in\R^n:\norm{x}{}\leq r}$ is convex.

Proof. Observe

\begin{align*}\norm{\lam x+(1-\lam)y}{}\leq \lam\norm{x}{}+(1-\lam)\norm{y}{}\leq \lam r+(1-\lam)r=r\end{align*}

$\square$

Definition 13.1.16 (Affine Map).label A map $T:\R^{n}\to\R^{m}$ is affine if $T(x)=L(x)+b$ for a linear map $L:\R^{n}\to\R^{m}$ and a fixed vector $b\in\R^{m}$

Lemma 13.1.17 (Image of Convex).label Let $c\suf\R^{n}$ be convex and $T$ is linear or affine then $T(c)$ is convex.

Proof. Let $u,v\in T(c)$ then $u=T(x),v=T(y)$ for some $x,y\in c$. Let $\lam\in [0,1]$ then

\begin{align*}\lam u+(1-\lam v)&=\lam T(x)+(1-\lam)T(y)\\&=\lam L(x)+\lam b+(1-\lam)L(y)+(1-\lam)b\\&=\lam L(x)+(1-\lam)L(y)+b\\&=L(\lam x+(1-\lam)y)+b\\&=T(\lam x+(1-\lam)y)\in T(c)\end{align*}

$\square$

Theorem 13.1.18 (Caratheodory).label Let $A\suf\R^{n}$ then $\fall x\in Conv(A)$, $\exists \curl{\lam_i}_{1}^{n+1}\geq 0,\sums{n+1 }{i=1}\lam_{i}=1$ and $\curl{x_i}_{1}^{n+1}\in A$ such that $x=\sums{n+1}{i=1}\lam_{i}x_{i}$.

Proof. Suppose $\exists x\in Conv(A)$ such that $x=\sums{m}{i=1}\lam_{i}x_{i},m=n+2,\sums{m }{i=1}\lam_{i}=1,x_{i}\in A,i=\cl{i,m}$. WLOG $\lam_{i}\neq 0,i=\cl{1,m}$. Consider $x_{1}-x_{m},...,x_{m-1}-x_{m}\implies \exists a_{i}\in \R$ such that $\sums{m-1}{i=1}a_{i}(x_{i}-x_{m})=\vec{0}$. Let $a_{m}\define -\sums{m-1}{i=1}a_{i}$ then

  • $\sums{m }{i=1}a_{i}=0$

  • $\sums{m }{i=1}a_{i}x_{i}=\vec{0}$

  • $\sums{m-1}{i=1}a_{i}x_{i}-\parens{\sums{m-1}{i=1}a_i}x_{m}=\vec{0}$

We can assume that at least one of $a_{i}$ is positive and define

\begin{align*}t&\define \MIN{i:a_i>0}\frac{\lam_{i}}{a_{i}}>0\\ \mu_{i}&\define \lam_{i}-ta_{i}&&i=\cl{1,m}\end{align*}

Observe $\mu_{i}\geq 0,i=\cl{1,m}$ since $a_{i}t<\lam_{i}$ for all $i$ such that $a_{i}>0$. Furthermore

\begin{align*}\sums{m}{i=1}\mu_{i}=\sums{m }{i=1}\lam_{i}-t \sums{m }{i=1}a_{i}=1-0=1\end{align*}

Consider

\begin{align*}\sums{m }{i=1}\mu_{i}x_{i}=\sums{m}{i=1}\lam_{i}x_{i}-t \sums{m}{i=1}a_{i}x_{i}=x-0\end{align*}

Hence $x$ can be written as the convex combination of $n+1$ points.$\square$

Corollary 13.1.19.label If $A\suf\R^{n}$ is compact then $Conv(A)$ is compact.

Example 13.1.20 (Infinite Dimensional Vector Space).label $V\define C(\R;\R)$ is a vector space over $\R$ under pointwise addition and scalar multiplication. We observe $\dim(V)=\infty$ since $\curl{1,e^x,...,e^{mx}}$ is a family of independent vectors such that $e^{kx}$ for $k>m\in\N$ is not in the span of this set.

We note that Corollary 13.1.19 is not true if $A$ is compact in an infinite dimensional vector space. This is because $Conv(A)$ may not be closed. [2]

Definition 13.1.21 (Separating Hyperplanes for Convex Sets in $\R^{n}$).label Let $H\suf\R^{n}$ be subsets then $H$ is a hyperplane if $\exists a\in\R^{n}\del \curl{\vec{0}}, \al\in\R$ such that $H=\curl{x\in\R^n:\inner{x}{a}=\al}$. Let $A,B\suf\R^{n}$ be subsets then a hyperplane $H:\inner{x}{a}=\al$ (equivalently, the pair $(a,\al)$) weakly separates $A$ and $B$ if $\fall x\in A,y\in B$

\begin{align*}\inner{x}{a}\leq \al\leq \inner{y}{a}\end{align*}

The following are equivalent

  1. (CS1)

    $\exists \e>0$ such that

    \begin{align*}\inner{x}{a}\leq \al-\e&&\inner{y}{a}\geq \al+\e\end{align*}

  2. (CS2)

    $\SUP{x\in A}\inner{x}{a}<\INF{y\in B}\inner{y}{a}$

$H$ strongly separates $A$ and $B$ if it satisfies the above conditions.

Example 13.1.22 (Separated).label Consider

\begin{align*}A=\curl{(x,e^x:x\in\R)}&&B=\curl{(x,0):x\in\R}\end{align*}

then $A\cap B=\emp$. $A$ and $B$ are weakly separated since

\begin{align*}\inner{(x_1,x_2)}{\UBC{(0,1)}{a}}&=\UBC{0}{\al}\\ \inner{(x,e^x)}{(0,1)}&=e^{x}>0\\ \inner{(x,0)}{(0,1)}&=0\leq 0\end{align*}

However $A$ and $B$ are not strongly separated since they ”touch” (the sup and inf approaches each other) at $-\infty$. We can change $A=\curl{(x,y):y\geq e^x}$ to get $A,B$ convex and in context of Theorem 13.1.26 $A,B$ are both not bounded.

Lemma 13.1.23 (Nearest-Point Projection).label Let $\vec{0}\nin E\neq\emp\suf\R^{n}$ be closed convex then $\exists! z\in E$ which attains $\INF{x\in E}\norm{x-\vec{0}}{}$ and

\begin{align*}\inner{z}{x}\geq\norm{z}{}^{2}>0&&\fall x\in E\end{align*}

We can upgrade this from $\vec{0}$ to any $x_{0}\in\R^{n}$ by Lemma 13.1.24

Proof. Existence Fix $x_{0}\in E$ and $R\define \norm{x_0}{}$. The set $E\cap \cl{B}(0,R)$ is closed and bounded hence compact, and nonempty since it contains $x_{0}$. The continuous function $x\mto \norm{x}{}$ attains its minimum at some $z\in E$. For $x\in E$ with $\norm{x}{}>R$ we have $\norm{x}{}>R\geq \norm{z}{}$ so $z$ minimizes $\norm{\cd}{}$ over all of $E$.

Uniqueness Suppose $z_{1}\neq z_{2}\in E$ both achieve the minimum value $m\define\MIN{x\in E}\norm{x}{}$. By convexity $\frac{z_{1}+z_{2}}{2}\in E$. By parallelogram identity

\begin{align*}\norm{\frac{z_{1}+z_{2}}{2}}{}^{2}=\frac{1}{2}\norm{z_1}{}^{2}+\frac{1}{2}\norm{z_2}{}^{2}-\frac{1}{4}\norm{z_1-z_2}{}^{2}=m^{2}-\frac{1}{4}\norm{z_1-z_2}{}^{2}<m^{2}\end{align*}

since $z_{1}\neq z_{2}$, contradicting minimality of $m$. Variational Inequality Let $x\in E$ and $t\in (0,1]$. By convexity $z+t(x-z)\in E$, so $\norm{z+t(x-z)}{}^{2}\geq \norm{z}{}^{2}$. Expanding we have

\begin{align*}\norm{z}{}^{2}+2t\inner{z}{x-z}+t^{2}\norm{x-z}{}^{2}\geq\norm{z}{}^{2}\implies 2\inner{z}{x-z}+t\norm{x-z}{}^{2}\geq 0\end{align*}

Letting $t\to 0^{+}$ gives $\inner{z}{x-z}\geq 0$ hence $\inner{z}{x}\geq \norm{z}{}^{2}$. Since $0\nin E,z\neq 0$ so $\norm{z}{}^{2}>0$.$\square$

Lemma 13.1.24.label Let $E\suf\R^{n}$ be convex (resp. closed) then $E-x_{0}=\curl{x-x_0:x\in E}$ is convex (resp. closed) for any $x_{0}\in\R^{n}$.

Proof. Obvious.$\square$

Theorem 13.1.25.label Let $C\suf\R^{n}$ be closed convex and $x_{0}\nin C$ then $C$ and $\curl{x_0}$ can be strongly separated

Proof. WLOG $0\nin C$ then by Lemma 13.1.23 then $\exists z\in C$ such that $\inner{z}{x}\geq \norm{z}{}^{2}$ for all $x\in C$. Let $\al=\frac{\norm{z}{}^{2}}{z}$ then

\begin{align*}\inner{z}{x}>\frac{\norm{z}{}^{2}}{z}=\al&&\fall x\in C\end{align*}

Since $x_{0}\nin C$ we have $\inner{z}{x_0}<\norm{z}{}^{2}\implies \inner{z}{x_0}<\frac{\norm{z}{}^{2}}{z}$ taking $\e\in (0,\al)$ we are done. If $0\in C$ and $z=0$ then consider $c-\de e$ for $\de>0$ and $\til{x_0}=x_{0}-\de e$.$\square$

Theorem 13.1.26 (Separating Hyperplane).label Let $A,B$ be convex disjoint sets in $\R^{n}$ then

  1. (1)

    If $A$ is compact and $B$ is closed then $A$ and $B$ can be strongly separated.

  2. (2)

    $A$ and $B$ can always be weakly separated.

Proof.

  1. (1)

    Let $E=A-B$ then $0\nin E$. $E$ is convex. $\lam\in [0,1]$ and $z_{1},z_{2}\in E$

    \begin{align*}(1-\lam)z_{1}+\lam z_{2}=(1-\lam)(x_{1}-y_{1})+\lam (x_{2}-y_{2})=\braks{(1-\lam)(x_1)+\lam (x_2)}-\braks{(1-\lam)(y_1)+\lam (y_2)}\in E\end{align*}

    $E$ is closed. Let $\curl{z_k}_{k\in\N}\suf E$ such that $z_{k}=x_{k}-y_{k}\to \to z$. Since $A$ is compact there exists a subsequence $x_{k_m}\to x\in C$ then $y_{k_m}=x_{k_m}-z_{k_m}\to x-z=y\in B$ since $B$ is closed. Thus $z=x-(x-y)\in A-B=E$. By Theorem 13.1.25 $\exists a\in\R^{n}\del\curl{\vec{0}}$ and $\al'\in\R$ such that $\inner{z}{a}>\al'$ for all $z\in\E$. So

    \begin{align*}\inner{x}{a}>\inner{y}{a}+\al'&&\fall x\in A,y\in B\\ \UBC{\INF{x\in A}\inner{x}{a}}{I}\geq\UBC{\SUP{y\in B}\inner{y}{a}}{S}+\al'\end{align*}

    Let $\al\define \frac{1}{2}(I+S),\e\define \al'/2$ hence

    \begin{align*}\al-\e&=\frac{I+S-\al'}{2}\geq \frac{S+\al'+S-\al'}{2}=S\\ \al+\e&=\frac{I+S+\al'}{2}\leq \frac{I+I-\al'+\al'}{2}=I\end{align*}

    showing $A,B$ are strongly separated.

  2. (2)

    [3]

$\square$

  1. I see essentially no reason (other than convience) to consider $\R^{n}$ over any vector space over $K\in \curl{\R,\com}$.keyboard_return
  2. Check this a bit more I feel some intuition here is not quite correctkeyboard_return
  3. laterkeyboard_return

Post a Comment

Name:Email:
Please enter the tag of the current page (92) to post the comment.
Tag:

Direct References

The Eigenspace

BibliographyComments

Direct References