Chương 1 Kiến thức chuẩn bị Chương này tóm tắt lại các kết quả chính trình bày trong [1], gồm phương pháp tựa Newton miền tin cậy và phương pháp Lagrange tăng cường, làm cơ sở để xây dựng các phương pháp giải bài toán đa mục tiêu trong Chương 2.1 Phương pháp tựa Newton miền tin cậy Xét bài toán tối ưu không ràng buộc min f (x) , (1.1) x∈Rn trong đó f : Rn → R. Giả sử ∇2 f liên tục trong một lân cận mở của x∗ , trong đó ∇ f (x∗ ) = 0 và ∇2 f (x∗ ) xác định dương. Khi đó x∗ là cực tiểu địa phương chặt của f. Giả sử f khả vi tới cấp hai và Hessian ∇2 f (x) liên tục Lipschitz trong một lân cận của nghiệm x∗ thỏa mãn điều kiện đủ trong Định lý 1.
Xét phép lặp h i−1 2 xk+1 = xk − ∇ f (xk ) ∇ f (xk ) .2) Khi đó i) Nếu xấp xỉ ban đầu x0 đủ gần x∗ , thì dãy lặp hội tụ tới x∗ ; 3 4 ii) Dãy {xk } hội tụ bậc hai; và iii) Dãy các chuẩn gradient {k∇ f (xk )k} hội tụ bậc hai tới 0. Phương pháp tựa Newton là một phương pháp tối ưu hóa không ràng buộc được sử dụng để tìm giá trị tối ưu của một hàm mục tiêu f (x) không yêu cầu tính toán trực tiếp ma trận Hessian. Thay vào đó, nó xấp xỉ ma trận Hessian bằng cách cập nhật một ma trận xác định dương B sau mỗi lần lặp. Dưới đây là mô tả chi tiết về phương pháp tựa Newton: Bước 1: Khởi tạo • Chọn một xấp xỉ ban đầu x0.
• Khởi tạo ma trận xác định dương B0. Thông thường, ma trận B0 được chọn là ma trận đơn vị hoặc một xấp xỉ tốt cho ma trận Hessian. Bước 2: Lặp: Cho k = 0, 1, 2, ., thực hiện các bước sau cho đến khi đạt được tiêu chí dừng: Bước 2.1: Tính toán đạo hàm bậc nhất (gradient) tại điểm hiện tại, tại điểm xk : ∇ f (xk ) .2: Tính toán hướng tìm kiếm dk bằng cách nhân ma trận xác định dương Bk với đạo hàm bậc nhất: dk = −Bk ∇ f (xk ) .3: Tìm kích thước bước tối ưu αk bằng cách giải bài toán tối ưu một biến cho hàm mục tiêu f (xk + αk dk ). Có nhiều phương pháp có thể được sử dụng để tìm αk , bao gồm tìm kiếm theo dãy, giảm dần ngẫu nhiên (stochastic gradient descent), hoặc các phương pháp tối ưu hóa một chiều khác.4: Cập nhật điểm xk+1 bằng cách thêm kích thước bước αk nhân với hướng tìm kiếm dk : xk+1 = xk + αk dk .5: Cập nhật ma trận xác định dương Bk+1 bằng cách sử dụng một phương pháp cập nhật như BFGS (Broyden-Fletcher-Goldfarb- Shanno) hoặc DFP (Davidon-Fletcher-Powell).
Các phương pháp cập nhật này giúp cải thiện xấp xỉ của ma trận Hessian.6: Kiểm tra tiêu chí dừng để xem liệu ta nên kết thúc quá trình tối ưu hóa hay tiếp tục lặp. Ví dụ về một tiêu chí dừng phổ biến là kiểm tra xem đạo hàm bậc nhất có đủ gần 0 hay không. Bước 3: Kết thúc: Nếu tiêu chí dừng được đạt, kết thúc quá trình tối ưu hóa và trả về xk là giá trị ước tính tối ưu của hàm mục tiêu f. Phương pháp tựa Newton là một phương pháp hiệu quả để giải các bài toán tối ưu không ràng buộc mà không đòi hỏi tính toán đạo hàm bậc hai của hàm mục tiêu.
BFGS và DFP là hai phương pháp cập nhật ma trận xác định dương phổ biến trong phương pháp tựa Newton, và chúng thường được sử dụng để cải thiện hiệu suất của phương pháp. Phương pháp tựa Newton miền tin cậy là một biến thể của phương pháp tựa Newton trong việc tối ưu hàm mục tiêu không ràng buộc. Nó kết hợp hai yếu tố quan trọng: phương pháp tựa Newton để xấp xỉ ma trận Hessian và miền tin cậy để giới hạn khoảng cách mà bước tối ưu có thể di chuyển từ điểm hiện tại. Cụ thể, trong Bước 2.3, bước tối ưu sẽ bị giới hạn trong miền tin cậy với bán kính ∆k (gọi là bán kính tin cậy) quanh điểm hiện tại xk.
Phương pháp tựa Newton miền tin cậy kết hợp sự ưu việt của phương pháp tựa Newton trong việc xấp xỉ ma trận Hessian và sự kiểm soát hiệu quả bước tối ưu bằng miền tin cậy. Nó thường hoạt động hiệu quả cho các bài toán tối ưu không ràng buộc và đảm bảo tính tin cậy của các bước tối ưu.2 Phương pháp Lagrange tăng cường Phương pháp Lagrange tăng cường cũng được dùng để giải quyết bài toán tối ưu với các ràng buộc đẳng thức. Phương pháp này mở rộng phương pháp Lagrange truyền thống để xử lý ràng buộc bằng cách tăng cường một hàm Lagrange với một hàm phạt. Xét bài toán tối ưu min f (x) , x∈Rn (1.6) với ci (x) = 0, i ∈ E , trong đó f và các hàm ci là các hàm số trơn trên Rn.
Phương pháp Lagrange tăng cường gồm các bước 1. Hàm Lagrange: đầu tiên, ta xây dựng hàm Lagrange bằng cách sử dụng các véctơ λ gồm nhân tử Lagrange L (x, λ ) = f (x) − ∑ λi ci (x). Hàm Lagange tăng cường: chúng ta xây dựng hàm Lagrange tăng cường bằng cách thêm vào hàm Lagrange một hàm phạt dựa trên ràng buộc đẳng thức: µ LA (x, λ ; µ) = L (x, λ ) + ∑ c2i (x) 2 i∈E µ (1. Tối ưu hàm Lagrange tăng cường: ta giải bài toán tối ưu không ràng buộc theo biến x min LA (x, λ ; µ) (1.9) bằng các phương pháp tối ưu không ràng buộc như phương pháp gra- dient hướng giảm, phương pháp Newton, hoặc các phương pháp tối ưu khác.
Cập nhật các nhân tử Lagrange và tham số phạt: sau khi có giá trị tốt nhất từ bước 3, ta cập nhật λ và tham số µ dựa trên các quy tắc cụ thể. Cập nhật này giúp hội tụ nhanh hơn đối với ràng buộc và đảm bảo sự hội tụ tổng thể của phương pháp. Lặp lại bước 3 và 4 cho đến khi đạt được tiêu chí dừng. Phương pháp Lagrange tăng cường thường được sử dụng để giải các bài toán tối ưu với ràng buộc đẳng thức bằng cách kết hợp ưu điểm của phương pháp Lagrange và phương pháp phạt.
Nó cho phép điều chỉnh độ chặt chẽ của ràng buộc thông qua tham số µ và cần ít giả thiết hơn về điều kiện khả vi. Giả sử với điểm khả thi x∗ ∈ Rn có véctơ nhân tử Lagrange λ ∗ thỏa mãn điều kiện Karush–Kuhn–Tucker cho ràng buộc đẳng thức ∇x L (x∗ , λ ∗ ) = 0, ci (x∗ ) = 0, ∀i ∈ E , (1. Ngoài ra, giả sử wT ∇2xx L (x∗ , λ ∗ ) w > 0, ∀w ∈ Rn − {0}.11) Khi đó x∗ là nghiệm địa phương chặt của (1. Ta phát biểu hai kết quả để bảo đảm việc sử dụng hàm Lagrange tăng cường và phương pháp nhân tử Lagrange cho các bài toán có ràng buộc đẳng thức.
Cho x∗ là một nghiệm địa phương của (1.6), mà tại đó các gradient ∇ci (x∗ ) , i ∈ E là các véctơ độc lập tuyến tính, và thỏa mãn điều kiện đủ bậc hai trong Định lý 3 với λ = λ ∗. Khi đó tồn tại ngưỡng giá trị µ sao cho với mọi µ ≥ µ, x∗ là một cực tiểu địa phương chặt của LA (x, λ ∗ , µ). Giả sử các giả thiết của Định lý 4 thỏa mãn tại x∗ và λ ∗ , và µ là ngưỡng được chỉ ra trong định lý đó. Khi đó tồn tại các số dương δ , ε và M sao cho: i) Với mọi λ k và µk thỏa mãn λ k − λ ∗ ≤ µk δ , µk ≥ µ, (1.12) bài toán k min LA x, λ ; µk với kx − x∗ k ≤ ε x có nghiệm duy nhất xk.
Hơn nữa, ta có ∗M λk −λ∗ kxk − x k ≤ .13) µk ii) Với mọi λ k và µk thỏa mãn (1.14) µk trong đó λ k+1 xác định bởi λik+1 = λik − µk ci (xk ) , ∀i ∈ E , (1.15) iii) Với mọi λ k và µk thỏa mãn (1.12), ma trận ∇2xx LA xk , λ k ; µk xác định dương và các gradient ràng buộc ∇ci (xk ) , i ∈ E độc lập tuyến tính. Chương 2 Phương pháp gradient cho bài toán đa mục tiêu Chương này tập trung xây dựng cơ sở toán học cho bài toán tối ưu của hàm đa mục tiêu dựa trên nguyên lý Pareto (xem [2]), trong đó phương pháp tổng có trọng số được xây dựng dựa trên phương pháp Newton, và phương pháp giao biên pháp tuyến dựa trên phương pháp Lagrange tăng cường.1 Bài toán đa mục tiêu Bài toán tối ưu đa mục tiêu có dạng ( min f (u) = ( f1 (u), f2 (u), .1) với u ∈ S, trong đó fi : Rn → R, và S ⊂ Rn là miền khả thi. , un )T là véctơ quyết định hay véctơ các biến tối ưu và f (u) = ( f1 (u) , f2 (u) ,. , fm (u))T là véctơ mục tiêu.
Không gian véctơ Rn gọi là không gian quyết định và không gian véctơ Rm chứa tập tất cả các véctơ mục tiêu là không gian mục tiêu. Miền khả thi S xác định bởi S = {u ∈ Rn | e(u) = (e1 (u), e2 (u),. , cni (u)) ≤ 0}, 9 10 trong đó các ei biểu diễn các ràng buộc đẳng thức và ci biểu diễn các ràng buộc bất đẳng thức. Ta cũng định nghĩa tập Z (được mô tả trong Hình 2.2) trong không gian mục tiêu Z = { f (u) = ( f1 (u) , f2 (u) , .3) Lưu ý tập Z là ảnh của tập S trong không gian mục tiêu bởi hàm véctơ f.
f2 f1 11 được làm trội bởi ít nhất một điểm trên mặt Pareto. Định nghĩa về mối quan hệ trội được giới thiệu sau. Ba định nghĩa và mệnh đề sau có thể được tìm thấy trong [3]. Cho hai véctơ quyết định u1 , u2 ∈ S ⊂ Rn , ta nói u1 trội hơn u2 , ký hiệu u1 ≺ ≺ ∼ u2 hay f (u1 ) ∼ f (u2 ) nếu 1.
, m} sao cho fi (u1 ) < fi (u2 ). Véctơ quyết định u∗ ∈ S ⊂ Rn là tối ưu Pareto nếu không có véctơ quyết định u ∈ S trội hơn u∗ , tức là tập {u | u ∈ S, u ≺ ∗ ∼ u } = ∅.