Các thuật toán cho vấn đề lồi
Phương pháp xuống dốc nhất
Phương pháp này còn được gọi là phương pháp Gradient hoặc phương pháp Cauchy. Phương pháp này liên quan đến các thuật ngữ sau:
$$ x_ {k + 1} = x_k + \ alpha_kd_k $$
$ d_k = - \ bigtriangledown f \ left (x_k \ right) $ hoặc $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $
Cho $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $
Bằng cách phân biệt $ \ phi $ và cân bằng nó với 0, chúng ta có thể nhận được $ \ alpha $.
Vì vậy, thuật toán diễn ra như sau:
Khởi tạo $ x_0 $, $ \ varepsilon_1 $, $ \ varepsilon_2 $ và đặt $ k = 0 $.
Đặt $ d_k = - \ bigtriangledown f \ left (x_k \ right) $ hoặc $ d_k = - \ frac {\ bigtriangledown f \ left (x_k \ right)} {\ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ |} $.
tìm $ \ alpha_k $ sao cho nó thu nhỏ $ \ phi \ left (\ alpha \ right) = f \ left (x_k + \ alpha d_k \ right) $.
Đặt $ x_ {k + 1} = x_k + \ alpha_kd_k $.
Nếu $ \ left \ | x_ {k + 1-x_k} \ right \ | <\ varepsilon_1 $ hoặc $ \ left \ | \ bigtriangledown f \ left (x_ {k + 1} \ right) \ right \ | \ leq \ varepsilon_2 $, hãy chuyển sang bước 6, nếu không thì đặt $ k = k + 1 $ và chuyển sang bước 2.
Giải pháp tối ưu là $ \ hat {x} = x_ {k + 1} $.
Phương pháp Newton
Phương pháp Newton hoạt động dựa trên nguyên tắc sau:
$ f \ left (x \ right) = y \ left (x \ right) = f \ left (x_k \ right) + \ left (x-x_k \ right) ^ T \ bigtriangledown f \ left (x_k \ right) + \ frac {1} {2} \ left (x-x_k \ right) ^ TH \ left (x_k \ right) \ left (x-x_k \ right) $
$ \ bigtriangledown y \ left (x \ right) = \ bigtriangledown f \ left (x_k \ right) + H \ left (x_k \ right) \ left (x-x_k \ right) $
Tại $ x_ {k + 1}, \ bigtriangledown y \ left (x_ {k + 1} \ right) = \ bigtriangledown f \ left (x_k \ right) + H \ left (x_k \ right) \ left (x_ {k +1} -x_k \ right) $
Để $ x_ {k + 1} $ là giải pháp tối ưu thì $ \ bigtriangledown y \ left (x_k + 1 \ right) = 0 $
Do đó, $ x_ {k + 1} = x_k-H \ left (x_k \ right) ^ {- 1} \ bigtriangledown f \ left (x_k \ right) $
Ở đây $ H \ left (x_k \ right) $ không phải là số ít.
Do đó thuật toán diễn ra như sau:
Step 1 - Khởi tạo $ x_0, \ varepsilon $ và đặt $ k = 0 $.
Step 2 - tìm $ H \ left (x_k \ right) \ bigtriangledown f \ left (x_k \ right) $.
Step 3 - Giải hệ tuyến tính $ H \ left (x_k \ right) h \ left (x_k \ right) = \ bigtriangledown f \ left (x_k \ right) $ cho $ h \ left (x_k \ right) $.
Step 4 - tìm $ x_ {k + 1} = x_k-h \ left (x_k \ right) $.
Step 5- Nếu $ \ left \ | x_ {k + 1} -x_k \ right \ | <\ varepsilon $ hoặc $ \ left \ | \ bigtriangledown f \ left (x_k \ right) \ right \ | \ leq \ varepsilon $ sau đó chuyển sang bước 6, nếu không thì đặt $ k = k + 1 $ và chuyển sang bước 2.
Step 6 - Giải pháp tối ưu là $ \ hat {x} = x_ {k + 1} $.
Phương pháp Gradient Liên hợp
Phương pháp này được sử dụng để giải các bài toán thuộc các dạng sau:
$ min f \ left (x \ right) = \ frac {1} {2} x ^ T Qx-bx $
trong đó Q là ma trận nXn xác định dương và b là hằng số.
Cho $ x_0, \ varepsilon, $ compute $ g_0 = Qx_0-b $
Đặt $ d_0 = -g_0 $ cho $ k = 0,1,2, ..., $
Đặt $ \ alpha_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Q d_k} $
Tính $ x_ {k + 1} = x_k + \ alpha_kd_k $
Đặt $ g_ {k + 1} = g_k + \ alpha_kd_k $
Tính $ \ beta_k = \ frac {g_ {k} ^ {T} g_k} {d_ {k} ^ {T} Qd_k} $
Tính $ x_ {k + 1} = x_k + \ alpha_kd_k $
Đặt $ g_ {k + 1} = x_k + \ alpha_kQd_k $
Tính $ \ beta_k = \ frac {g_ {k + 1} ^ {T} g_ {k + 1}} {g_ {k} ^ {T} gk} $
Đặt $ d_ {k + 1} = - g_ {k + 1} + \ beta_kd_k $.