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

Learn & Enjoy …

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

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

Để chứng minh tính lồi của một hàm, ngoài việc dùng định nghĩa, ta có thể dựa vào một số biến đổi giữ nguyên tính lồi để xây dựng nên hàm lồi mới hoặc chứng minh tính lồi của hàm.

Tổ hợp tuyến tính với hệ số dương: \sum_{i=1}^n a_i f_i(x) lồi nếu f_i(x) lồi và a_i\geq 0 với mọi i.

Chứng minh:

(i) Hiển nhiên, ta có \lambda f(x) lồi nếu f(x) lồi và \lambda\geq 0

(ii) Cũng dễ thấy f(x)+g(x) lồi nếu f(x),g(x) lồi.

(iii) Từ (i) và (ii) suy ra \sum_{i=1}^n a_i f_i(x) lồi nếu f_i(x) lồi và a_i\geq 0 với mọi i.

Lấy supremum: \displaystyle g(x)=\sup_\alpha f_\alpha(x) lồi nếu f_\alpha(x) lồi với mọi \alpha.

Chứng minh: Rõ ràng \displaystyle \mathrm{epi}g = \bigcap_\alpha\mathrm{epi}f_\alpha. Do đó \mathrm{epi}g lồi vì nó là giao của các tập lồi.

Tổ hợp hàm: f_i(x), i=1,\ldots,m lồi, F(y) lồi trên R^m và đồng biến thì g(x)=F(f_1(x),\ldots,f_m(x)) lồi trên \displaystyle\mathrm{Dom}g=\bigcap_i \mathrm{Dom}f_i.

Chứng minh: Nếu x,y\in\mathrm{Dom}g, ta có

\lambda g(x)+(1-\lambda)g(y)=\lambda F(f_1(x),\ldots,f_m(x))+(1-\lambda)F(f_1(y),\ldots,f_m(y))

\geq F(\lambda f_1(x)+(1-\lambda)f_1(y),\ldots,\lambda f_m(x)+(1-\lambda)f_m(y))

\geq F(f_1(\lambda x+(1-\lambda)y),\ldots,f_m(\lambda x+(1-\lambda)y))=g(\lambda x+(1-\lambda)y)

Nhận xét: Nếu f_i(x) là hàm affine, f_i(x)=A_i x+b_i, thì F không cần phải đồng biến, ta vẫn có g(x) lồi.

Lấy minimum: Nếu f(x,y) lồi và g(x)=\inf_y f(x,y)>-\infty thì g(x) cũng lồi.

Chứng minh: Nếu x, y\in\mathrm{Dom}g, suy ra với mọi \epsilon>0, tồn tại x',y' sao cho

g(x)\geq f(x,x')-\epsilong(y)\geq f(y,y')-\epsilon

Ta có

\lambda g(x)+(1-\lambda)g(y)\geq\lambda f(x,x')+(1-\lambda)f(y,y')-\epsilon

\geq f(\lambda x+(1-\lambda)y,\lambda x'+(1-\lambda)y')-\epsilon\geq g(\lambda x+(1-\lambda)y)-\epsilon.

Bất đẳng thức trên đúng với mọi \epsilon>0, vậy ta có

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

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: