---
tags: vaje, om, ven, kkt
hackmd: https://hackmd.io/v3C28VrbSROpVgYzxDilGg
plugins: mathjax
---
# Optimizacijske metode - vaje 21.5.2021

---

## Problem vezanega ekstrema z neenačbami

### 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$.

----


$$
\begin{aligned}
f_{\min} &= x+y+z & \text{linearna} \\
f_{\max} &= -x-y-z & \text{linearna} \\
g_1 &= x^2 + y^2 - z & \text{konveksna} \\
g_2 &= z - 1 & \text{linearna} \\
H_{g_1} &= \begin{pmatrix}
2 & 0 & 0 \\
0 & 2 & 0 \\
0 & 0 & 0
\end{pmatrix} \ge 0
\end{aligned}
$$

#### Minimum

$$
\begin{aligned}
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 \\
\lambda_1 &> 0 \\
g_1 &= 0 \\
x &= y < 0 \\
z &= 2x^2
\end{aligned}
$$

1. $$
\begin{aligned}
g_2 &= 0 \\
z &= 1 = 2x^2 \\
x &= y = -\sqrt{2}/2 \\
L_x &= 1 - \lambda_1 \sqrt{2} = 0 \\
L_y &= 1 - \lambda_1 \sqrt{2} = 0 \\
L_z &= 1 - \lambda_1 + \lambda_2 = 0 \\
\lambda_1 &= \sqrt{2}/2 \ge 0 \\
\lambda_2 &= \sqrt{2}/2 - 1 < 0
\end{aligned}
$$

2. $$
\begin{aligned}
\lambda_2 &= 0 \\
L_x &= 1 + 2 \lambda_1 x = 0 \\
L_y &= 1 + 2 \lambda_1 y = 0 \\
L_z &= 1 - \lambda_1 = 0 \\
\lambda_1 &= 1 \\
x &= y = -1/2 \\
z &= 1/2 \\
g_2 &= 1/2 - 1 = -1/2 \le 0
\end{aligned}
$$

Minimum: $(x, y, z) = (-1/2, -1/2, 1/2)$

----

#### Maksimum

$$
\begin{aligned}
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 \\
\lambda_1 &> 0 \\
g_1 &= 0 \\
x &= y > 0 \\
z &= 2x^2
\end{aligned}
$$

1. $$
\begin{aligned}
g_2 &= 0 \\
z &= 1 = 2x^2 \\
x &= y = \sqrt{2}/2 \\
L_x &= -1 + \lambda_1 \sqrt{2} = 0 \\
L_y &= -1 + \lambda_1 \sqrt{2} = 0 \\
L_z &= -1 - \lambda_1 + \lambda_2 = 0 \\
\lambda_1 &= \sqrt{2}/2 \ge 0 \\
\lambda_2 &= 1 + \sqrt{2}/2 \ge 0
\end{aligned}
$$

Maksimum: $(x, y, z) = (\sqrt{2}/2, \sqrt{2}/2, 1)$

---

### Naloga 2

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}
f &= x^2 + y^2 + z^2 + 2xz - 3x - z + 2 & \text{konveksna} \\
g_1 &= x - y - 1 & \text{linearna} \\
g_2 &= y - z - 3 & \text{linearna} \\
H_f &= \begin{pmatrix}
2 & 0 & 2 \\
0 & 2 & 0 \\
2 & 0 & 2
\end{pmatrix} \ge 0 \\[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 \\
\lambda_1 &\ne \lambda_2
\end{aligned}
$$


1. $$
\begin{aligned}
g_1 &= 0 \\
y &= x - 1 \\
g_2 &= x - z - 4 \\
L_x &= 2x + 2z - 3 + \lambda_1 = 0 \\
L_y &= 2x - 2 - \lambda_1 + \lambda_2 = 0 \\
L_z &= 2x + 2z - 1 - \lambda_2 = 0 \\
\end{aligned}
$$

1. $$
\begin{aligned}
g_2 &= 0 \\
z &= x - 4 \\
L_x &= 4x - 11 + \lambda_1 = 0 \\
L_y &= 2x - 2 - \lambda_1 + \lambda_2 = 0 \\
L_z &= 4x - 9 - \lambda_2 = 0 \\
L_x + L_y + L_z &= 10x - 22 = 0 \\
x &= 11/5 \\
\lambda_1 &= 11 - 44/5 = 11/5 \ge 0 \\
\lambda_2 &= 44/5 - 9 = -1/5 < 0
\end{aligned}
$$

2. $$
\begin{aligned}
g_2 &< 0 \\
\lambda_2 &= 0 \\
L_x &= 2x + 2z - 3 + \lambda_1 = 0 \\
L_y &= 2x - 2 - \lambda_1 = 0 \\
L_z &= 2x + 2z - 1 = 0 \\
L_x - L_z &= -2 + \lambda_1 = 0 \\
\lambda_1 &= 2 \ge 0 \\
x &= 2 \\
z &= -3/2 \\
y &= 1 \\
g_2 &= 1 + 3/2 - 3 = -1/2 < 0
\end{aligned}
$$

Optimalna rešitev: $(x, y, z) = (2, 1, -3/2)$

---

### Naloga 3

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}
$$

----

$$
\begin{aligned}
f &= 3x^2 + 2xy + 3y^2 - 12x - 4y & \text{konveksna} \\
g_1 &= 2x + y - 1 & \text{linearna} \\
g_2 &= -x & \text{linearna} \\
g_3 &= -x - y & \text{linearna} \\
H_f &= \begin{pmatrix}
6 & 2 \\
2 & 6
\end{pmatrix} \ge 0 \\
\det H_f &= 6 \cdot 6 - 2 \cdot 2 = 32 \ge 0 \\[1ex]
L_x &= 6x + 2y - 12 + 2 \lambda_1 - \lambda_2 - \lambda_3 = 0 \\
L_y &= 2x + 6y - 4 + \lambda_1 - \lambda_3 = 0
\end{aligned}
$$

