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

Learn & Enjoy …

Hàm lồi (5) – Tính chất của cực đại

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

Định lý: Nếu hàm lồi f đạt cực đại tại x^*\in\mathrm{rintDom}f thì f là hằng số trên \mathrm{Dom}f.

Chứng minh: Xét điểm x\in\mathrm{Dom}f, ta sẽ chứng minh f(x)=f(x^*). Thật vậy, vì x^*\in\mathrm{rintDom}f nên với \epsilon>0 đủ nhỏ, ta có z=x^*-\epsilon(x-x^*)\in\mathrm{Dom}f. Hiển nhiên ta có

x^* = \frac{1}{1+\epsilon}z+\frac{\epsilon}{1+\epsilon}x

tức là x^* nằm bên trong đoạn thẳng (x,z). Vậy

f(x^*)\leq\frac{1}{1+\epsilon}f(z)+\frac{\epsilon}{1+\epsilon}f(x)

\Rightarrow f(x^*)-\frac{1}{1+\epsilon}f(z)\leq\frac{\epsilon}{1+\epsilon}f(x)

f(z)\leq f(x^*) nên \frac{\epsilon}{1+\epsilon}f(x)\geq \frac{\epsilon}{1+\epsilon}f(x^*), tức là f(x)\geq f(x^*). Suy ra f(x)= f(x^*).

Định lý (tồn tại điểm cực biên là cực đại): Nếu hàm lồi f đạt giá trị cực đại trên tập \mathrm{Dom}f không chứa đường thẳng thì trong các cực đại có một điểm cực biên của \mathrm{Dom}f.

Chứng minh: Xét điểm z\in\mathrm{Dom}f là cực đại của f. Nếu z là điểm cực biên, z\in\mathrm{ExtDom}f thì ta có điều phải chứng minh. Nếu z không phải là điểm cực biên, z \notin \mathrm{ExtDom}f, ta xét 2 trường hợp

  1. z\in\mathrm{rintDom}f, theo định lý trên, f là hằng số trên \mathrm{Dom}f, tức là f cũng đạt cực đại trên một điểm cực biên nào đó của \mathrm{Dom}f (điểm này luôn tồn tại do \mathrm{Dom}f là tập lồi không chứa đường thẳng).
  2. z\in\partial\mathrm{Dom}f. Xét siêu phẳng \Pi qua z đỡ lấy \mathrm{Dom}f. Xét tập S=\Pi\cap\mathrm{Dom}f. Rõ ràng z cũng là cực đại của f trên S đồng thời \dim S<\dim \mathrm{Dom}fz \notin \mathrm{Ext}S\mathrm{Ext}S \subset \mathrm{ExtDom}f. Áp dụng lập luận ở (1) và (2) ta lại giảm được \dim S, đến khi \dim S=0, tức là S=\emptyset, vô lý vì z\in S. Như vậy đến một bước nào đó ta phải có z\in \mathrm{rint}S và ta có kết luận ở bước (1).

Định lý (hàm lồi bị chặn trên đa diện lồi có cực đại): Nếu hàm lồi f bị chặn trên trong đa diện lồi Q=\{x:Ax\leq b\} thì f đạt cực đại trên Q.

Chứng minh: Theo định lý về cấu trúc của đa diện lồi, ta có

Q=\mathrm{Conv}V+\mathrm{Cone}D

trong đó, V,D là hai tập hữu hạn.

Bổ đề: Nếu f bị chặn trên và r\in\mathrm{Cone}D thì f(x+tr)\leq f(x), \forall x\in Q, t\geq 0. Nghĩa là g(t)=f(x+tr), t\geq 0 là hàm không tăng với mọi x\in Q,r\in\mathrm{Cone}D.

Chứng minh: Giả sử ngược lại, tồn tại r\in\mathrm{Cone}D, x\in Q, t\geq 0, sao cho f(x+tr)> f(x). Rõ ràng, ta có t\neq 0. Xét y=x+sr với s > t. Vì x+tr=\displaystyle\left(1-\frac{t}{s}\right)x+\frac{t}{s}(x+sr) nên

\displaystyle f(x+tr)\leq\left(1-\frac{t}{s}\right)f(x)+\frac{t}{s}f(x+sr)

\displaystyle f(x+tr)-\left(1-\frac{t}{s}\right)f(x)\leq \frac{t}{s}f(x+sr)

Nhân hai vế với \displaystyle\frac{s}{t} ta được f(x+sr)\geq\displaystyle \frac{s}{t}(f(x+tr)-f(x))+f(x). Nghĩa là g(s)=f(x+sr) lớn hơn hàm tuyến tính của s với hệ số dương, nói cách khác g(s) không bị chặn trên, mâu thuẫn với giả thiết.

Tiếp tục chứng minh định lý: Ta sẽ chứng minh f(x)\leq\displaystyle\max_{v\in V} f(v),\forall x\in Q.

Thật vậy, với mọi x\in Q, ta có thể viết x dưới dạng

\displaystyle x=\sum_{i=1}^n\lambda_i v_i+r

trong đó \lambda_i\geq 0, \displaystyle\sum_{i=1}^n\lambda_i=1,v_i\in V,r\in\mathrm{Cone}D. Theo bổ đề trên ta có

\displaystyle f(x)\leq f\left(\sum_{i=1}^n\lambda_i v_i\right)\leq \sum_{i=1}^n\lambda_i f(v_i)\leq\max_{v\in V}f(v).

Tức là, cực đại của f trên tập hữu hạn V\subset Q cũng là cực đại của f trên Q.

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: