DL-CO pset 3

1.

Let $G=(V,E)$ be an undirected graph and $s,t\in V$. Consider the following problem:

\begin{array}[cc] a\min & \sum_{uv \in E} \lvert x_{u} - x_{v} \rvert \\ \text{s.t. } & x_{s} - x_{t} = 1 \end{array}

This is not a linear program in this form. Rewrite it as a linear program. (1pt)

Megoldás:
Legyen $\alpha =({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_{|E|})$, ahol minden élhez tartozik egy ${\alpha }_i$.
Legyen az LP feladat feltétele, hogy minden $e_i=(uv)\in E$ -re $x_u-x_v\le {\alpha }_i$ és $x_v-x_u\le {\alpha }_i$.

Ez azt jelenti, hogy $|x_u-x_v|\ge {\alpha }_i$.
A fenti $2|E|$ darab deltétel mellé még tartsuk meg a $x_s-x_t=1$ feltételt és legyen a célfüggvényünk $\min {\sum }_{i=1}^{|E|}{\alpha }_i$.

\begin{array}[cc] a\min & \sum_{i = 1} ^{\lvert E \rvert } \alpha_{i} \\ \text{s.t. } & x_{s} - x_{t} = 1 \\ \text{s.t. } & e_{i} = (uv) \text{-re } \alpha_{i} \geq x_{u} - x_{v} \\ \text{s.t. } & e_{i} = (uv) \text{-re } \alpha_{i} \geq x_{v} - x_{u} \end{array}

2.

Let us consider the following functions:

$$f_1(w_1,w_2)=\frac{1}{2}{w}_1^2+\frac{7}{2}{w}_2^2$$ $$f_2(w_1,w_2)=100(w_2-w_1^2{)}^2+(1-w_1{)}^2$$

a) Calculate the gradients of the functions (2pts)
b) Are these function convex? (2pts)
c) Determine the global minimum of the functions. (2pts)
d) Choose a starting point $w=(w_1,w_2)$ within distance $5$ from an optimal solution, and perform one step of the Gradient descent algorithm. (2pts)

Megoldás:
a)

$$\nabla f_1(w_1,w_2)=\nabla \left(\frac{1}{2}{w}_1^2+\frac{7}{2}{w}_2^2\right)=\left[\begin{array}{c}{w}_1\\ 7w_2\end{array}\right]$$ $$\nabla f_2(w_1,w_2)=\nabla \left(100(w_2-w_1^2{)}^2+(1-w_1{)}^2\right)=\left[\begin{array}{c}400w_1^3-400w_1{w}_2+2w_1-2\\ -200w_1^2+200w_2\end{array}\right]$$

b)
Elég belátni, hogy a Hesse mátrixok pozitív definitek minden $w_1,w_2$-re.

$${\nabla }^2{f}_1(w_1,w_2)=\left[\begin{array}{cc}1& 0\\ 0& 7\end{array}\right]$$ $${\nabla }^2{f}_2(w_1,w_2)=\left[\begin{array}{cc}1200w_1^2-400w_2+2& -400w_1\\ -400w_1& 200\end{array}\right]$$

Az elsőre látszik, hogy pozitív definit, mert nem függ $w_1$ és $w_2$-től és egy diagonális mátrix, melynek a főátlójában csupa pozitív elem van.
A második nem pozitív definit, mert:

$$\left[\begin{array}{cc}{x}_1& x_2\end{array}\right]\cdot \left[\begin{array}{cc}1200w_1^2-400w_2+2& -400w_1\\ -400w_1& 200\end{array}\right]\cdot \left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{cc}{x}_1& x_2\end{array}\right]\cdot \left[\begin{array}{c}1200w_1^2{x}_1-400w_2{x}_1+2x_1-400w_1{x}_2\\ -400w_1{x}_1+200x_2\end{array}\right]$$ $$=(1200w_1^2{x}_1^2-400w_2{x}_1^2+2x_1^2-400w_1{x}_1{x}_2)+(-400w_1{x}_1{x}_2+200x_2^2)=1200w_1^2{x}_1^2-400w_2{x}_1^2+2x_1^2-800w_1{x}_1{x}_2+200x_2^2$$

$x_1=1,x_2=0,w_1=0,w_2=1$ választással a fenti $x^T\cdot {\nabla }^2{f}_2(w_1,w_2)\cdot x=0-400\cdot 1\cdot 1+2\cdot 1-0+0=-400+2=-398<0$. Mivel nem pozitív (semi) definit a Hesse mátrixa $f_2$-nek ezért nem konvex.

c)
Az első függvényről most láttuk be, hogy konvex tehát ott van globális minimuma, ahol a gradiense $0$. Ez meg csak a $(0,0)$ helyen valósul meg.

A Rosenbrock függvényről látszik, hogy nem negatív mert két négyzetes tag összege szerepel, melyek egyenként nem negatívak. Tehát jó minimum hely lenne, ahol a függvény felveszi a $0$-t. Ránézésre, pont ilyen hely a $(w_1,w_2)=(1,1)$.
Formálisabban meg kell oldanunk a következő egyenletrendszert:

$$\left[\begin{array}{c}400w_1^3-400w_1{w}_2+2w_1-2\\ -200w_1^2+200w_2\end{array}\right]=\left[\begin{array}{c}0\\ 0\end{array}\right]$$

és megnézni melyik megoldás ad legkisebb értéket.
Látható, hogy az $(1,1)$ megoldása a fentinek. Továbbá, nem vehet fel ennél kisebb értéket $f_2$.

d)
Legyen a kezdőpont $w_{t_0}=(1,1)$. Legyen továbbá $\eta =1$.

$$w_{t_1}=w_{t_0}-\eta \nabla f_1(w_{t_0})$$ $$w_{t_1}=(1,1)-\eta (1,7)=(1,1)-(1,7)=(0,-6)$$

Legyen $f_2$ esetben a kezdőpont $w_{t_0}=(0,0)$. És megint legyen $\eta =1$.

$$w_{t_1}=w_{t_0}-\eta \nabla f_2(w_{t_0})$$ $$w_{t_1}=(0,0)-\eta (-2,0)=(0,0)-(-2,0)=(2,0)$$

3.

Given a convex, differentiable function $F:K\to \mathbb{R}$ over a convex subset $K$ of ${\mathbb{R}}^n$, the Bergman divergence of $x,y\in K$ is defines as follows:

$$D_F(x,y)=F(x)-F(y)-⟨\nabla F(y),x-y⟩$$

Prove that $D_F(x,y)\ge 0$. (1pt)

Megoldás:
Az elsőrendű konvexitás kritérium szerint. Differenciálható $f:{\mathbb{R}}^n\to \mathbb{R}$ függvénynek egy konvex $K$ halmazon a következő igaz:

$$f(y)⩾f(x)+⟨\nabla f(x),y-x⟩$$

Ezt rendezve egy oldalra kapjuk a következőt:

$$f(y)-f(x)-⟨\nabla f(x),y-x⟩\ge 0$$

Ezzel megkaptuk a belátandó állítást, mivel a baloldalon pont a Bergman divergencia szerepel.

related: DL-CO