CHƯƠNG 1: THUẬT TOÁN BFGS 1. Thuật toán Newton 1. Thuật toán Newton cho hàm một biến Phương pháp Newton [1], [2], [3] được đặt tên theo Isaac Newton và Joseph Paphson, là một phương pháp tìm nghiệm xấp xỉ gần đúng của một hàm số thực.1) Thuật toán Newton được thực thi như sau: Giả sử hàm f có đạo hàm liên tục. Bắt đầu bởi số thực x, với đạo hàm f ' và một số gần đúng x0 khá gần với nghiệm x * của phương trình f ( x ) 0 , ta tìm được một điểm x1 gần với nghiệm x * hơn x0 xác định như sau: f ( x0 ) x1 x0 (1.
Quá trình này cứ thế được lặp lại với: f ( xn ) xn 1 xn (1.3) f '( xn ) cho đến khi dãy điểm hội tụ về nghiệm x *. Khả năng tốc độ hội tụ của phương pháp Newton phụ thuộc nhiều vào giá trị khởi tạo ban đầu x0. Giá trị x0 càng gần với nghiệm thực tế của phương trình (1.1) thì thuật toán Newton hội tụ càng nhanh. Trong trường hợp phương trình không có nghiệm, phương pháp này cũng không thể phát hiện ra.
Một điểm hạn chế nữa là do yêu cầu tính đạo hàm của hàm số, phương pháp này sẽ gặp khó khăn trong trường hợp việc tính toán đạo hàm phức tạp. Trong trường hợp này, người ta có thể xấp xỉ việc tính đạo hàm bằng các phương pháp số khác. 11 Khóa luận tốt nghiệp 1. Thuật toán Newton cho nhiều biến Bây giờ xét bài toán tìm nghiệm của hệ n phương trình sau: f1 ( x1 , x2 , , xn ) 0 f ( x , x , , x ) 0 (1., xn ) là nghiệm của hệ phương trình * * * * (1.
Mở rộng từ thuật toán Newton cho hàm một biến, bắt đầu từ điểm x (1 ) ta lấy vi phân hành đạo hàm từng phần mỗi phương trình fi : n f f i f df i ( x (1) ) dx1 i dxn j dxi .5) x1 xn i 1 xi Ta tiến hành tính xấp xỉ hiệu fi ( x ) fi ( x ) như sau: (2) (1) n f fi ( x(2) ) fi ( x(1) ) j xi(2) xi(1) , i {1,2,, n}.6) i 1 xi Gọi x ( k ) là giá trị xấp xỉ của nghiệm x * ở lần lặp thứ k. Ta mong muốn fi (x (k 1) ) 0 , do đó hệ n phương trình (1.6) có thể viết dưới dạng ma trận: J ( k ) x ( k ) R ( k ) , (1.9) 12 Khóa luận tốt nghiệp và x ( k ) x ( k 1) x ( k ) .10) Do đó nghiệm tại bước thứ k 1 là x( k 1) x( k ) x( k ) .11) Tổng quát lại ta có thuật toán Newton cho hệ n phương trình như sau: (1) 1. Khởi tạo điểm ban đầu x. Tính ma trận Jacobi và vector thặng dư.
Giải phương trình (1.7) bằng các phương pháp trong đại số tuyến tính, 4. Cập nhật x mới theo (1. Lặp lại bước 2 đến bước 4 nếu kết quả còn chưa hội tụ. Hạn chế của thuật toán Newton Điểm khởi tạo phải rất gần với nghiệm thực.
Ý tưởng của Newton là dựa vào triển khai Taylor của hàm số f(x) tới đạo hàm thứ nhất 0 f ( x* ) f ( xt ) f '( xt )( xt x* ) (1.12) để từ đó tính ra ngiệm xấp xỉ. Nhận xét rằng trong việc giải phương trình f ( x ) 0 , chúng ta có đạo hàm ở mẫu số. Khi đạo hàm này gần với 0, ta sẽ được một đường thẳng song song với trục hoành. Ta sẽ hoặc không tìm được giao điểm, hoặc được một giao điểm ở vô cùng.
Đặc biệt khi nghiệm chính là điểm có đạo hàm bằng 0, thuật toán gần như sẽ không tìm được nghiệm. Khi áp dụng thuật tóa Newton cho bài toán tối ưu trong không gian nhiều chiều, chúng ta cần tính nghịch đảo của ma trận Hessian. Khi số chiều và số điển dữ liệu lớn, đạo hàm bậc hai của hàm f ( x ) là một ma trận rất lớn, ảnh hưởng tới cả bộ nhớ và tốc độ tính toán của hệ thống. Thuật toán Quasi-Newton Thuật toán quasi-Newton [4], [5], [6] là thuật toán dùng để tìm số nghiệm hoặc đi tìm cực trị của các hàm số, như là một thuật toán thay thế cho thuật toán Newton.
Thuật toán 13 Khóa luận tốt nghiệp quasi-Newton có thể được sử dụng nếu ma trận Jacobian hoặc Hessian không có sẵn hoặc quá khó khăn để tính toán được. Việc tìm tối thiểu hoặc tối đa của hàm có giá trị vô hướng không khác gì việc tìm kiếm các số 0 của gradient của hàm đó, các phương pháp quasi-Newton có thể dễ dàng tìm cực trị của hàm. Nói cách khác, nếu g là gradient của hàm số f , sau đó tìm kiếm các số 0 của hàm có giá trị véc tơ g tương ứng với việc tìm kiếm cực trị của hàm số f , ma trận Jacobi của g bây giờ thành Hessian của f. Sự khác biệt chính là ma trận Hessian là một ma trận đối xứng, không giống như Jacobi khi tìm kiếm các số 0.
Hầu hết trong các bài toán tối ưu hóa đều khác thác tính chất này. Thuật toán Quasi-Newton dựa trên thuật toán Newton để tìm điểm dừng của hàm, trong gradient là 0. Phương pháp của Newton giả định rằng các hàm có thể xấp xỉ cục bộ như một phương trình bậc hai quanh vùng tối ưu và sử dụng điểm thứ nhất và thứ hai đạo hàm để tìm điểm dừng. Ở các chiều cao hơn, thuật toán Newton sử dụng gradient và ma trận Hessian của các đạo hàm thứ hai của các hàm chức năng được giảm thiểu.
Trong các thuật toán Quasi-Newton, ma trận Hessian không cần phải tính toán. Thay vào đó, ma trận Hessian được cập nhật bằng cách phân tích các véc tơ gradient liên tiếp. Các thuật toán Quasi-Newton là một khái quát của thuật toán secant để tìm ra gốc của đạo hàm đầu tiên cho các hàm đa chiều. Trong nhiều chiều, phương trình secant được xác định dưới mức và các thuật toán quasi-Newton khác nhau về cách cập nhật, thông thường bằng cách thêm một lần cập nhật thứ hạng đơn giản vào ước tính hiện tại của ma trận Hessian.
Trong thuật toán Newton, người ta sử dụng xấp xỉ bậc hai để tìm mức tối thiểu của hàm số f ( x ). Triển khai Taylor của f ( x ) ta được: 1 f ( xk x) f ( xk ) f ( xk )T xT Bx (1.13) 2 Ở đây f là gradient và B là ma trận xỉ với ma trận Hessian. Gradient của xấp xỉ này là: 14 Khóa luận tốt nghiệp f (xk x) f (xk ) Bx (1.14) Và ta đặt gradient này về 0 (là mục tiêu của tối thiểu hóa) đặt lại giá trị cho bước lặp Newton: x B1f (xk ) (1.15) Ma trận xấp xỉ ma trận Hessian được chọn để thỏa mãn f (xk x) f (xk ) Bx (1.17) được gọi là phương trình secant (là chuỗi khai triển Taylor của gradient). Trong nhiều chiều B không xác định.
Trong một chiều, ta áp dụng thuật toán Newton và cập nhật giá trị tương đương với phương trình secant. Thuật toán quasi-Newton có thể có nhiều giải pháp cho phương trình secant. Trong đó phương pháp đối xứng là phương pháp được sử dụng phổ biến nhất. Nếu ta đặt: sk xk1 xk , yk f (xk1) f (xk ) (1.18) Vậy thì theo định lý của phép tích phân ta được: f ( x ts )dt s y 1 0 2 k k k k (1.19) Ma trận nằm trong dấu ngoặc nhọn có thể hiểu là trung bình của ma trận Hessian trên đoạn xk , xk sk .
Kết quả này chứng minh rằng, khi ma trận được nhân với véc tơ sk thì thu được véc tơ là yk. Theo những quan sát này, ta có thể khiến Bk1 bắt chước hành vi của f bằng cách thực thi điều kiện quasi-Newton. 2 Bk1sk yk (1.20) Điều kiện này được thỏa mãn bằng cách thực hiện cập nhật xếp hạng thấp đơn giản cho Bk. Họ cập nhập được sử dụng phổ biến nhất là lớp cập nhật hạng hai của Broyden, có dạng: Bk sk ( Bk sk )T y k y kT Bk 1 Bk T T k skT Bk sk vk vkT (1.21) sk Bk sk y k sk 15 Khóa luận tốt nghiệp Khi cho 0,1 và y B s vk T k T k k (1.22) yk sk sk Bk sk 1.
Thuật toán Backtracking line search Xét bài toán sau: Cho hàm số f ( x ) với x R n và một vectơ đơn vị (hướng) dx ngược hướng với gradient f ( x ). Hãy xác định kích thước để cực tiểu hóa giá trị f (x . Backtracking line search [7], [8] là thuật toán được sử dụng để tìm ra nghiệm xấp xỉ của bài toán này. Nó liên quan đến việc bắt đầu với một ước lượng tương đối về độ lớn bước di chuyển dọc theo hướng tìm kiếm và lặp đi lặp lại việc thu nhỏ độ lớn bước di chuyển, cho đến khi giá trị của hàm số không còn giảm tiếp được nữa.
Vì hướng tìm kiếm dx là một vectơ đơn vị theo hướng ngược T hướng với gradient f ( x ) nên m 0. Dựa trên một tham số điều kiện được chọn c (0,1), chúng ta sẽ kiểm tra xem liệu có đúng khi chúng ta di chuyển từ vị trí hiện tại x đến vị trí mới là x .dx đạt mức giảm tương ứng ở hàm mục tiêu không. Điều kiện để được đáp ứng là: f (x dx ) f (x) cm f (x) f (x dx ) cm 0 (1.22) Điều kiện này khi được sử dụng một cách thích hợp đóng vai trò như là một phần của thuật toán, có để đảm bảo kích thước của các bước không quá lớn. Tuy nhiên điều kiện này không đủ khả năng để đảm bảo rằng, độ lớn của bước là tối ưu, vì bất kỳ giá trị nào của đủ nhỏ đều sẽ đáp ứng được điều kiện trên.
Do do, chúng ta sẽ tìm kiếm bắt đầu bằng một giá trị tương đối lớn và liên tục thu nhỏ nó bằng một nhân tố (0,1) chừng nào điều kiện trên vẫn chưa được đáp ứng.