Đến đây ta có hai thế giới song song: ở phần II của chương, và ở vài chủ đề vừa qua. Ở đây ta dựng ba cây cầu giữa chúng. Cây cầu thứ nhất đi từ hàm sang tập: Các tập mức dưới của một hàm lồi là tập lồi. Cây cầu thứ hai đi theo cả hai chiều: Một hàm lồi khi và chỉ khi miền nằm phía trên đồ thị của nó, gọi là , là một tập lồi. Cây cầu thứ ba nối hàm lồi với xác suất: Bất đẳng thức Jensen.

Mỗi cây cầu cho ta một cách mới để nhìn và để chứng minh. Ta sẽ dùng để viết lại bài toán tối ưu, dùng Jensen để thấy vì sao phương sai không âm, vì sao thêm nhiễu không làm giảm một , và vì sao những bất đẳng thức như AM–GM hay Hölder thật ra chỉ là một.

1. Tập mức dưới

Định nghĩa. Tập mức dưới mức $\alpha$ của hàm $f$ là $C_{\alpha }=\{x\in \mathrm{dom}f:f(x)\le \alpha \}$.

Nếu $f$ lồi thì mọi tập mức dưới đều lồi, với mọi $\alpha$. Lời chứng minh đi thẳng từ định nghĩa: Nếu $x,y\in C_{\alpha }$ với trọng số $\theta \in [0,1]$ thì

$$\begin{array}{rl}f(\theta x+(1-\theta )y)& \le \theta f(x)+(1-\theta )f(y)\\ & \le \theta \alpha +(1-\theta )\alpha =\alpha .\end{array}$$

Bằng hình ảnh, cắt đồ thị của một cái bát bằng một mặt phẳng nằm ngang ở độ cao $\alpha$, phần đáy bát nằm dưới mặt cắt chiếu xuống thành một miền lồi.

Chiều ngược lại sai, xét ví dụ phản chứng trực quan: $-e^x$ lõm nghiêm ngặt, vậy mà mọi tập mức dưới $\{x:-e^x\le \alpha \}$ đều là một khoảng, nên lồi. Ở chủ đề điều kiện bậc nhất, hàm $-\exp (-x_1^2-2x_2^2)$ cũng có mọi tập mức dưới là hình ellipse dù không phải . Những hàm có mọi tập mức dưới lồi được gọi là hàm tựa lồi, một họ hàm rộng hơn hàm lồi.

Epigraph và tập mức dưới

Hàm f(x) = x²|x|eˣ0.3x² + sin(1.5x)−eˣx³α = 2.00

Tập mức dưới {x : f(x) ≤ 2.00} (vạch xanh trên trục) gồm 1 khoảng: [−1.41, 1.41].

Tập mức dưới là một khoảng, tức là một tập lồi.

Trong mô phỏng, vạch xanh trên trục hoành là tập mức dưới. Kéo thanh trượt $\alpha$ với $x^2$ hay $e^x$, vạch xanh luôn là một khoảng liền. Với $0.3x^2+\sin (1.5x)$, có những mức $\alpha$ mà tập mức dưới tách thành hai khoảng rời nhau, và đó là một bằng chứng không lồi. Với $-e^x$ và $x^3$, tập mức dưới luôn là một khoảng, dù cả hai hàm đều không lồi trên $\mathbb{R}$.

Dùng tập mức dưới để chứng minh một tập là lồi. Kết quả vừa chứng minh cho một cách nhận ra rất gọn. Muốn chứng minh tập $S$ lồi, ta cố viết nó thành $\{x:f(x)\le \alpha \}$ với $f$ lồi, hoặc $\{x:g(x)\ge \alpha \}$ với $g$ lõm, vì tập mức trên của hàm lõm cũng lồi. Chẳng hạn, ràng buộc $\parallel w{\parallel }_2\le r$ trong học máy là tập mức dưới của một chuẩn, nên lồi. Xét một bài toán thú vị: Tập các $x\in {\mathbb{R}}_{+}^n$ có trung bình nhân ít nhất bằng $\alpha$ lần trung bình cộng, với $0\le \alpha \le 1$, chính là tập mức trên mức 0 của hàm lõm $G(x)-\alpha A(x)$, do đó là một tập lồi.

Một hệ quả có ý nghĩa thực tế: Nếu hàm mất mát huấn luyện $L(w)$ lồi theo $w$, thì tập các mô hình "đủ tốt" $\{w:L(w)\le \epsilon \}$ là . Lấy trung bình tham số của hai mô hình đủ tốt luôn cho một mô hình đủ tốt. Với mạng nơ-ron, hàm mất mát không lồi, và trung bình tham số của hai mạng huấn luyện độc lập có thể cho một mạng rất tệ.

2. Epigraph: Hàm lồi chính là tập lồi

Định nghĩa. của $f$ là tập $\mathrm{epi}f=\{(x,t):x\in \mathrm{dom}f,f(x)\le t\}$, một tập con của ${\mathbb{R}}^{n+1}$.

Tiền tố "epi" trong tiếng Hy Lạp nghĩa là "phía trên": bao gồm đồ thị và toàn bộ các điểm nằm phía trên đồ thị đó. Định lý cầu nối giữa hai thế giới khẳng định:

$f$ lồi khi và chỉ khi $\mathrm{epi}f$ là .

Hai chiều đều ngắn. Nếu $f$ lồi và $(x,t),(y,s)$ thuộc , thì

$$\begin{array}{rl}f(\theta x+(1-\theta )y)& \le \theta f(x)+(1-\theta )f(y)\\ & \le \theta t+(1-\theta )s,\end{array}$$

nên điểm $(\theta x+(1-\theta )y,\theta t+(1-\theta )s)$ cũng thuộc . Ngược lại, nếu epigraph lồi, lấy hai điểm $(x,f(x))$ và $(y,f(y))$ của nó, của chúng thuộc epigraph, và đó chính là bất đẳng thức dây cung. Tương tự, $f$ lõm khi và chỉ khi hypograph $\{(x,t):t\le f(x)\}$ lồi.

Hãy so sánh với đồ thị: Đồ thị của một không affine thì không phải . Đồ thị của $x^2$ chứa $(-1,1)$ và $(1,1)$ nhưng không chứa trung điểm $(0,1)$, điểm này nằm hẳn phía trên đồ thị. Phải "đổ đầy" phần phía trên thì mới được một tập lồi.

Điều kiện bậc nhất nhìn từ . Điều kiện $f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^T(y-x)$ có thể viết lại thành: Với mọi $(y,t)\in \mathrm{epi}f$,

$${\left[\begin{array}{c}\mathrm{\nabla }f(x)\\ -1\end{array}\right]}^T(\left[\begin{array}{c}y\\ t\end{array}\right]-\left[\begin{array}{c}x\\ f(x)\end{array}\right])\le 0.$$

Đây đúng là định nghĩa của một siêu phẳng tựa của $\mathrm{epi}f$ tại điểm biên $(x,f(x))$, với pháp tuyến $(\mathrm{\nabla }f(x),-1)$. Tiếp tuyến của chính là siêu phẳng tựa của , và điều kiện bậc nhất là định lý siêu phẳng tựa ở chủ đề trước, áp dụng cho một tập lồi cụ thể.

Dùng để chứng minh tính lồi. Ta xét ứng dụng epigraph chứng minh tính lồi cho hàm $x^2/y$ và trường hợp tổng quát của nó. Với $y>0$, theo phần bù Schur,

$$\frac{x^2}{y}\le t⟺\left[\begin{array}{cc}y& x\\ x& t\end{array}\right]⪰0.$$

bên phải phụ thuộc affine vào $(x,y,t)$, và điều kiện nghĩa là ma trận nằm trong nón PSD, một . Vậy là ảnh ngược của một tập lồi qua một ánh xạ affine, nên lồi, và . So với việc tính ở chủ đề điều kiện bậc hai, lời chứng minh này không cần đạo hàm nào. Thử bằng số: Với $(x,y)=(1,2)$, ta có $x^2/y=0.5$. Ma trận $\left[\begin{array}{cc}2& 1\\ 1& 0.5\end{array}\right]$ nửa xác định dương, còn $\left[\begin{array}{cc}2& 1\\ 1& 0.4\end{array}\right]$ thì không, đúng như $0.5\le 0.5$ còn $0.5>0.4$.

Dạng của bài toán tối ưu. Mẹo dùng nhiều nhất của epigraph là trong mô hình hóa: Cực tiểu $f(x)$ tương đương với cực tiểu một biến mới $t$ dưới ràng buộc $f(x)\le t$. Hàm mục tiêu trở thành tuyến tính, và toàn bộ độ phức tạp chuyển vào một ràng buộc lồi. Kỹ thuật này đã xuất hiện trực quan ở chủ đề về hai dạng bài toán kinh điển: Cực tiểu sai số lớn nhất $\underset{i}{max}|r_i|$ được viết lại thành cực tiểu $t$ với $-t\le r_i\le t$, và nhờ vậy trở thành một quy hoạch tuyến tính. Kỹ thuật này được gọi là dạng epigraph chuẩn tắc của bài toán tối ưu.

3. Bất đẳng thức Jensen

Bất đẳng thức dây cung $f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$ đôi khi được gọi là bất đẳng thức Jensen. Bằng quy nạp, nó mở rộng cho của $k$ điểm:

$$f({\theta }_1{x}_1+\cdots +{\theta }_k{x}_k)\le {\theta }_{1}f(x_1)+\cdots +{\theta }_{k}f(x_k)$$

với các hệ số trọng số ${\theta }_i\ge 0$ thỏa mãn điều kiện chuẩn hóa phân bổ:

$$\sum _{i=1}^k{\theta }_i={\theta }_1+{\theta }_2+\cdots +{\theta }_k=1.$$

Đọc ${\theta }_i$ như xác suất để một biến ngẫu nhiên $X$ nhận giá trị $x_i$, ta được dạng xác suất, dạng quan trọng nhất:

$$f(\mathbf{E}X)\le \mathbf{E}f(X)$$

với mọi biến ngẫu nhiên $X$ nhận giá trị trong miền xác định của $f$, với giả thiết các kỳ vọng đều tồn tại hữu hạn. Nói một cách trực quan: Giá trị của hàm lồi tại điểm trung bình không bao giờ vượt quá kỳ vọng của đó. Bất đẳng thức này đóng vai trò là điều kiện đặc trưng cốt lõi của tính lồi: Nếu $f$ không lồi, ta luôn tìm được một biến ngẫu nhiên rời rạc hai giá trị làm bất đẳng thức bị vi phạm.

Bất đẳng thức Jensen

Hàm f(x) = x²eˣ|x|−log x (x > 0)−x²x₁ = −2.00x₂ = 0.50x₃ = 2.00P(x₁) = 0.30P(x₂) = 0.50

E x = 0.05, f(E x) = 0.00 (điểm vàng), còn E f(x) = 2.13 (vòng tròn rỗng).

E f(x) − f(E x) = 2.123. Với hàm lồi, hiệu này luôn không âm.

Mô phỏng đặt ba điểm với ba xác suất. Điểm vàng là $f(\mathbf{E}X)$, vòng tròn rỗng là $\mathbf{E}f(X)$, và vòng tròn luôn nằm trên với . Vòng tròn rỗng luôn nằm trong vùng tô màu, của ba điểm trên đồ thị, vì nó là một tổ hợp lồi của chúng. Với $-x^2$, chiều bất đẳng thức đảo lại.

Phương sai là khoảng cách Jensen

Áp dụng Jensen cho $f(x)=x^2$:

$$\mathbf{E}{X}^2-(\mathbf{E}X{)}^2\ge 0.$$

Vế trái chính là phương sai của $X$. Vậy "phương sai không âm" là bất đẳng thức Jensen cho hàm bình phương, và khoảng cách Jensen ở đây đo đúng độ phân tán. Với $X$ phân phối đều trên $\{1,2,3,4\}$, ta có $\mathbf{E}{X}^2=7.5$, $(\mathbf{E}X{)}^2=6.25$, và hiệu $1.25$ đúng bằng phương sai.

Cùng phép tính ấy cho ra phân tích độ lệch và phương sai trong học máy. Gọi $\hat{y}$ là dự đoán của một mô hình, ngẫu nhiên theo dữ liệu huấn luyện, và $y$ là giá trị đúng. Áp dụng đẳng thức trên cho $X=\hat{y}-y$:

$$\mathbf{E}(\hat{y}-y{)}^2=(\mathbf{E}\hat{y}-y{)}^2+\mathrm{Var}(\hat{y}).$$

Sai số bình phương trung bình bằng bình phương độ lệch cộng phương sai, và phương sai chính là khoảng cách Jensen. Với $\hat{y}$ nhận ba giá trị $2.5$, $3.5$, $4$ đồng khả năng và $y=3$, sai số trung bình là $0.5$, gồm bình phương độ lệch $1/9\approx 0.111$ và phương sai $7/18\approx 0.389$.

Thêm nhiễu không làm giảm hàm lồi

Một hệ quả trực quan rút ra từ tính chất này: Nếu $z$ là một ngẫu nhiên có kỳ vọng bằng 0, tức $\mathbf{E}z=0$, thì

$$\mathbf{E}f(x+z)\ge f(x).$$

Nguyên nhân: Do kỳ vọng $\mathbf{E}(x+z)=x$, áp dụng bất đẳng thức Jensen ta có $f(x)=f(\mathbf{E}(x+z))\le \mathbf{E}f(x+z)$. Thêm nhiễu cân bằng vào đầu vào của một không bao giờ làm nó giảm đi tính trung bình. Với $f(x)=x^2$ và nhiễu $\pm 1$ đồng khả năng, $\mathbf{E}(1.5+z{)}^2=3.25={1.5}^2+1$, lớn hơn đúng bằng phương sai của nhiễu. Khi đang đứng tại điểm cực tiểu của hàm lồi, mọi nhiễu động ngẫu nhiên trong lân cận chỉ khiến giá trị trung bình kỳ vọng xấu đi.

Cận dưới ELBO trong học máy

Với hàm lõm, Jensen đảo chiều: $\mathbf{E}g(X)\le g(\mathbf{E}X)$. Áp dụng cho $g=\log$, ta được một trong những bất đẳng thức được dùng nhiều nhất của học máy hiện đại. Trong một mô hình có biến ẩn $z$, xác suất của dữ liệu $p(x)=\sum _{z}p(x,z)$ thường không tính được. Chọn một phân phối $q(z)$ bất kỳ có $q(z)>0$ ở mọi nơi $p(x,z)>0$, rồi viết

$$\begin{array}{rl}\log p(x)& =\log {\mathbf{E}}_{z\sim q}\left[\frac{p(x,z)}{q(z)}\right]\\ & \ge {\mathbf{E}}_{z\sim q}[\log \frac{p(x,z)}{q(z)}].\end{array}$$

Vế phải gọi là cận dưới bằng chứng (evidence lower bound, ELBO). Thay vì cực đại $\log p(x)$, các phương pháp suy luận biến phân, trong đó có mô hình tự mã hóa biến phân (VAE), cực đại cận dưới này. Jensen còn cho biết khi nào cận chặt: Khi biến ngẫu nhiên $p(x,z)/q(z)$ là hằng số, tức $q(z)$ đúng bằng phân phối hậu nghiệm $p(z\mid x)$.

Ví dụ: ELBO trên một mô hình hai trạng thái

Biến ẩn $z\in \{0,1\}$ với $p(z)=(0.5,0.5)$, và $p(x\mid z)=(0.2,0.6)$. Khi đó $p(x)=0.4$ và $\log p(x)\approx -0.916$. Phân phối hậu nghiệm là $p(z\mid x)=(0.25,0.75)$. Với $q=(0.5,0.5)$, ELBO $\approx -1.060$. Với $q=(0.1,0.9)$, ELBO $\approx -0.989$. Với $q=(0.25,0.75)$, ELBO bằng đúng $-0.916$. Mọi giá trị đều không vượt $\log p(x)$, và dấu bằng xảy ra đúng tại hậu nghiệm.

4. Một lý thuyết về bất đẳng thức

Tính lồi cùng bất đẳng thức Jensen tạo dựng nền tảng vững chắc cho cả một hệ thống các bất đẳng thức kinh điển trong giải tích và xác suất. Hai ví dụ tiêu biểu dưới đây minh chứng rõ nét điều đó.

AM–GM. Hàm $-\log x$ là nghiêm ngặt trên ${\mathbb{R}}_{++}$. Áp dụng bất đẳng thức Jensen với $n$ điểm cùng trọng số bằng nhau ${\theta }_i=1/n$:

$$-\log \left(\frac{x_1+\cdots +x_n}{n}\right)\le -\frac{\log x_1+\cdots +\log x_n}{n},$$

và lấy mũ hai vế được bất đẳng thức giữa trung bình nhân và trung bình cộng:

$${\left(\prod _{i=1}^n{x}_i\right)}^{1/n}=(x_1{x}_2\dots x_n{)}^{1/n}\le \frac{x_1+x_2+\cdots +x_n}{n}=\frac{1}{n}\sum _{i=1}^n{x}_i.$$

Với biến ngẫu nhiên $X$ phân phối đều trên $\{1,2,3,4\}$, trung bình nhân xấp xỉ $2.213$ trong khi trung bình cộng bằng $2.5$. Với bộ trọng số tùy ý, cùng lập luận trên cho dạng tổng quát có trọng số:

$$a^{\theta }{b}^{1-\theta }\le \theta a+(1-\theta )b,\mathrm{\forall }a,b\ge 0,\theta \in [0,1].$$

Hölder. Với các số thực $p,q>1$ thỏa mãn điều kiện liên hợp $1/p+1/q=1$, ta có bất đẳng thức:

$$\sum _{i=1}^n|x_i{y}_i|=|x_1{y}_1|+\cdots +|x_n{y}_n|\le {(\sum _{i=1}^n|x_i{|}^p)}^{1/p}{(\sum _{i=1}^n|y_i{|}^q)}^{1/q}.$$

Phép chứng minh bất đẳng thức này quy về việc áp dụng AM–GM có trọng số với cách chuẩn hóa khéo léo: Đặt $a_i=|x_i{|}^p/\sum _{j=1}^n|x_j{|}^p$, $b_i=|y_i{|}^q/\sum _{j=1}^n|y_j{|}^q$, chọn trọng số $\theta =1/p$, rồi lấy tổng theo chỉ số $i$. Do $1/p+1/q=1$, vế phải sau khi lấy tổng bằng đúng 1, và bất đẳng thức Hölder lập tức xuất hiện. Khi $p=q=2$, ta thu được bất đẳng thức Cauchy–Schwarz quen thuộc. Kiểm tra bằng số với $x=(1,2,3)$, $y=(3,1,2)$, $p=3$, $q=1.5$: Vế trái bằng $11$, vế phải xấp xỉ $3.302\times 4.335\approx 14.31$. Với trường hợp $p=q=2$, vế phải bằng $\sqrt{14}\cdot \sqrt{14}=14$.

Bất đẳng thức Hölder là lý do chuẩn ${\ell }_p$ và chuẩn ${\ell }_q$ đối ngẫu với nhau khi $1/p+1/q=1$, đúng như cặp ${\ell }_1$ và ${\ell }_{\mathrm{\infty }}$ ở chủ đề nón đối ngẫu.

5. Những câu hỏi để đào sâu

Câu 1. Xét lập luận sau: "Một $f$ khả vi có mọi tập mức dưới đều là , do đó điểm dừng thỏa mãn $\mathrm{\nabla }f(x)=0$ ắt hẳn là cực tiểu toàn cục." Lập luận này sai lầm ở điểm nào?

Xem lời giải thích

Tập mức dưới lồi chỉ cho tính tựa lồi, và với hàm tựa lồi, bằng 0 không bảo đảm cực tiểu toàn cục. Hàm $x^3$ có mọi tập mức dưới là một nửa trục $(-\mathrm{\infty },{\alpha }^{1/3}]$, nên tựa lồi, và $f^{\prime }(0)=0$, nhưng gốc không phải cực tiểu. Điều kiện bậc nhất "gradient bằng 0 suy ra cực tiểu toàn cục" cần tính lồi thật sự, tức cần tiếp tuyến nằm dưới toàn bộ đồ thị, chứ không chỉ cần các tập mức dưới lồi.

Câu 2. Hàm $max\{f_1,f_2\}$ của hai có lồi không? Hãy trả lời chỉ bằng , không viết bất đẳng thức nào.

Xem lời giải thích

Có. Điểm $(x,t)$ nằm trên đồ thị của $max\{f_1,f_2\}$ khi và chỉ khi nó nằm trên đồ thị của cả $f_1$ lẫn $f_2$. Vậy $\mathrm{epi}max\{f_1,f_2\}=\mathrm{epi}{f}_1\cap \mathrm{epi}{f}_2$, giao của hai , nên lồi. Lập luận này dùng được cho max của bao nhiêu hàm cũng được, kể cả vô hạn, và nó là nội dung của quy tắc "supremum theo từng điểm" ở chủ đề tiếp theo. Ngược lại, $\mathrm{epi}min\{f_1,f_2\}$ là hợp của hai , thường không lồi.

Câu 3. Jensen nói $\mathbf{E}f(X)\ge f(\mathbf{E}X)$ cho $f$ lồi. Một nhà đầu tư dùng điều này để nói: "Vì $e^x$ lồi, lợi nhuận trung bình $\mathbf{E}{e}^X$ lớn hơn $e^{\mathbf{E}X}$, nên càng biến động càng có lợi." Phân tích lập luận này.

Xem lời giải thích

Bất đẳng thức đúng: Với $X$ đều trên $\{1,2,3,4\}$, $\mathbf{E}{e}^X\approx 21.20$ trong khi $e^{\mathbf{E}X}\approx 12.18$. Nhưng kết luận "biến động càng có lợi" chỉ đúng nếu điều ta quan tâm là trung bình của $e^X$. Nếu điều ta quan tâm là một hàm lõm của của cải, như logarit, thì Jensen đi theo chiều ngược lại và biến động gây thiệt. Bài học tổng quát: Jensen cho biết nhiễu tác động theo chiều nào tùy vào độ cong của hàm mà ta lấy trung bình. Với , trung bình được lợi từ nhiễu, với hàm lõm thì bị thiệt.

Câu 4. Trong ví dụ ELBO, vì sao ELBO với $q=(0.1,0.9)$ lại tốt hơn với $q=(0.5,0.5)$, dù $(0.5,0.5)$ chính là phân phối tiên nghiệm $p(z)$?

Xem lời giải thích

Biến đổi trực tiếp cho thấy khoảng cách giữa $\log p(x)$ và ELBO đúng bằng $D_{\mathrm{kl}}(q,p(\cdot \mid x))$, độ phân kỳ KL từ $q$ tới hậu nghiệm, đại lượng mà chủ đề điều kiện bậc nhất đã chứng minh là không âm. Hậu nghiệm là $(0.25,0.75)$. Phân phối $(0.1,0.9)$ lệch về cùng phía với hậu nghiệm, còn $(0.5,0.5)$ thì không nhìn dữ liệu chút nào. Tính ra, $\log p(x)-\text{ELBO}$ bằng khoảng $0.144$ với $q=(0.5,0.5)$ và $0.073$ với $q=(0.1,0.9)$, đúng bằng hai độ phân kỳ KL tương ứng.

6. Bài tập tự luyện

Bài tập 1: Một tập mức dưới

Chứng minh tập $S=\{x\in {\mathbb{R}}^2:x_1^2+2x_2^2+e^{x_1}\le 3\}$ là và khác rỗng. Tìm khoảng mà $S$ chiếm trên trục $x_1$ (giải số).

Lời giải

Hàm $f(x)=x_1^2+2x_2^2+e^{x_1}$ là tổng của các , nên lồi, và $S$ là tập mức dưới mức 3 của nó, nên lồi. Điểm $(0,0)$ cho $f=1\le 3$, nên $S$ khác rỗng. Trên trục $x_1$ (tức $x_2=0$), điều kiện là $x_1^2+e^{x_1}\le 3$. Giải số phương trình $x_1^2+e^{x_1}=3$ được hai nghiệm $x_1\approx -1.677$ và $x_1\approx 0.834$, nên $S$ cắt trục $x_1$ theo đoạn $[-1.677,0.834]$. Đoạn này lệch về bên trái vì $e^{x_1}$ tăng nhanh khi $x_1>0$.

Bài tập 2: Epigraph của 1/x như một điều kiện ma trận

Chứng minh rằng với $x>0$, $1/x\le t$ khi và chỉ khi $\left[\begin{array}{cc}x& 1\\ 1& t\end{array}\right]⪰0$. Từ đó suy ra $1/x$ lồi trên ${\mathbb{R}}_{++}$ mà không cần đạo hàm.

Lời giải

Với $x>0$, $2\times 2$ đối xứng khi và chỉ khi $x\ge 0$, $t\ge 0$ và $xt-1\ge 0$. Vì $x>0$, điều kiện cuối là $t\ge 1/x$, và nó kéo theo $t>0$. Vậy của $1/x$ là $\{(x,t):x>0\}$ giao với ảnh ngược của nón PSD qua ánh xạ affine $(x,t)\mapsto \left[\begin{array}{cc}x& 1\\ 1& t\end{array}\right]$. Giao của hai là tập lồi, nên epigraph lồi và $1/x$ lồi. Kiểm tra bằng số: Cặp giá trị $(x,t)=(2,0.5)$ cho ma trận nửa xác định dương và đúng $1/2\le 0.5$, còn $(2,0.4)$ cho ma trận có định thức âm và đúng $0.5>0.4$.

Bài tập 3: Ba khoảng cách Jensen

Cho $X$ phân phối đều trên $\{1,2,3,4\}$. Tính khoảng cách Jensen $\mathbf{E}f(X)-f(\mathbf{E}X)$ cho (a) $f(x)=x^2$, (b) $f(x)=-\log x$, (c) $f(x)=e^x$. Khoảng cách nào lớn nhất, và điều đó nói gì về độ cong của ba hàm trên đoạn $[1,4]$?

Lời giải

$\mathbf{E}X=2.5$. (a) $7.5-6.25=1.25$, bằng phương sai. (b) $\mathbf{E}(-\log X)\approx -0.795$ và $-\log 2.5\approx -0.916$, hiệu xấp xỉ $0.122$. (c) $\mathbf{E}{e}^X\approx 21.20$ và $e^{2.5}\approx 12.18$, hiệu xấp xỉ $9.02$. Khoảng cách của $e^x$ lớn nhất vì trên $[1,4]$ độ cong $f^{″}(x)=e^x$ của nó lớn hơn hẳn: Từ $e\approx 2.7$ tới $e^4\approx 54.6$, trong khi $x^2$ có độ cong không đổi bằng 2 và $-\log x$ có độ cong $1/x^2$ chỉ từ $1/16$ tới 1. Khi phân tán của $X$ nhỏ, khoảng cách Jensen xấp xỉ $\frac{1}{2}{f}^{″}(\mathbf{E}X)\mathrm{Var}(X)$, nên độ cong càng lớn thì khoảng cách càng lớn.

Tóm tắt

Tập mức dưới của luôn lồi, nhưng chiều ngược lại sai: Hàm có mọi tập mức dưới lồi chỉ là tựa lồi. Viết một tập thành tập mức dưới của một hàm lồi là cách nhanh để chứng minh nó lồi. nối hai thế giới theo cả hai chiều: Khẳng định $f$ lồi khi và chỉ khi $\mathrm{epi}f$ lồi. Từ đó, tiếp tuyến là siêu phẳng tựa của epigraph, các hàm như $x^2/y$ được chứng minh lồi bằng phần bù Schur, và mọi bài toán tối ưu có thể viết ở dạng epigraph với hàm mục tiêu tuyến tính.

Bất đẳng thức Jensen $f(\mathbf{E}X)\le \mathbf{E}f(X)$ là dạng xác suất của tính lồi. Nó giải thích vì sao phương sai không âm, vì sao sai số bình phương tách thành độ lệch và phương sai, vì sao nhiễu trung bình 0 không làm giảm một , và vì sao ELBO là một cận dưới. AM–GM và Hölder cũng chỉ là Jensen cho hàm $-\log$.

Tài liệu tham khảo

• Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press.