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

Learn & Enjoy …

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

Posted by Trần Quốc Long 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 ftậ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)

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: