Cvičení IV

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)

1. Kužely

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

1. Př. 1: test \(\alpha x + \beta y \in K\)

1. Bonus 3D: K₅ = {z ≥ √(x²+y²)}

táhněte myší pro otočení

1. Kdo je kdo

2. Obaly: čtyři pravidla pro koeficienty

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)\)

2. Obaly naživo (Př. 2)

2. Př. 2(a): koeficienty jako sloupce

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\)

2. Př. 2 a 3: přehled

\(S\)convposAffL
\([0,1],[1,0],[1,1]\)trojúhelník1. kvadrant\(\mathbb R^2\)\(\mathbb R^2\)
\([1,1],[2,2]\)úsečkapolopřímka z 0přímka \(y=x\)přímka \(y=x\)
\([1,0],[0,1]\)úsečka1. kvadrantpřímka \(x+y=1\)\(\mathbb R^2\)
kružnicekruh\(\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\)

3. Krajní bod, směr, krajní směr

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)\)

3. Je bod p krajní? (táhněte p)

u hranice se p přichytí; zkuste vrchol, hranu, oblouk

3. Bonus Př. 4: směry množiny z 4(a)

bod a lze táhnout

3. Rozložte směr s

3. Př. 4(a): rozklad A = conv(ext A) + pos(extd A)

\(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)\}\)

3. Př. 4: přehled

množinaextdirect (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)\)
kruhcelá 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)

4. Konvexní funkce

\(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)

4. Tětiva nad grafem (táhněte x, y)

4. Epigraf (táhněte p, q)

konvexita funkce = konvexita množiny nad grafem

5. Př. 6: operace zachovávající konvexitu

\(\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\)

5. Př. 6.1: αf + βg

5. Př. 6.2: supremum přímek

5. Př. 6.3: složení h(g(x))

vnitřní g:

vnější h:

zkuste e⁻ᵗ∘x² (Gaussova křivka) a t²∘(x²−1)

6. Hessova matice a definitnost

\(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\)

6. Kvadratická forma xᵀAx pro A = (a b; b c)

7. Př. 7(b): f = x²/y, y > 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í)

7. Př. 7(c): f = (x² + y²)⁴

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í

7. Př. 7(d): f = x² + y² − z² + 2xy + 2xz + 2yz

\(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

7. Př. 7(e): f = xy·log(xy), x, y > 0

\(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}\))

7. Př. 7: přehled

funkcemetodavýsledek
\(|x_1| + \dots + |x_n|\)součet konvexních / normakonvexní
\(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í

8. Úrovňové množiny

\(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í

8. Úrovňová množina {f ≤ r}

8. Př. 8: které množiny jsou konvexní?

8. Bonus Př. 9(a–c): množiny

body jsou nastavené na protipříklad; zkuste je posunout

8. Bonus Př. 9(d): f = exp(x² + e⁻ʸ) + 6xy

\(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í

8. Bonus Př. 9(e): f = log(e^(x+ay) / (1 + e^(x+ay)))

\(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

Shrnutí

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