Hàm lồi (1) – Định nghĩa và tính chất cơ bản « CS Study Fun

Tháng Hai 2008
T2	T3	T4	T5	T6	T7	CN
		Tháng 3 »
	1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29

Hàm lồi (1) – Định nghĩa và tính chất cơ bản

Đăng bởi tqlong on Tháng Hai 5, 2008

Định nghĩa (hàm lồi): Hàm $f$ trên $\mathbb{R}^n$ lồi nếu

Miền xác định $\mathrm{Dom}f$ lồi.
$x,y\in \mathrm{Dom}f: f(\lambda x+(1-\lambda)y)\leq\lambda f(x)+(1-\lambda)f(y)$ (*)

Định nghĩa tương đương: $f$ lồi nếu tập

$\mathrm{epi}f = \{(x,t)\in \mathbb{R}^{n+1}:f(x)\leq t\}$

gọi là epigraph của $f$ là tập lồi trong $\mathbb{R}^{n+1}$ (epi – có nghĩa là bên trên, phía trên).

Chứng minh:

“ $\mathrm{epi}f$ lồi $\Rightarrow f$ lồi”: $x,y\in\mathrm{Dom}f$ , suy ra $(x,f(x)), (y,f(y))\in\mathrm{epi}f$ . Vì $\mathrm{epi}f$ lồi nên $\lambda (x,f(x))+(1-\lambda)(y,f(y))\in\mathrm{epi}f$ . Nghĩa là

$f(\lambda x+(1-\lambda)y)\leq\lambda f(x)+(1-\lambda)f(y)$

“ $f$ lồi $\Rightarrow\mathrm{epi}f$ lồi”: Nếu $(x,y),(z,t)\in\mathrm{epi}f$ , suy ra $y\geq f(x), t\geq f(z)$ , ta có

$\Rightarrow\lambda y+(1-\lambda)t\geq\lambda f(x)+(1-\lambda)f(z)\geq f(\lambda x+(1-\lambda)z)$

Nghĩa là $(\lambda x+(1-\lambda)z, \lambda y+(1-\lambda)t)\in\mathrm{epi}f$ .

Ý nghĩa: Với $x<z<y, z=\lambda x+(1-\lambda)y, 0<\lambda<1$ , ta có

$||y-x||:||y-z||:||z-x||=1:\lambda:1-\lambda$

Nếu $f$ lồi thì

$\mathrm{slope}_f(x,z)\leq\mathrm{slope}_f(x,y)\leq\mathrm{slope}_f(y,z)$

$\displaystyle\frac{f(z)-f(x)}{||z-x||}\leq\frac{f(y)-f(x)}{||y-x||}\leq\frac{f(y)-f(z)}{||y-z||}$

Ví dụ:

Hàm mũ chẵn: $x^2,x^4,\ldots$ .
Hàm lũy thừa: $e^x$ .
Nếu $x\in R^+$ : $x^p,p\geq 1$ ; $-x^p, 0\leq p\leq 1$ .
Nếu $x\in R^n$ : hàm affine $a^Tx+b$ , chuẩn $||x||$ .

Định lý (Bất đẳng thức Jensen): Nếu $f$ lồi và $x_i\in\mathrm{Dom}f,\lambda_i\geq 0,\sum_{i=1}^n\lambda_i=1$

$\sum_{i=1}^n f(\lambda_i x_i)\leq\sum_{i=1}^n \lambda_i f(x_i)$

Chứng minh: Chứng minh bằng quy nạp theo $n$ .

Mở rộng: Nếu $\mathrm{Dom}f$ đóng, $\mu(x)$ là phân bố xác suất trên đó đồng thời $f$ liên tục.

$f(\mathrm{E}_\mu x)\leq \mathrm{E}_\mu f(x)$ .

Ví dụ: Khoảng cách Kullback-Leibler giữa hai phân bố

$\displaystyle\int_{R^n}\ln\frac{p(x)}{q(x)}p(x)dx \geq 0$

Chứng minh:

$\displaystyle\int_{R^n}\ln\frac{p(x)}{q(x)}p(x)dx = \int_{R^n}-\ln\frac{q(x)}{p(x)}p(x)dx = \mathrm{E}_p\left(-\ln\frac{q(x)}{p(x)}\right)$

$\displaystyle\geq -\ln E_p\frac{q(x)}{p(x)} = -\ln\int_{R^n}\frac{q(x)}{p(x)}p(x)dx= -\ln\int_{R^n}q(x)dx=-\ln 1=0$

Chứng minh trên áp dụng bất đẳng thức Jensen cho hàm lồi $-\ln(x)$ .

Định nghĩa (Mở rộng hàm lồi trên toàn $\mathbb{R}^n$ ):

$f(x)=\begin{cases}f(x)&x\in\mathrm{Dom}f\\+\infty&x\notin\mathrm{Dom}f\end{cases}$

Lưu ý: tính chất (*) vẫn giữ nguyên nếu áp dụng các luật tính toán sau với giá trị $+\infty$

$a+(+\infty)=a.(+\infty)=+\infty, 0.(+\infty)=0$
$a\leq(+\infty)\leq(+\infty)$

Bài viết này được đăng vào Tháng Hai 5, 2008 lúc 10:42 chiều và tập tin được lưu ở Giải tích lồi. Tagged: hàm lồi, Jensen, Kullback-Leibler. Bạn có thể theo dõi các phản hồi của bài viết này thông qua RSS 2.0 dòng thông tin. Bạn có thể Để lại lời nhắn, hoặc trackback từ trang của bạn.

Để lại hồi âm

« Bài toán đối ngẫu

Hàm lồi (2) – Biến đổi giữ nguyên tính lồi »

	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Phân lớp bằng siêu phẳng (1) …
	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Bất đẳng thức xác suất (1) …
	H.T.D. trong bài Bất đẳng thức xác suất (1) …

CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Phân loại

Lưu trữ

Thống kê

Bài gần đây

Lời bình gần đây

Trang

Blogroll

Quản trị

Lịch

Theo dõi

Blog D.Q. Huy

Các phương pháp điểm trong

Xem nhiều nhất

Từ khóa

Hàm lồi (1) – Định nghĩa và tính chất cơ bản

Để lại hồi âm