. 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. | . 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
