chương 1 sẽ được tác giả xem như một robot hụt dẫn động. Công cụ hiệu quả nhất cho bài toán động học của đối tượng này là phương pháp GRG [6]. Chương 2 này sẽ trình bày các vấn đề cơ bản nhất về phương pháp GRG làm cơ sở cho chương 3.1 Khái niệm Gradient Trong giải tích vectơ, gradient của một trường vô hướng là một vectơ có chiều hướng về phía mức độ tăng lớn nhất của trường vô hướng: y= f (x1,…, xn) (2.1) Theo định nghĩa, gradient là một vectơ cột mà thành phần là đạo hàm theo tất cả các biến củaf: T y y f 1 ,.2) x1 xn *Ý nghĩa của gradient Ví dụ, nhiệt độ trong một căn phòng được cho bởi một trường vô hướng t, sao cho tại mỗi điểm (x; y; z) nhiệt độ là t(x; y; z) (giả thiết rằng nhiệt độ không thay đổi theo thời gian). Trong trường hợp này, tại mỗi điểm trong căn phòng, gradient của t tại điểm đó cho biết hướng mà theo đó nhiệt độ tăng lên nhanh nhất.
Độ lớn của gradient quyết định nhiệt độ thay đổi nhanh đến mức nào nếu ta đi theo hướng đó. Trong một ví dụ khác, một ngọn đồi có độ cao so với mực nước biển tại điểm (x; y) là H(x; y). Gradient của H tại mỗi điểm là một vector chỉ theo hướng dốc nhấttại điểm đó. Độ dốc của dốc này được cho biết bởi độ lớn của vector gradient.
download by : skknchat@gmail.com 13 Gradient còn có thể được dùng để đo sự thay đổi của một trường vô hướng theo những hướng khác, không chỉ hướng có sự thay đổi lớn nhất, bằng cách lấy tíchđiểm. Trong ví dụ ở trên, giả sử dốc lên đồi dốc nhất là 40%. Nếu một con đường đi thẳng lên đồi thì đoạn dốc nhất trên con đường đó cũng là 40%. Nếu thay vì đi thẳng, con đường này đi vòng quanh đồi theo một góc, nó sẽ kém dốc hơn[8].2 Phương pháp giảm Gradient (Reduced Gradient) Trong toán tối ưu, chúng ta thường xuyên phải tìm giá trị nhỏ nhất (hoặc đôi khi là lớn nhất) của một hàm số nào đó.
Nhìn chung, việc tìm giá trị nhỏ nhất của các hàm là rất phức tạp, thậm chí là bất khả thi. Thay vào đó, người ta thường cố gắng tìm các điểm cực tiểu, và ở một mức độ nào đó, coi đó là nghiệm cần tìm của bài toán. Các điểm cực tiểu là nghiệm của phương trình mà tại đó đạo hàm bằng 0. Nếu bằng một cách nào đó có thể tìm được toàn bộ (hữu hạn) các điểm cực tiểu, ta chỉ cần thay từng điểm cực tiểu đó vào hàm số rồi tìm điểm làm cho hàm có giá trị nhỏ nhất.
Tuy nhiên, trong hầu hết các trường hợp, việc giải phương trình đạo hàm bằng 0 là bất khả thi. Nguyên nhân có thể đến từ sự phức tạp của dạng của đạo hàm, từ việc các điểm dữ liệu có số chiều lớn, hoặc từ việc có quá nhiều điểm dữ liệu. Hướng tiếp cận phổ biến nhất là xuất phát từ một điểm mà chúng ta coi là gần với nghiệm của bài toán, sau đó dùng một phép toán lặp để tiến dần đến điểm cần tìm, tức đến khi đạo hàm gần với 0. Giảm Gradient và các biến thể của nó là một trong những phương pháp được dùng nhiều nhất.
Xét bài toán lồi có ràng buộc tuyến tính sau: (LC) min f (x) Sao cho Ax = b, (2.3) x≥0 Các giả thuyết: f làkhả vi và liên tục; download by : skknchat@gmail.com 14 Mỗi tập con của m cột của ma trận A cỡ là độc lập tuyến tính; Mỗi điểm cực trị của tập khả thi có ít nhất m phần tử dương (giả thuyết không suy biến). Hoàn toàn chứng minh được rằng theo giả thuyết không suy biến, mỗi có ít nhất m phần tử dương. Nếu , gọi một tập gồm m cột B của A là một cơ sở nếu thì cột i là một cột của B. Chia xthành biếncơ sở và các biến không cơ sở sao cho các biến cơ sở tương ứng với các cột của B.
Chú ý rằng không bắt buộc bằng 0. Để đơn giản các ký hiệu, giả thiết rằng có thể phân chia ma trận Athành A = [B, N] và phân chia x cho phù hợp, với. Do đó ta có thể viết lại Ax = b thành: (2.5) ( tồn tại theo giả thuyết) Với , chúng ta sẽ chọn B là các cột tương ứng với các thành phần lớn nhất m của x. Các biến cơ sở bây giờ có thể bị loại bỏ khỏi bài toán (2.3) để có được bài toán cực tiểu: Sao cho: , Trong đó.
Chú ý rằng bất kỳ hướng khả thi s đối với bài toán (LC) trong (2.3) đều phải thỏa mãn As = 0. Nếu chúng ta viết đối với một cơ sở B cho trước, điều kiện As = 0 có thể viết lại thành: download by : skknchat@gmail.com 15 Giải phương trình này được: (2.6) Chọn hướng tìm kiếm Nhắc lại rằng s là một hướng giảm của f tại khi và chỉ khi , điều này tương đương với Với là gradient tương ứng với các biến cơ sở, thay từ (2.7) là gradient giảm của f tại x đối với B cơ sở. Như vậy: Nói cách khác, gradient giảm r đóng vai trò tương tự trong bài toán giảm như gradient đã làm trong bài toán gốc (LC). Trên thực tế, gradient giảm chính xác là gradient của hàm với trong bài toán giảm.
Bên cạnh đó chứng minh được rằng , trong đó:. Nhắc lại rằng phương pháp gradient sử dụng hướng tìm kiếm. Tương tự, ý tưởng cơ sở cho phương pháp giảm gradient là sử dụng gradient giảm âm như hướng tìm kiếm cho các biến , và sau đó tính hướng tìm kiếm đối với các biến từ (2.8) Tại phép lặp k của thuật toán chúng ta thực hiện một thuật toán line search nhằm tìm sao cho: Trong đó là một cận trên trên chiều dài bước khả thi tối đa và được cho bởi: download by : skknchat@gmail.9) Sự lựa chọn này đối với bảo đảm rằng và Những hiệu chỉnh cần thiết đối với hướng tìm kiếm Nếu chúng ta chọn , khi đó có thể xảy ra và tại phép lặp i nào đó.Trong trường hợp này và chúng ta không thể thực hiện được bước tìm kiếm. Một nghiệm với tập các phần tử không cơ sở có thể có các tình huống sau: (2.10) Chú ý rằng điều này tránh được các bước 0 và các bước rất nhỏ.
Kết quả hội tụ Vì phương pháp giảm gradient có thể được xem là một sự mở rộng của phương pháp gradient, không có gì là bất ngờ rằng các kết quả hội tụ ở phương pháp giảm gradient tương tự như đối với phương pháp gradient. Giả định rằng phương pháp giảm gradient phát sinh các giá trị lặp: Định lý 2.1Hướng tìm kiếm tại luôn là một hướng giảm có thể khả thi trừ khi. Nếu , thì là một điểm KKT của bài toán (LC). (Điều kiện tối ưu Karush-Kuhn-Tucker (KKT)) So sánh điều này với phương pháp gradient trong đó, theo định nghĩa, khi và chỉ khi là một điểm dừng ( Thuật toán giảm gradient: tóm tắt 1.
Sự khởi tạo Chọn một điểm bắt đầu sao cho Ax = b.Bước chính [1.1] Hình thành B từ những cột của A tương ứng với các thành phần lớn nhất mcủa. download by : skknchat@gmail.com 17 Xác định Nlà các cột còn lại của A, xác định là các phần tử của tương ứng với B,và xác định tương tự.2] Tính gradient giảm r từ (2. Hình thành từ và .4] Nếu , DỪNG LẠI ( là một điểm KKT) 3.2] Thực hiện thuật toánline search [2.3] Đặt và thay k bằng k + 1.4] Lặp lại bước chính. Nhận xét: Trong toàn bộ thuật toán, nghiệm không nhất thiết phải là một nghiệm cơ sở, do đó các tọa độ dương trong có thể xuất hiện.
Các biến này thường được đề cập đến như là các biến siêu cơ sở. Nhớ lại rằng chúng ta đã đưa ra một giả thuyết không suy biến khó kiểm tra trong thực tiễn. Nếu suy biến xảy ra trong thực tế, các kỹ thuật tương tự như trong trương hợp tối ưu tuyến tính được áp dụng để giải quyết suy biến và ngăn chặn chu kỳ. Phương pháp đơn hình lồi thu được như là sự chuyển hóa của sơ đồ giảm gradient ở trên nếu định nghĩa hướng tìm kiếm được sửa đổi.
Chúng ta chỉ cho phép một tọa độ j của khác 0 và được xác định theo:. Phần còn lại của tọa độ được xác định bằng 0 và , trong đó là cột thứ j của ma trận A. download by : skknchat@gmail.com 18 Phương pháp đơn hình của LO thu được như một sự chuyên môn hóa của Phương pháp đơn hình lồi. Người ta giả thuyết rằng hàm mục tiêu là tuyến tính và nghiệm đầu tiên là một nghiệm cơ sở.3 Phương pháp giảm Gradient tổng quát Trước khi phát triển thuật toán giảm Gradient tổng quát, vài phương pháp quy hoạch phi tuyến đã chỉ có thể được giải quyết trong những trường hợp đặc biệt.
Năm 1963 và 1967, Wolfe đã phát triển một thuật toán mà có thể giải quyết các bài toán với hàm mục tiêu phi tuyến và ràng buộc tuyến tính. Sự mở rộng của phương pháp của Wolfe để giải một dạng tổng quát của bài toán quy hoạch phi tuyến, với tên gọi là Generalized Reduced Gradient (GRG) đã được trình bày bởi Abadie và Carpentier vào năm 1967. Phương pháp giảm gradient có thể được tổng quát hóa cho bài toán tối ưu có ràng buộc phi tuyến. Tương tự với trường hợp có ràng buộc tuyến tính, chúng ta xét bài toán với các ràng buộc là đẳng thức và các biến không âm như sau: min f(x) Sao cho (2.,hmđược cho là khả vi và liên tục.
Ý tưởng cơ sở là thay thế các phương trình phi tuyến bằng phép xấp xỉ Taylor tuyến tính của chúng tại giá trị hiện tại của x, và sau đó áp dụng thuật toán giảm gradient để cho kết quả bài toán. Giả định rằng gradient của các hàm ràng buộc là độc lập tuyến tính tại mọi điểm , và do đó mỗi x khả thi có ít nhất m phần tử dương. Những giả định này bảo đảm rằng chúng ta có thể luôn áp dụng thuật toán giảm gradient đối với bài toán tuyến tính hóa. Khó khăn thêm ở đây là vìvùng khả thi không phải là lồi.
Quy trình nàycó thể tạo ra phép lặp nằm ngoài , và sau đó cần bổ sung một số yếu tố cần thiết để khôi phục lại tính khả thi.Cho một nghiệm khả thi với với tất cả j đã cho. Theo giả thuyết ma trận Jacobian của các ràng buộc download by : skknchat@gmail.com 19 tại mỗi có đủ hạng, để đơn giản tại điểm sẽ được biểu thị bởi. Giả định rằng tìm đượcmột B cơ sở,với .