Một số điểm bất lợi của phương pháp Steepeset Descent

Phương pháp Steepset Descent là một phương pháp số phổ biến để tìm cực trị địa phương cho bài toán cực trị không điều kiện. Mặc dù phương pháp có một số điểm thuận lợi về lý thuyết: đưa ra hướng giảm nhanh nhất, nhưng lý do vì sao mà phương pháp này ít được sử dụng đến lại không được giải thích rõ ràng ở các tài liệu. Chính vì vậy, trong bài viết này, chúng tôi sẽ tìm hiểu một số bất lợi của phương pháp.

(Lưu ý: một số tài liệu cho rằng đây là phương pháp phổ biến, đơn giản (xem http://sces.phys.utk.edu/~moreo/mm08/XuWangP571.pdf) nhưng tài liệu khác lại đưa ra một số nhược điềm và giải thích rằng đó là lý do nó ít được sử dụng đến (xem http://www.rose-hulman.edu/~bryan/lottamath/steepest.pdf))

 

Trước hết, chúng tôi sẽ điểm qua một số điểm thuận lợi của phương pháp:

It is not hard to see why the method of steepest descent is so popular among many mathematicians: it is very simple, easy to use, and each repetition is fast. But the biggest advantage of this method lies in the fact that it is guaranteed to find the minimum through numerous times of iterations as long as it exists  (Xem http://sces.phys.utk.edu/~moreo/mm08/XuWangP571.pdf)

Sự hội tụ của phương pháp, Kantorovich Inequality, như trang 28 của tài liệu  http://www-personal.umich.edu/~mepelman/teaching/IOE511/Handouts/511notes07-7.pdf

\frac{f(u_{k+1})-f(u^{*})}{f(u_{k})-f(u^{*})} \le \left(\frac{\kappa -1}{\kappa+1}\right)^2,

trong đó \kappa là tỉ số trị riêng nhỏ nhất trên trị riêng lớn nhất của ma trận Hessian của f tại  lời giải tối ưu u{*}, hay \kappa_2(H).

Một số điểm bất lợi của phương pháp:

Cách tìm kiểm: sử dụng các từ khóa pifall, drawback, disadvantage, flaw of Steepest Descent để tìm ra các tài liệu về hạn chế một phương pháp.

Một điểm rõ ràng nhất: phương pháp này chỉ đảm bảo tính trực giao liên tiếp và chỉ tối ưu cục bộ một bước  nhưng đối với Conjugate Gradient lại cho ta tối ưu trên toàn miền không gian đã xét (tương ứng tính conjugate với các bước trước đó!).
Điều này thể hiện rõ qua hình ảnh hội tụ zigzag của phương pháp.

 

+ Hội tụ chậm

+Not scale invariant

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: