Tối ưu hóa phần 10

Thuật toán Frank – Wolfe giải bài toán quy hoạch lồi có miền ràng buộc là tập lồi đa diện Ví dụ 13 minh họa cho thuật toán Frank – Wolfe, một trong các phương pháp hướng chấp nhận giải BTQHPT: Min f(x) với x ∈ S = {x: Ax ≤ b}, trong đó S được giả thiết là giới nội. Bước khởi tạo Tìm một điểm x1 ∈ S (nói chung x1 là điểm cực biên ), đặt k := 1. Các bước lặp (bước lặp thứ k) Bước 1: Tính ∇f (x k ) . Bước 2: Xác định hàm Φ(x) = ∇f...
Nội dung trích xuất từ tài liệu:
Tối ưu hóa phần 10 5.2. Thuật toán Frank – Wolfe giải bài toán quy hoạch lồi có miền ràng buộc là tập lồi đa diện Ví dụ 13 minh họa cho thuật toán Frank – Wolfe, một trong các phương pháp hướng chấp nhận giải BTQHPT: Min f(x) với x ∈ S = {x: Ax ≤ b}, trong đó S được giả thiết là giới nội. Bước khởi tạo Tìm một điểm x1 ∈ S (nói chung x1 là điểm cực biên ), đặt k := 1. Các bước lặp (bước lặp thứ k) Bước 1: Tính ∇f (x k ) . Bước 2: Xác định hàm Φ(x) = ∇f (x k )T (x − x k ) . Giải bài toán Min Φ(x) với x ∈ S. Bước 3: i) Giả sử μ = M in Φ(x) = Φ(x / ) và μ ≥ 0 thì dừng với xk là phương án tối ưu. x∈S ii) Nếu μ < 0 thì dk = x/ – xk chính là hướng giảm tốt nhất. iii) Nếu ∇f (x k )T (x / − x k ) < ε thì dừng với x/ là nghiệm gần đúng có độ chính xác ε, trong đó ε là số dương khá nhỏ tuỳ ý chọn trước. Bước 4: Hướng cải thiện là hướng dk = (x/ – xk). Tìm độ dài bước dịch chuyển λ ≥ 0 bằng cách sử dụng kỹ thuật tối ưu thích hợp để giải bài toán Min f (x k + λd k ) với điều kiện xk + λdk ∈ S và tìm ra λ. Tính xk+1 = xk + λdk , đặt k := k + 1 và quay về bước 1. Chú ý. Để giải bài toán ở bước 4 phải có kỹ thuật tối ưu thích hợp cho BTQHPT với một biến λ. Kỹ thuật này được gọi là kỹ thuật tìm kiếm trên hướng (line search technique). 5.3. Phương pháp gradient rút gọn Trong mục này, chúng ta trình bày phương pháp gradient rút gọn (the reduced gradient ∈ ∈ Rn: method) để giải BTQHPT sau đây: Min f(x) với x D = {x Ax = b, x≥ 0}, trong đó A là ma trận cấp m×n, f(x) là hàm khả vi liên tục. Ngoài ra, điều kiện không suy biến được giả sử là đúng, tức là m véc tơ cột bất kì của A là độc lập tuyến tính và mỗi điểm cực biên của D đều có đúng m tọa độ dương (do đó, mỗi phương án x của bài toán đều có ít nhất m tọa độ dương). Giả sử x là một phương án cực biên của bài toán. Lúc đó có thể phân rã A = [N B] với B là ma trận khả nghịch, x T = [x N , x B ] với véc tơ biến cơ sở xB ≥ 0. Véc tơ gradient cũng được phân T T rã một cách tương ứng: ∇f (x)T = [ ∇ N f (x)T , ∇ B f (x)T ] . Dễ dàng chứng minh được rằng d là một hướng cải thiện tại x nếu ∇f (x)T d < 0 và Ad = 0, tọa độ thứ j của d là dj ≥ 0 nếu tọa độ thứ j của x là xj = 0. Đặt dT = [d N ,d B ] , thì 0 = Ad = NdN + BdB được thỏa mãn với dB = – B–1NdN. T T Đặt r T = [rN ,rB ] = ∇f (x)T − ∇ B f (x)T B −1 A = [ ∇ N f (x)T − ∇ B f (x)T B −1N, 0] , thì rT được T T gọi là véc tơ gradient rút gọn. Lúc đó dễ dàng nhận được: 172 ∇f (x)T d = ∇ N f (x)T d N + ∇ B f (x)T d B = [ ∇ N f (x)T − ∇ B f (x)T B −1N ]d N = rN d N . T (6.33) Để xây dựng hướng cải thiện d, cần chọn dN sao cho rN d N < 0 và dj ≥ 0 một khi xj = 0, sau T đó chọn dB = – B–1NdN. Vậy chúng ta có quy tắc xây dựng hướng cải thiện như sau: “với mỗi tọa độ j ứng với biến xj ngoài cơ sở chọn dj = – rj nếu rj ≤ 0, chọn dj = – xjrj nếu rj > 0”. Quy tắc này sẽ đảm bảo rằng dj ≥ 0 một khi xj = 0 và ∇f (x)T d ≤ 0 (nếu dN ≠ 0 thì dấu bất đẳng thức là nghiêm ngặt). Nhận xét. Nếu d ≠ 0 thì d là hướng cải thiện hàm mục tiêu. Còn d = 0 khi và chỉ khi x là điểm thỏa mãn điều kiện Kuhn – Tucker. Thật vậy, x là điểm Kuhn – Tucker khi và chỉ khi tồn tại các véc tơ u và v sao cho: ⎧u T = (u B ,u N ) ≥ (0,0) T T ⎪ ⎨[ ∇ B f (x) , ∇ N f (x) ] + v (B,N ) − (u B ,u N ) = (0,0) T T T T T (6.34) ⎪T ⎩u B x B = 0,u N x N = 0. T Do xB > 0, u B ≥ 0 nên u B x B = 0 khi và chỉ khi u B = 0 . Từ (6.34) suy ra T T T v T = −∇ B f (x)T B −1 và u N = ∇ N f (x)T + v T N = ∇ N f (x)T − ∇ B f (x)T B −1N . Do đó uN = rN. Vậy T điều kiện Kuhn – Tucker trở thành rN ≥ 0 và rN x N = 0 . Như vậy, x là điểm Kuhn – Tucker khi T và chỉ khi d = 0. Sau đây chúng ta trình bày thuật toán gradient rút gọn. Việc chứng minh tính hội tụ của thuật toán tới điểm Kuhn – Tucker là không dễ dàng nhưng cũng không quá khó, xin dành cho bạn đọc tự tìm hiểu. Thuật toán gradient rút gọn Bước khởi tạo Chọn một điểm x1 thỏa mãn Ax1 = b, x1 ≥ 0. Đặt k := 1. Các bước lặp (bước lặp thứ k) Bước 1: Đặt Ik là tập m tọa độ lớn nhất của xk, B = {aj: j ∈ Ik} và N = {aj: j ∉ Ik}, r T = ∇f (x k )T − ∇ B f (x k )T B −1 A , ⎧ −r j , ∀j ∉ I ,r j ≤ 0 k ⎪ dj = ⎨ ⎪ −x j r j , ∀j ∉ I ,r j > 0. k ⎩ Nếu ∀j ∉ Ik, dj = 0 thì dừng. Nếu trái lại, đặt (d k )T = [d N ,d B ] , với dN xác định như trên và dB = – B–1NdN. T T 173 Bước 2: Giải bài toán tìm kiếm trên hướng Min f(xk + λdk) với 0 ≤ λ ≤ λmax, trong đó ⎧ ⎧ −x k ⎫ ⎪j ⎪ ⎪M in ⎨ k : d k < 0 ⎬ khi d k ≥ 0 ...