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} \]

  1. \[ \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} \]

  2. \[ \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} \]

  1. \[ \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} \]

  1. \[ \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} \]

    1. \[ \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} \]

    2. \[ \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} \]

  1. \[ \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} \]

    1. \[ \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} \]

    2. \[ \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} \]

  2. \[ \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} \]

Select a repo