« nazaj
Optimizacijske metode - vaje 22.5.2020
Karush-Kuhn-Tuckerjevi pogoji
Naloga 1
Poišči minimum in maksimum funkcije $f(x, y, z) = x+y+z$ v $\mathbb{R}^3$ pri pogoju $x^2+y^2 \le z \le 1$.
Minimum
\[\begin{aligned}
f &= x + y + z \\
g_1 &= x^2 + y^2 - z \\
g_2 &= z - 1 \\[1ex]
L &= x + y + z + \lambda_1 (x^2 + y^2 - z) + \lambda_2 (z - 1) \\
L_x &= 1 + 2 \lambda_1 x = 0 \\
L_y &= 1 + 2 \lambda_1 y = 0 \\
L_z &= 1 - \lambda_1 + \lambda_2 = 0
\end{aligned}\]
-
\[\begin{aligned}
g_2 &= 0 \\
z &= 1 \\[1ex]
L_x &= 1 + 2 \lambda_1 x = 0 \\
L_y &= 1 + 2 \lambda_1 y = 0 \\
L_z &= 1 - \lambda_1 + \lambda_2 = 0 \\[1ex]
\lambda_1 &> 0 \\
x = y &= -1/(2 \lambda_1) \\
g_1 &= 0 \\
y^2 &= 1 - x^2 \\
y &= -\sqrt{1 - x^2} \\
x = y &= - \sqrt{2}/2 \\
\lambda_1 &= \sqrt{2}/2 \\
L_x &= 1 - 2 \sqrt{2}/2 \cdot \sqrt{2}/2 = 0 \\
L_y &= 1 - 2 \sqrt{2}/2 \cdot \sqrt{2}/2 = 0 \\
L_z &= 1 - \sqrt{2}/2 + \lambda_2 = 0 \\
\lambda_2 &= \sqrt{2}/2 - 1 < 0
\end{aligned}\]
-
\[\begin{aligned}
\lambda_2 &= 0 \\
g_2 &< 0 \\
z &< 1 \\[1ex]
L_x &= 1 + 2 \lambda_1 x = 0 \\
L_y &= 1 + 2 \lambda_1 y = 0 \\
L_z &= 1 - \lambda_1 = 0 \\[1ex]
\lambda_1 &= 1 \\
x = y &= -1/2 \\
g_1 &= 0 \\
z &= 1/2 \\
g_2 &= 1/2 - 1 = -1/2 < 0
\end{aligned}\]
Minimum: $(x, y, z) = (-1/2, -1/2, 1/2)$
Maksimum
\[\begin{aligned}
f &= -x - y - z \\
g_1 &= x^2 + y^2 - z \\
g_2 &= z - 1 \\[1ex]
L &= -x - y - z + \lambda_1 (x^2 + y^2 - z) + \lambda_2 (z - 1) \\
L_x &= -1 + 2 \lambda_1 x = 0 \\
L_y &= -1 + 2 \lambda_1 y = 0 \\
L_z &= -1 - \lambda_1 + \lambda_2 = 0 \\[1ex]
\lambda_1 &> 0 \\
x = y &= 1/(2 \lambda_1) > 0 \\
g_1 &= 0 \\
z &= x^2 + y^2
\end{aligned}\]
-
\[\begin{aligned}
g_2 &= 0 \\
z &= 1 \\
\lambda_1 = x = y &= \sqrt{2}/2 \\[1ex]
L_x &= -1 + 2 \sqrt{2}/2 \cdot \sqrt{2}/2 = 0 \\
L_y &= -1 + 2 \sqrt{2}/2 \cdot \sqrt{2}/2 = 0 \\
L_z &= -1 - \sqrt{2}/2 + \lambda_2 = 0 \\[1ex]
\lambda_2 &= 1 + \sqrt{2}/2 > 0
\end{aligned}\]
Maksimum: $(x, y, z) = (\sqrt{2}/2, \sqrt{2}/2, 1)$
Fisherjev model trga
\[\begin{aligned}
a_i &> 0 \quad \text{kapital kupca $i = 1, \dots, m$} \\
u_{ij} &\ge 0 \quad \text{zadovoljstvo kupca $i = 1, \dots, m$ z dobrino $j = 1, \dots, n$} \\
p_j &> 0 \quad \text{cena dobrine $j = 1, \dots, n$} \\
x_{ij} &\ge 0 \quad \text{količina dobrine $j = 1, \dots, n$, ki jo kupi kupec $i = 1, \dots, m$}
\end{aligned}\]
Eisenberg-Galeov konveksni program:
\[\begin{aligned}
\Omega &= \left\{x \in \mathbb{R}^{mn} \mid \forall i = 1, \dots, m : \sum_{j=1}^n u_{ij} x_{ij} > 0\right\} \\[2ex]
-\min &\ -\sum_{i=1}^m a_i \log \left(\sum_{j=1}^n u_{ij} x_{ij}\right) \\[1ex]
\sum_{i=1}^m x_{ij} &\le 1 \quad \text{za } j = 1, \dots, n \\
x_{ij} &\ge 0 \quad \text{za } i = 1, \dots, m, \ j = 1, \dots, n
\end{aligned}\]
Zapišimo Lagrangeevo funkcijo:
\[\begin{aligned}
f(x) &= -\sum_{i=1}^m a_i \log \left(\sum_{j=1}^n u_{ij} x_{ij}\right) \\
g_j(x) &= \sum_{i=1}^m x_{ij} - 1 \\
h_{ij}(x) &= -x_{ij} \\[1ex]
L(x) &= f(x) + \sum_{j=1}^n p_j g_j(x) + \sum_{i=1}^m \sum_{j=1}^n \mu_{ij} h_{ij}(x)
\end{aligned}\]
Naloga 2
Trgovec z začimbami na bazarju ima zalogo
$50$kg cimeta in $2$kg žafrana. Njegovi glavni kupci so Arabci, ki mu tedensko prinesejo $550.000$ dinarjev prometa, in Berberi, ki mu tedensko prinesejo $250.000$ dinarjev prometa. Zadovoljstvo Arabca ob nakupu kilograma cimeta je $5$, ob nakupu kilograma žafrana pa $360$. Zadovoljstvo Berbera ob nakupu kilograma cimeta je $4$, ob nakupu kilograma žafrana pa $440$. Kako naj trgovec postavi izklicne cene, da bodo ravnovesne in da bo zadovoljstvo kupcev čim večje?
\[\begin{aligned}
a_A &= 550 \\
a_B &= 250 \\
u_{Ac} &= 250 \\
u_{Až} &= 720 \\
u_{Bc} &= 200 \\
u_{Bž} &= 880 \\[1ex]
L &= -550 \log(250 x_{Ac} + 720 x_{Až}) - 250 \log(200 x_{Bc} + 880 x_{Bž}) + \\
&\ + p_c (x_{Ac} + x_{Bc} - 1) + p_ž (x_{Až} + x_{Bž} - 1) \\
&\ - \mu_{Ac} x_{Ac} - \mu_{Až} x_{Až} - \mu_{Bc} x_{Bc} - \mu_{Bž} x_{Bž} \\[1ex]
L_{Ac} &= {-550 \cdot 250 \over 250 x_{Ac} + 720 x_{Až}} + p_c - \mu_{Ac} = 0 \\
L_{Až} &= {-550 \cdot 720 \over 250 x_{Ac} + 720 x_{Až}} + p_ž - \mu_{Až} = 0 \\
L_{Bc} &= {-250 \cdot 200 \over 200 x_{Bc} + 880 x_{Bž}} + p_c - \mu_{Bc} = 0 \\
L_{Bž} &= {-250 \cdot 880 \over 200 x_{Bc} + 880 x_{Bž}} + p_ž - \mu_{Bž} = 0 \\[1ex]
g_c = g_ž &= 0 \\
x_{Bc} &= 1 - x_{Ac} \\
x_{Bž} &= 1 - x_{Až} \\[1ex]
L_{Ac} &= {-550 \cdot 250 \over 250 x_{Ac} + 720 x_{Až}} + p_c - \mu_{Ac} = 0 \\
L_{Až} &= {-550 \cdot 720 \over 250 x_{Ac} + 720 x_{Až}} + p_ž - \mu_{Až} = 0 \\
L_{Bc} &= {-250 \cdot 200 \over 200 (1 - x_{Ac}) + 880 (1 - x_{Až})} + p_c - \mu_{Bc} = 0 \\
L_{Bž} &= {-250 \cdot 880 \over 200 (1 - x_{Ac}) + 880 (1 - x_{Až})} + p_ž - \mu_{Bž} = 0 \\[1ex]
\end{aligned}\]
-
\[\begin{aligned}
h_{Bc} &= 0 = x_{Bc} \\
x_{Ac} &= 1 \\
h_{Ac} &< 0 \\
\mu_{Ac} &= 0 \\[1ex]
L_{Ac} &= {-550 \cdot 250 \over 250 + 720 x_{Až}} + p_c = 0 \\
L_{Až} &= {-550 \cdot 720 \over 250 + 720 x_{Až}} + p_ž - \mu_{Až} = 0 \\
L_{Bc} &= {-250 \cdot 200 \over 880 (1 - x_{Až})} + p_c - \mu_{Bc} = 0 \\
L_{Bž} &= {-250 \over (1 - x_{Až})} + p_ž - \mu_{Bž} = 0 \\[1ex]
\end{aligned}\]
-
\[\begin{aligned}
h_{Až} &= 0 = x_{Až} \\
x_{Bž} &= 1 \\
h_{Bž} &< 0 \\
\mu_{Bž} &= 0 \\[1ex]
L_{Ac} &= -550 + p_c = 0 \\
L_{Až} &= {-550 \cdot 720 \over 250} + p_ž - \mu_{Až} = 0 \\
L_{Bc} &= {-250 \cdot 200 \over 880} + p_c - \mu_{Bc} = 0 \\
L_{Bž} &= -250 + p_ž = 0 \\[1ex]
p_c &= 550 \\
p_ž &= 250 \\
\mu_{Až} &= 250 - {550 \cdot 720 \over 250} < 0
\end{aligned}\]
-
\[\begin{aligned}
\mu_{Až} &= 0 \\[1ex]
L_{Ac} &= {-550 \cdot 250 \over 250 + 720 x_{Až}} + p_c = 0 \\
L_{Až} &= {-550 \cdot 720 \over 250 + 720 x_{Až}} + p_ž = 0 \\
L_{Bc} &= {-250 \cdot 200 \over 880 (1 - x_{Až})} + p_c - \mu_{Bc} = 0 \\
L_{Bž} &= {-250 \over (1 - x_{Až})} + p_ž - \mu_{Bž} = 0 \\[1ex]
x_{Až} &< 1 \\
x_{Bž} &> 0 \\
h_{Bž} &< 0 \\
\mu_{Bž} &= 0 \\[1ex]
p_c &= {550 \cdot 250 \over 250 + 720 x_{Až}} \\
p_ž &= {550 \cdot 720 \over 250 + 720 x_{Až}} \\
{550 \cdot 720 \over 250 + 720 x_{Až}} &= {250 \over (1 - x_{Až})} \\
250 (250 + 720 x_{Až}) &= 550 \cdot 720 (1 - x_{Až}) \\
800 \cdot 720 x_{Až} &= 550 \cdot 720 - 250 \cdot 250 \\
x_{Až} &= 0.58 \\
x_{Bž} &= 0.42 \\
p_c &= 206.19 \\
p_ž & = 593.81 \\
\mu_{Bc} &= {-250 \cdot 200 \over 880 (1 - x_{Až})} + p_c = 71.22 > 0
\end{aligned}\]
Naloga 3
Poišči optimalno rešitev problema vezanih ekstremov z neenačbami
\[\begin{aligned}
\min &\quad x^2 + y^2 + z^2 + 2xz - 3x - z + 2 \\[1ex]
&\quad x - y \le 1 \\
&\quad y - z \le 3 \ .
\end{aligned}\]
\[\begin{aligned}
H_f &= \begin{pmatrix}
2 & 0 & 2 \\
0 & 2 & 0 \\
2 & 0 & 2
\end{pmatrix} \ge 0 \\
\det (2) &= 2 > 0 \\
\det \begin{pmatrix}
2 & 0 \\
0 & 2 \\
\end{pmatrix} &= 4 > 0 \\
\det H_f &= 0
\end{aligned}\]
\[\begin{aligned}
H_g &= \begin{pmatrix}
2 & 2 & 0 \\
2 & 2 & 0 \\
0 & 0 & 2
\end{pmatrix} \ge 0 \\
\det (2) &= 2 > 0 \\
\det \begin{pmatrix}
2 & 2 \\
2 & 2 \\
\end{pmatrix} &= 0 \\
\det \begin{pmatrix}
2 & 0 \\
0 & 2 \\
\end{pmatrix} &= 4 > 0 \\
\end{aligned}\]
Druga vrstica je linearno odvisna od prejšnjih - pri nadaljnjih korakih smo izpustili drugo vrstico in stolpec!
\[\begin{aligned}
H_h &= \begin{pmatrix}
2 & 2 & 0 \\
2 & 2 & 1 \\
0 & 1 & 2
\end{pmatrix} \not\ge 0 \\
\det (2) &= 2 > 0 \\
\det \begin{pmatrix}
2 & 2 \\
2 & 2 \\
\end{pmatrix} &= 0 \\
\det \begin{pmatrix}
2 & 0 \\
0 & 2 \\
\end{pmatrix} &= 4 > 0 \\
\end{aligned}\]
Druga vrstica ni linearno odvisna od prejšnjih - matrika ni pozitivno semidefinitna!
Protiprimer $x = [2\ {-2}\ 1]^\top$:
\[x^\top H_h x = -2 < 0\]
\[\begin{aligned}
f &= x^2 + y^2 + z^2 + 2xz - 3x - z + 2 \\
g_1 &= x - y - 1 \\
g_2 &= y - z - 3 \\[1ex]
L_x &= 2x + 2z - 3 + \lambda_1 = 0 \\
L_y &= 2y - \lambda_1 + \lambda_2 = 0 \\
L_z &= 2x + 2z - 1 - \lambda_2 = 0
\end{aligned}\]
-
\[\begin{aligned}
g_2 &= 0 \\
y &= z + 3 \\[1ex]
L_x &= 2x + 2z - 3 + \lambda_1 = 0 \\
L_y &= 2z + 6 - \lambda_1 + \lambda_2 = 0 \\
L_z &= 2x + 2z - 1 - \lambda_2 = 0
\end{aligned}\]
-
\[\begin{aligned}
g_1 &= 0 \\
x &= z + 4 \\[1ex]
L_x &= 4z + 5 + \lambda_1 = 0 \\
L_y &= 2z + 6 - \lambda_1 + \lambda_2 = 0 \\
L_z &= 4z - 7 - \lambda_2 = 0 \\[1ex]
\lambda_2 &= 4z - 7 < 0 \\
\lambda_1 &= 6z - 1 < 0 \\
10z + 4 &= 0 \\
z &= -2/5
\end{aligned}\]
-
\[\begin{aligned}
\lambda_1 &= 0 \\[1ex]
L_x &= 2x + 2z - 3 = 0 \\
L_y &= 2z + 6 + \lambda_2 = 0 \\
L_z &= 2x + 2z - 1 - \lambda_2 = 0 \\[1ex]
\lambda_2 &= 2 \\
z &= -4 \\
y &= -1 \\
x &= 11/2 \\
g_1 &> 0
\end{aligned}\]
-
\[\begin{aligned}
\lambda_2 &= 0 \\[1ex]
L_x &= 2x + 2z - 3 + \lambda_1 = 0 \\
L_y &= 2y - \lambda_1 = 0 \\
L_z &= 2x + 2z - 1 = 0 \\[1ex]
\lambda_1 &= 2 \\
g_1 &= 0 \\
x &= y + 1 \\
y &= 1 \\
x &= 2 \\
z &= -3/2 \\
g_2 &= -1/2 < 0
\end{aligned}\]
Optimalna rešitev: $(x, y, z) = (2, 1, -3/2)$
Naloga 4
Poišči optimalno rešitev problema vezanih ekstremov z neenačbami
\[\begin{aligned}
\min &\quad 3x^2 + 2xy + 3y^2 - 12x - 4y \\[1ex]
2x + y &\le 1 \\
x &\ge 0 \\
x+y &\ge 0 \ .
\end{aligned}\]