TAILIEUCHUNG - 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. | . 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 e 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 e 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 Vf xk . Bước 2 Xác định hàm O x Vf xk T x - xk . Giải bài toán Min O x với x e S. Bước 3 i Giả sử p Min O x O x và p 0 thì dừng với xk là phương án tối ưu. xeS ii Nếu p 0 thì dk X - xk chính là hướng giảm tốt nhất. iii Nếu IVf xk T x - xk s thì dừng với X là nghiệm gần đúng có độ chính xác s trong đó s 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 xk Àdk với điều kiện xk Àdk e 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 . . 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 method để giải BTQHPT sau đây Min f x với x e D x e Rn Ax b x 0 trong đó A là ma trận cấp mxn 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 xT xN xB với véc tơ biến cơ sở xB 0. Véc tơ gradient cũng được phân rã một cách tương ứng Vf x T VNf x T VBf 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 Vf 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 dT dT thì 0 Ad NdN BdB được thỏa mãn với

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.