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

Learn & Enjoy …

«
»

Tối ưu không ràng buộc (2) – Tìm kiếm trên đường thẳng (line search)

Posted by Trần Quốc Long trên Tháng Tư 22, 2008

Giả sử khi cực tiểu hóa hàm \displaystyle f(x), tại điểm \displaystyle x ta đã tìm được hướng làm giảm hàm mục tiêu \displaystyle d. Ta cần tìm bước nhảy (step size) \displaystyle t>0 sao cho

\displaystyle \phi(t)<\phi(0),

trong đó \displaystyle \phi(t)=f(x+td). Việc tìm bước nhảy \displaystyle t được gọi là tìm kiếm trên đường thẳng (line search). Rõ ràng, lý tưởng nhất là ta tìm được bước nhảy

\displaystyle t_{\mathrm{min}}=\arg\min_t \phi(t).

Việc tìm \displaystyle t_{\mathrm{min}} gọi là tìm kiếm chính xác (exact line search), còn nếu ta chỉ cần tìm \displaystyle t sao cho \displaystyle \phi(t)<\phi(0) thì ta gọi là tìm kiếm không chính xác (inexact line search).

Tìm kiếm chính xác: Bài toán chuyển về việc cực tiểu hóa hàm 1 biến \displaystyle \phi(t). Ta có thể dễ dàng tìm \displaystyle t_{\mathrm{min}} nếu \displaystyle \phi(t) là hàm tuyến tính, đa thức bậc 2. Các trường hợp khác thường được quy về việc giải phương trình

\displaystyle \phi'(t) = 0

và \displaystyle t_{\mathrm{min}} là một trong các nghiệm của phương trình trên. Một trường hợp khác có thể giải khá hiệu quả là khi

  1. Ta cần cực tiểu hóa hàm liên tục \displaystyle \phi(t) trên đoạn \displaystyle [a,b].
  2. Trên đoạn \displaystyle [a,b], hàm \displaystyle \phi(t) có dạng hình nón ngửa và chỉ có một cực tiểu duy nhất.

Phương pháp tìm cực tiểu của \displaystyle \phi(t) trong trường hợp này như sau:

  1. Chọn \displaystyle t_1,t_2 bất kì sao cho

    \displaystyle a<t_1<t_2<b

  2. Nếu \displaystyle \phi(t_1)\geq\phi(t_2), rõ ràng \displaystyle t_{\mathrm{min}} không thể nằm trong đoạn \displaystyle [a,t_1] vì nếu như vậy

    \displaystyle \phi(a)\geq \phi(t_{\mathrm{min}}) \leq \phi(t_1) \geq \phi(t_2)

    Tức là hàm \displaystyle \phi(t) không có dạng hình nón ngửa. Vậy \displaystyle t_{\mathrm{min}}\in[t_1,b]. Nói cách khác \displaystyle [t_1,b] là tập ứng cử viên mới.

  3. Nếu \displaystyle \phi(t_1)\leq\phi(t_2), tương tự như trên, ta kết luận \displaystyle [a,t_2] là tập ứng cử viên mới.
  4. Trong cả hai trường hợp, ta đều giảm được tập ứng cử viên. Tiếp tục lặp lại bước 1 cho đến khi tập ứng cử viên đủ nhỏ.

Trong phương pháp trên, dễ thấy, ta hoàn toàn tự do khi lựa chọn \displaystyle t_1, t_2. Một lựa chọn dễ thấy là chọn

\displaystyle t_1=a+\frac{b-a}{3},t_2=b-\frac{b-a}{3}

để chia đoạn \displaystyle [a,b] làm 3 đoạn thẳng bằng nhau. Để ý là tại mỗi bước lặp, ta phải tính toán giá trị \displaystyle \phi(t) hai lần tại \displaystyle t_1,t_2. Nếu ta khéo léo lựa chọn \displaystyle t_1,t_2, ta có thể giảm được số lần tính toán \displaystyle \phi(t). Ý tưởng đơn giản như sau, tại mỗi bước lặp, ta lựa chọn \displaystyle t_1,t_2 theo một tỉ lệ nhất định để trong lần lặp sau, một trong 2 giá trị của \displaystyle \phi(t_1),\phi(t_2) đã được tính toán từ lần lặp trước. Tỉ lệ này như sau

\displaystyle \rho=\frac{t_2-a}{b-a}=\frac{b-t_1}{b-a}=\frac{t_1-a}{t_2-a}=\frac{b-t_2}{b-t_1}

Dễ thấy

\displaystyle b-t_1=t_2-a=\rho(b-a)

\displaystyle b-t_2=t_1-a=b-a-(t_2-a)=(b-a)(1-\rho)

Suy ra

\displaystyle \rho=\frac{b-t_2}{b-t_1}=\frac{1-\rho}{\rho}

Giải phương trình bậc 2 này ta được

\displaystyle \rho=\frac{\sqrt{5}-1}{2}=0.6180...

Đây chính là tỉ lệ vàng (golden ratio) (có lúc người ta coi \displaystyle \frac{1}{\rho}=\frac{\sqrt{5}+1}{2}=1.6180... là tỉ lệ vàng). Để ý là, sau mỗi bước lặp, kích thước của tập ứng cử viên giảm đi theo tỉ lệ

\displaystyle \rho=\frac{t_2-a}{b-a}=\frac{b-t_1}{b-a}

nên phương pháp này còn được gọi là phương pháp phân chia theo tỉ lệ vàng (golden search). Tốc độ hội tụ của các phương pháp phân chia theo tỉ lệ cố định là tuyến tính.

Tìm kiếm không chính xác: Phép kiểm tra Armijo (Armijo’s test) cho phép kiểm tra bước nhảy \displaystyle t có làm giảm hàm mục tiêu quá một ngưỡng cho trước hay không. Phép kiểm tra này như sau:

  1. Bước nhảy \displaystyle t>0 được gọi là thích hợp (appropriate) nếu

    \displaystyle \phi(t)\leq \phi(0) + \epsilon t \phi'(0)

    với \displaystyle 0<\epsilon<1.

  2. Bước nhảy \displaystyle t>0 được gọi là tốt nhất (nearly maximal) nếu

    \displaystyle \phi(\nu t)> \phi(0)+\epsilon \nu t \phi'(0)

    với \displaystyle \nu>1.

  3. Bước nhảy \displaystyle t_{\mathrm{Armijo}} gọi là bước nhảy Armijo nếu nó thích hợp và tốt nhất.

Nhận xét:

  1. Nếu \displaystyle \phi'(0)<0, bước nhảy thích hợp chắc chắn sẽ làm giảm hàm mục tiêu vì

    \displaystyle \phi(t)\leq \phi(0) + \epsilon t \phi'(0) < \phi(0)

  2. Như vậy, khi \displaystyle \phi'(0)<0, bước nhảy Armijo \displaystyle t_{\mathrm{Armijo}} chắc chắn sẽ làm giảm hàm mục tiêu nhưng \displaystyle \nu t_{\mathrm{Armijo}}>t_{\mathrm{Amijo}} không còn là bước nhảy thích hợp nữa (đây là lý do ta gọi bước nhảy Armijo là tốt nhất).

Thuật toán tìm bước nhảy Armijo: Ta đã biết, khi \displaystyle \phi'(0)<0 thì chắc chắn tồn tại \displaystyle t>0 sao cho \displaystyle \phi(t)<\phi(0). Thuật toán sau đây cho phép tìm ra bước nhảy Armijo (với tham số \displaystyle \epsilon,\nu) khi \displaystyle \phi(t) bị chặn dưới và \displaystyle \phi'(0)<0:

  1. Bắt đầu với một bước nhảy \displaystyle t_0>0 bất kì.
  2. Nếu \displaystyle t_0 là bước nhảy thích hợp, lần lượt kiểm tra các bước nhảy \displaystyle \nu t_0,\nu^2 t_0,\nu^3 t_0,\ldots đến khi gặp một bước nhảy không thích hợp. Bước nhảy trước đó chính là bước nhảy Amijo.
  3. Nếu \displaystyle t_0 không phải là bước nhảy thích hợp, lần lượt kiểm tra các bước nhảy \displaystyle \nu^{-1} t_0,\nu^{-2}t_0,\nu^{-3}t_0,\ldots đến khi gặp một bước nhảy thích hợp. Bước nhảy này chính là bước nhảy Amijo.

Chứng minh: Nếu thuật toán chạy vào bước 2, việc kiểm tra các bước nhảy phải dừng vì nếu

\displaystyle \nu^nt_0\rightarrow \infty và \displaystyle \phi(\nu^nt_0)\leq \phi(0)+\epsilon\nu^nt_0\phi'(0)

thì do \displaystyle \phi'(0)<0 nên \displaystyle \phi(\nu^nt_0)\rightarrow -\infty, tức là \displaystyle \phi(t) không bị chặn, mâu thuẫn.

Nếu thuật toán chạy vào bước 3, ta có

\displaystyle \phi(t)=\phi(0)+t\phi'(0)+\Theta(t^2)

Do \displaystyle 0<\epsilon<1, nên khi \displaystyle t>0 đủ nhỏ, ta có

\displaystyle t\phi'(0)+\Theta(t^2)<\epsilon t\phi'(0)

Rõ ràng

\displaystyle \nu^{-n}t_0\rightarrow 0

nên đến một lúc nào đó \displaystyle \nu^{-n}t_0 sẽ đủ nhỏ để

\displaystyle \phi(\nu^{-n}t_0)\leq \phi(0)+\epsilon \nu^{-n}t_0\phi'(0)

tức là việc kiểm tra cũng dừng.

Advertisements

This entry was posted on Tháng Tư 22, 2008 lúc 7:16 chiều and is filed under Quy hoạch phi tuyến. Tagged: , , , , , , , , , . You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, hoặc trackback from your own site.

Trả lờ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:

Gravatar
WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com ( Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter ( Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook ( Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ ( Đăng xuất / Thay đổi )

Hủy bỏ

Connecting to %s

«
»
 
%d bloggers like this: