\input{opt-def}

\begin{document}

\lecture{2}{Konvexn� mno�iny}{2. 3. 2012}{\today}{Jan Rozto�il, Tom� Musil}

\section{P��klady}
                   
\subsection{Vrcholov� pokryt�}

Je d�n neorientovan� graf $G=(V, E)$, vrcholov� pokryt� je podmno�ina vrchol� $U
\subseteq V$ takov�, �e ka�d� hrana z $E$ je incidentn� aspo� jednomu vrcholu z
$U$. Zavedeme prom�nn� pro vrcholy $x_{v}$, jejich hodnota je bu� $1$, pokud je
vrchol $v$ ve vrcholov�m pokryt�, nebo $0$, kdy� ne. Celo��seln� program:

\[
\begin{LPminpro}{\sum_{v \in V} x_{v}}{\bfx \in \set{0, 1}^n}
    x_{u} + x_{v} \geq 1 & \forall \set{u,v} \in E
\end{LPminpro}
\]

Podm�nky $x_{u} + x_{v} \geq 1$ n�m zaru��, �e ka�d� hrana bude pokryt�
vrcholem a v�b�r prom�nn�ch z $\set{0, 1}$ zase celo��selnost. {\bf LP
relaxace} t�to �lohy: 

\[
\begin{LPminpro}{\sum_{v \in V} x_{v}}{0 \leq x_{v} \leq 1}
    x_{u} + x_{v} \geq 1 & \forall \set{u,v} \in E
\end{LPminpro}
\]

Probl�m je, �e optim�ln� �e�en� t�to LP relaxace nemus� (a pravd�podobn� tak�
nebude) optim�ln�m �e�en�m p�vodn� �lohy celo��seln�ho programov�n�. Nav�c
prom�nn� budou realn� ��sla mezi $0$ a $1$.


\subsection{Nez�visl� mno�ina}
Je d�n neorientovan� graf $G=(V,E)$, nez�visl� mno�ina je podmno�ina vrchol�
$U \subseteq V$ takov�, �e �adn� dva vrcholy z $U$ nejsou spojen� hranou. V
celo��seln�m programu op�t pou�ijeme prom�nn� pro vrcholy. $x_{v}$ je rovno $1$,
pokud $v$ pat�� do nez�visl� mno�iny, $0$ jinak.

\[
\begin{LPmaxpro}{\sum_{v \in V}\bfx_{v}}{\bfx\in \set{0, 1}^n}
    x_{u} + x_{v} \leq 1 & \forall \set{u,v} \in E
\end{LPmaxpro}
\]

Podm�nky $x_{u} + x_{v} \leq 1$ zaru�uj�, �e do vrcholov�ho pokryt� se m��e
dostat nejv��e jeden z vrchol� incidentn�ch ka�d� hran�. LP relaxace by se
provedla jako u vrcholov�ho pokryt�.

\paragraph{}
Podobn� m��eme modelovat i dal�� grafov� probl�my, line�rn� programov�n� je vhodn�
zj. pro ty, kdy jsou omezuj�c� podm�nky lok�ln� (tedy ne nap�. TSP, kde je
probl�m zajistit souvislost).

\subsection{Minim�ln� perfektn� p�rov�n� v bipartitn�m grafu}
Na vstupu m�me bipartitn� graf $G = (U, V, E)$ $|U| = |V| = n$, $E \subseteq U \times V$,
$G$ m� perfektn� p�rov�n�, a v�hovou funkci $w: E \rightarrow \RR_{0}^{+}$. A
hled�me perfekn� p�rovan� $M \subseteq E$ takov�, �e $\sum_{e \in M}w(e)$ je
minim�ln�.

V celo��seln�m programu tentokr�t zvol�me prom�nn� pro hrany:

\[
\begin{LPminpro}{\sum_{e \in E} w(e)x_{e}}{\bfx \in \set{0, 1}^n}
    \sum_{v \in V} x_{uv} &= 1 & \forall u \in U
    \\
    \sum_{u \in U} x_{uv} &= 1 & \forall v \in V
\end{LPminpro}
\]

Podm�nky zajist�, �e do ka�d�ho vrcholu v $U$ i $V$ vch�z� pr�v�
jedna hrana tedy, �e se jedn� o perfektn� p�rov�n�. P��mo dostaneme i LP
relaxaci t�to �lohy:

\[
\begin{LPminpro}{\sum_{e \in E} w(e)x_{e}}{\bfx \geq 0}
    \sum_{v \in V} x_{uv} &= 1 & \forall u \in U
    \\
    \sum_{u \in U} x_{uv} &= 1 & \forall v \in V
\end{LPminpro}
\]

Tady u� n�m podm�nky nezajist� perfeknt� p�rov�n�. M��e se st�t, �e nap�.
dostaneme vrchol stupn� $2$ takov�, �e prom�nn� pro hrany jemu incidentn� budou
m�t ob� hodnotu $0.5$ nebo dokonce $0.9$ a $0.1$. Na�t�st� pro bipartitn� grafy
plat� n�sleduj�c� v�ta.


\begin{veta} M�jme v�en� bipartitn� graf $G = (V, E)$ a celo��seln� program
    odpov�daj�c� hled�n� minim�ln�ho perfektn�ho p�rov�n� v $G$, pak existuje
    optim�ln� �e�en� $\bfx$ LP relaxace, kter� z�rove� spl�uje $\bfx \in \set{0, 1}^m$.
\end{veta}

\begin{proof}
Pokud graf nem� perfektn� p�rov�n�, pak neexistuje ani p��pustn� �e�en�, nen�
tedy co dokazovat. Naopak kdy� graf m� perfeknt� p�rov�n�, pak optim�ln� �e�esn�
existuje, proto�e p��pustn� �e�en� tvo�� kompaktn� mno�inu (je
omezen�, proto�e $0\leq\bfx\leq1$).
Vezmeme tedy $\bfx$ optim�ln� �e�en� LP relaxace s minim�ln�m po�tem
necelo��seln�ch prom�nn�ch. 

Vybereme podmno�inu hran $E' = \setcond{e \in E}{x_{e} \in
  (0,1)}$. Tvrd�me, �e graf $G'$ indukovan� hranami z $E'$ neobsahuje
vrcholy stupn� $1$, kdyby toti� takov� vrchol m�l, tak ten by musel
b�t celo��seln�, proto�e plat� podm�nky z LP, tady spor s v�b�rem hran
do $E'$

D�le tvrd�me, �e v $G'$ existuje cyklus $C \subseteq E'$, co� plyne z
p�edchoz�ho. A proto�e je $G$ bipartitn�, tak $|C| = 2k$ ($C$ je sud� d�lky).
Hrany v cyklu o��slujeme $C = e_{1},e_{2},\ldots,e_{2k}$.

Zvolme jin� �e�en� $\bfy$ a n�jak� mal� re�ln� $\varepsilon$ takto:

\[
y_{e} = \left \{
    \begin{array}{l l}
        x_{e} + \varepsilon & \quad e_{1},e_{3},\ldots,e_{2k-1} \\
        x_{e} - \varepsilon & \quad e_{2},e_{4},\ldots,e_{2k} \\
        x_{e} & \quad \text{jinak} \\
    \end{array} \right.
\]

M�me st�le p��pustn� �e�en�? Proto�e ke ka�d�mu vrcholu jednou $\varepsilon$
pri�teme a jednou od n�j ode�teme, tak suma z�stane stejn�. A proto�e $x_{e}$
pro hrany z $C$ jsou z ostr�ho intervalu $(0,1)$, tak pro dostate�n� mal�
$\varepsilon$ bude platit i podminka $0 \leq x_{e} \leq 1$.

Jak to zm�n� ��elovou funkci?
\[
\sum_{e \in E} w(e)y_{e} = \sum_{e \in E} w(e)x_{e} +
\varepsilon \overbrace{
    ( \sum_{\text{sude } e \in C} w(e)x_{e} -
      \sum_{\text{liche } e \in C} w(e)x_{e})
      }^{= 0}
\]

Proto�e $\bfx$ je optim�ln�, mus� b�t v�raz ve svorce $0$, jinak bychom mohli
vhodnou volbou kladn�ho nebo z�porn�ho $\varepsilon$ zlep�it optimum.

Pro maxim�ln� $\varepsilon$ takov�, �e $\bfy$ je p��pustne �e�en�, plat� pro
n�kterou hranu  $e \in \set{e_{1},\ldots,e_{2k}}$, �e $x_{e} \in \set{0,1}$, tedy
$\bfx$ m� m�n� necelo��seln�ch slo�ek. Postup opakujeme, dokud nejsou v�echny $x_{e}$
celo��seln�.

\end{proof}

\section{Opakov�n� line�rn� algebry}

\subsection{Afinn� prostory}
\begin{definice}
$A$ je {\bf afinn� prostor}, pokud $A = \bfx + L$ pro n�jak� $\bfx \in \RR^n$, $L$ vektorov� podprostor.
\end{definice}

\begin{definice}
{\bf Afinn� obal} $X \subseteq \mathbb{R}^n$ je pr�nik v�ech afinn�ch prostor� $A$, $X \subseteq A$.
\end{definice}

\begin{definice}
{\bf Afinn� kombinace} bod� z $X$ je bod (v�raz)
$\alpha_0 a_0 + \ldots + \alpha_k a_k, \text {kde } k \in \NN, a_i \in X, \alpha_i \in \RR, \sum {\alpha_i} = 1$
\end{definice}

\begin{veta}
Afinn� obal $X$ je roven
$\setcond{\alpha_0 a_0 + \ldots + \alpha_k a_k }{ k \in \NN, a_i \in X, \alpha_i \in \RR, \sum {\alpha_i} = 1}$
\end{veta}

\begin{definice}
$a_0, \ldots, a_k$ jsou {\bf afinn� nez�visl�}, pokud neexistuj� netrivi�ln�
$\alpha_0, \ldots, \alpha_k \in \RR$ (tj. ne v�echny $= 0$) tak, �e $\alpha_0a_0
+ \ldots + \alpha_ka_k = 0$ a $\sum \alpha_i = 0$.
\end{definice}

\begin{pozorovani}
$a_0, \ldots, a_k$ afinn� nez�visle pr�v� tehdy, kdy� $a_1 - a_0, a_2 - a_0,
\ldots, a_k  - a_0$ jsou line�rn� nez�visl�
\end{pozorovani}

\begin{definice}
{\bf Dimenze mno�iny} $X \subseteq \RR^n$ je dimenze afinn�ho obalu X.
\end{definice}

\begin{pozorovani}
Dimenze mno�iny $X$ je maxim�ln� $d$ takove, �e v $X$ existuj� afinn� nez�visl� $a_0, \ldots, a_d$.
\end{pozorovani}

\subsection{Konvexn� mno�iny}

\begin{definice}
    $X \subseteq \RR^n$ je {\bf konvexn�}, pokud $\forall \bfx, \bfy \in X$ a $\forall t
    \in [0,1]$ plat� $t \bfx + (1 - t) \bfy \in X$ (s ka�d�mi dv�ma body je v $X$ i
    �se�ka mezi nimi).
\end{definice}

\begin{definice}
{\bf Konvexn� obal} $X \subseteq \RR^n$ je definov�n jako pr�nik v�ech
konvexn�ch mno�in obsahuj�c�ch $X$:
\[
conv(X) = \bigcap_{\substack{C \text{ konvexn�} \\ C \supseteq X}} C.
\]
\end{definice}

\begin{definice}
{\bf Konvexn� kombinace} bod� z $X$ je (bod nebo v�raz): 
$\alpha_0 a_0 + \ldots + \alpha_k a_k$, kde $k \in \NN, a_i \in X,
\alpha_i \geq 0, \sum {\alpha_i} = 1$.
\end{definice}

\begin{veta}
Konvexn� obal $X$ je roven 
$\{\alpha_0 a_0 + \ldots + \alpha_k a_k \mid k \in \NN, a_i \in X, \alpha_i \geq 0, \sum {\alpha_i} = 1\}$
\end{veta}

\begin{proof}
TODO
\end{proof}

\begin{veta}
{\bf (Carath�odory)} Nech� $X \subseteq \RR^n$, $dimX=d$. Pak $conv(X) =
\{\alpha_0 a_0 + \ldots + \alpha_d a_d \mid a_i \in X, \alpha_i \geq 0, \sum {\alpha_i} = 1\}$
\end{veta}

\begin{proof}
Nech� $\bfx \in conv(X)$ lze zapsat jako konvexn� kombinaci $\bfx = \alpha_0a_0 + \ldots +
\alpha_k a_k$, $\alpha_i \geq 0$, $\sum \alpha_i$ tak, �e $k$ je minin�ln�.

Pokud $k \leq d$, pak je $\bfx$ zjevn� i konvexn� kombinace $d$ prvk�, m�me hotovo.

Pokud $k > d$, pak $a_0, \ldots, a_k$ jsou afinn� z�visl�, tedy
existuj� $\beta_i \geq 0$ tak, �e $\beta_0 a_0 + \ldots + \beta_k a_k
= {\bf 0}$, $\sum \beta_i = 0$, ale pro n�jak� $i$, $\beta_i \neq 0$,
mezi $\beta_i$ jsou tedy kladn� i z�porn� ��sla. D�le vezmeme $\gamma$
maxim�ln� takov�, �e $(\forall
i)(\gamma \beta_i + \alpha_i \geq 0)$. Takov� ��slo bude existovat, proto�e mno�ina $\gamma$, ze kter�
vyb�r�me, je nepr�zdn� (obsahuje $\gamma=0$), omezen� (proto�e n�kter�
$\beta_i$ je z�porn�) a uzav�en� (dan� neostr�mi nerovnostmi)

\[
\sum_{i=0}^{k} \underbrace{(\gamma \beta_i + \alpha_i)}_{\geq 0} a_i = \bfx
\]

Vid�me, �e je tato kombinace konvexn�, nez�pornost m�me d�ky v�b�ru $\gamma$ a
plat� $\sum (\gamma \beta_i + \alpha_i) = 1$, to plyne z $\sum \alpha_i = 1$ a $\sum
\beta_i = 0$.

D�le d�ky maximalit� $\gamma$ bude existovat $i$ tak, �e $\gamma \beta_i + \alpha_i
= 0$, tedy $\bfx$ lze vyj�d�it jako konvexn� kombinaci m�n� bod�.

\end{proof}

\end{document}
