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

Learn & Enjoy …

Hàm lồi (3) – Kiểm tra tính lồi

Posted by Trần Quốc Long on Tháng Hai 6, 2008

Hàm lồi trong phần này sử dụng định nghĩa hàm lồi mở rộng.

Định lý (Tính chất lồi có tính một chiều):

f(x) lồi khi và chỉ khi g(t)=f(x+th) lồi với mọi x và mọi hướng h.

Chứng minh:

\Rightarrow“: Nếu f(x), do g(t)tổ hợp của f(x) và hàm affine ht+x, nên g(t) cũng lồi.

\Leftarrow“: Nếu g(t)=f(x+th) lồi với mọi x và mọi hướng h, lấy 2 điểm bất kì x,y\in\mathrm{Dom}f, chọn h=y-x, ta có

\lambda f(x)+(1-\lambda)f(y)=\lambda g(0)+(1-\lambda)g(1)

\geq g(1-\lambda)=f(x+(1-\lambda)(y-x))=f(\lambda x+(1-\lambda)y).

Nhận xét: Việc kiểm tra tính lồi của một hàm có thể quy về kiểm tra tính lồi theo hướng bất kì.

Điều kiện để hàm 1 biến \phi(x): \mathrm{R}\rightarrow\mathrm{R} lồi:

Định lý (Điều kiện cần và đủ): Với mọi x < y

\displaystyle\phi'(x)\leq\frac{\phi(y)-\phi(x)}{y-x}\leq\phi'(y)

Nghĩa là đạo hàm của \phi(x) không giảm trên miền xác định.

Chứng minh:

\Rightarrow“: Ta có

\displaystyle\frac{\phi(z)-\phi(x)}{z-x}\leq\frac{\phi(y)-\phi(x)}{y-x}\leq\frac{\phi(y)-\phi(z)}{y-z}

với mọi x < z < y. Cho z\rightarrow x^+ rồi cho z\rightarrow y^- ta có điều phải chứng minh.

\Leftarrow“: Nếu x < z < y, ta có

\displaystyle\frac{\phi(z)-\phi(x)}{z-x}=\phi'(\nu) với x\leq\nu\leq z.

\displaystyle\frac{\phi(y)-\phi(z)}{y-z}=\phi'(\zeta) với z\leq\zeta\leq y.

\nu\leq\zeta nên \phi'(\nu)\leq\phi'(\zeta) theo giả thiết, do đó ta có điều phải chứng minh.

\displaystyle\frac{\phi(z)-\phi(x)}{z-x}\leq\frac{\phi(y)-\phi(z)}{y-z}

Định lý (Điều kiện đủ): Nếu đạo hàm bậc hai \phi''(x) tồn tại và không âm thì \phi(x) lồi.

Chứng minh: \phi''(x) tồn tại và không âm chứng tỏ \phi'(x) không giảm, suy ra \phi(x) lồi.

Định lý (Điều kiện đủ cho hàm nhiều biến f): \mathrm{Dom}f\subset\mathrm{R}^n\rightarrow\mathrm{R} lồi: Nếu ma trận Hessian \nabla^2 f=\left[\frac{\partial^2f}{\partial x_i\partial x_j}\right] xác định không âm thì f(x) lồi.

Chứng minh: Đặt g(t)=f(x+th) với x,x+th\in\mathrm{Dom}f. Đạo hàm bậc 1 và bậc 2 của f tại x theo hướng h

\displaystyle\mathrm{D}f[h]=\left.\frac{\partial g}{\partial t}\right|_{t=0}=\nabla f^T h, \displaystyle\mathrm{D}^2f[h]=\left.\frac{\partial^2 g}{\partial t^2}\right|_{t=0}=h^T\nabla^2 f h

Nếu \nabla^2 f xác định không âm, \displaystyle\mathrm{D}^2f[h]=h^T\nabla^2 f h\geq 0 với mọi hướng h, nghĩa là f lồi.

Ví dụ: \displaystyle f(x)=\ln\left(\sum_{i=1}^n e^{x_i}\right) lồi trên R^n.

Nhận xét: Tuy e^{x_i} là hàm lồi, \ln(x) đồng biến nhưng lại là hàm lõm (-\ln(x) lồi) nên ta không thể dùng phương pháp tổ hợp để chứng minh hàm đã cho lồi.

Chứng minh: Tính đạo hàm bậc hai theo hướng h bất kì:

\displaystyle\frac{\partial f}{\partial x_i}=\frac{e^{x_i}}{\sum_{i=1}^n e^{x_i}},

\displaystyle\frac{\partial^2 f}{\partial x_i\partial x_j}=\begin{cases}\displaystyle\frac{e^{x_i}}{\sum_{i=1}^n e^{x_i}}-\frac{e^{x_i}e^{x_i}}{\left(\sum_{i=1}^n e^{x_i}\right)^2}&i=j\\\displaystyle-\frac{e^{x_i}e^{x_j}}{\left(\sum_{i=1}^n e^{x_i}\right)^2}&i\neq j\end{cases}

\displaystyle\mathrm{D}^2f[h]=h^T\nabla^2 f h=-\left(\frac{\sum_{i=1}^n e^{x_i}h_i}{\sum_{i=1}^n e^{x_i}}\right)^2+\frac{\sum_{i=1}^n e^{x_i}h_i^2}{\sum_{i=1}^n e^{x_i}}

Để thấy được \displaystyle\mathrm{D}^2f[h]\geq 0, đặt p_i=\frac{e^{x_i}}{\sum_{i=1}^n e^{x_i}}, ta có

\displaystyle\mathrm{D}^2f[h]=-\left(\sum_{i=1}^n p_i h_i\right)^2+\sum_{i=1}^n p_i h_i^2.

Do p_i\geq 0\sum_{i=1}^n p_i=1, đồng thời hàm x^2 lồi, ta có \sum_{i=1}^n p_i h_i^2\geq\left(\sum_{i=1}^n p_i h_i\right)^2, điều phải chứng minh.

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: