Kužely, obaly, krajní body — a konvexní funkce
NMFM204 Úvod do optimalizace · 21. 10. 2026
→ další téma ↓ rozbor tématu
„…in fact, the great watershed in optimization isn't between linearity and nonlinearity, but convexity and nonconvexity.“
R. Tyrrell Rockafellar, Lagrange Multipliers and Optimality, SIAM Review 35(2), 1993
dnes: dokončíme konvexní množiny (Př. 1–5) a přejdeme ke konvexním funkcím (Př. 6–9)
kužel: \(0 \in K\) a \(\forall x \in K,\ \alpha \ge 0:\ \alpha x \in K\)
konvexní kužel: \(0 \in K\) a \(\forall x, y \in K,\ \alpha, \beta \ge 0:\ \alpha x + \beta y \in K\)
konvexní polyedrický kužel: konvexní kužel a zároveň konvexní polyedrická množina
typicky \(\{x : Ax \ge 0\}\) — nerovnosti s nulovou pravou stranou
táhněte myší pro otočení
vždy konečné kombinace \(\sum_{s \in I} \lambda(s)\, s\) bodů z \(S\):
| bez podmínky na součet | \(\sum \lambda(s) = 1\) | |
|---|---|---|
| \(\lambda(s) \in \mathbb R\) | lineární obal \(\mathrm L(S)\) | afinní obal \(\mathrm{Aff}(S)\) |
| \(\lambda(s) \ge 0\) | nezáporný obal \(\mathrm{pos}(S)\) | konvexní obal \(\mathrm{conv}(S)\) |
nejmenší … obsahující \(S\): podprostor · afinní podprostor · konvexní kužel · konvexní množina
\(\mathrm{conv}(S) \subseteq \mathrm{Aff}(S) \cap \mathrm{pos}(S)\) a \(\mathrm{Aff}(S) \cup \mathrm{pos}(S) \subseteq \mathrm L(S)\)
bod \((x,y)\) jako kombinace \([0,1], [1,0], [1,1]\) se součtem 1:
\(\lambda_1 = 1 - x,\ \ \lambda_2 = 1 - y,\ \ \lambda_3 = x + y - 1\)
| \(S\) | conv | pos | Aff | L |
|---|---|---|---|---|
| \([0,1],[1,0],[1,1]\) | trojúhelník | 1. kvadrant | \(\mathbb R^2\) | \(\mathbb R^2\) |
| \([1,1],[2,2]\) | úsečka | polopřímka z 0 | přímka \(y=x\) | přímka \(y=x\) |
| \([1,0],[0,1]\) | úsečka | 1. kvadrant | přímka \(x+y=1\) | \(\mathbb R^2\) |
| kružnice | kruh | \(\mathbb R^2\) | \(\mathbb R^2\) | \(\mathbb R^2\) |
Bonus Př. 3: v 2(a) je \(\mathrm{Aff} \cap \mathrm{pos}\) = kvadrant \(\ne\) trojúhelník → rovnost obecně neplatí
v 2(c) rovnost platí: \(0 \notin \mathrm{Aff}(S)\), funkce \(\varphi(x,y) = x+y \equiv 1\) na Aff vynutí \(\sum\lambda = 1\)
krajní bod \(a\): neleží uvnitř žádné úsečky v \(A\) (\(a = \alpha x + (1-\alpha) y\), \(x \ne y\), \(0<\alpha<1\) nejde)
směr \(s\): existuje \(a \in A\) a celá polopřímka \(\{a + ts : t \ge 0\} \subseteq A\)
krajní směr \(s\): nejde složit \(s = \alpha x + \beta y\) ze směrů \(x, y \notin \mathrm{pos}(\{s\})\) — hrana kužele směrů
\(\mathrm{extd}(A)\) = krajní směry jednotkové délky
\(P = \mathrm{conv}(\mathrm{ext}\,P)\) · kužel bez přímky: \(K = \mathrm{pos}(\mathrm{extd}\,K)\)
u hranice se p přichytí; zkuste vrchol, hranu, oblouk
bod a lze táhnout
\(A\) z Př. 4(a):
\(\mathrm{ext}\,A = \{(0,1), (0,2), (2,0)\}\)
\(\mathrm{extd}\,A = \{(1,0),\ \tfrac{1}{\sqrt{13}}(3,2)\}\)
| množina | ext | direct (bonus) | extd |
|---|---|---|---|
| Př. 4(a) | \((0,1),(0,2),(2,0)\) | \(0 \le s_2 \le \tfrac23 s_1\) | \((1,0),\ \tfrac{1}{\sqrt{13}}(3,2)\) |
| kruh | celá kružnice | \(\{0\}\) | \(\emptyset\) |
| \(K = \{0 \le x \le y\}\) | \(\{0\}\) | \(K\) | \((0,1),\ \tfrac{1}{\sqrt2}(1,1)\) |
| polorovina \(y \ge 0\) | \(\emptyset\) | \(s_2 \ge 0\) | \((1,0),(-1,0)\) — ale pos \(\ne\) polorovina |
| \(y \ge x^2\) | celá parabola | \((0,s_2),\ s_2 \ge 0\) | \((0,1)\) |
Bonus Př. 5: vnitřní bod není krajní; krajní body leží na hranici, ale ne každý hraniční bod je krajní (střed hrany čtverce)
\(f : D \to \mathbb R\), \(D\) konvexní, je konvexní, pokud \(\ f(\lambda x + (1-\lambda) y) \le \lambda f(x) + (1-\lambda) f(y)\ \ \forall x, y \in D,\ \lambda \in [0,1]\)
slovy: tětiva leží nad grafem
konkávní: \(-f\) je konvexní
epigraf \(\mathrm{epi}(f) = \{(x,t) : f(x) \le t\}\) — vše nad grafem
\(f\) konvexní \(\iff\) \(\mathrm{epi}(f)\) je konvexní množina (most mezi funkcemi a množinami)
konvexita funkce = konvexita množiny nad grafem
\(\alpha f + \beta g\), \(\alpha, \beta \ge 0\): sečteme nerovnosti vynásobené nezápornými čísly
\(\sup_i f_i\): \(f_i(z) \le \lambda f_i(x) + (1-\lambda) f_i(y) \le \lambda F(x) + (1-\lambda) F(y)\) \(\mathrm{epi}(F) = \bigcap_i \mathrm{epi}(f_i)\)
\(h \circ g\), \(h\) konvexní neklesající, \(g\) konvexní:
\(h(g(z)) \le h(\lambda g(x) + (1-\lambda) g(y)) \le \lambda h(g(x)) + (1-\lambda) h(g(y))\)
první nerovnost potřebuje monotonii \(h\), druhá konvexitu \(h\)
vnitřní g:
vnější h:
zkuste e⁻ᵗ∘x² (Gaussova křivka) a t²∘(x²−1)
\(f \in C^2\): \(\ H_f(x) = \big(\partial^2 f / \partial x_i \partial x_j\big)_{i,j}\)
\(A \succeq 0\) (poz. semidefinitní): \(x^TAx \ge 0\ \forall x\); \(A \succ 0\) (poz. definitní): \(x^TAx > 0\ \forall x \ne 0\)
\(D\) otevřená konvexní: \(\ f\) konvexní na \(D\) \(\iff\) \(H_f(x) \succeq 0\ \ \forall x \in D\)
Sylvester: \(A \succeq 0 \iff\) vlastní čísla \(\ge 0 \iff\) všechny hlavní minory \(\ge 0\)
\(A \succ 0 \iff\) vedoucí minory \(D_1, \dots, D_n > 0\)
pozor: \(\begin{pmatrix} 0 & 0 \\ 0 & -1 \end{pmatrix}\) má \(D_1 = D_2 = 0\), ale \(\not\succeq 0\)
1. derivace: \(f_x = \dfrac{2x}{y},\quad f_y = -\dfrac{x^2}{y^2}\)
2. derivace: \(f_{xx} = \dfrac{2}{y},\quad f_{xy} = -\dfrac{2x}{y^2},\quad f_{yy} = \dfrac{2x^2}{y^3}\)
\(H_f = \begin{pmatrix} 2/y & -2x/y^2 \\ -2x/y^2 & 2x^2/y^3 \end{pmatrix}\)
minory řádu 1: \(\tfrac{2}{y} > 0,\ \tfrac{2x^2}{y^3} \ge 0\) řádu 2: \(\det H_f = \tfrac{4x^2}{y^4} - \tfrac{4x^2}{y^4} = 0\)
všechny hlavní minory \(\ge 0\) ⇒ \(H_f \succeq 0\) ⇒ konvexní (\(\det = 0\): jen semidefinitní)
složením: \(g = x^2 + y^2 \ge 0\) konvexní, \(h(t) = t^4\) na \([0,\infty)\) konvexní neklesající ⇒ konvexní
Hessiánem: \(r = x^2+y^2\), \(\ f_x = 4r^3\cdot 2x = 8x r^3,\ \ f_y = 8y r^3\)
\(f_{xx} = 8r^3 + 48x^2r^2,\ \ f_{xy} = 48xy\,r^2,\ \ f_{yy} = 8r^3 + 48y^2r^2\)
\(\det H_f = 64r^6 + 384r^5(x^2+y^2) + 48^2x^2y^2r^4 - 48^2x^2y^2r^4 = 448\,r^6 \ge 0\)
diagonála \(\ge 0\), \(\det \ge 0\) ⇒ konvexní
\(f_x = 2x+2y+2z,\ f_y = 2x+2y+2z,\ f_z = 2x+2y-2z\)
\(H_f = \begin{pmatrix} 2 & 2 & 2 \\ 2 & 2 & 2 \\ 2 & 2 & -2 \end{pmatrix}\)
vedoucí minory: \(D_1 = 2,\ D_2 = 0,\ D_3 = 0\) — všechny \(\ge 0\)…
…ale hlavní minor \(h_{33} = \) \(-2 < 0\)
řez osou \(z\): \(f(0,0,t) = -t^2\) → není konvexní
pro \(\succeq 0\) kontrolujeme všechny hlavní minory
\(L = \log x + \log y\): \(\ f_x = yL + xy\cdot\tfrac1x = y(L+1),\ \ f_y = x(L+1)\)
\(f_{xx} = \tfrac{y}{x},\ \ f_{yy} = \tfrac{x}{y},\ \ f_{xy} = (L+1) + y\cdot\tfrac1y = L + 2\)
\(\det H_f = \tfrac{y}{x}\cdot\tfrac{x}{y} - (L+2)^2 = 1 - (L+2)^2\)
v bodě \((1,1)\): \(L = 0\), \(\det H_f = 1 - 4 = -3 < 0\)
indefinitní ⇒ není konvexní (\(\det \ge 0\) jen pro \(e^{-3} \le xy \le e^{-1}\))
| funkce | metoda | výsledek |
|---|---|---|
| \(|x_1| + \dots + |x_n|\) | součet konvexních / norma | konvexní |
| \(x^2/y,\ y>0\) | minory \(\tfrac2y,\ \tfrac{2x^2}{y^3} \ge 0\), \(\det = 0\) | konvexní |
| \((x^2+y^2)^4\) | \(t^4\) na \([0,\infty)\) neklesající ˆ \(x^2+y^2\) | konvexní |
| \(x^2+y^2-z^2+\dots\) | \(h_{33} = -2\) | není |
| \(xy\log(xy)\) | \(\det = 1 - (2+\log xy)^2 < 0\) v \((1,1)\) | není |
\(f\) konvexní \(\Rightarrow\) \(L_r = \{x : f(x) \le r\}\) je konvexní pro každé \(r\)
důkaz: \(f(\lambda x + (1-\lambda) y) \le \lambda f(x) + (1-\lambda) f(y) \le \lambda r + (1-\lambda) r = r\)
důsledek: \(\{x : g_1(x) \le 0, \dots, g_m(x) \le 0\}\) pro konvexní \(g_i\) je konvexní (průnik)
opak neplatí: \(x^3\) nebo \(\sqrt{|x|+|y|}\) mají konvexní úrovňové množiny, ale nejsou konvexní
body jsou nastavené na protipříklad; zkuste je posunout
\(a = e^{-y},\ E = e^{x^2 + a}\): \(\ a_y = -a,\ E_x = 2xE,\ E_y = -aE\)
\(f_x = 2xE + 6y,\quad f_y = -aE + 6x\)
\(f_{xx} = (2+4x^2)E,\quad f_{xy} = 6 - 2xaE,\quad f_{yy} = aE + a^2E = a(1+a)E\)
\(\det H_f = (2+4x^2)a(1+a)E^2 - (6 - 2xaE)^2 = 2[(1+2x^2+a)aE^2 + 12xaE - 18]\)
\(y \to \infty\): \(a \to 0\), \(\det H_f \to -36\); např. v \((2, 10)\): \(\det H_f \approx -33{,}4\)
indefinitní ⇒ není konvexní
\(t = x + ay\): \(\ f = \psi(t) = t - \log(1 + e^t)\)
\(\psi'(t) = 1 - \tfrac{e^t}{1+e^t} = \tfrac{1}{1+e^t},\quad \psi''(t) = -\tfrac{e^t}{(1+e^t)^2} < 0\)
\(t_x = 1,\ t_y = a\): \(\ f_{xx} = \psi'',\ f_{xy} = a\psi'',\ f_{yy} = a^2\psi''\)
\(H_f = \psi''\begin{pmatrix} 1 & a \\ a & a^2\end{pmatrix}\): \(\ f_{xx} < 0\), \(\det H_f = 0\)
\(H_f \preceq 0\) ⇒ konkávní pro každé \(a\), konvexní ne
kužel / obaly / krajní body a směry: \(A = \mathrm{conv}(\mathrm{ext}\,A) + \mathrm{pos}(\mathrm{extd}\,A)\)
konvexní funkce: tětiva nad grafem \(\iff\) epigraf konvexní
stavebnice: \(\alpha f + \beta g\) (\(\alpha,\beta \ge 0\)), \(\sup_i f_i\), \(h \circ g\) (\(h\) neklesající)
\(C^2\): \(H_f \succeq 0\) — Sylvester přes všechny hlavní minory
konvexní \(g_i\) ⇒ \(\{g_i \le 0\}\) konvexní — přípustná množina „dobré“ úlohy
čtení navíc: Boyd, Vandenberghe: Convex Optimization, kap. 2–3 — web.stanford.edu/~boyd/cvxbook