---
tags: om
---

# Optimizacijske metode, 2. del

[1. del](https://hackmd.io/@jaanos/SkZjM4n2Y) \| 2. del

---

## Prirejanja in pokritja

**_Definicija._** Naj bo $G = (V, E)$ neusmerjen graf. Množici $M \subseteq E$ pravimo _prirejanje_ (angl. _matching_), če nobeni dve povezavi iz $M$ nimata skupnega krajišča (tj., $\forall e, f \in M: (e \ne f \Rightarrow e \cap f = \emptyset)$). Prirejanje $M$ je _popolno prirejanje_, če je vsako vozlišče grafa $G$ krajišče povezave iz $M$ (tj., $\forall v \in V \ \exists e \in M: v \in e$).

**_Primeri._**

* Prirejanje:

  graph G {
    rankdir=LR
    nodesep=0.5
    ranksep=1
    node [label=""]
    
    a -- b [color=red]
    a -- c
    b -- c [constraint=false]
    b -- d
    c -- e [style=invis]
    d -- e [color=red,constraint=false]
    d -- f
    e -- f
  }

* Ni prirejanje:

  graph G {
    rankdir=LR
    nodesep=0.5
    ranksep=1
    node [label=""]
    
    a -- b [color=red]
    a -- c
    b -- c [constraint=false]
    b -- d
    c -- e [style=invis]
    d -- e [color=red,constraint=false]
    d -- f [color=red]
    e -- f
  }

* Popolno prirejanje:

  graph G {
    rankdir=LR
    nodesep=0.5
    ranksep=1
    node [label=""]
    
    a -- b
    a -- c [color=red]
    b -- c [constraint=false]
    b -- d [color=red]
    c -- e [style=invis]
    d -- e [constraint=false]
    d -- f
    e -- f [color=red]
  }

**_Trditev._** Če ima $G = (V, E)$ popolno prirejanje, je $|V|$ soda.

**_Definicija._** Naj bo $G = (V, E)$ neusmerjen graf. Množici $C \subseteq V$ pravimo _pokritje_ (angl. _vertex cover_), če ima vsaka povezava iz $E$ krajišče v $C$ (tj., $\forall e \in E: e \cap C \ne \emptyset$).

**_Primeri._**

* Pokritje:

  graph G {
    rankdir=LR
    nodesep=0.5
    ranksep=1
    node [label="", style=filled, fillcolor=red]
    
    a [style=empty]
    
    a -- b
    a -- c
    b -- c [constraint=false]
    b -- d
    c -- e [style=invis]
    d -- e [constraint=false]
    d -- f
    e -- f
  }

* Ni pokritje:

  graph G {
    rankdir=LR
    nodesep=0.5
    ranksep=1
    node [label="", fillcolor=red]
    
    a [style=filled]
    b [style=filled]
    e [style=filled]
    
    a -- b
    a -- c
    b -- c [constraint=false]
    b -- d
    c -- e [style=invis]
    d -- e [constraint=false]
    d -- f
    e -- f
  }

* (Najmanjše) pokritje:

  graph G {
    rankdir=LR
    nodesep=0.5
    ranksep=1
    node [label="", style=filled, fillcolor=red]
    
    a [style=empty]
    e [style=empty]
    
    a -- b
    a -- c
    b -- c [constraint=false]
    b -- d
    c -- e [style=invis]
    d -- e [constraint=false]
    d -- f
    e -- f
  }

Iščemo **čim večje prirejanje** in **čim manjše pokritje**.

* $\mu(G)$ ... velikost največjega prirejanja v $G$
* $\tau(G)$ ... velikost najmanjšega pokritja v $G$

**_Primera._**

* $G_1 = (V_1, E_1)$, $|V_1| = 6$:

  graph G1 {
    rankdir=LR
    nodesep=0.5
    ranksep=1
    node [label=""]
    
    a -- d
    b -- d [color=red]
    c -- d
    d -- e
    d -- f
    
    d [style=filled, fillcolor=red]
  }

- $\mu(G_1) = 1$
- $\tau(G_1) = 1$

* $G_2$:

  graph G2 {
    rankdir=LR
    nodesep=0.5
    ranksep=1
    node [label="", style=filled, fillcolor=red]
    
    a [style=empty]
    e [style=empty]
    
    a -- b
    a -- c [color=red]
    b -- c [constraint=false]
    b -- d [color=red]
    c -- e [style=invis]
    d -- e [constraint=false]
    d -- f
    e -- f [color=red]
  }

- $\mu(G_2) = 3$
- $\tau(G_2) = 4$

**_Trditev._** Naj bo $M$ prirejanje in $C$ pokritje v grafu $G$. Potem velja $|M| \le |C|$.

**_Posledica._** Če velja $|M| = |C|$, potem je $M$ največje prirejanje in $C$ najmanjše pokritje v $G$.

**_Posledica._** Za vsak graf $G$ velja $\mu(G) \le \tau(G)$.

**Opomba.** Lahko se zgodi, da velja $\mu(G) < \tau(G)$. Za dvodelne grafe velja $\mu(G) = \tau(G)$ (dokaz kasneje).

_Dokaz._ Ker ima vsaka povezava iz $M$ vsaj eno krajišče v $C$, obstaja preslikava $f : M \to C$, za katero velja $\forall e \in M: f(e) \in e \cap C$. Ker je vsako vozlišče iz $C$ krajišče največ ene povezave iz $M$, je preslikava $f$ injektivna, od koder sledi $|M| \le |C|$.

**_Definicija._** Naj bo $M$ prirejanje v grafu $G = (V, E)$. Rečemo, da je

* vozlišče $v \in V$
- _prosto_, če $\lnot \exists e \in M: v \in e$, in
- _vezano_, če $\exists e \in M: v \in e$;
* povezava $e \in E$
- _prosta_, če $e \not\in M$, in
- _vezana_, če $e \in M$; ter
* pot v $G$
- _izmenična_ (_alternirajoča_), če se v njej izmenjujejo proste in vezane povezave, in
- _povečujoča_, če je izmenična ter se začne in konča s prostim vozliščem.

Če na povečujoči poti zamenjamo proste in vezane povezave, se prirejanje poveča:

graph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  node [label=""]
  
  a -- b
  b -- c [color=red]
  c -- d
  d -- e [color=red]
  e -- f
}

graph H {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  node [label=""]
  
  a -- b [color=red]
  b -- c
  c -- d [color=red]
  d -- e
  e -- f [color=red]
}

**_Definicija._** _Simetrična vsota_ množic $A$ in $B$ je
$$
A \oplus B := (A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A) .
$$

**_Trditev._** Če je $M$ prirejanje v $G$ in $P$ povečujoča pot z množico povezav $E(P)$, je $M' = M \oplus E(P)$ prirejanje v $G$ in $|M'| = |M| + 1$.

**_Trditev (Berge)._** Naj bo $M$ prirejanje v grafu $G$. Potem je $M$ največje prirejanje v $G$ natanko tedaj, ko zanj ne obstaja povečujoča pot.

_Dokaz._ Dokazujemo enakovredno izjavo: $M$ ni največje prirejanje v $G = (V, E)$ natanko tedaj, ko zanj obstaja povečujoča pot.

* $(\Longleftarrow)$ Sledi iz prejšnje trditve.
* $(\Longrightarrow)$ Denimo, da $M$ ni največje prirejanje v $G$. Potem obstaja prirejanje $M'$ v $G$, za katerega velja $|M'| > |M|$. Potem je $H = (V, M \oplus M')$ graf z maksimalno stopnjo $\Delta_H \le 2$ - njegove povezane komponente so poti in sodi cikli.

  graph H {
    rankdir=LR
    nodesep=0.5
    ranksep=1
    node [label=""]
    
    a -- b [label=<<i>M</i>>]
    a -- c [label=<<i>M'</i>>]
    b -- d [label=<<i>M'</i>>]
    c -- e [label=<<i>M</i>>]
    d -- f [label=<<i>M</i>>]
    e -- f [label=<<i>M'</i>>]
    g -- h [label=<<i>M</i>>]
    h -- i [label=<<i>M'</i>>]
    j -- k [label=<<i>M</i>>]
    k -- l [label=<<i>M'</i>>]
    l -- m [label=<<i>M</i>>]
    n -- o [label=<<i>M'</i>>]
    o -- p [label=<<i>M</i>>]
    p -- q [label=<<i>M'</i>>]
  }

Ker je $|M'| > |M|$, obstaja v $H$ pot $P$, katere prva in zadnja povezava sta v $M'$. Trdimo, da je $P$ povečujoča pot za $M$:
- je alternirajoča, saj $E(P) \cap M' \subseteq M \oplus M'$ in zato $E(P) \cap M' \cap M = \emptyset$;
- začne in konča se s prostim vozliščem: denimo, da je $u$ krajišče poti $P$ in ni prosto za $M$ - potem obstaja povezava $uv \in M \setminus (M \oplus M') = M \cap M'$, kar je v protislovju s predpostavko, da je $M'$ prirejanje.

Iskanje največjega prirejanja se torej prevede na iskanje povečujočih poti. Če je graf $G = (V, E)$ dvodelen ($V = X + Y$, $X \cap Y = \emptyset$, $\forall e \in E: (e \cap X \ne \emptyset \land e \cap Y \ne \emptyset)$; ekvivalentno, v $G$ ni lihih ciklov), povečujočo pot poiščemo z **madžarsko metodo**.

* Naj bo $G = (X + Y, E)$ dvodelen graf in $M$ prirejanje v $G$. Postavimo množico prostih vozlišč v $X$ kot množico $S$ in $T := \emptyset$.
* Ponavljamo:
- $T := T \cup \{v \in Y \mid u \in S, uv \not\in M \}$
- $S := S \cup \{u \in X \mid v \in T, uv \in M\}$
* Če je v $T$ v nekem trenutku prosto vozlišče, smo našli povečujočo pot. Postopek ustavimo in povečamo prirejanje (in začnemo od začetka).
* Sicer sta v nekem trenutku nova $S$ in $T$ enaka starima.

**_Izrek._** Če sta nova $S$ in $T$ enaka starima, potem je $M$ največje prirejanje, $C := (X \setminus S) + T$ je najmanjše pokritje, in $|M| = |C| = \mu(G) = \tau(G)$.

_Dokaz._ Trdimo:

* med $S$ in $Y \setminus T$ ni prostih povezav (sicer bi lahko povečali $T$)
* med $S$ in $Y \setminus T$ ni vezanih povezav (do $S$ vodijo vezane povezave samo iz $T$)
* med $X \setminus S$ in $T$ ni vezanih povezav (sicer bi lahko povečali $S$)

graph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  
  S [label=<<i>S</i>>]
  T [label=<<i>T</i>>]
  XS [label=<<i>X \ S</i>>]
  YT [label=<<i>Y \ T</i>>]
  
  S -- T [color=red, label=<<i>M<sub>1</sub></i>>]
  S -- T
  XS -- T
  XS -- YT
  XS -- YT [color=red, label=<<i>M<sub>2</sub></i>>]
  S -- YT [style=invis]
}

Množica $C := (X \setminus S) + T$ je torej pokritje. Definirajmo še množico $M_1$ vezanih povezav med $S$ in $T$ ter množico $M_2$ vezanih povezav med $X \setminus S$ in $Y \setminus T$. Potem je $M = M_1 + M_2$ ter velja $|M_1| = |T|$ (sicer je v $T$ prosto vozlišče) in $|M_2| = |X \setminus S|$ (vsa prosta vozlišča iz $X$ so v $S$). Velja torej
$$
|M| = |M_1| + |M_2| = |T| + |X \setminus S| = |C|.
$$
$M$ je torej največje prirejanje, $C$ pa najmanjše pokritje.

**_Primer._**

digraph G {
  rankdir=RL
  nodesep=0.5
  ranksep=1
  node [label=""]
  edge [arrowhead=none]
  
  e -> a [style=invis]
  f -> a [color=red]
  e -> b
  g -> b [color=red]
  h -> b
  i -> b
  f -> c
  g -> c [style=invis]
  h -> c [color=red]
  g -> d [color=blue,arrowhead=normal]
  h -> d [color=blue,arrowhead=normal]
  Y -> X [style=invis]
  
  X [label=<<i>X</i>>,color=none]
  Y [label=<<i>Y</i>>,color=none]
  d [xlabel=<<i>S</i>>]
  g [xlabel=<<i>T</i>>]
  h [xlabel=<<i>T</i>>]
}

digraph G {
  rankdir=RL
  nodesep=0.5
  ranksep=1
  node [label=""]
  edge [arrowhead=none]
  
  e -> a [style=invis]
  f -> a [color=red]
  e -> b [color=blue,arrowhead=normal]
  g -> b [color=red]
  h -> b [color=blue,arrowhead=normal]
  i -> b [color=blue,arrowhead=normal]
  f -> c [color=blue,arrowhead=normal]
  g -> c [style=invis]
  h -> c [color=red]
  g -> d [arrowhead=normal]
  h -> d [arrowhead=normal]
  Y -> X [style=invis]
  
  X [label=<<i>X</i>>,color=none]
  Y [label=<<i>Y</i>>,color=none]
  
  d [xlabel=<<i>S</i>>]
  g [xlabel=<<i>T</i>>]
  h [xlabel=<<i>T</i>>]
  b [xlabel=<<i>S</i>>]
  c [xlabel=<<i>S</i>>]
  e [xlabel=<<i>T</i>>]
  f [xlabel=<<i>T</i>>]
  i [xlabel=<<i>T</i>>]
}

Imamo prosto vozlišče v $T$, torej smo našli povečujočo pot.

digraph G {
  rankdir=RL
  nodesep=0.5
  ranksep=1
  node [label="", fillcolor=red]
  edge [arrowhead=none]
  
  e -> a [style=invis]
  f -> a [color=red]
  e -> b [color=red]
  g -> b
  h -> b
  i -> b
  f -> c
  g -> c [style=invis]
  h -> c [color=red]
  g -> d [color=red]
  h -> d
  Y -> X [style=invis]
  
  X [label=<<i>X</i>>,color=none]
  Y [label=<<i>Y</i>>,color=none]
  a [style=filled]
  b [style=filled]
  c [style=filled]
  d [style=filled]
}

Ni več prostih vozlišč v $X$, torej imamo največje prirejanje in najmanjše pokritje $C = X$.

V posebnem (za dvodelne grafe) velja torej **_Kőnig-Egerváryjev izrek._** Za dvodelen graf $G$ velja $\mu(G) = \tau(G)$.

**Opomba.** Obstaja tudi algoritem za iskanje povečujoče poti v splošnem grafu: Edmondsov algoritem (angl. tudi _blossom algorithm_). Ta algoritem je "učinkovit", torej polinomski.

| | dvodelni grafi | splošni grafi |
| ------------------- | -------------- | --------------- |
| največje prirejanje | lahek (MM) | lahek (Edmonds) |
| najmanjše pokritje | lahek (MM) | težek |

---

**_Hallov izrek._** Naj bo $G = (X+Y, E)$ dvodelen graf. Potem obstaja _popolno prirejanje iz $X$ v $Y$_ (tj., prirejanje, ki pokrije $X$) natanko tedaj, ko velja $\forall A \subseteq X: |A| \le |N(A)|$, kjer je $N(A) = \{v \in Y \mid \exists u \in A: uv \in E\}$ _soseščina_ (angl. _neighbourhood_) množice $A$.

_Dokaz._

* ($\Longrightarrow$) Naj bo $M$ popolno prirejanje iz $X$ v $Y$. Obstaja injektivna preslikava $f : A \to N(A)$, $f(u) = v \Leftrightarrow uv \in M$.

  graph G {
    rankdir=LR
    nodesep=0.5
    ranksep=1
    node [label=""]
    
    a -- i
    b -- j
    b -- k [style=invis]
    c -- k [style=invis]
    d -- l [style=invis]
    e -- m [style=invis]
    e -- n [style=invis]
    e -- o [style=invis]
    f -- m [style=invis]
    f -- n [style=invis]
    g -- o [style=invis]
    h -- k [style=invis]
    h -- p [style=invis]
    a -- k [color=red]
    b -- i [color=red]
    c -- j [color=red]
    c -- l
    d -- j
    d -- m [color=red]
    e -- k
    e -- l [color=red]
    e -- p
    f -- o [color=red]
    g -- m
    g -- p [color=red]
    h -- n [color=red]
    h -- o
    
    a [xlabel=<<i>A</i>>]
    d [xlabel=" "]
    e [xlabel=<<i>A</i>>]
    f [xlabel=<<i>A</i>>]
    i [xlabel=<                            <i>N</i>(<i>A</i>)>]
    k [xlabel=<                            <i>N</i>(<i>A</i>)>]
    l [xlabel=<                            <i>N</i>(<i>A</i>)>]
    o [xlabel=<                            <i>N</i>(<i>A</i>)>]
    p [xlabel=<               <i>N</i>(<i>A</i>)>]
  }

* ($\Longleftarrow$) Uporabimo madžarsko metodo, da dobimo največje prirejanje $M$ in najmanjše pokritje $C$.

  graph G {
    rankdir=LR
    nodesep=0.5
    ranksep=1
  
    S [label=<<i>S</i>>]
    T [label=<<i>T</i>>]
    XS [label=<<i>X \ S</i>>]
    YT [label=<<i>Y \ T</i>>]
  
    S -- T [color=red]
    S -- T
    XS -- T
    XS -- YT
    XS -- YT [color=red]
    S -- YT [style=invis]
  }

Velja $N(S) \subseteq T$, torej $|S| \le |N(S)| \le |T|$. Nadalje velja
$$
|M| = |C| = |T| + |X \setminus S| \ge |S| + |X \setminus S| = |X|.
$$
Ker velja $|M| \le |X|$, sledi $|M| = |X|$, torej smo našli popolno prirejanje iz $X$ v $Y$.

**Opomba.** Zgornji izrek je oblike $\exists \ldots \Leftrightarrow \forall \ldots$.

* Če želimo dokazati, da obstaja popolno prirejanje iz $X$ v $Y$, ga poiščemo.
* Če želimo dokazati, da ne obstaja popolno prirejanje iz $X$ v $Y$, poiščemo $A \subseteq X$, da velja $|A| > |N(A)|$.

Taka karakterizacija recimo ni znana za hamiltonskost grafa (obstoj Hamiltonovega cikla).

---

### Minimalna in maksimalna popolna prirejanja

Imamo poln dvodelen graf $K_{n, n} = (X + Y, E)$, kjer je $X = \{u_1, u_2, \dots, u_n\}$, $Y = \{v_1, v_2, \dots, v_n\}$ in $E = \{u_i v_j \mid 1 \le i, j \le n\}$, ter uteži $c_{ij}$ (cene) na povezavah $u_i v_j$ ($1 \le i, j \le n$), ki jih zapišemo v matriko $A = (c_{ij})_{i,j=1}^n$.

Tak graf ima $n!$ popolnih prirejanj. Iščemo popolno prirejanje z minimalno (maksimalno) ceno, kjer je cena prirejanja $M$ enaka $\sum_{u_i v_j \in M} c_{ij}$.

**_Primeri._**

* Problem štafete;
* druge razporeditve opravil ($n$ ljudi, $n$ opravil, vsak dobi natanko eno opravilo).

Opazimo: če v matriki $A$ odštejemo konstanto $\epsilon$ od vseh elementov v eni vrstici ali enem stolpcu, se optimalna rešitev ne spremeni, saj ima vsako popolno prirejanje natanko eno povezavo s krajiščem v vozlišču, ki ustreza izbrani vrstici ali stolpcu. Cena vsakega popolnega prirejanja se tedaj zmanjša za $\epsilon$.

**_Primer._** Zmanjšajmo za najmanjšo vrednost v vsaki vrstici, nato pa še v vsakem stolpcu:
$$
\begin{bmatrix} 3 & 1 \\ 4 & 2 \end{bmatrix} \to
\begin{bmatrix} 2 & 0 \\ 2 & 0 \end{bmatrix} \to
\begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}
$$

**Madžarska metoda z utežmi** za iskanje minimalnega popolnega prirejanja:

1. Od vsake vrstice odštejemo njen minimum. Od vsakega stolpca odštejemo njegov minimum. Dobimo nenegativno matriko z vsaj eno ničlo v vsaki vrstici in vsakem stolpcu.
2. Poiščemo $n$ ničel, v vsaki vrstici in vsakem stolpcu eno. Če jih najdemo, nam dajo minimalno popolno prirejanje.
3. Sicer lahko vse ničle v matriki pokrijemo z manj kot $n$ vrsticami in stolpci. Naj bo $\epsilon$ minimum nepokritih števil. Od nepokritih števil odštejemo $\epsilon$, dvakrat pokritim številom pa prištejemo $\epsilon$. Vrnemo se na 2. korak.

**_Primer_** - štafeta.

| | prsno | hrbtno | delfin | prosto | počiva | počiva |
| - | ----- | ------ | ------ | ------ | ------ | ------ |
| 1 | 65 | 73 | 63 | 57 | 0 | 0 |
| 2 | 67 | 76 | 65 | 58 | 0 | 0 |
| 3 | 68 | 72 | 69 | 55 | 0 | 0 |
| 4 | 67 | 75 | 70 | 59 | 0 | 0 |
| 5 | 71 | 69 | 75 | 57 | 0 | 0 |
| 6 | 69 | 71 | 66 | 59 | 0 | 0 |

Minimum v vsaki vrstici je $0$ - odštejmo še minimume stolpcev:

| | prsno | hrbtno | delfin | prosto | počiva | počiva |
| - | ----- | ------ | ------ | ------ | ------ | ------ |
| 1 | **0** | **4** | **0** | **2** | **_0_** | **_0_** |
| 2 | 2 | 7 | 2 | 3 | **0** | **0** |
| 3 | **3** | **3** | **6** | **0** | **_0_** | **_0_** |
| 4 | 2 | 6 | 7 | 4 | **0** | **0** |
| 5 | **6** | **0** | **12** | **2** | **_0_** | **_0_** |
| 6 | 4 | 2 | 3 | 4 | **0** | **0** |

Vse ničle smo pokrili s tremi vrsticami in dvema stolpcema (skupaj manj kot $n = 6$). Najmanjša nepokrita vrednost je $\epsilon = 2$ - zmanjšamo nepokrita in povečamo dvakrat pokrita števila za $\epsilon$:

| | prsno | hrbtno | delfin | prosto | počiva | počiva |
| - | ----- | ------ | ------ | ------ | ------ | ------ |
| 1 | **0** | 4 | 0 | 2 | 2 | 2 |
| 2 | 0 | 5 | **0** | 1 | 0 | 0 |
| 3 | 3 | 3 | 6 | **0** | 2 | 2 |
| 4 | 0 | 4 | 5 | 2 | **0** | 0 |
| 5 | 6 | **0** | 12 | 2 | 2 | 2 |
| 6 | 2 | 0 | 1 | 2 | 0 | **0** |

Dobimo optimalno rešitev:

| | prsno | hrbtno | delfin | prosto | počiva | počiva |
| - | ----- | ------ | ------ | ------ | ------ | ------ |
| 1 | **65**| 73 | 63 | 57 | 0 | 0 |
| 2 | 67 | 76 | **65** | 58 | 0 | 0 |
| 3 | 68 | 72 | 69 | **55** | 0 | 0 |
| 4 | 67 | 75 | 70 | 59 | **0** | 0 |
| 5 | 71 | **69** | 75 | 57 | 0 | 0 |
| 6 | 69 | 71 | 66 | 59 | 0 | **0** |

Cena optimalne rešitve: 65 + 69 + 65 + 55 + 0 + 0 = 254.

Kaj pravzaprav naredimo v 2. in 3. koraku? Naj bo $H = (X+Y, E')$ dvodelen graf, kjer je $E' = \{u_i v_j \mid c_{ij} = 0\}$ (_ničelni graf_).

graph H {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  node [fillcolor=red]

  1 [style=filled]
  2 [xlabel=<<i>S</i>>]
  3 [style=filled]
  4 [xlabel=<<i>S</i>>]
  5 [style=filled]
  6 [xlabel=<<i>S</i>>]
  p1 [label="počiva", style=filled, xlabel=<                                   <i>T</i>>]
  p2 [label="počiva", style=filled, xlabel=<                                   <i>T</i>>]
  
  1 -- prsno
  5 -- hrbtno [color=red]
  1 -- delfin [color=red]
  3 -- prosto [color=red]
  1 -- p1
  2 -- p1
  3 -- p1
  4 -- p1 [color=red]
  5 -- p1
  6 -- p1
  1 -- p2
  2 -- p2
  3 -- p2
  4 -- p2
  5 -- p2
  6 -- p2 [color=red]
}

Na $H$ poiščemo največje prirejanje $M$ in najmanjše pokritje $C = (X \setminus S) + T$ z madžarsko metodo.

* Če je $M$ popolno prirejanje ($|M| = n$), nam to da $n$ ničel, eno v vsaki vrstici in stolpcu.
* Če je $|M| = |C| < n$, nam vozlišča iz $C$ dajo manj kot $n$ vrstic in stolpcev, ki pokrijejo vse ničle. Vrsticam v $C$ (torej v $X \setminus S$) prištejemo $\epsilon$, stolpcem izven $C$ (torej v $X \setminus T$) odštejemo $\epsilon$. Res torej od nepokritih števil odštejemo $\epsilon$, dvakrat pokritim pa prištejemo $\epsilon$.

---

Zakaj se madžarska metoda z utežmi vedno ustavi?

digraph G {
  rankdir=LR
  nodesep=0.5
  ranksep=1
  edge [arrowhead=none]

  S [label=<<i>S</i>>]
  T [label=<<i>T</i>>]
  XS [label=<<i>X \ S</i>>]
  YT [label=<<i>Y \ T</i>>]
  x [style=invis]
  y [style=invis]
  S2 [label=<<i>S</i>>]
  T2 [label=<<i>T</i>>]
  XS2 [label=<<i>X \ S</i>>]
  YT2 [label=<<i>Y \ T</i>>]
  
  S -> T [color=red]
  S -> T
  XS -> T
  XS -> YT
  XS -> YT [color=red]
  S -> YT [style=invis]
  
  T -> x [style=invis]
  YT -> x [style=invis]
  x -> y [arrowhead=normal]
  y -> S2 [style=invis]
  y -> XS2 [style=invis]
  
  S2 -> T2 [color=red]
  S2 -> T2
  XS2 -> T2 [style=invis]
  XS2 -> YT2
  XS2 -> YT2 [color=red]
  S2 -> YT2
}

V tretjem koraku se znebimo povezav med $X \setminus S$ in $T$ (dvakrat pokrita števila) in pridelamo vsaj eno povezavo med $S$ in $Y \setminus T$ (med nepokritimi števili je bil $\epsilon$, ki smo ga zmanjšali na $0$) - naj bo to povezava $uv$ ($u \in S$, $v \in Y \setminus T$). Imamo dve možnosti:

* $v$ je prosto vozlišče: našli smo povečujočo pot, prirejanje se poveča;
* $v$ je vezano vozlišče: poveča se množica $T$.

Množica $T$ se lahko poveča največ $n$-krat, preden se poveča prirejanje. Prirejanje se poveča največ $n$-krat. Madžarska metoda z utežmi ima torej največ $n^2$ korakov. Ker pri tem opravi približno $n^2$ operacij za izvedbo madžarske metode, za madžarsko metodo z utežmi potrebujemo $O(n^4)$ operacij.

---

**Opomba.** Če iščemo maksimalno popolno prirejanje, poiščemo minimalno popolno prirejanje za $-A$.

**Opomba.** Iščemo $\min \sum_{i=1}^n A_{i \pi(i)}$ po vseh permutacijah $\pi \in S(n)$ ($n!$ permutacij). Če se omejimo samo na ciklične permutacije (tj., oblike $\pi = (i_1 \ i_2 \ \dots \ i_n)$ - $(n-1)!$ permutacij), je to problem potujočega trgovca - zanj ne poznamo učinkovitega algoritma.

---

## Konveksna optimizacija

**_Definicija._** Množica $A \subseteq \mathbb{R}^m$ je _konveksna_, če za vsaka $x, y \in A$ in vsak $\lambda \in [0, 1]$ velja $(1 - \lambda) x + \lambda y \in A$.

Torej: množica $A$ je konveksna, če je vsaka daljica s krajišči v množici $A$ v celoti vsebovana v $A$.

**_Trditev._** Presek konveksnih množic je konveksen: $A_i$ ($i \in I$) konveksne $\Rightarrow \bigcap_{i \in I} A_i$ konveksna.

_Dokaz._ Preveriti moramo: za vsaka $x, y \in \bigcap_{i \in I} A_i$ in vsak $\lambda \in [0, 1]$ velja $\forall i \in I: (1-\lambda) x + \lambda y \in A_i$. To je res, ker so množice $A_i$ ($i \in I$) konveksne.

**_Definicija._** Vektor $\lambda_1 x_1 + \lambda_2 x_2 + \dots + \lambda_n x_n$, kjer $\lambda_1, \lambda_2, \dots, \lambda_n \ge 0$, $\lambda_1 + \lambda_2 + \dots + \lambda_n = 1$, je _konveksna kombinacija_ vektorjev $x_1, x_2, \dots, x_n$.

Za $n = 2$ pišemo $\lambda := \lambda_2$, $\lambda_1 = 1 - \lambda$, torej $\lambda_1 x_1 + \lambda_2 x_2 = (1 - \lambda) x_1 + \lambda x_2$.

**_Trditev._** Množica $A$ je konveksna natanko tedaj, ko je v $A$ vsaka konveksna kombinacija vektorjev iz $A$.

_Dokaz._

* ($\Longleftarrow$) Očitno.
* ($\Longrightarrow$) Naj bo $x = \lambda_1 x_1 + \lambda_2 x_2 + \dots + \lambda_n x_n$ konveksna kombinacija vektorjev $x_1, x_2, \dots, x_n \in A$. Naredimo indukcijo na $n$.
- $n = 1$: $x = 1 \cdot x_1 = x_1 \in A$.
- $n = 2$: po definiciji.
- $n > 2$: če $\lambda_n = 1$, potem $\lambda_1 = \lambda_2 = \dots = \lambda_{n-1} = 0$ in $x = 1 \cdot x_n = x_n \in A$. Sicer $\lambda_n < 1$ - tedaj naj bo
$$
y := {\lambda_1 x_1 + \lambda_2 x_2 + \dots + \lambda_{n-1} x_{n-1} \over 1 - \lambda_n} .
$$
Ker je ${\lambda_1 \over 1 - \lambda_n}, {\lambda_2 \over 1 - \lambda_n}, \dots, {\lambda_{n-1} \over 1 - \lambda_n} \ge 0$ in ${\lambda_1 \over 1 - \lambda_n} + {\lambda_2 \over 1 - \lambda_n} + \dots + {\lambda_{n-1} \over 1 - \lambda_n} = 1$, je $y$ konveksna kombinacija vektorjev $x_1, x_2, \dots, x_{n-1} \in A$. Po indukcijski predpostavki je $y \in A$, torej je tudi $x = (1 - \lambda_n) y + \lambda_n x_n \in A$.

**_Definicija._** Množica $\operatorname{conv}(A) := \bigcap_{\substack{K \supseteq A \\ K \text{ konveksna}}} K$ je _konveksna ogrinjača_ (ali _konveksna ovojnica_) množice $A \subseteq \mathbb{R}^m$.

**Opomba.** Primerjaj z linearno ogrinjačo $\operatorname{Lin}(A) = \bigcap_{\substack{V \supseteq A \\ V \text{ podprostor}}} V$.

**_Trditev._** Naj bosta $A, B \subseteq \mathbb{R}^m$ množici, pri čemer je množica $B$ konveksna. Potem velja sledeče.

1. $A \subseteq \operatorname{conv}(A)$.
2. $\operatorname{conv}(A)$ je konveksna množica.
3. $A \subseteq B \Rightarrow \operatorname{conv}(A) \subseteq B$.
4. Če je $A$ konveksna množica, potem $\operatorname{conv}(A) = A$.
5. $\operatorname{conv}(A) = \{\lambda_1 x_1 + \lambda_2 x_2 + \dots + \lambda_n x_n \mid n \in \mathbb{N}, x_1, x_2, \dots, x_n \in A, \lambda_1, \lambda_2, \dots, \lambda_n \ge 0, \lambda_1 + \lambda_2 + \dots + \lambda_n = 1\}$ - tj., množica konveksnih kombinacij vektorjev iz $A$.

_Dokaz._

1. $\operatorname{conv}(A) = \bigcap_{\substack{K \supseteq A \\ K \text{ konveksna}}} K \supseteq A$
2. Presek konveksnih množic je konveksen.
3. Ker je $B$ konveksna, sledi iz definicije konveksne ogrinjače.
4. Po 3. je $\operatorname{conv}(A) \subseteq A \subseteq \operatorname{conv}(A)$.
5. Naj bo $C$ množica konveksnih kombinacij vektorjev iz $A$. Dokažimo $\operatorname{conv}(A) = C$.
* ($\subseteq$) Po 3. velja $\operatorname{conv}(A) \subseteq C$, saj:
- $A = \{1 \cdot x \mid x \in A\} \subseteq C$;
- $C$ je konveksna, ker je vsaka konveksna kombinacija vektorjev $x, y \in C$
$$
\begin{aligned}
z &= (1 - \lambda) x + \lambda y \\
&= (1 - \lambda)(\mu_1 x_1 + \dots + \mu_k x_k) + \lambda (\nu_1 y_1 + \dots + \nu_\ell y_\ell) \\
&= (1 - \lambda) \mu_1 x_1 + \dots + (1 - \lambda) \mu_k x_k + \lambda \nu_1 y_1 + \dots + \lambda \nu_\ell y_\ell
\end{aligned}
$$
tudi konveksna kombinacija vektorjev $x_1, \dots, x_k, y_1, \dots, y_\ell \in A$, saj $(1-\lambda) \mu_i, \lambda \nu_j \ge 0$ ($1 \le i \le k$, $1 \le j \le \ell$) in $(1 - \lambda) \mu_1 + \dots + (1 - \lambda) \mu_k + \lambda \nu_1 + \dots + \lambda \nu_\ell = (1 - \lambda) + \lambda = 1$, torej $z \in C$.
* ($\supseteq$) Ker je vsak $x \in C$ konveksna kombinacija vektorjev $x_1, x_2, \dots, x_n \in A$, za vsako konveksno množico $K \supseteq A$ velja $x_1, x_2, \dots, x_n \in K$, torej $x \in K$ in zato $x \in \operatorname{conv}(A)$. Sledi $\operatorname{conv}(A) \supseteq C$.

**_Definicija._** Naj bo $A$ konveksna množica. Točka $a \in A$ je _ekstremna točka_, če velja $\forall x, y \in A \ \forall \lambda \in (0, 1): (a = (1 - \lambda) x + \lambda y \Rightarrow x = y = a)$ (tj., $a$ ne leži v notranjosti nobene daljice med različnima točkama iz $A$).

**_Primeri._** Ekstremne točke so prikazane z rdečo barvo.


V zadnjem primeru ni ekstremnih točk.

**_Definicija._** Množica $A \ne \emptyset$ je _afina_, če velja $\forall x, y \in A \ \forall \lambda \in \mathbb{R}: (1 - \lambda) x + \lambda y \in A$ (tj., vsaka premica skozi različni točki iz $A$ je vsebovana v $A$).

**_Definicija._** Vektor $\lambda_1 x_1 + \lambda_2 x_2 + \dots + \lambda_n x_n$, kjer je $\lambda_1 + \lambda_2 + \dots + \lambda_n = 1$, je _afina kombinacija_ vektorjev $x_1, x_2, \dots, x_n$.

**_Trditev._** Naj bo $A \subseteq \mathbb{R}^m$ neprazna množica. Sledeče trditve so ekvivalentne.

1. Množica $A$ je afina.
2. Vsaka afina kombinacija točk iz $A$ je v $A$.
3. $\exists v \in \mathbb{R}^m$, $\exists V \le \mathbb{R}^m$ linearen podprostor: $A = v + V = \{v + x \mid x \in V\}$.

**Opomba.** Primeri afinih množic so premica v $\mathbb{R}^m$, ravnina v $\mathbb{R}^m$, ... - rečemo jim tudi _afini podprostori_. Definiramo lahko tudi dimenzijo afinega podprostora.

_Dokaz._

* (1. $\Rightarrow$ 2.) Naj bo $x = \lambda_1 x_1 + \lambda_2 x_2 + \dots + \lambda_n x_n$ afina kombinacija vektorjev $x_1, x_2, \dots, x_n \in A$. Naredimo indukcijo na $n$.
- $n = 1$: $x = 1 \cdot x_1 = x_1 \in A$.
- $n = 2$: po definiciji.
- $n > 2$: brez škode za splošnost vzamemo $\lambda_n \ne 1$ - tedaj naj bo
$$
y := {\lambda_1 x_1 + \lambda_2 x_2 + \dots + \lambda_{n-1} x_{n-1} \over 1 - \lambda_n} .
$$
Ker je ${\lambda_1 \over 1 - \lambda_n} + {\lambda_2 \over 1 - \lambda_n} + \dots + {\lambda_{n-1} \over 1 - \lambda_n} = 1$, je $y$ afina kombinacija vektorjev $x_1, x_2, \dots, x_{n-1} \in A$. Po indukcijski predpostavki je $y \in A$, torej je tudi $x = (1 - \lambda_n) y + \lambda_n x_n \in A$.

* (2. $\Rightarrow$ 3.) Naj bo $v \in A$ poljuben vektor. Potem je $V := A - v$ linearen podprostor, saj za vsake $x, y \in A$ ter $\mu, \nu \in \mathbb{R}$ velja
$$
\begin{aligned}
\mu (x - v) + \nu (y - v) &= \mu x + \nu y - \mu v - \nu v \\
&= \mu x + \nu y + (1 - \mu - \nu) v - v \in V,
\end{aligned}
$$
saj $x, y, v \in A$ ter $\mu + \nu + (1 - \mu - \nu) = 1$. Velja torej $A = V + v$.

* (3. $\Rightarrow$ 1.) Poljubna vektorja iz $A$ lahko zapišemo kot $x+v$ in $y+v$, kjer $x, y \in V$. Za poljuben $\lambda \in \mathbb{R}$ velja
$$
(1 - \lambda) (x + v) + \lambda (y + v) = (1 - \lambda) x + \lambda y + v \in A.
$$

### Konveksni stožci in Farkaseva lema

**_Definicija._** Množica $A \subseteq \mathbb{R}^m$ je _konveksen stožec_, če velja $\forall x, y \in A \ \forall \lambda, \mu \ge 0: \lambda x + \mu y \in A$.

**Opomba.** Če za vsaka $x, y \in A$ velja

* $\forall \lambda, \mu: \lambda x + \mu y \in A$, potem je $A$ linearen podprostor;
* $\forall \lambda, \mu \ge 0: \lambda x + \mu y \in A$, potem je $A$ konveksen stožec;
* $\forall \lambda, \mu: (\lambda + \mu = 1 \Rightarrow \lambda x + \mu y \in A)$, potem je množica $A$ afina; in
* $\forall \lambda, \mu \ge 0: (\lambda + \mu = 1 \Rightarrow \lambda x + \mu y \in A)$, potem je množica $A$ konveksna.

Vsak konveksen stožec je konveksna množica; obratno ne velja.

**_Definicija._** Množica
$$
S(a_1, a_2, \dots, a_n) := \{\lambda_1 a_1 + \lambda_2 a_2 + \dots \lambda_n a_n \mid \lambda_1, \lambda_2, \dots, \lambda_n \ge 0\}
$$
je _konveksen stožec, napet na vektorjih_ $a_1, a_2, \dots, a_n$.

**_Trditev._** Množica $S(a_1, a_2, \dots, a_n)$ je konveksen stožec.

_Dokaz._ Naj bodo $\lambda, \lambda_1, \dots, \lambda_n, \mu, \mu_1, \dots, \mu_n \ge 0$. Potem velja
$$
\lambda (\lambda_1 a_1 + \dots + \lambda_n a_n) + \mu (\mu_1 a_1 + \dots + \mu_n a_n) = (\lambda \lambda_1 + \mu \mu_1) a_1 + \dots + (\lambda \lambda_n + \mu \mu_n) a_n \in S(a_1, \dots, a_n),
$$
saj $\lambda \lambda_i + \mu \mu_i \ge 0$ ($1 \le i \le n$).

**_Primeri._**

* $S(a_1)$:


* $S(a_1, a_2)$:


* $S(a_1, a_2, a_3)$:


**_Definicija._** Naj bo $A \subseteq \mathbb{R}^m$. Množici
$$
A^\ast := \{x \in \mathbb{R}^m \mid \forall a \in A: a^\top x \ge 0\}
$$
(tj., množici vektorjev, ki tvorijo ostri kot z vsemi vektorji iz $A$) pravimo _dualni stožec_ množice $A$.


**_Trditev._** Dualni stožec $A^\ast$ množice $A$ je konveksen stožec.

_Dokaz._ Vzemimo poljubne $x, y \in A^\ast$ in $\lambda, \mu \ge 0$. Potem za vsak $a \in A$ velja
$$
a^\top (\lambda x + \mu y) = \lambda \, a^\top x + \mu \, a^\top y \ge 0,
$$
torej $\lambda x + \mu y \in A^\ast$.

**_Trditev._** $A \subseteq A^{\ast\ast}$.

**Opomba.** V splošnem ne velja $A = A^{\ast\ast}$ (npr. če $A$ ni konveksen stožec).

_Dokaz._ Vzemimo poljuben $x \in A$. Potem za vsak $y \in A^\ast$ velja $x^\top y \ge 0$, torej velja tudi $x \in A^{\ast\ast}$.

**_Izrek (Farkaseva lema - geometrijska oblika)._** $S^{\ast\ast}(a_1, a_2, \dots, a_n) = S(a_1, a_2, \dots, a_n)$.

_Dokaz._

* ($\supseteq$) Po prejšnji trditvi.
* ($\subseteq$) Naj bo $A = [a_1 \, a_2 \, \dots \, a_n]$ matrika s stolpci $a_1, a_2, \dots, a_n$ in $b \in S^{\ast\ast}(a_1, a_2, \dots, a_n)$. Definirajmo linearni program $\Pi$ in njegov dual $\Pi'$:
| $\Pi$: | $\Pi'$: |
| ------ | ------- |
| $$\begin{aligned} \max \ 0^\top x \\[1ex] \text{p.p.} \quad A x &= b \\ x &\ge 0 \end{aligned}$$ | $$\begin{aligned} \min \ b^\top y \\[1ex] \text{p.p.} \quad A^\top y &\ge 0 \\ \phantom{} \end{aligned}$$ |

Ker je $y = 0$ dopustna rešitev $\Pi'$, je ta dopusten; pokazali bomo, da je tudi omejen. Naj bo $y$ dopustna rešitev za $\Pi'$, torej velja $A^\top y \ge 0$ oziroma
$$
\forall i \in \{1, 2, \dots, n\}: \ a_i^\top y \ge 0.
$$
Potem za poljubne $\lambda_1, \lambda_2, \dots, \lambda_n \ge 0$ velja
$$
(\lambda_1 a_1 + \lambda_2 a_2 + \dots + \lambda_n a_n)^\top y = \lambda_1 \, a_1^\top y + \lambda_2 \, a_2^\top y + \dots + \lambda_n \, a_n^\top y \ge 0
$$
Vektor $y$ torej tvori ostri kot z vsemi vektorji iz $S(a_1, a_2, \dots, a_n)$ in zato $y \in S^\ast(a_1, a_2, \dots, a_n)$. Ker velja $b \in S^{\ast\ast}(a_1, a_2, \dots, a_n)$, sledi $b^\top y \ge 0$, torej je $\Pi'$ omejen in zato optimalen. Po krepkem izreku o dualnosti je tudi $\Pi$ optimalen, torej $\exists x \ge 0: Ax = b$ oziroma
$$
\exists x_1, x_2, \dots, x_n \ge 0: \ x_1 a_1 + x_2 a_2 + \dots + x_n a_n = b,
$$
iz česar sledi $b \in S(a_1, a_2, \dots, a_n)$.

**Opomba.** Farkasevo lemo se da dokazati tudi neposredno, krepki izrek o dualnosti sledi iz nje. Imamo torej ekvivalenco Farkas $\Leftrightarrow$ KID.

**_Farkaseva lema - algebraična oblika._**

1. $\exists x \ge 0: \ Ax = b \ \Longleftrightarrow \ \forall y: \ (A^\top y \ge 0 \Rightarrow b^\top y \ge 0)$
2. $\exists x \ge 0: \ Ax \le b \ \Longleftrightarrow \ \forall y \ge 0: \ (A^\top y \ge 0 \Rightarrow b^\top y \ge 0)$
3. $\exists x: \ Ax = b \ \Longleftrightarrow \ \forall y: \ (A^\top y = 0 \Rightarrow b^\top y \ge 0)$
4. $\exists x: \ Ax \le b \ \Longleftrightarrow \ \forall y \ge 0: \ (A^\top y = 0 \Rightarrow b^\top y \ge 0)$

_Dokaz._

1. Naj bodo $a_1, a_2, \dots, a_n$ stolpci matrike $A$. Potem je izjava ekvivalentna izjavi $b \in S(a_1, a_2, \dots, a_n) \Longleftrightarrow b \in S^{\ast\ast}(a_1, a_2, \dots, a_n)$, ki sledi iz geometrijske oblike Farkaseve leme.

2. Obravnavamo linearna programa
| $\Pi$: | $\Pi'$: |
| ------ | ------- |
| $$\begin{aligned} \max \ 0^\top x \\[1ex] \text{p.p.} \quad A x &\le b \\ x &\ge 0 \end{aligned}$$ | $$\begin{aligned} \min \ b^\top y \\[1ex] \text{p.p.} \quad A^\top y &\ge 0 \\ y &\ge 0 \end{aligned}$$ |

3. Obravnavamo linearna programa
| $\Pi$: | $\Pi'$: |
| ------ | ------- |
| $$\begin{aligned} \max \ 0^\top x \\[1ex] \text{p.p.} \quad A x &= b \end{aligned}$$ | $$\begin{aligned} \min \ b^\top y \\[1ex] \text{p.p.} \quad A^\top y &= 0 \end{aligned}$$ |

4. Obravnavamo linearna programa
| $\Pi$: | $\Pi'$: |
| ------ | ------- |
| $$\begin{aligned} \max \ 0^\top x \\[1ex] \text{p.p.} \quad A x &\le b \\ \phantom{} \end{aligned}$$ | $$\begin{aligned} \min \ b^\top y \\[1ex] \text{p.p.} \quad A^\top y &= 0 \\ y &\ge 0 \end{aligned}$$ |

V vseh primerih ekvivalenco dokažemo tako:

* ($\Longrightarrow$) Sledi iz šibkega izreka o dualnosti.
* ($\Longleftarrow$) Dualni linearni program $\Pi'$ ima dopustno rešitev $y = 0$, po predpostavki pa je to tudi optimalna rešitev. Po krepkem izreku o dualnosti je tudi $\Pi$ optimalen, torej ima dopustno rešitev.

**_Primeri._**

1. Ali obstaja nenegativna rešitev sistema linearnih enačb $Ax = b$? Če obstaja, jo zapišemo. Če ne obstaja, poiščemo $y$, da velja $A^\top y \ge 0$, $b^\top y < 0$.

$$
\begin{aligned}
x_1 - x_2 + 2 x_3 &= 1 & / \cdot 1 \\
-x_1 - x_2 + x_3 &= 2 & / \cdot (-1) \\ \hline
2 x_1 + x_3 &= -1
\end{aligned}
$$

Dokažimo, da zgornji sistem nima nenegativnih rešitev.
$$
\begin{aligned}
A &= \begin{bmatrix}
1 & -1 & 2 \\ -1 & -1 & 1
\end{bmatrix}, \quad
b = \begin{bmatrix} 1 \\ 2 \end{bmatrix}, \quad
y = \begin{bmatrix} 1 \\ -1 \end{bmatrix} \\
A^\top y &= \begin{bmatrix}
1 & -1 \\ -1 & -1 \\ 2 & 1
\end{bmatrix}
\begin{bmatrix} 1 \\ -1 \end{bmatrix}
= \begin{bmatrix} 2 \\ 0 \\ 1 \end{bmatrix} \ge 0, \quad
b^\top y = -1 < 0
\end{aligned}
$$

Ustrezen $x$ oziroma $y$ lahko poiščemo s simpleksno metodo.

2. Pokažimo, da linearni program nima dopustne rešitve.
$$
\begin{aligned}
x_1 - x_2 &\le -1 & / \cdot 1 \\
-x_1 - x_2 &\le -3 & / \cdot 3 \\
2 x_1 + x_2 &\le 2 & / \cdot 4 \\
x_1, x_2 &\ge 0 \\ \hline
6 x_1 &\le -2
\end{aligned}
$$

$$
\begin{aligned}
A &= \begin{bmatrix}
1 & -1 \\ -1 & -1 \\ 2 & 1
\end{bmatrix}, \quad
b = \begin{bmatrix} -1 \\ -3 \\ 2 \end{bmatrix}, \quad
y = \begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix} \ge 0 \\
A^\top y &= \begin{bmatrix} 6 \\ 0 \end{bmatrix} \ge 0, \quad
b^\top y = -2 < 0
\end{aligned}
$$

3. Enakovredna izjava: $\exists x: \ Ax = b \ \Longleftrightarrow \ \forall y: \ (A^\top y = 0 \Rightarrow b^\top y = 0)$.

Pri linearni algebri $\lnot \exists x: \ Ax = b$ dokazujemo z Gaussovo eliminacijo.

$$
\begin{aligned}
x_1 - 2 x_2 &= 3 & / \cdot 1 \\
-x_1 + 2 x_2 &= 1 & / \cdot 1 \\ \hline
0 &= 4
\end{aligned}
$$

$$
\begin{aligned}
A &= \begin{bmatrix}
1 & -2 \\ -1 & 2
\end{bmatrix}, \quad
b = \begin{bmatrix} 3 \\ 1 \end{bmatrix}, \quad
y = \begin{bmatrix} 1 \\ 1 \end{bmatrix} \\
A^\top y &= \begin{bmatrix} 0 \\ 0 \end{bmatrix}, \quad
b^\top y = 4
\end{aligned}
$$

**Opomba.** Ekvivalentna trditev Farkasevi lemi:
$$
b \not\in S(a_1, a_2, \dots, a_n) \Longleftrightarrow b \not\in S^{\ast\ast}(a_1, a_2, \dots, a_n).
$$
Torej ($\Longrightarrow$): če $b$ ni v konveksnem stožcu, napetem na $a_1, a_2, \dots, a_n$, potem $b$ ne tvori ostrega kota z $y \in S^\ast(a_1, a_2, \dots, a_n)$ - med $b$ in $S(a_1, a_2, \dots, a_n)$ je tako neka hiperravnina.


---

### Konveksne funkcije

Konveksne funkcije so "obrnjene navzgor", npr $f(x) = x^2$.


**_Definicija._** Naj bo $K \subseteq \mathbb{R}^n$ konveksna množica. Funkcija $f : K \to \mathbb{R}$ je _konveksna_, če velja
$$
\forall x, y \in K \ \forall \lambda \in [0, 1]: f((1 - \lambda) x + \lambda y) \le (1 - \lambda) f(x) + \lambda f(y)
$$
Torej: graf funkcije leži pod zveznicami točk na grafu.

Funkcija $f : K \to \mathbb{R}$ je _konkavna_, če velja
$$
\forall x, y \in K \ \forall \lambda \in [0, 1]: f((1 - \lambda) x + \lambda y) \ge (1 - \lambda) f(x) + \lambda f(y)
$$
Torej: $f$ je konkavna $\Longleftrightarrow$ $-f$ je konveksna.

Funkcija $f : K \to \mathbb{R}$ je _strogo konveksna_, če velja
$$
\forall x, y \in K \ \forall \lambda \in (0, 1): f((1 - \lambda) x + \lambda y) < (1 - \lambda) f(x) + \lambda f(y)
$$

Funkcija $f : K \to \mathbb{R}$ je _strogo konkavna_, če velja
$$
\forall x, y \in K \ \forall \lambda \in (0, 1): f((1 - \lambda) x + \lambda y) > (1 - \lambda) f(x) + \lambda f(y)
$$

**_Primeri._**

1. Množica $K \subseteq \mathbb{R}$ je konveksna natanko tedaj, ko je množica $K$ interval. Trdimo: $f(x) = x^2$ je konveksna funkcija (za vsak interval $K$).
$$
\begin{aligned}
& f((1 - \lambda) x + \lambda y) \stackrel{?}{\le} (1 - \lambda) f(x) + \lambda f(y) \\[2ex]
& ((1 - \lambda) x + \lambda y)^2 - ((1 - \lambda) x^2 + \lambda y^2) \\
&= (1 - \lambda)^2 x^2 + 2(1 - \lambda) \lambda xy + \lambda^2 y^2 - (1 - \lambda) x^2 - \lambda y^2 \\
&= (1 - \lambda)(1 - \lambda - 1) x^2 + 2(1 - \lambda) \lambda xy + \lambda (\lambda - 1) y^2 \\
&= -\lambda(1 - \lambda) (x^2 - 2xy + y^2) = -\lambda(1 - \lambda) (x - y)^2 \le 0
\end{aligned}
$$

2. _Afina funkcija_ $f(x_1, x_2, \dots, x_n) = a_1 x_1 + a_2 x_2 + \dots + a_n x_n + b$ (ali $f(x) = a^\top x + b$) je konveksna:
$$
\begin{aligned}
f((1 - \lambda) x + \lambda y)
&= a^\top ((1 - \lambda) x + \lambda y) + b \\
&= (1 - \lambda) a^\top x + \lambda a^\top y + (1 - \lambda) b + \lambda b \\
&= (1 - \lambda) f(x) + \lambda f(y)
\end{aligned}
$$
Funkcija $f$ je tudi konkavna. Da se dokazati, da je funkcija konveksna in konkavna natanko tedaj, ko je afina.

3. _Norma_ $\Vert \cdot \Vert : \mathbb{R}^n \to \mathbb{R}$ (npr. dolžina vektorja $\Vert x \Vert = \sqrt{x^\top x} = \sqrt{x_1^2 + x_2^2 + \dots + x_n^2}$) je funkcija s sledečimi lastnostmi:
* $\Vert x \Vert \ge 0$, $\Vert x \Vert = 0 \Rightarrow x = 0$
* $\Vert \lambda x \Vert = \vert \lambda \vert \Vert x \Vert$
* $\Vert x + y \Vert \le \Vert x \Vert + \Vert y \Vert$ (_trikotniška neenakost_)

Norma je konveksna:
$$
\Vert (1 - \lambda) x + \lambda y \Vert \le \Vert (1 - \lambda) x \Vert + \Vert \lambda y \Vert = (1 - \lambda) \Vert x \Vert + \lambda \Vert y \Vert
$$

**_Trditev._** Naj bo $K \subseteq \mathbb{R}^n$ konveksna množica ter $f, g: K \to \mathbb{R}$ konveksni funkciji. Potem velja sledeče.

1. Če $c \ge 0$, potem je $c \cdot f$ konveksna funkcija.
2. Funkcija $f + g$ je konveksna.
3. Če je funkcija $f$ afina, je slika $f(K)$ konveksna množica.

_Dokaz._

1. $(c \cdot f)((1 - \lambda) x + \lambda y) \le c ((1 - \lambda) f(x) + \lambda f(y)) = ((1 - \lambda) (c \cdot f)(x) + \lambda (c \cdot f)(y))$
2. $$
\begin{aligned}
(f + g)((1 - \lambda) x + \lambda y)
&= f((1 - \lambda) x + \lambda y) + g((1 - \lambda) x + \lambda y) \\
&\le (1 - \lambda) f(x) + \lambda f(y) + (1 - \lambda) g(x) + \lambda g(y) \\
&= (1 - \lambda) (f + g)(x) + \lambda (f + g)(y)
\end{aligned}
$$
3. Funkcija $f(x) = a^\top x + b$ je konveksna in konkavna, za $x, y \in K$ velja $f(x), f(y) \in f(K)$. Ker je $(1 - \lambda) x + \lambda y \in K$, velja
$$
(1 - \lambda) f(x) + \lambda f(y) = f((1 - \lambda) x + \lambda y) \in f(K).
$$

**_Trditev._** Naj bo $K \subseteq \mathbb{R}^n$ konveksna množica ter $f: K \to \mathbb{R}$ in $g: \operatorname{conv}(f(K)) \to \mathbb{R}$ konveksni funkciji. Denimo, da velja vsaj eno od sledečega.

* Funkcija $f$ je afina, ali
* funkcija $g$ je naraščajoča.

Potem je kompozitum $g \circ f$ konveksna funkcija.

_Dokaz._
Trdimo, da velja
$$
\begin{aligned}
f((1 - \lambda) x + \lambda y) &\le (1 - \lambda) f(x) + \lambda f(y) \\
g(f((1 - \lambda) x + \lambda y)) &\le g((1 - \lambda) f(x) + \lambda f(y)) \\
&\le (1 - \lambda) (g \circ f)(x) + \lambda (g \circ f)(y)
\end{aligned}
$$
Prva neenakost velja zaradi konveksnosti funkcije $f$. Če je funkcija $g$ naraščajoča, potem velja tudi druga neenakost. Če pa je funkcija $f$ afina, velja enakost v prvi in posledično tudi v drugi neenakosti. V obeh primerih zadnja neenakost sledi zaradi konveksnosti funkcije $g$.

**_Neprimeri._**

* Produkt konveksnih funkcij ni nujno konveksna funkcija: $f(x) = x$, $g(x) = -x$, $(f \cdot g)(x) = -x^2$.
* Kompozitum konveksnih funkcij ni nujno konveksna funkcija: $f(x) = x^2$, $g(x) = -x$, $(g \circ f)(x) = -x^2$.
* Slika konveksne množice s konveksno funkcijo ni nujno konveksna množica:
$$
\begin{aligned}
f:&\ [0, 1] \to \mathbb{R} \\
f(x) &= \begin{cases}
0 & \text{če } 0 \le x < 1 \\
1 & \text{če } x = 1
\end{cases} \\
f([0, 1]) &= \{0, 1\}
\end{aligned}
$$

---

### Konveksne funkcije in optimizacija

**_Definicija._**
Naj bo $A \subseteq \mathbb{R}^n$ in $f: A \to \mathbb{R}$. Funkcija $f$ ima v točki $x^\ast \in A$:

* _globalni maksimum_, če $\forall x \in A: f(x) \le f(x^\ast)$;
* _globalni minimum_, če $\forall x \in A: f(x) \ge f(x^\ast)$;
* _lokalni maksimum_, če $\exists \epsilon > 0 \ \forall x \in A: (\Vert x - x^\ast \Vert < \epsilon \Rightarrow f(x) \le f(x^\ast))$; in
* _lokalni minimum_, če $\exists \epsilon > 0 \ \forall x \in A: (\Vert x - x^\ast \Vert < \epsilon \Rightarrow f(x) \ge f(x^\ast))$.

**_Trditev._** Naj bo $K \subseteq \mathbb{R}^n$ konveksna množica ter $f: K \to \mathbb{R}$ konveksna funkcija. Če ima $f$ v $x^\ast \in K$ lokalni minimum, ima v $x^\ast$ tudi globalni minimum.

_Dokaz._ Naj bo $\epsilon > 0$ tak, da velja $\forall x \in K: (\Vert x - x^\ast \Vert < \epsilon \Rightarrow f(x) \ge f(x^\ast))$. Če $x^\ast$ ni globalni minimum, potem obstaja tak $y \in K$, da velja $f(y) < f(x^\ast)$. Tedaj za vsak $\lambda \in (0, 1]$ velja
$$
f((1 - \lambda) x^\ast + \lambda y) \le (1 - \lambda) f(x^\ast) + \lambda f(y) < (1 - \lambda) f(x^\ast) + \lambda f(x^\ast) = f(x^\ast) .
$$
Za dovolj majhen $\lambda$ je $(1 - \lambda) x^\ast + \lambda y$ poljubno blizu $x^\ast$:
$$
\Vert (1 - \lambda) x^\ast + \lambda y - x^\ast \Vert = \Vert \lambda (y - x^\ast) \Vert = \lambda \Vert y - x^\ast \Vert < \epsilon, \text{ če } \lambda < {\epsilon \over \Vert y - x^\ast \Vert}
$$
Torej: če je $\lambda \in \left(0, {\epsilon \over \Vert y - x^\ast \Vert}\right)$, je $\Vert (1 - \lambda) x^\ast + \lambda y - x^\ast \Vert < \epsilon$ in tedaj $f((1 - \lambda) x^\ast + \lambda y) \ge f(x^\ast)$, protislovje.

Preverjanje konveksnosti po definiciji je v splošnem težko. Večinoma je lažje preverjati konveksnost z odvodi.

Naj bo $f: (a, b) \to \mathbb{R}$ konveksna funkcija. Njen graf potem leži nad vsako tangento (**kriterij 1. odvoda**), torej
$f(y) \ge f(x) + (y-x) f'(x)$ za vsaka $x, y \in (a, b)$.

**_Primer._** Naj bo $f(x) = x^2$. Preverimo, ali za vsaka $x, y \in \mathbb{R}$ velja
$$
y^2 \stackrel{?}{\ge} x^2 + (y-x) \cdot 2x .
$$
Res:
$$
y^2 - x^2 - 2xy + 2x^2 = y^2 - 2xy + x^2 = (x-y)^2 \ge 0.
$$

Smerni koeficienti tangent na graf konveksne funkcije $f$ naraščajo - njen odvod $f'$ je torej naraščajoča funkcija, torej $f''(x) \ge 0$ za vsak $x \in (a, b)$ (**kriterij 2. odvoda**).

**_Primer._** Naj bo $f(x) = x^2$. Potem je $f''(x) = 2 \ge 0$.

**_Izrek (kriterij 1. odvoda)._** Naj bo $K \subseteq \mathbb{R}^n$ odprta konveksna množica, ter $f: K \to \mathbb{R}$ funkcija, ki ima vse parcialne odvode ${\partial f \over \partial x_i}$ ($1 \le i \le n$) - te zapišemo v _gradient_ $\nabla f(x) = \left({\partial f \over \partial x_i}(x)\right)_{i=1}^n$. Potem je funkcija $f$ konveksna natanko tedaj, ko za vsaka $x, y \in K$ velja $f(y) \ge f(x) + (\nabla f(x))^\top (y - x)$.

_Dokaz._

* ($\Longleftarrow$) Naj bodo $x, y \in K$ in $\lambda \in [0, 1]$ poljubni ter pišimo $z := (1 - \lambda) x + \lambda y$. Potem velja:
$$
\begin{aligned}
f(x) &\ge f(z) + (\nabla f(z))^\top (x - z) &&/ \cdot (1 - \lambda) \\
f(y) &\ge f(z) + (\nabla f(z))^\top (y - z) &&/ \cdot \lambda \\
\hline
(1 - \lambda) f(x) + \lambda f(y) &\ge f(z) + (\nabla f(z))^\top ((1 - \lambda) x + \lambda y - z) \\
&= f((1 - \lambda) x + \lambda y)
\end{aligned}
$$
Funkcija $f$ je torej konveksna.

* ($\Longrightarrow$) Za fiksna $x, y \in K$ je $g_{x, y}(\lambda) = f((1 - \lambda) x + \lambda y)$ funkcija v $\lambda$ - zanima nas njen odvod pri $\lambda = 0$. Funkcija $g_{x, y}$ je definirana na $(-\epsilon, 1]$ za nek $\epsilon > 0$. Naj bo $\delta > 0$ tak, da je množica $K(x, \delta) = \{y \in \mathbb{R}^n \mid \Vert x - y \Vert \le \delta\}$ (tj., krogla s središčem v $x$ in polmerom $\delta$) vsebovana v $K$. Zadostuje, da za vse $\lambda \in (-\epsilon, 0]$ velja
$$
\Vert (1 - \lambda) x + \lambda y - x \Vert = \Vert \lambda y - \lambda x \Vert = |\lambda| \Vert y - x \Vert < \delta.
$$
Vzamemo lahko torej $\epsilon := {\delta \over \Vert y - x \Vert}$. Izračunajmo $g'_{x, y}(\lambda)$.
$$
\begin{aligned}
g'_{x, y}(\lambda)
&= {d \over d \lambda} f((1 - \lambda) x + \lambda y) \\
&= {d \over d \lambda} f((1 - \lambda) x_1 + \lambda y_1, \dots, (1 - \lambda) x_n + \lambda y_n) \\
&= {\partial f \over \partial x_1}((1 - \lambda) x + \lambda y) \cdot (y_1 - x_1) + \dots + {\partial f \over \partial x_n}((1 - \lambda) x + \lambda y) \cdot (y_n - x_n) \\
&= (\nabla f((1 - \lambda) x + \lambda y))^\top (y - x)
\end{aligned}
$$
Velja torej $g'_{x, y}(0) = (\nabla f(x))^\top (y - x)$. Po definiciji odvoda nadalje velja
$$
\begin{aligned}
g'_{x, y}(0)
&= \lim_{\lambda \to 0} {g_{x, y}(\lambda) - g_{x, y}(0) \over \lambda} \\
&= \lim_{\lambda \to 0} {f((1 - \lambda) x + \lambda y) - f(x) \over \lambda} \\
&= \lim_{\lambda \searrow 0} {f((1 - \lambda) x + \lambda y) - f(x) \over \lambda} \\
&\le \lim_{\lambda \searrow 0} {(1 - \lambda) f(x) + \lambda f(y) - f(x) \over \lambda} & \text{(ker $\lambda > 0$)} \\
&= f(y) - f(x).
\end{aligned}
$$
Velja torej $f(y) \ge f(x) + (\nabla f(x))^\top (y - x)$.

**_Izrek (kriterij 2. odvoda za funkcije ene spremenljivke)._** Naj bo $f: (a, b) \to \mathbb{R}$ dvakrat odvedljiva funkcija. Potem je funkcija $f$ konveksna natanko tedaj, ko za vsak $x \in (a, b)$ velja $f''(x) \ge 0$.

_Dokaz._

* ($\Longrightarrow$) Naj bo $x \in (a, b)$ in $h > 0$ tak, da $x \pm h \in (a, b)$. Zaradi konveksnosti funkcije $f$ potem velja:
$$
f(x) = f\left({1 \over 2} (x + h) + {1 \over 2} (x - h)\right) \le {1 \over 2} f(x + h) + {1 \over 2} f(x - h)
$$
Z dvakratno uporabo L'Hôpitalovega pravila potem izpeljemo
$$
0 \le \lim_{h \to 0} {f(x + h) + f(x - h) - 2f(x) \over h^2} = \lim_{h \to 0} {f'(x + h) - f'(x - h) \over 2h} = \lim_{h \to 0} {f''(x + h) + f''(x - h) \over 2} = f''(x).
$$

* ($\Longleftarrow$) Naj bosta $x, y \in (a, b)$ (brez škode za splošnost privzamemo $x < y$) ter $\lambda \in (0, 1)$. Postavimo $z = (1 - \lambda) x + \lambda y \in (x, y)$. Po Lagrangeevem izreku velja
$$
\begin{aligned}
\exists \xi_1 &\in (x, z): & {f(z) - f(x) \over z - x} &= f'(\xi_1) \\
\exists \xi_2 &\in (z, y): & {f(y) - f(z) \over y - z} &= f'(\xi_2) \\
\exists \xi_3 &\in (\xi_1, \xi_2): & {f'(\xi_2) - f'(\xi_1) \over \xi_2 - \xi_1} &= f''(\xi_3)
\end{aligned}
$$
Ker velja $f''(\xi_3) \ge 0$ in $\xi_1 < \xi_2$, sledi $f'(\xi_1) \le f'(\xi_2)$ (tj., funkcija $f'$ narašča, ker je njen odvod nenegativen). Velja torej:
$$
\begin{aligned}
{f(z) - f(x) \over z - x} &\le {f(y) - f(z) \over y - z} & / \cdot (z - x)(y - z) \\
(y - z)(f(z) - f(x)) &\le (z - x)(f(y) - f(z)) \\
(y - z + z - x) f(z) &\le (y - z) f(x) + (z - x) f(y) \\
(y - x) f(z) &\le (1 - \lambda)(y - x) f(x) + \lambda (y - x) f(y) \\
f((1 - \lambda) x + \lambda y) &\le (1 - \lambda) f(x) + \lambda f(y)
\end{aligned}
$$

---

Pri Algebri 1 se naučite: $x \in \mathbb{C}^n \setminus \{0\}$ je _lastni vektor_ matrike $A \in \mathbb{R}^{n \times n}$, če obstaja _lastna vrednost_ $\lambda \in \mathbb{C}$, da velja $Ax = \lambda x$. Matrika $A$ je _diagonalizabilna_, če obstaja $n$ linearno neodvisnih lastnih vektorjev.

**_Primer._** Matrika
$A = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}$ ni diagonalizabilna:
$$
\begin{gathered}
\begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}
\begin{bmatrix} x \\ y \end{bmatrix} =
\begin{bmatrix} y \\ 0 \end{bmatrix} =
\lambda \begin{bmatrix} x \\ y \end{bmatrix} \\
\begin{aligned}
\lambda &= 0: & y &= 0, & x &\ne 0 \\
\lambda &\ne 0: & y &= 0, & x &= 0 & \text{ni lastni vektor}
\end{aligned}
\end{gathered}
$$
Imamo torej samo en linearno neodvisen lastni vektor.

Lastne vrednosti poiščemo kot ničle karakterističnega polinoma $\det(A - \lambda I)$. Lastni vektorji so neničelne rešitve enačbe $(A - \lambda I) x = 0$ za lastne vrednosti $\lambda$.

Realna matrika ima lahko kompleksne lastne vrednosti in lastne vektorje:
$$
A = \begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix} \qquad
\begin{vmatrix} -\lambda & 1 \\ -1 & -\lambda \end{vmatrix} = \lambda^2 + 1, \quad
\lambda = \pm i
$$

Če je $A$ diagonalizabilna matrika, jo lahko zapišemo kot $A = PDP^{-1}$, kjer je $P$ obrnljiva matrika, katere stolpci so linearno neodvisni lastni vektorji, $D$ pa diagonalna matrika z ustreznimi lastnimi vrednostmi na diagonali.

**_Definicija._** Matrika $A \in \mathbb{R}^{n \times n}$ je _simetrična_, če velja $A^\top = A$.

**_Izrek._** Simetrična matrika $A \in \mathbb{R}^{n \times n}$ ima realne lastne vrednosti in je diagonalizabilna v ortonormirani bazi (tj., lastni vektorji imajo normo $1$ in so drug na drugega pravokotni). Tedaj lahko pišemo $A = UDU^\top$, kjer je $U$ ortogonalna matrika (tj., $U^\top U = I$ oziroma $U^{-1} = U^\top$) z lastnimi vektorji v stolpcih.

**_Definicija._** Naj bo $A \in \mathbb{R}^{n \times n}$ simetrična matrika.

* $A$ je _pozitivno semidefinitna_ ($A \ge 0$), če ima same nenegativne lastne vrednosti.
* $A$ je _pozitivno definitna_ ($A > 0$), če ima same pozitivne lastne vrednosti.
* $A$ je _negativno semidefinitna_ ($A \le 0$), če ima same nepozitivne lastne vrednosti.
* $A$ je _negativno definitna_ ($A < 0$), če ima same negativne lastne vrednosti.
* $A$ je _nedefinitna_, če ima tako pozitivne kot negativne lastne vrednosti.

**_Definicija._** Naj bo $A = (a_{ij})_{i,j=1}^n \in \mathbb{R}^{n \times n}$ simetrična matrika. _Kvadratna forma_, ki pripada $A$, je
$$
f(x) = x^\top A x = [x_1 \ x_2 \ \dots \ x_n] \begin{bmatrix}
a_{11} x_1 + a_{12} x_2 + \dots a_{1n} x_n \\
a_{21} x_1 + a_{22} x_2 + \dots a_{2n} x_n \\
\vdots \\
a_{n1} x_1 + a_{n2} x_2 + \dots a_{nn} x_n
\end{bmatrix} = \sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i x_j
$$

**_Primera._**

* Kvadratna forma za matriko $A = \begin{bmatrix} 3 & 1 \\ 1 & -2 \end{bmatrix}$ je $f(x_1, x_2) = 3 x_1^2 + 2 x_1 x_2 - 2 x_2^2$.
* Kvadratna forma $f(x_1, x_2, x_3) = 4 x_1^2 - 2 x_1 x_2 + 3 x_1 x_3 - x_2^2 + x_3^2$ ustreza matriki
$$
A = \begin{bmatrix} 4 & -1 & {3 \over 2} \\ -1 & -1 & 0 \\ {3 \over 2} & 0 & 1 \end{bmatrix}.
$$

**_Trditev._**

* $A \ge 0 \Longleftrightarrow \forall x \in \mathbb{R}^n: \ x^\top A x \ge 0$,
* $A > 0 \Longleftrightarrow \forall x \in \mathbb{R}^n \setminus \{0\}: \ x^\top A x > 0$,
* $A \le 0 \Longleftrightarrow \forall x \in \mathbb{R}^n: \ x^\top A x \le 0$,
* $A < 0 \Longleftrightarrow \forall x \in \mathbb{R}^n \setminus \{0\}: \ x^\top A x < 0$,
* $A$ je nedefinitna natanko tedaj, ko $x^\top A x$ doseže tako pozitivne kot negativne vrednosti.

_Dokaz._ Vzemimo $x \in \mathbb{R}^n$ in diagonalizirajmo $A = UDU^\top$. Če je $x = 0$, potem je $x^\top A x = 0$. Sicer pišimo $\tilde{x} = U^\top x$, posledično velja tudi $x = U \tilde{x}$. Potem velja
$$
x^\top A x = x^\top UDU^\top x = \tilde{x}^\top D \tilde{x} = \sum_{i=1}^n \lambda_i \tilde{x}_i^2.
$$
Matrika $A$ ima tako vse lastne vrednosti nenegativne/pozitivne/nepozitivne/negativne natanko tedaj, ko je za vsak $x \in \mathbb{R}^n \setminus \{0\}$ zgornja vrednost $\ge/>/\le/< 0$.

**_Primer._** Naj bo $A$ simetrična matrika dimenzij $2 \times 2$:
$$
A = \begin{bmatrix} a & b \\ b & c \end{bmatrix}
$$
Potem velja:
$$
\begin{alignedat}{8}
A \ge 0 \quad &\Leftrightarrow &\quad \lambda_1, \lambda_2 &\ge 0 \quad \Leftrightarrow &\quad \lambda_1 + \lambda_2 &\ge 0 &\quad &\Leftrightarrow &\quad \operatorname{tr} A &=&\ a + c &\ge 0 \\
&&&& \lambda_1 \lambda_2 &\ge 0 &&& \det A &=&\ ac - b^2 &\ge 0 \\[2ex]
A > 0 \quad &\Leftrightarrow &\quad \lambda_1, \lambda_2 &> 0 \quad \Leftrightarrow &\quad \lambda_1 + \lambda_2 &> 0 &\quad &\Leftrightarrow &&&\ a + c &> 0 &\quad &\Leftrightarrow & a &> 0 \\
&&&& \lambda_1 \lambda_2 &> 0 &&&&& ac - b^2 &> 0 &&& ac - b^2 &> 0 \\[2ex]
A \le 0 \quad &\Leftrightarrow &\quad \lambda_1, \lambda_2 &\le 0 \quad \Leftrightarrow &\quad \lambda_1 + \lambda_2 &\le 0 &\quad &\Leftrightarrow &&&\ a + c &\le 0 \\
&&&& \lambda_1 \lambda_2 &\ge 0 &&&&& ac - b^2 &\ge 0 \\[2ex]
A < 0 \quad &\Leftrightarrow &\quad \lambda_1, \lambda_2 &< 0 \quad \Leftrightarrow &\quad \lambda_1 + \lambda_2 &< 0 &\quad &\Leftrightarrow &&&\ a + c &< 0 &\quad &\Leftrightarrow & a &< 0 \\
&&&& \lambda_1 \lambda_2 &> 0 &&&&& ac - b^2 &> 0 &&& ac - b^2 &> 0 \\[2ex]
A \text{ nedefinitna} \quad &\Leftrightarrow &\quad \lambda_1 &> 0 \quad \Leftrightarrow &\quad \lambda_1 \lambda_2 &< 0 &\quad &\Leftrightarrow &&& ac - b^2 &< 0 \\
&& \lambda_2 &< 0
\end{alignedat}
$$

**_Definicija._** _Glavne poddeterminante_ matrike $A = (a_{ij})_{i,j=1}^n \in \mathbb{R}^{n \times n}$ so vrednosti $\det (a_{ij})_{i,j=1}^\ell$ ($1 \le \ell \le n$).

**_Trditev._** Naj bo $A \in \mathbb{R}^{n \times n}$ simetrična matrika. Potem velja:

* $A > 0$ natanko tedaj, ko so vse glavne poddeterminante pozitivne.
* $A < 0$ natanko tedaj, ko glavne poddeterminante alternirajo med negativnimi in pozitivnimi vrednostmi.

**_Definicija._** Naj bo $\Omega \subseteq \mathbb{R}^n$ odprta množica in $f: \Omega \to \mathbb{R}$ funkcija, za katero obstajajo vsi drugi parcialni odvodi ${\partial^2 f \over \partial x_j \partial x_i}$ ($1 \le i, j \le n$). _Hessejeva matrika_ funkcije $f$ je $H_f(x) = \left({\partial^2 f \over \partial x_j \partial x_i}(x)\right)_{i,j=1}^n$.

Če so vsi drugi parcialni odvodi **zvezni** ($f \in \mathcal{C}^2(\Omega)$), velja $\forall i, j: {\partial^2 f \over \partial x_j \partial x_i} = {\partial^2 f \over \partial x_i \partial x_j}$, torej je $H_f(x)$ simetrična.

**_Izrek (kriterij 2. odvoda)._** Naj bo $K \subseteq \mathbb{R}^n$ odprta konveksna množica, ter $f: K \to \mathbb{R}$ funkcija iz $\mathcal{C}^2(K)$. Potem je funkcija $f$ konveksna natanko tedaj, ko za vsak $x \in K$ velja $H_f(x) \ge 0$.

_Dokaz._ Trdimo, da je funkcija $f$ konveksna natanko tedaj, ko za vsaka $x, y \in K$ obstaja tak $\epsilon$, da je funkcija $h_{x,y}: (-\epsilon, 1+\epsilon) \to \mathbb{R}$, $h_{x,y}(t) = f((1 - t) x + ty)$ konveksna in $h_{x,y} \in \mathcal{C}^2(-\epsilon, 1+\epsilon)$. Dokažimo najprej to trditev.

* ($\Longrightarrow$) Ker je množica $K$ odprta, obstaja tak $\epsilon$, da je funkcija z zgornjim predpisom dobro definirana. Ker velja $f \in \mathcal{C}^2(K)$, velja tudi $h_{x,y} \in \mathcal{C}^2(-\epsilon, 1+\epsilon)$. Dokažimo še, da je $h_{x,y}$ konveksna funkcija. Vzemimo torej poljubne $s, t \in (-\epsilon, 1+\epsilon)$ in $\lambda \in [0, 1]$. Ker je $f$ konveksna, velja:
$$
\begin{aligned}
f((1 - \lambda)((1 - t) x + ty) + \lambda ((1 - s) x + sy)) &\le (1 - \lambda) f((1 - t) x + ty) + \lambda f((1 - s) x + sy) \\
f((1 - (1 - \lambda) t - \lambda s) x + ((1 - \lambda) t + \lambda s) y) &\le (1 - \lambda) f((1 - t) x + ty) + \lambda f((1 - s) x + sy) \\
h_{x,y}((1 - \lambda) t + \lambda s) &\le (1 - \lambda) h_{x,y}(t) + \lambda h_{x,y}(s)
\end{aligned}
$$

* ($\Longleftarrow$) Ker je za vsaka $x, y \in K$ funkcija $h_{x,y}$ konveksna, za vsak $\lambda \in [0, 1]$ velja:
$$
\begin{aligned}
h_{x,y}(\lambda) = h_{x,y}((1 - \lambda) \cdot 0 + \lambda \cdot 1) &\le (1 - \lambda) h_{x,y}(0) + \lambda h_{x,y}(1) \\
f((1 - \lambda) x + \lambda y) &\le (1 - \lambda) f(x) + \lambda f(y)
\end{aligned}
$$
Funkcija $f$ je torej konveksna.

Za poljubna $x, y \in K$ lahko torej zapišemo:
$$
\begin{aligned}
h_{x,y}(t) &= f((1 - t) x + ty) \\
&= f((1 - t) x_1 + ty_1, \dots, (1 - t) x_n + ty_n) \\[2ex]
h'_{x,y}(t) &= {\partial f \over \partial x_1}((1 - t) x + ty) \cdot (y_1 - x_1) + \dots + {\partial f \over \partial x_n}((1 - t) x + ty) \cdot (y_n - x_n) \\
&= (\nabla f((1 - t) x + ty))^\top (y - x) \\[2ex]
h''_{x,y}(t) &= {\partial^2 f \over \partial x_1 \partial x_1}((1 - t) x + ty) \cdot (y_1 - x_1)(y_1 - x_1) + \dots + {\partial^2 f \over \partial x_n \partial x_1}((1 - t) x + ty) \cdot (y_n - x_n)(y_1 - x_1) \\
&+ \dots \\
&+ {\partial^2 f \over \partial x_1 \partial x_n}((1 - t) x + ty) \cdot (y_1 - x_1)(y_n - x_n) + \dots + {\partial^2 f \over \partial x_n \partial x_n}((1 - t) x + ty) \cdot (y_n - x_n)(y_n - x_n) \\
&= \sum_{i=1}^n \sum_{j=1}^n {\partial^2 f \over \partial x_j \partial x_i}((1 - t) x + ty) \cdot (y_j - x_j)(y_i - x_i) \\
&= (y - x)^\top H_f((1 - t) x + ty) (y - x)
\end{aligned}
$$
Velja torej:
$$
\forall x, y \in K \ \forall t \in [0, 1]: h''_{x,y}(t) \ge 0 \iff
\forall x, y \in K \ \forall t \in [0, 1]: H_f((1 - t) x + ty) \ge 0 \iff
\forall x \in K: H_f(x) \ge 0
$$

**Opomba.** Taylorjev razvoj funkcije več spremenljivk lahko zapišemo kot
$$
f(y) = f(x) + (\nabla f(x))^\top (y - x) + {1 \over 2} (y - x)^\top H_f(x) (y - x) + \text{členi višjega reda}
$$
Če je v $x$ lokalni minimum, potem velja $H_f(x) \ge 0$, $\nabla f(x) = 0$. Če velja $H_f(x) > 0$ in $\nabla f(x) = 0$, potem je v $x$ lokalni minimum.

----

Iz dokazov za kriterij 2. odvoda lahko ugotovimo, da če za vsak $x \in K$ velja $H_f(x) > 0$, potem je $f$ strogo konveksna. Obratno ne velja v splošnem (npr. $f(x) = x^4$).

**_Trditev._** Naj bo $K \subseteq \mathbb{R}^n$ konveksna množica, ter $f: K \to \mathbb{R}$ strogo konveksna funkcija. Če je $x^\ast \in K$ globalni maksimum funkcije $f$, potem je $x^\ast$ ekstremna točka za $K$.

_Dokaz._ Predpostavimo, da $x^\ast$ ni ekstremna točka, torej obstajajo $x, y \in K, \ x \ne y$ ter $\lambda \in (0, 1)$, da velja $x^\ast = (1 - \lambda) x + \lambda y$. Potem velja
$$
f(x^\ast) = f((1 - \lambda) x + \lambda y) < (1 - \lambda) f(x) + \lambda f(y) \le (1 - \lambda) f(x^\ast) + \lambda f(x^\ast) = f(x^\ast),
$$
protislovje.

**_Neprimer._** Naj bo $K = [-1, 1] \times \mathbb{R}$ in $f: K \to \mathbb{R}$, $f(x, y) = x^2$. Funkcija $f$ je konveksna, saj velja $H_f(x, y) = \begin{bmatrix} 2 & 0 \\ 0 & 0 \end{bmatrix} \ge 0$ (lastni vrednosti sta $0$ in $2$), a ni strogo konveksna, saj za vse $\lambda \in (0, 1)$ velja
$$
1 = f(1, \lambda) = f((1 - \lambda) (1, 0) + \lambda (1, 1)) = (1 - \lambda) f(1, 0) + \lambda f(1, 1) = 1
$$
Globalni maksimumi funkcije $f$ so doseženi v točkah iz $\{-1, 1\} \times \mathbb{R}$. Množica $K$ nima ekstremnih točk.

---

### Konveksne funkcije in vezani ekstremi

Naj bo $\Omega \subseteq \mathbb{R}^n$ odprta množica. Problem **vezanih ekstremov z neenačbami (VEN)** definiramo kot
$$
\begin{aligned}
\max / \min \ f(x) \\[1ex]
\text{p.p.} \quad
x &\in \Omega \\
g_1(x) &\le 0 \\
g_2(x) &\le 0 \\
&\vdots \\
g_m(x) &\le 0
\end{aligned}
$$
Množica dopustnih rešitev je torej
$$
D = \{x \in \Omega \mid \forall i \in \{1, 2, \dots, m\}: g_i(x) \le 0\}.
$$

**_Primeri._** Iščemo maksimum in minimum funkcije $f(x, y) = 2x^3 + 4x^2 + y^2 - 2xy$ v območju med $y = 4$ in $y = x^2$.


Imamo torej:
$$
\begin{aligned}
\Omega &= \mathbb{R}^2 \\
y &\le 4 & y - 4 &\le 0 \\
y &\ge x^2 & x^2 - y &\le 0
\end{aligned}
$$

1. način:
* V notranjosti:
$$
\begin{alignedat}{2}
{\partial f \over \partial x}(x, y) &=&\ 6x^2 + 8x - 2y &= 0 \\
{\partial f \over \partial y}(x, y) &=&\ 2y - 2x &= 0 \Longrightarrow x = y \\
&& 6x^2 + 6x &= 0 \\
&& x(x+1) &= 0
\end{alignedat}
$$
Dobimo kandidata $x = y = 0$ in $x = y = -1$, ki pa nista v $\mathring{D}$ (relativna notranjost $D$).
* Na zgornjem robu: $x \in (-2, 2)$, $y = 4$
$$
\begin{gathered}
\begin{aligned}
g(x) &= f(x, 4) = 2x^3 + 4x^2 - 8x + 16 \\
g'(x) &= 6x^2 + 8x - 8 = 2(3x^2 + 4x - 4) = 0 \\
x &= {-4 \pm \sqrt{16 + 48} \over 6} = {-2 \pm 4 \over 3}
\end{aligned} \\
\begin{aligned}
x_1 &= -2 & f(-2, 4) &= 32 \quad \text{(ni v relativni notranjosti roba)} \\
x_2 &= {2 \over 3} & f\left({2 \over 3}, 4\right) &= {352 \over 27} \approx 13.037
\end{aligned}
\end{gathered}
$$
* Na spodnjem robu: $x \in (-2, 2)$, $y = x^2$
$$
\begin{aligned}
h(x) &= f(x, x^2) = x^4 + 4x^2 \\
h'(x) &= 4x^3 + 8x = 4x(x^2 + 2) = 0 \\
x &= 0 \quad \ \ f(0, 0) = 0
\end{aligned}
$$
* Na stičiščih obeh robov: $x = \pm 2$, $y = 4$
$$
f(-2, 4) = 32 \qquad f(2, 4) = 32
$$
Globalni maksimum je torej v $(\pm 2, 4)$, globalni minimum pa v $(0, 0)$.

2. način:
* V notranjosti: kot prej.
* Na zgornjem robu: $y - 4 = 0$.
Definirajmo _Lagrangeevo funkcijo_
$$
L(x, y, \lambda) = 2x^3 + 4x^2 + y^2 - 2xy + \lambda (y - 4),
$$
kjer je $\lambda$ _Lagrangeev množitelj (multiplikator)_. Poiščimo parcialne odvode Lagrangeeve funkcije:
$$
\begin{gathered}
\begin{alignedat}{2}
{\partial L \over \partial x} &= 6x^2 + 8x - 2y &&= 0 \\
{\partial L \over \partial y} &= 2y - 2x + \lambda &&= 0 \\
{\partial L \over \partial \lambda} &= y - 4 &&= 0
\end{alignedat} \\
y = 4 \qquad x = {-2 \pm 4 \over 3} \qquad \lambda = {-28 \pm 8 \over 3}
\end{gathered}
$$
Sistem enačb ima rešitvi $(x, y, \lambda) = (-2, 4, -12)$ in $(x, y, \lambda) = \left({2 \over 3}, 4, -{20 \over 3}\right)$.
* Na spodnjem robu:
$$
\begin{gathered}
L(x, y, \mu) = 2x^3 + 4x^2 + y^2 - 2xy + \mu (x^2 - y) \\
\begin{alignedat}{2}
{\partial L \over \partial x} &= 6x^2 + 8x - 2y + 2 \mu x &&= 0 \\
{\partial L \over \partial y} &= 2y - 2x - \mu &&= 0 \\
{\partial L \over \partial \mu} &= x^2 - y &&= 0 \\[2ex]
y &= x^2 \\
\mu &= 2x^2 - 2x \\
0 &= 4x^3 + 8x = 4x (x^2 + 2)
\end{alignedat} \\
x = 0 \qquad y = 0 \qquad \mu = 0
\end{gathered}
$$
Sistem enačb ima rešitev $(x, y, \mu) = (0, 0, 0)$.
* Na stičišču obeh robov:
$$
\begin{gathered}
L(x, y, \lambda, \mu) = 2x^3 + 4x^2 + y^2 - 2xy + \lambda (y - 4) + \mu (x^2 - y) \\
\begin{alignedat}{2}
{\partial L \over \partial x} &= 6x^2 + 8x - 2y + 2 \mu x &&= 0 \\
{\partial L \over \partial y} &= 2y - 2x + \lambda - \mu &&= 0 \\
{\partial L \over \partial \lambda} &= y - 4 &&= 0 \\
{\partial L \over \partial \mu} &= x^2 - y &&= 0 \\[2ex]
\end{alignedat} \\
y = 4 \qquad x = \pm 2 \qquad \mu = \mp 4 - 4 \qquad \lambda = -12
\end{gathered}
$$
Sistem enačb ima rešitvi $(x, y, \lambda, \mu) = (-2, 4, -12, 0)$ in $(x, y, \lambda, \mu) = (2, 4, -12, -8)$.

3. način:
$$
\begin{alignedat}{2}
f(x, y) &= 2x^3 + 4x^2 + y^2 - 2xy \\
\text{p.p.} \quad y - 4 &\le 0 \\
x^2 - y &\le 0 \\[2ex]
L(x, y, \lambda, \mu) &= 2x^3 + 4x^2 + y^2 - 2xy &&+ \lambda (y - 4) + \mu (x^2 - y) \\
L_x := {\partial L \over \partial x} &= 6x^2 + 8x - 2y + 2 \mu x &&= 0 \\
L_y := {\partial L \over \partial y} &= 2y - 2x + \lambda - \mu &&= 0 \\
\end{alignedat}
$$
Ločimo primere:
* $\lambda = 0$, $\mu = 0$: notranjost
* $y - 4 = 0$, $\mu = 0$: zgornji rob
* $\lambda = 0$, $x^2 - y = 0$: spodnji rob
* $y - 4 = 0$, $x^2 - y = 0$: stičišči robov

Za problem vezanih ekstremov z neenačbami lahko torej zapišemo Lagrangeevo funkcijo
$$
L(x_1, \dots, x_n, \lambda_1, \dots, \lambda_m) = f(x_1, \dots, x_n) + \sum_{i=1}^m \lambda_i g_i(x_1, \dots, x_n)
$$
Lokalni ekstremi so doseženi pri
$$
\begin{align}
L_j := {\partial L \over \partial x_j}(x_1, \dots, x_n, \lambda_1, \dots, \lambda_m) &= 0 & (1 \le j \le n) \\
\lambda_i g_i(x_1, \dots, x_n) &= 0 & (1 \le i \le m) \\
g_i(x_1, \dots, x_n) &\le 0 & (1 \le i \le m)
\end{align}
$$
Ločimo na $2^m$ primerov glede na $g_i(x_1, \dots, x_n) = 0$ oziroma $g_i(x_1, \dots, x_n) < 0$ in posledično $\lambda_i = 0$ ($1 \le i \le m$).

**_Definicija._** Vrednosti $x_1, \dots, x_n, \lambda_1, \dots, \lambda_m$ ustrezajo _Karush-Kuhn-Tuckerjevim (KKT) pogojem_ za problem vezanega ekstrema z neenačbami, če velja
$$
\begin{align}
L_j := {\partial L \over \partial x_j}(x_1, \dots, x_n, \lambda_1, \dots, \lambda_m) &= 0 & (1 \le j \le n) \\
\lambda_i g_i(x_1, \dots, x_n) &= 0 & (1 \le i \le m) \\
g_i(x_1, \dots, x_n) &\le 0 & (1 \le i \le m) \\
\lambda_i &\ge 0 & (1 \le i \le m)
\end{align}
$$

Ali so Karush-Kuhn-Tuckerjevi pogoji za $(x^\ast, \lambda^\ast)$ zadoščeni natanko tedaj, ko je $x^\ast$ globalni ekstrem? V splošnem **NE**. Bo pa odgovor pritrdilen za **konveksne optimizacijske probleme**.

**_Primera._**

1. $$
\begin{aligned}
\min \ x^2 - y^2 \\[1ex]
\text{p.p.} \quad
x, y &\in \mathbb{R} & (\Omega = \mathbb{R}^2) \\
x, y &\ge 0
\end{aligned}
$$
Tak problem je neomejen - globalnega minimuma ni! Vseeno lahko najdemo točko, ki ustreza Karush-Kuhn-Tuckerjevim pogojem:
$$
\begin{alignedat}{5}
L(x, y, \lambda, \mu) &= x^2 - y^2 &&- \lambda x - \mu y \\
L_x &= 2x - \lambda &&= 0 & -\lambda x &= 0 &\qquad x &\ge 0 &\qquad \lambda &\ge 0 \\
L_y &= -2y - \mu &&= 0 & -\mu y &= 0 &\qquad y &\ge 0 &\qquad \mu &\ge 0 \\
x &= y = \lambda = \mu &&= 0
\end{alignedat}
$$

2. $$
\begin{aligned}
\min \ x \\[1ex]
\text{p.p.} \quad
x, y &\in \mathbb{R} & (\Omega = \mathbb{R}^2) \\
0 \le y &\le x^3
\end{aligned}
$$
Globalni minimum je v točki $(x, y) = (0, 0)$:


$$
\begin{alignedat}{5}
L(x, y, \lambda, \mu) &= x - \lambda y +{} &\mu &(y - x^3) \\
L_x &= 1 - 3 \mu x^2 &&= 0 &\qquad -\lambda y &= 0 &\qquad y &\ge 0 &\qquad \lambda &\ge 0 \\
L_y &= -\lambda + \mu &&= 0 &\qquad \mu (y - x^3) &= 0 &\qquad y &\le x^3 &\qquad \mu &\ge 0 \\
\lambda &= \mu\ne 0 & y &= x = 0 & 1 &= 0 & \rightarrow\!&\!\leftarrow
\end{alignedat}
$$

**_Izrek._** Naj bo $\Omega \subseteq \mathbb{R}^n$ odprta konveksna množica ter $f, g_1, g_2, \dots, g_m: \Omega \to \mathbb{R}$ konveksne odvedljive funkcije. Če $(x^\ast, \lambda^\ast) \in \Omega \times \mathbb{R}^m$ zadošča Karush-Kuhn-Tuckerjevim pogojem, potem je $x^\ast$ globalni minimum funkcije $f|_D$, kjer je $D = \{x \in \Omega \mid \forall i \in \{1, 2, \dots, m\}: g_i(x) \le 0\}$ (tj., $x^\ast$ je optimalna rešitev ustreznega problema vezanih ekstremov z neenačbami).

**Opomba.** Pri pogojih iz zgornjega izreka so torej Karush-Kuhn-Tuckerjevi pogoji zadostni za optimalnost rešitve.

_Dokaz._ Vzemimo poljuben $x \in D$. Zaradi konveksnosti (kriterij 1. odvoda) velja:
$$
\begin{aligned}
f(x) &\ge f(x^\ast) + (\nabla f(x^\ast))^\top (x - x^\ast) \\
\forall i \in \{1, 2, \dots, m\}: \ g_i(x) &\ge g_i(x^\ast) + (\nabla g_i(x^\ast))^\top (x - x^\ast) \qquad / \cdot \lambda_i^\ast \\ \hline
f(x) \ge f(x) + \sum_{i=1}^m \lambda_i^\ast g_i(x) &\ge f(x^\ast) + \sum_{i=1}^m \lambda_i^\ast g_i(x^\ast) + \left(\nabla f(x^\ast) + \sum_{i=1}^m \lambda_i^\ast \nabla g_i(x^\ast)\right)^\top (x - x^\ast) \\
&= f(x^\ast) + (\nabla L(x^\ast, \lambda^\ast))^\top (x - x^\ast) = f(x^\ast) \\
\end{aligned}
$$

**_Izrek._** Naj bo $\Omega \subseteq \mathbb{R}^n$ odprta množica ter $f, g_1, g_2, \dots, g_m: \Omega \to \mathbb{R}$ funkcije, pri čemer je funkcija $f$ odvedljiva. Če je $x^\ast$ globalni minimum funkcije $f|_D$ za $D = \{x \in \Omega \mid \forall i \in \{1, 2, \dots, m\}: g_i(x) \le 0\}$ in velja vsaj eno od sledečega:

* funkcije $g_1, g_2, \dots, g_m$ so afine; ali
* množica $\Omega$ je konveksna, $\mathring{D} \ne \emptyset$ ter funkcije $f, g_1, g_2, \dots, g_m$ so konveksne; ali
* funkcije $g_1, g_2, \dots, g_m$ so odvedljive ter $(\nabla g_i(x^\ast))_{\!\!\!\!\!\substack{i = 1 \\ g_i(x^\ast) = 0}}^m$ je zaporedje linearno neodvisnih vektorjev,

potem obstaja tak $\lambda^\ast \in \mathbb{R}^m$, da $(x^\ast, \lambda^\ast)$ ustreza Karush-Kuhn-Tuckerjevim pogojem.

Dokaz izpustimo. V dokazu se uporabi Farkaseva lema.

**Opomba.** Pri pogojih iz zgornjega izreka so torej Karush-Kuhn-Tuckerjevi pogoji potrebni za optimalnost rešitve.

**_Posledica._** Naj bo $\Omega \subseteq \mathbb{R}^n$ odprta konveksna množica ter $f, g_1, g_2, \dots, g_m: \Omega \to \mathbb{R}$ konveksne odvedljive funkcije, tako da velja $\mathring{D} \ne \emptyset$. Potem je $x^\ast \in \Omega$ globalni minimum problema vezanih ekstremov z neenačbami natanko tedaj, ko obstaja tak $\lambda^\ast \in \mathbb{R}^m$, da $(x^\ast, \lambda^\ast)$ ustreza Karush-Kuhn-Tuckerjevim pogojem.

**Opomba.** Takemu problemu rečemo **konveksni problem** oziroma **problem konveksne optimizacije**. Čim najdemo eno rešitev Karush-Kuhn-Tuckerjevih pogojev, smo našli optimalno rešitev takega problema (tj., globalni minimum).

**_Primer._**
$$
\begin{aligned}
\min \ x \\[1ex]
\text{p.p.} \quad
x, y &\in \mathbb{R} & (\Omega = \mathbb{R}^2) \\
0 \le y &\le x^3
\end{aligned}
$$
Globalni minimum je v točki $(x^\ast, y^\ast) = (0, 0)$, kjer pa Karush-Kuhn-Tuckerjevi pogoji niso izpolnjeni. Velja namreč:
$$
\begin{aligned}
g_1(x, y) &= -y & g_1(0, 0) &= 0 & \text{afina} \\
g_2(x, y) &= y - x^3 & g_2(0, 0) &= 0 & \text{ni afina} \\
H_{g_2}(x, y) &= \begin{bmatrix} -6x & 0 \\ 0 & 0 \end{bmatrix} \not\ge 0 & (\text{za } x &> 0) & \text{ni konveksna} \\
\nabla g_1(x, y) &= \begin{bmatrix} 0 \\ -1 \end{bmatrix} &
\nabla g_2(x, y) &= \begin{bmatrix} -3x^2 \\ 1 \end{bmatrix} \\
\nabla g_1(0, 0) &= \begin{bmatrix} 0 \\ -1 \end{bmatrix} &
\nabla g_2(0, 0) &= \begin{bmatrix} 0 \\ 1 \end{bmatrix} &
\text{nista linearno neodvisna}
\end{aligned}
$$

**_Trditev._** Naj bo $K \subseteq \mathbb{R}^n$ konveksna množica, $f: K \to \mathbb{R}$ konveksna funkcija, ter $b \in \mathbb{R}$. Potem je množica $A = \{x \in K \mid f(x) \le b\}$ konveksna.

_Dokaz._ Vzemimo poljubne $x, y \in A$ ter $\lambda \in [0, 1]$. Potem velja
$$
f((1 - \lambda) x + \lambda y) \le (1 - \lambda) f(x) + \lambda f(y) \le (1 - \lambda) b + \lambda b = b.
$$
Velja torej $(1 - \lambda) x + \lambda y \in A$, zato je množica $A$ konveksna.

**Opomba.** Če je množica $\Omega$ konveksna in so funkcije $g_1, g_2, \dots, g_m: \Omega \to \mathbb{R}$ konveksne ter $b \in \mathbb{R}^m$, potem je množica $\{x \in \Omega \mid \forall i \in \{1, 2, \dots, m\}: g_i(x) \le b_i\}$ konveksna. Na primer, za $f(x, y) = x^2 + y^2$ imamo $H_f(x, y) = \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \ge 0$, torej je $f$ konveksna funkcija in je tako $\{(x, y) \in \mathbb{R}^2 \mid f(x, y) \le 4\}$ konveksna množica.

**_Primer._**
$$
\begin{aligned}
\min \ {1 \over x} + {2 \over y} \\[1ex]
\text{p.p.} \quad
x &> 0 \\
y &> 0 \\
x + y &\le 5 \\
3x^2 + 2y^2 &\le 35
\end{aligned}
$$


To je konveksni problem:
$$
\begin{aligned}
\Omega &= \{(x, y) \in \mathbb{R}^2 \mid x > 0, y > 0\} & \text{konveksna,} &\ \text{odprta} \\
f(x, y) &= {1 \over x} + {2 \over y} &
H_f(x, y) &= \begin{bmatrix} 2x^{-3} & 0 \\ 0 & 4y^{-3} \end{bmatrix} \ge 0 \\
g_1(x, y) &= x + y - 5 && \text{afina} \\
g_2(x, y) &= 3x^2 + 2y^2 - 35 &
H_{g_2}(x, y) &= \begin{bmatrix} 6 & 0 \\ 0 & 4 \end{bmatrix} \ge 0
\end{aligned}
$$

$$
\begin{alignedat}{3}
L(x, y, \lambda, \mu) &= {1 \over x} + {2 \over y} + \lambda (x + y &{} - 5) &+ \mu (3x^2 &{} + 2y^2 - 35) \qquad \\
\text{KKT:} \quad L_x &= -{1 \over x^2} + \lambda + 6 \mu x &&= 0 \\
L_y &= -{2 \over y^2} + \lambda + 4 \mu y &&= 0 \\
0 &= \lambda (x + y - 5) & \lambda &\ge 0 & x + y - 5 &\le 0 \\
0 &= \mu (3x^2 + 2y^2 - 35) & \mu &\ge 0 & 3x^2 + 2y^2 - 35 &\le 0
\end{alignedat}
$$

1. $g_1(x, y) = x + y - 5 = 0$: $y = 5 - x$
$$
\begin{alignedat}{3}
L(x, 5 - x, \lambda, \mu) &= {1 \over x} + {2 \over 5 - x} + \mu (5x^2 - 20x &&+ 15) \qquad \\
\text{KKT:} \quad L_x &= -{1 \over x^2} + \lambda + 6 \mu x &&= 0 \\
L_y &= -{2 \over (5 - x)^2} + \lambda + 4 \mu (5 - x) &&= 0 \\
0 &= \mu (5x^2 - 20x + 15) && \lambda, \mu \ge 0 \qquad 5x^2 - 20x + 15 \le 0
\end{alignedat}
$$

1. $g_2(x, 5 - x) = 0$: $x = 2 \pm 1$, $y = 3 \mp 1$
$$
\begin{alignedat}{3}
x = 1, y = 4: \\
L(1, 4, \lambda, \mu) &= 1 + {1 \over 2} &&= {3 \over 2} &\qquad \lambda, \mu &\ge 0 \\
\text{KKT:} \quad L_x &= -1 + \lambda + 6 \mu &&= 0 \\
L_y &= -{1 \over 8} + \lambda + 16 \mu &&= 0 \\
\mu &= -{7 \over 80} < 0 &&\rightarrow\!\leftarrow \\[2ex]
x = 3, y = 2: \\
L(3, 2, \lambda, \mu) &= {1 \over 3} + 1 &&= {4 \over 3} &\qquad \lambda, \mu &\ge 0 \\
\text{KKT:} \quad L_x &= -{1 \over 9} + \lambda + 18 \mu &&= 0 \\
L_y &= -{1 \over 2} + \lambda + 8 \mu &&= 0 \\
\mu &= -{7 \over 180} < 0 &&\rightarrow\!\leftarrow
\end{alignedat}
$$

2. $g_2(x, 5 - x) < 0$, $\mu = 0$:
$$
\begin{alignedat}{3}
L(x, 5 - x, \lambda, 0) &= {1 \over x} + {2 \over 5 - x} &&\ \lambda \ge 0 \\
\text{KKT:} \quad L_x &= -{1 \over x^2} + \lambda &&= 0 \\
L_y &= -{2 \over (5 - x)^2} + \lambda &&= 0 \\
&\quad\ 5x^2 - 20x + 15 &&< 0 \\
\lambda &= {1 \over x^2} = {2 \over (5 - x)^2} \\
2x^2 &= (5 - x)^2 = x^2 -{} && 10x + 25 \\
0 &= x^2 + 10x - 25 \\
x &= -5 + 5\sqrt{2} \\
y &= 10 - 5\sqrt{2} \\
\lambda &= {1 \over 75 - 50 \sqrt{2}} &&> 0 \\
5x^2 - 20x + 15 &= 490 - 350 \sqrt{2} &&< 0
\end{alignedat}
$$

Po zgornji posledici je $(x^\ast, y^\ast) = (5(\sqrt{2} - 1), 5(2 - \sqrt{2}))$ globalni minimum. Ostalih možnosti nam ni potrebno preverjati.

**_Primer._** Uporabimo Karush-Kuhn-Tuckerjeve pogoje za linearni program $\Pi$.
$$
\begin{aligned}
\max \ c^\top x \\[1ex]
\text{p.p.} \quad A x &\le b \\
x &\ge 0
\end{aligned}
$$
Zgornji linearni program zapišimo kot problem vezanega ekstrema z neenačbami.
$$
\begin{aligned}
\min \ -c^\top x \\[1ex]
\text{p.p.} \quad x &\in \mathbb{R}^n \\
a_i^\top x - b_i &\le 0 & (1 &\le i \le m) \\
-x_j &\le 0 & (1 &\le j \le n)
\end{aligned}
$$
Ciljna funkcija in vezi so konveksne, torej imamo konveksni problem. Zapišimo Lagrangeevo funkcijo in Karush-Kuhn-Tuckerjeve pogoje.
$$
\begin{alignedat}{3}
L(x, \lambda, \mu) &= -c^\top x + \lambda^\top (A x -{} &{} b) &- \mu^\top x \\
&= -\sum_{j=1}^n c_j x_j \ + \ \sum_{i=1}^m &{} \lambda_i &\Big(\sum_{j=1}^n a_{ij} x_j &{} - \ b_i \Big) &- \sum_{j=1}^n \mu_j x_j \\
\text{KKT:} \quad L_j(x, \lambda, \mu) &= -c_j + \sum_{i=1}^n \lambda_i a_{ij} -{} &{} \mu_j &= 0 && (1 \le j \le n) \\
\nabla L(x, \lambda, \mu) &= -c + A^\top \lambda - \mu &&= 0 \\
\lambda^\top (A x - b) &= 0 & \lambda &\ge 0 & Ax - b &\le 0 \\
-\mu^\top x &= 0 & \mu &\ge 0 & -x &\le 0
\end{alignedat}
$$
Ker velja $\mu = A^\top \lambda - c \ge 0$, vektor $\lambda$ ustreza ravno spremenljivkam dualnega linearnega programa $\Pi'$. Iz izreka o dualnem dopolnjevanju sledi, da je $x^\ast$ optimalna rešitev linearnega programa $\Pi$ in $\lambda^\ast$ optimalna rešitev njegovega duala $\Pi'$ natanko tedaj, ko $(x^\ast, \lambda^\ast, \mu^\ast := A^\top \lambda^\ast - c)$ ustreza Karush-Kuhn-Tuckerjevim pogojem.

---

### Fisherjev model trga

Imamo $m$ kupcev in $n$ dobrin. Naj bo $a_i > 0$ kapital, ki ga ima na voljo $i$-ti kupec, $b_j > 0$ količina $j$-te dobrine na trgu, ter $u_{ij} \ge 0$ zadovoljstvo $i$-tega kupca z enoto $j$-te dobrine ($1 \le i \le m$, $1 \le j \le n$). Imamo torej $a \in \mathbb{R}^m$, $b \in \mathbb{R}^m$ in $U = (u_{ij})_{i,j=1}^{m,n} \in \mathbb{R}^{m \times n}$. Predpostavimo še, da si vsak kupec želi vsaj ene dobrine (torej $\forall i \ \exists j: \ u_{ij} > 0$) ter da si vsake dobrine želita vsaj dva kupca (torej $\forall j \ \exists i_1, i_2: \ (i_1 \ne i_2 \land u_{i_1 j} > 0 \land u_{i_2 j} > 0)$).

Iščemo cene $p_j \ge 0$ $j$-te dobrine in količine $x_{ij} \ge 0$ $j$-te dobrine, ki jo kupi $i$-ti kupec ($1 \le i \le m$, $1 \le j \le n$) - torej $p \in \mathbb{R}^n$ in $X = (x_{ij})_{i,j=1}^{m,n} \in \mathbb{R}^{m \times n}$, da velja:

* $\forall i: \ \sum_{j=1}^n x_{ij} p_j = a_i$ oziroma $Xp = a$ (vsak kupec porabi ves svoj kapital)
* $\forall j: \ \sum_{i=1}^n x_{ij} = b_j$ oziroma $X^\top \mathbf{1} = b$ (vsaka dobrina se proda v celoti)
* pri cenah $p$ je zadovoljstvo $i$-tega kupca $u_i(X) = \sum_{j=1}^n u_{ij} x_{ij}$ maksimalno

**_Definicija._** Cene $p$ so _ravnovesne_, če obstaja $X \in \mathbb{R}^{m \times n}$, da so izpolnjeni zgornji pogoji.

**_Primer._**
$$
a = \begin{bmatrix} 20 \\ 60 \\ 100 \end{bmatrix} \qquad
b = \begin{bmatrix} 2 \\ 4 \end{bmatrix} \qquad
U = \begin{bmatrix} 8 & 10 \\ 5 & 30 \\ 5 & 20 \end{bmatrix}
$$
Ali so cene $p = \begin{bmatrix} 18 \\ 36 \end{bmatrix}$ ravnovesne?
$$
\begin{aligned}
18 x_{11} + 36 x_{12} &= 20 & x_{12} &= {5 \over 9} - {1 \over 2} x_{11} \\
18 x_{21} + 36 x_{22} &= 60 & x_{22} &= {5 \over 3} - {1 \over 2} x_{21} \\
18 x_{31} + 36 x_{32} &= 100 & x_{32} &= {25 \over 9} - {1 \over 2} x_{31} \\
x_{11} + x_{21} + x_{31} &= 2 & x_{31} &= 2 - x_{11} - x_{21} \\
x_{12} + x_{22} + x_{32} &= 4 & {45 \over 9} - 1 &= 4 \\
0 \le x_{11} &\le {10 \over 9} & 0 &\le x_{21} \le 2 & 0 &\le x_{31} \le 2 \\
u_1(X) &= 8 x_{11} + 10 x_{12} & u_2(X) &= 5 x_{21} + 30 x_{22} & u_3(X) &= 5 x_{31} + 20 x_{32} \\
&= 3x_{11} + {50 \over 9} &&= -10 x_{21} + 50 &&= -5 x_{31} + {500 \over 9} \\
x_{11} &= {10 \over 9} & x_{21} &= 0 & x_{31} &= 0 \ne 2 - x_{11} - x_{12} \\
u_1(X) &= {80 \over 9} & u_2(X) &= 50 && \rightarrow\!\leftarrow
\end{aligned}
$$
Pogoji niso kompatibilni, zato cene niso ravnovesne.

**_Vaja._** Dokaži, da so cene $p = \begin{bmatrix} 10 \\ 40 \end{bmatrix}$ ravnovesne.

**_Trditev._** Če ravnovesne cene $p$ obstajajo, potem so pozitivne in $b^\top p = \mathbf{1}^\top a$ (tj., vse dobrine se prodajo za ves kapital na voljo).

_Dokaz._ Denimo, da za nek $j$ velja $p_j = 0$. Ker obstajata taka različna $i_1, i_2$, da velja $u_{i_1 j}, u_{i_2 j} > 0$, sta kupca $i_1$ in $i_2$ najbolj zadovoljna, če dobita vso dobrino $j$, protislovje. Nadalje velja $b^\top p = \mathbf{1}^\top Xp = \mathbf{1}^\top a$.

**_Definicija._** _Zadovoljstvo $i$-tega kupca z $j$-to dobrino na denarno enoto_ je $z_{ij} := {u_{ij} \over p_j}$ ($1 \le i \le m$, $1 \le j \le n$). Naj bo $z_i := \max\{z_{ij} \mid 1 \le j \le n\}$. _Optimalni sveženj $i$-tega kupca_ je množica $S_i := \{j \in \{1, 2, \dots, n\} \mid z_{ij} = z_i\}$.

**_Trditev._** Naj bosta $p > 0$ in $X \ge 0$ takšna, da velja $Xp = a$ in $X^\top \mathbf{1} = b$. Če vsak kupec kupuje samo iz svojega optimalnega svežnja (tj., $\forall i, j: \ (x_{ij} > 0 \Rightarrow j \in S_i)$), potem so cene $p$ ravnovesne.

**_Primer._**
$$
a = \begin{bmatrix} 20 \\ 60 \\ 100 \end{bmatrix} \qquad
b = \begin{bmatrix} 2 \\ 4 \end{bmatrix} \qquad
U = \begin{bmatrix} 8 & 10 \\ 5 & 30 \\ 5 & 20 \end{bmatrix}
$$
Pokažimo, da so cene $p = \begin{bmatrix} 10 \\ 40 \end{bmatrix}$ ravnovesne.

$$
\begin{aligned}
z_{11} &= {8 \over 10} & z_{12} &= {10 \over 40} & z_1 &= {4 \over 5} & S_1 &= \{1\} \\
z_{21} &= {5 \over 10} & z_{22} &= {30 \over 40} & z_2 &= {3 \over 4} & S_2 &= \{2\} \\
z_{31} &= {5 \over 10} & z_{32} &= {20 \over 40} & z_3 &= {1 \over 2} & S_3 &= \{1, 2\}
\end{aligned}
$$
$$
\begin{aligned}
x_{11} &= {20 \over 10} = 2 & x_{12} &= 0 \\
x_{21} &= 0 & x_{22} &= {60 \over 40} = {3 \over 2} \\
x_{31} &= 0 & x_{32} &= {100 \over 40} = {5 \over 2}
\end{aligned}
$$

_Dokaz._ Če vsak kupec kupuje samo iz svojega optimalnega svežnja, potem velja $\forall i, j: \left(x_{ij} > 0 \Rightarrow z_i = z_{ij} = {u_{ij} \over p_j}\right)$. Za vsak $i$ torej velja
$$
u_i(X) = \sum_{j=1}^n u_{ij} x_{ij} = \sum_{j=1}^n z_i p_j x_{ij} = z_i \sum_{j=1}^n p_j x_{ij} = z_i a_i.
$$
Naj bo $X' = (x'_{ij})_{i,j=1}^{m,n}$ neka druga dopustna izbira kupljenih količin. Ker velja $\forall i, j: z_{ij} = {u_{ij} \over p_j} \le z_i$, za vsak $i$ sledi
$$
u_i(X') = \sum_{j=1}^n u_{ij} x'_{ij} \le \sum_{j=1}^n z_i p_j x'_{ij} = z_i a_i = u_i(X).
$$
Vrednosti $u_i(X)$ so torej optimalne za vsak $i$.

Vprašanji:

* Ali ravnovesne cene obstajajo? **JA.**
* Kako jih poiščemo? S **Karush-Kuhn-Tuckerjevimi pogoji**.

#### Eisenberg-Galeov konveksni program (EGP)

Brez škode za splošnost lahko predpostavimo, da za vsak $j$ velja $b_j = 1$ (oziroma $b = \mathbf{1}$) - tj., celotna količina vsake dobrine je $1$ enota. Če temu ni tako, lahko $j$-ti stolpec matrike $U$ pomnožimo s staro vrednostjo $b_j$ (in podobno za dobljeno rešitev $X$).

Pri Fisherjevem modelu trga želimo maksimizirati zadovoljstvo **vseh** kupcev. Kako iz $n$ funkcij dobimo eno? Kako iz $n$ števil dobimo eno? Nekaj možnosti:

* ${x_1 + x_2 + \dots + x_n \over n}$ - aritmetična sredina
* ${a_1 x_1 + a_2 x_2 + \dots + a_n x_n \over a_1 + a_2 + \dots + a_n}$ - utežena aritmetična sredina ($\forall i: a_i > 0$)
* $\sqrt[n]{x_1 x_2 \cdots x_n}$ - geometrijska sredina ($\forall i: x_i > 0$)
* $\sqrt[a_1 + a_2 + \dots + a_n]{x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}}$ - utežena geometrijska sredina

Izkaže se, da je "prava" funkcija
$$
\left(\prod_{i=1}^m u_i(X)^{a_i}\right)^{1 \over \sum_{i=1}^m a_i}.
$$
Iskali bomo torej maksimum te funkcije. Za lažje delo bomo funkcijo logaritmirali; da jo obravnavamo kot ciljno funkcijo konveksnega problema, pa tudi negirali in iskali njen minimum.

**_Trditev._** Funkcija
$$
f(X) = -\sum_{i=1}^m a_i \log(u_i(X))
$$
je konveksna.

_Dokaz._ Pišemo lahko $f = \sum_{i=1}^m a_i \cdot ((-\log) \circ u_i)$. Funkcija $-\log$ je konveksna (saj $(-\log)''(x) = {1 \over x^2} > 0$), za vsak $i$ pa je funkcija $u_i$ afina in $a_i > 0$. Potem je za vsak $i$ funkcija $a_i \cdot ((-\log) \circ u_i)$ konveksna. Funkcija $f$ je torej vsota konveksnih funkcij in je tako konveksna.

Zapišimo torej **Eisenberg-Galeov konveksni program (EGP)**.
$$
\begin{alignedat}{2}
\min \ -\sum_{i=1}^m &\ a_i \log(u_i(X)) \\[1ex]
\text{p.p.} \quad X \in \Omega &= \{X \in \mathbb{R}^{m \times n} &&\mid \forall i \in \{1, 2, \dots, m\}: u_i(X) > 0\} \\
\sum_{i=1}^m x_{ij} &\le 1 && (1 \le j \le n) \\
x_{ij} &\ge 0 && (1 \le i \le m, 1 \le j \le n)
\end{alignedat}
$$

Opazimo:

* za vsak $i$ je $u_i$ linearna funkcija (torej afina in zvezna), tako da je $\Omega$ konveksna odprta množica
* ciljna funkcija je konveksna in odvedljiva
* vse vezi so afine (torej konveksne in odvedljive)

Karush-Kuhn-Tuckerjevi pogoji so torej **potrebni** in **zadostni** za optimalnost rešitve.

Spomnimo se: množica $A \subseteq \mathbb{R}^n$ je kompaktna, ko je zaprta in omejena. Zvezna funkcija na kompaktni množici doseže minimum in maksimum.

**_Izrek._** Eisenberg-Galeov konveksni program je dopusten in optimalen.

_Dokaz._ Pokažimo najprej, da je $\overline{x}_{ij} = {1 \over m}$ ($1 \le i \le m$, $1 \le j \le n$) dopustna rešitev. Res, velja $u_i(\overline{X}) > 0$ ($1 \le i \le m$), $\sum_{i=1}^m \overline{x}_{ij} = 1$ ($1 \le j \le n$) in $\overline{x}_{ij} \ge 0$ ($1 \le i \le m$, $1 \le j \le n$).

Naj bo
$$
D = \left\{X \in \Omega \mid \forall j \in \{1, 2, \dots, n\}: \left(\sum_{i=1}^m x_{ij} \le 1 \land \forall i \in \{1, 2, \dots, m\}: x_{ij} \ge 0\right)\right\}
$$
množica dopustnih rešitev. Za $\epsilon > 0$ definirajmo še množico
$$
D_\epsilon = \{X \in D \mid \forall i \in \{1, 2, \dots, m\}: u_i(X) \ge \epsilon\}.
$$
Množica $D_\epsilon$ je omejena (saj $\forall i, j: 0 \le x_{ij} \le 1$) in zaprta, torej je kompaktna. Funkcija $f$ je zvezna, torej doseže minimum na $D_\epsilon$.

Vrednost $\epsilon$ bomo izbrali tako, da bo $\overline{X} \in D_\epsilon$ in $\forall X \in D \setminus D_\epsilon: f(X) > f(\overline{X})$. To bo pomenilo, da funkcija $f$ doseže minimum na $D$.

Da bo $\overline{X} \in D_\epsilon$, mora veljati
$$
\forall i \in \{1, 2, \dots, m\}: \ \epsilon \le u_i(\overline{X}) = {1 \over m} \sum_{j=1}^n u_{ij}.
$$
Poleg tega bomo zahtevali še
$$
\forall h \in \{1, 2, \dots, m\}: \ \epsilon \le e^{-{1 \over a_h}\left(f(\overline{X}) + \sum_{\substack{i = 1 \\ i \ne h}}^m a_i \log \left(\sum_{j=1}^n u_{ij}\right)\right)}.
$$
Naj bo $X \in D \setminus D_\epsilon$. Potem za nek $h_0$ velja $u_{h_0}(X) < \epsilon$. Z logaritmiranjem tako dobimo
$$
\begin{aligned}
\log(u_{h_0}(X)) &< -{1 \over a_{h_0}}\left(f(\overline{X}) + \sum_{\substack{i = 1 \\ i \ne h_0}}^m a_i \log \left(\sum_{j=1}^n u_{ij}\right)\right) \\
-a_{h_0} \log(u_{h_0}(X)) &> f(\overline{X}) + \sum_{\substack{i = 1 \\ i \ne h_0}}^m a_i \log\left(\sum_{j=1}^n u_{ij}\right)
\end{aligned}
$$
Ker za vsak $i$ velja $u_i(X) = \sum_{j=1}^n u_{ij} x_{ij} \le \sum_{j=1} u_{ij}$, velja tudi
$$
-a_i \log(u_i(X)) \ge -a_i \log \left(\sum_{j=1}^n u_{ij}\right).
$$
Če k prejšnji neenakosti prištejemo zgornjo za vsak $i \ne h_0$, dobimo
$$
f(X) = -\sum_{i=1}^m a_i \log(u_i(X)) > f(\overline{X})
$$
Ker so vse zgornje meje za $\epsilon$ pozitivne, lahko torej izberemo tak $\epsilon$, da veljajo zgornji pogoji. Funkcija $f$ tako doseže minimum na $D$, zato je konveksni problem optimalen.

Zapišimo Karush-Kuhn-Tuckerjeve pogoje za Eisenberg-Galeov konveksni program:
$$
\begin{alignedat}{3}
L(X, p, \Lambda) &= \quad -\sum_{i=1}^m a_i & \log(u_i(X)) &+ \sum_{j=1}^n p_j \Big(\sum_{i=1}^m & x_{ij} &- 1\Big) - {} && \sum_{i=1}^m \sum_{j=1}^n \lambda_{ij} x_{ij} \\
L_{ij} := {\partial L \over \partial x_{ij}}(X, p, \Lambda) &= -a_i {u_{ij} \over u_i(X)} &{} + p_j - \lambda_{ij} &= 0 &&&& (1 \le i \le m, 1 \le j \le n) \\
p_j \left(\sum_{i=1}^m x_{ij} - 1\right) &= 0 & \sum_{i=1}^m x_{ij} &\le 1 & p_j &\ge 0 && (1 \le j \le n) \\
\lambda_{ij} x_{ij} &= 0 & x_{ij} &\ge 0 & \lambda_{ij} &\ge 0 && (1 \le i \le m, 1 \le j \le n)
\end{alignedat}
$$

**_Izrek._** Naj bosta $X \in \mathbb{R}^{m \times n}$ in $p \in \mathbb{R} ^m$. Sledeči trditvi sta ekvivalentni.

1. $X$ je optimalna razdelitev za Fisherjev model trga s cenami $p$, kjer vsak kupec kupuje le dobrine iz svojega optimalnega svežnja.
2. $X \in \Omega$ in $(X, p, \Lambda)$ zadošča Karush-Kuhn-Tuckerjevim pogojem, kjer $\Lambda = (\lambda_{ij})_{i,j=1}^{m,n} \in \mathbb{R}^{m \times n}$ ustreza
$$
\lambda_{ij} = \begin{cases}
0 & \text{če $x_{ij} > 0$, in} \\
p_j - a_i {u_{ij} \over u_i(X)} & \text{če $x_{ij} = 0$}
\end{cases}
$$
(tj., $p$ so Lagrangeevi množitelji za vezi $\sum_{i=1}^m x_{ij} \le 1$ ($1 \le j \le n$)).

_Dokaz._

* (1. $\Rightarrow$ 2.) Pogoji $\sum_{i=1}^m x_{ij} = 1$, $p_j \left(\sum_{i=1}^m x_{ij} - 1\right) = 0$, $p_j \ge 0$ ($1 \le j \le n$) ter $\lambda_{ij} x_{ij} = 0$, $x_{ij} \ge 0$ ($1 \le i \le m$, $1 \le j \le n$) so očitno izpolnjeni. Za vsaka $i, j$ ločimo dva primera, pri čemer bomo upoštevali $u_i(X) = z_i a_i$.
- Če je $x_{ij} > 0$, potem je $\lambda_{ij} = 0$. Ker je $j \in S_i$, velja $u_{ij} = p_j z_i$, torej
$$
L_{ij} = -a_i {u_{ij} \over u_i(X)} + p_j - \lambda_{ij} = -a_i {p_j z_i \over z_i a_i} + p_j = 0.
$$
- Če je $x_{ij} = 0$, potem velja
$$
L_{ij} = -a_i {u_{ij} \over u_i(X)} + p_j - \lambda_{ij} = 0.
$$
Ker velja $u_{ij} \le p_j z_i$, velja tudi
$$
\lambda_{ij} \ge p_j - a_i {p_j z_i \over z_i a_i} = 0.
$$

Za $(X, p, \Lambda)$ torej veljajo Karush-Kuhn-Tuckerjevi pogoji.

* (2. $\Rightarrow$ 1.) Ker za vsako dobrino obstaja kupec, ki si je želi, za vsak $j$ obstaja $i$, da velja $p_j \ge a_i {u_{ij} \over u_i(X)} > 0$ in posledično $\sum_{i=1}^m x_{ij} = 1$ - tj., vsaka dobrina se proda v celoti.

Sledi tudi $z_{ij} = {u_{ij} \over p_j} \le {u_i(X) \over a_i}$. Če velja $x_{ij} > 0$, potem velja $\lambda_{ij} = 0$ in velja enakost v prejšnji neenakosti - tj., vsak kupec kupuje le dobrine iz svojega optimalnega svežnja.

Nazadnje za vsak $i$ izpeljemo še
$$
\begin{aligned}
\sum_{j=1}^n a_i u_{ij} x_{ij} &= \sum_{j=1}^n p_j u_i(X) x_{ij} \\
a_i u_i(X) &= u_i(X) \sum_{j=1}^n p_j x_{ij}
\end{aligned}
$$
Velja torej $a_i = \sum_{j=1}^n p_j x_{ij}$ - tj., vsak kupec je porabil ves svoj kapital.

Zapišimo še poenostavljene Karush-Kuhn-Tuckerjeve pogoje za Eisenberg-Galeov konveksni program:
$$
\begin{aligned}
a_i {u_{ij} \over u_i(X)} + \lambda_{ij} &= p_j & x_{ij} &\ge 0 && (1 \le i \le m, 1 \le j \le n) \\
\sum_{i=1}^m x_{ij} &= 1 & p_j &> 0 && (1 \le j \le n) \\
\lambda_{ij} x_{ij} &= 0 & \lambda_{ij} &\ge 0 && (1 \le i \le m, 1 \le j \le n)
\end{aligned}
$$

**_Primer._**
$$
a = \begin{bmatrix} 2 \\ 1 \end{bmatrix} \qquad
U = \begin{bmatrix} 2 & 2 \\ 1 & 2 \end{bmatrix}
$$
S Karush-Kuhn-Tuckerjevimi pogoji dobimo sledečo rešitev:
$$
p = \begin{bmatrix} {3 \over 2} \\ {3 \over 2} \end{bmatrix} \qquad
X = \begin{bmatrix} 1 & {1 \over 3} \\ 0 & {2 \over 3} \end{bmatrix}
$$
Trdimo, da so tudi $p' = \begin{bmatrix} 1 \\ 2 \end{bmatrix}$ ravnovesne cene.
$$
\begin{alignedat}{4}
x'_{11} + 2 x'_{12} &= 2 &&& x'_{12} &= 1 \,-\, {1 \over 2} & x'_{11} \\
x'_{21} + 2 x'_{22} &= 1 &&& x'_{22} &= {1 \over 2} - {1 \over 2} & x'_{21} &= {1 \over 2} x'_{11} \\
x'_{11} + x'_{21} &= 1 &&& x'_{21} &= 1 - x'_{11} \\
x'_{12} + x'_{22} &= 1 &&& 0 &\le x'_{11} \le 1 \\
u_1(X') &= 2 x'_{11} &{} + 2 x'_{12} &= x'_{11} + 2 &\qquad u_2(X') &= x'_{21} + 2 & x'_{22} &= 1 \\
x'_{11} &= 1 & x'_{12} &= {1 \over 2} & x'_{21} &= 0 & x'_{22} &= {1 \over 2} \\
u_1(X') &= 3 &&& u_2(X') &= 1 \\
z'_1 &= 2 & S'_1 &= \{1\} & z'_2 &= 1 & S'_2 &= \{1, 2\}
\end{alignedat}
$$
Ravnovesne cene torej niso enolične! V tem primeru prvi kupec kupuje tudi izven svojega optimalnega svežnja. Izkaže se, da so pri teh podatkih vse možne ravnovesne cene
$$
\begin{gathered}
\tilde{p} = \begin{bmatrix} \lambda \\ 3 - \lambda \end{bmatrix} \qquad
\tilde{X} = \begin{bmatrix} 1 & {2 - \lambda \over 3 - \lambda} \\ 0 & {1 \over 3 - \lambda} \end{bmatrix} \qquad
\left(\lambda \in \left[1, {3 \over 2}\right]\right) \\
u_1(\tilde{X}) = 4 - {2 \over 3 - \lambda} \qquad
u_2(\tilde{X}) = {2 \over 3 - \lambda}
\end{gathered}
$$

---

## Lokalna optimizacija

Lokalna optimizacija je pristop, ki ga običajno uporabimo pri reševanju "težkih" problemov, npr. problema potujočega trgovca.

**_Primer._**

graph G {
    rankdir=LR
    nodesep=0.5
    ranksep=1
    splines=false
    node [label=""]

    u -- x [label=5]
    u -- y [label=5]
    x -- v [xlabel=5]
    y -- w [label=5]
    v -- w [label=5, constraint=false]
    u -- v [xlabel="  1"]
    u -- w [xlabel="1   "]
    x -- y [xlabel="  10", constraint=false]
    x -- w [label=10, constraint=false]
    y -- v [label=10, constraint=false]
}

Za graf z $n$ vozlišči imamo $(n-1)!$ dopustnih rešitev.

| $n$ | $(n-1)!$ |
| --- | ---------------------------- |
| 5 | 24 |
| 10 | 3.6 &#8729; 10⁵ |
| 20 | 1.2 &#8729; 10¹⁷ |
| 50 | 6.1 &#8729; 10⁶² |
| 100 | 9.3 &#8729; 10¹⁵⁵ |

Ideja: iščemo "lokalne optimume" in upamo, da so tudi globalni optimumi.

**_Definicija._** Naj bo $X$ množica. Relacija $S \subseteq X \times X$ je _relacija sosednosti_, če je refleksivna ($\forall x \in X: \ x \, S \, x$) in simetrična ($\forall x, y \in S: (x \, S \, y \Rightarrow y \, S \, x)$).

Za element $x \in X$ je množica $S[x] := \{y \in X \mid x \, S \, y\}$ _soseščina_ elementa $x$. Element $x \in X$ je _$S$-lokalni minimum_ (_$S$-lokalni maksimum_) funkcije $f: X \to \mathbb{R}$, če velja $\forall y \in S[x]: \ f(y) \ge f(x)$ ($\forall y \in S[x]: \ f(y) \le f(x)$).

**Metoda za iskanje globalnih minimumov:** izberemo naključen $x_0 \in X$, in nastavimo $i := 0$. Preverimo, če je $x_i$ $S$-lokalni minimum - če je, postopek končamo, sicer pa obstaja $x_{i+1} \in S[x_i]$, da $f(x_{i+1}) < f(x_i)$. Postavimo $i := i+1$ in ponavljamo. Če se postopek konča, smo našli $S$-lokalni minimum.

Postopek večkrat ponovimo in izberemo najboljšega izmed dobljenih $S$-lokalnih minimumov.

**_Definicija._** Relacija $S$ je _natančna_ za $f$, če je $S$-lokalni minimum tudi globalni minimum.

**_Primeri._**

1. $X = \mathbb{R}^n$, izberemo $\epsilon > 0$. Naj bo $x \, S \, y \Leftrightarrow \Vert x - y \Vert < \epsilon$. Relacija $S$ ni natančna za splošne $f$, je pa natančna za konveksne $f$.
2. Množica dopustnih rešitev $D$ linearnega programa $\Pi$ je politop (angl. _polytope_). Globalni minimum in maksimum sta dosežena na ekstremni točki, torej na oglišču. Naj bo torej $X$ množica oglišč $D$ in definirajmo relacijo $S$ tako, da velja $x \, S \, y$ natanko tedaj, ko sta $x$ in $y$ na istem robu. Zgoraj opisana metoda za $S$ je ravno simpleksna metoda. Relacija $S$ je natančna za ciljno funkcijo $\Pi$.
3. $G = (V, E)$ povezan graf, $c : E \to \mathbb{R}$ uteži povezav. Naj bo $X$ množica (množic povezav $E' \subseteq E$) vpetih dreves $T = (V, E')$ v $G$ in $f(E') = \sum_{e \in E'} c(e)$ funkcija cene vpetega drevesa. To je **problem najcenejšega vpetega drevesa** - za reševanje lahko uporabimo Primov ali Kruskalov algoritem. Definiramo relacijo $S$, tako da velja $E'_1 \, S \, E'_2 \Leftrightarrow |E'_1 \oplus E'_2| \le 2$. Relacija $S$ je natančna za $f$ (brez dokaza).
4. **Problem potujočega trgovca:** $G = (V, E)$ povezan graf, $c : E \to \mathbb{R}$ uteži povezav. Naj bo $X$ množica Hamiltonovih ciklov v $G$ in $f(C) = \sum_{e \in C} c(e)$ funkcija cene Hamiltonovega cikla. Relacijo $S$ definiramo tako, da sta dva Hamiltonova cikla sosedna, če lahko "prevežemo" dve povezavi na ciklu.

   graph G {
      rankdir=LR
      nodesep=0.5
      ranksep=0.7
      node [label=""]
      
      a1 -- b1
      a1 -- c1
      b1 -- d1 [color=red]
      c1 -- e1 [color=red]
      d1 -- f1
      e1 -- f1
      
      f1 -- S -- a2 [style=invis]
      
      a2 -- b2
      a2 -- c2
      b2 -- d2 [style=invis]
      b2 -- e2
      c2 -- d2
      c2 -- e2 [style=invis]
      d2 -- f2
      e2 -- f2
      
      S [label=S,color=none,fontsize="25pt"]
   }

Relacija $S$ **ni** natančna. Naj bo $G = K_n = (V, {V \choose 2})$, $u, v, w, x, y \in V$ in $C$ Hamiltonov cikel z $uv, uw, xy \not\in C$, $vw, ux, uy \in C$ ter
$$
\begin{aligned}
\forall e \in C: \ c(e) &= 5 \\
c(uv) = c(uw) &= 1 \\
\forall e \not\in C \cup \{uv, uw\}: \ c(e) &= 10
\end{aligned}
$$
Potem velja:
$$
\begin{aligned}
f(C) &= 5n \\
\forall C' \in S[C]: f(C') &= 5(n-2) + 2 \cdot 10 \lor f(C') = 5(n-2) + 10 + 1 \\
\forall C' \in S[C]: f(C') &> f(C) \\
f(C \oplus \{ux, uy, vw, uv, uw, xy\}) &= 5(n-3) + 10 + 2 \cdot 1 = 5n - 3 < f(C)
\end{aligned}
$$
$C$ je torej $S$-lokalni minimum, ni pa tudi globalni minimum.

   graph G {
      rankdir=LR
      nodesep=0.5
      ranksep=1
      splines=false
      
      u -- x [label=5, color=red, fontcolor=red]
      u -- y [label=5, color=red, fontcolor=red]
      x -- v [xlabel=5, color=red, fontcolor=red]
      y -- w [label=5, color=red, fontcolor=red]
      v -- w [label=5, color=red, fontcolor=red, constraint=false]
      u -- v [xlabel="  1"]
      u -- w [xlabel="1   "]
      x -- y [xlabel="  10", constraint=false]
      x -- w [label=10, constraint=false]
      y -- v [label=10, constraint=false]
   }

   graph G {
      rankdir=LR
      nodesep=0.5
      ranksep=1
      splines=false
      
      u -- x [label=5, color=red, fontcolor=red]
      u -- y [label=5, color=red, fontcolor=red]
      x -- v [xlabel=5]
      y -- w [label=5]
      v -- w [label=5, color=red, fontcolor=red, constraint=false]
      u -- v [xlabel="  1"]
      u -- w [xlabel="1   "]
      x -- y [xlabel="  10", constraint=false]
      x -- w [label=10, color=red, fontcolor=red, constraint=false]
      y -- v [label=10, color=red, fontcolor=red, constraint=false]
   }

   graph G {
      rankdir=LR
      nodesep=0.5
      ranksep=1
      splines=false
      
      u -- x [label=5]
      u -- y [label=5, color=red, fontcolor=red]
      x -- v [xlabel=5, color=red, fontcolor=red]
      y -- w [label=5, color=red, fontcolor=red]
      v -- w [label=5, constraint=false]
      u -- v [xlabel="  1", color=red, fontcolor=red]
      u -- w [xlabel="1   "]
      x -- y [xlabel="  10", constraint=false]
      x -- w [label=10, color=red, fontcolor=red, constraint=false]
      y -- v [label=10, constraint=false]
   }

   graph G {
      rankdir=LR
      nodesep=0.5
      ranksep=1
      splines=false
      
      u -- x [label=5]
      u -- y [label=5]
      x -- v [xlabel=5, color=red, fontcolor=red]
      y -- w [label=5, color=red, fontcolor=red]
      v -- w [label=5, constraint=false]
      u -- v [xlabel="  1", color=red, fontcolor=red]
      u -- w [xlabel="1   ", color=red, fontcolor=red]
      x -- y [xlabel="  10", color=red, fontcolor=red, constraint=false]
      x -- w [label=10, constraint=false]
      y -- v [label=10, constraint=false]
   }