Hàm Lồi (3) – Kiểm Tra Tính Lồi | My Weblog

Trang chủ » Hàm Lồi Khi Nào » Hàm Lồi (3) – Kiểm Tra Tính Lồi | My Weblog

Có thể bạn quan tâm

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) là 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.

Vì \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 là

\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 và \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.

Chia sẻ:

  • Facebook
  • X
Thích Đang tải...

Có liên quan

Nhãn: hàm lồi, tính lồi

This entry was posted on Tháng Hai 6, 2008 at 10:38 sáng and is filed under Giải tích lồi. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Từ khóa » Hàm Lồi Khi Nào