Predavanje 18.5.
Primer (nadaljevanje). Iščemo optimalno rešitev konveksnega problema: $$ \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} $$
$g_1(x, y) = x + y - 5 = 0$: $y = 5 - x$
- $g_2(x, 5 - x) = 0$: prišli smo do protislovja
- $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_{x_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.