Optimizacijske metode

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 {5 \over 3} & 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$. Prepričajmo se, da je $(-\log) \circ u_i)$ konveksna funkcija. $$ ((-\log) \circ u_i)((1 - \lambda) X + \lambda Y) = -\log((1 - \lambda) u_i(X) + \lambda u_i(Y)) \le (1 - \lambda) \cdot ((-\log) \circ u_i)(X) + \lambda \cdot ((-\log) \circ u_i)(Y) $$ 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, n\}: 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}}^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.