1. $$
\begin{aligned}
g_2 &= 0 \\
x &= 0 \\
g_1 &= y - 1 \\
g_3 &= -y \\
L_x &= 2y - 12 + 2 \lambda_1 - \lambda_2 - \lambda_3 = 0 \\
L_y &= 6y - 4 + \lambda_1 - \lambda_3 = 0
\end{aligned}
$$

1. $$
\begin{aligned}
g_3 &= 0 \\
y &= 0 \\
g_1 &= -1 < 0 \\
\lambda_1 &= 0 \\
L_x &= -12 - \lambda_2 - \lambda_3 = 0 \\
L_y &= -4 - \lambda_3 = 0 \\
\lambda_3 &= -4 < 0
\end{aligned}
$$

2. $$
\begin{aligned}
g_3 &< 0 \\
\lambda_3 &= 0 \\
L_x &= 2y - 12 + 2 \lambda_1 - \lambda_2 = 0 \\
L_y &= 6y - 4 + \lambda_1 = 0
\end{aligned}
$$

1. $$
\begin{aligned}
g_1 &= 0 \\
y &= 1 \\
g_3 &= -1 < 0 \\
L_x &= -10 + 2 \lambda_1 - \lambda_2 = 0 \\
L_y &= 2 + \lambda_1 = 0 \\
\lambda_1 &= -2 < 0
\end{aligned}
$$

2. $$
\begin{aligned}
g_1 &< 0 \\
\lambda_1 &= 0 \\
L_x &= 2y - 12 - \lambda_2 = 0 \\
L_y &= 6y - 4 = 0 \\
y &= 2/3 \\
\lambda_2 &= -32/3 < 0
\end{aligned}
$$

2. $$
\begin{aligned}
g_2 &< 0 \\
\lambda_2 &= 0 \\
L_x &= 6x + 2y - 12 + 2 \lambda_1 - \lambda_3 = 0 \\
L_y &= 2x + 6y - 4 + \lambda_1 - \lambda_3 = 0
\end{aligned}
$$

1. $$
\begin{aligned}
g_3 &= 0 \\
y &= -x \\
g_1 &= x - 1 \\
g_2 &= -x \\
L_x &= 4x - 12 + 2 \lambda_1 - \lambda_3 = 0 \\
L_y &= -4x - 4 + \lambda_1 - \lambda_3 = 0
\end{aligned}
$$

1. $$
\begin{aligned}
g_1 &= 0 \\
x &= 1 \\
g_2 &= -1 < 0 \\
L_x &= -8 + 2 \lambda_1 - \lambda_3 = 0 \\
L_y &= -8 + \lambda_1 - \lambda_3 = 0 \\
L_x - L_y &= \lambda_1 = 0 \\
\lambda_3 &= -8 < 0
\end{aligned}
$$

2. $$
\begin{aligned}
g_1 &< 0 \\
\lambda_1 &= 0 \\
L_x &= 4x - 12 - \lambda_3 = 0 \\
L_y &= -4x - 4 - \lambda_3 = 0 \\
L_x + L_y &= -16 - 2\lambda_3 = 0 \\
\lambda_3 &= -8 < 0
\end{aligned}
$$

2. $$
\begin{aligned}
g_3 &< 0 \\
\lambda_3 &= 0 \\
L_x &= 6x + 2y - 12 + 2 \lambda_1 = 0 \\
L_y &= 2x + 6y - 4 + \lambda_1 = 0
\end{aligned}
$$

1. $$
\begin{aligned}
g_1 &= 0 \\
y &= -2x + 1 \\
L_x &= 2x - 10 + 2 \lambda_1 = 0 \\
L_y &= -10x + 2 + \lambda_1 = 0 \\
5 L_x + L_y &= -48 + 11 \lambda_1 = 0 \\
\lambda_1 &= 48/11 \ge 0 \\
L_x - 2 L_y &= 22x - 14 = 0 \\
x &= 7/11 \\
y &= -3/11 \\
g_2 &= -7/11 < 0 \\
g_3 &= -7/11 + 3/11 = -4/11 < 0
\end{aligned}
$$

Optimalna vrednost: $(x, y) = (7/11, -4/11)$

---

### Naloga 4

Poišči optimalno rešitev problema vezanih ekstremov z neenačbami

$$
\begin{aligned}
\min \quad x^2 -4x + y^2 -6y &+ 8 \\[1ex]
x^2 - x + y^3 + \ln y &\le 1 \\
-2y + 1 &\le 0 \\
x + 2y &\le 3 \ .
\end{aligned}
$$

**Namig:** v optimalni rešitvi sta dva pogoja izpolnjena z enačajem.

----

$$
\begin{aligned}
f &= x^2 -4x + y^2 -6y + 8 & \text{konveksna} \\
g_1 &= x^2 - x + y^3 + \ln y - 1 \\
g_2 &= -2y + 1 & \text{linearna } (y \ge 1/2) \\
g_3 &= x + 2y - 3 & \text{linearna} \\
H_f &= \begin{pmatrix}
2 & 0 \\
0 & 2
\end{pmatrix} \ge 0 \\
H_{g_1} &= \begin{pmatrix}
2 & 0 \\
0 & 6y - {1 \over y^2}
\end{pmatrix} \ge 0 &\text{če } y \ge \sqrt[3]{1/6} > 1/2
\end{aligned}
$$

Nismo uspeli dokazati, da je območje, omejeno z ${g_1}, {g_2}, {g_3}$, konveksno!