Thực đơn
trang chủTiểu sử

Khái niệm điểm yên ngựa. Định lý Kuhn-Tucker. Điều kiện Karush-Kuhn-Tucker

Vị trí trung tâm trong lý thuyết quy hoạch phi tuyến là định lý Kuhn-Tucker. Cho bài toán quy hoạch phi tuyến:

tìm giá trị lớn nhất của hàm số Z=f(x 1, x 2, ..., xn) có hạn chế

Hãy soạn hàm Lagrange cho bài toán này:

(4.2)

Nếu điều kiện chính quy được thỏa mãn (có ít nhất một điểm X, mà tôi(X)>0 cho mọi người Tôi), thì định lý sau đây đúng.

Định lý. Vectơ X(0) khi và chỉ nếu là nghiệm tối ưu của bài toán (4.1) khi tồn tại vectơ Λ (0) sao cho khi cho tất cả

Chấm ( X(0),Λ (0)) được gọi là Yên xeđiểm cho chức năng F(X,Λ), và định lý được gọi là định lý điểm yên ngựa. Hãy chứng minh đủ điều kiện (4.3).

Bằng chứng. Cho phép X(0) >0 và Λ (0) >0 - điểm yên của hàm số F(X,Λ). Nếu trong (4.3) thay vào đó F(X,Λ) thay giá trị của nó (4.2), ta được

Tại .

Bất đẳng thức đúng có giá trị với mọi , do đó

Khi đó từ bất đẳng thức bên trái ta có

Vì trong trường hợp này

Cái đó f(X(0))>f(X).

Vì vậy, điểm X(0) thỏa mãn (4.1) và tại tất cả các điểm khác thỏa mãn (4.1), hàm số nhận giá trị nhỏ hơn tại X(0).

Tuyên bố này đưa lời giải của bài toán NLP đến việc tìm các điểm yên của hàm Lagrange F(X,Λ).

Việc chứng minh sự cần thiết của điều kiện (4.3) không được xem xét do tính phức tạp của nó.



Nếu như f(X) Và tôi(X)-các hàm khả vi thì điều kiện (4.3) tương đương với các điều kiện Kuhn-Tucker cục bộ sau:

Sự biểu lộ

có nghĩa là giá trị đạo hàm riêng của hàm Lagrange được lấy tại điểm ( X(0), Λ (0)), trong đó

X(0)=(x 1 (0) , x 2 (0) , ..., xn(0)), Λ (0) =(λ 1 (0) , λ 2 (0) , ..., λ N (0)).

Những điều kiện này có thể được viết dưới dạng vector:

Ví dụ. Tìm tối đa Z=-x 1 2 -x 2 2 có hạn chế

Hãy chứng minh rằng tồn tại Λ (0) 0 thỏa mãn điều kiện Kuhn-Tucker (4.4), (4.5) cho hàm số tại điểm tối ưu F(X,Λ):

F(X,Λ)=- x 1 2 -x 2 2 +λ 1 (2 x 1 +x 2 -2)+λ 2 (8-2 x 1 -x 2)+λ 3 (6- x 1 -x 2).

Theo điều kiện (4.5) λ 2 và λ 3 cần lấy giá trị 0, vì, thay thế x 1 = 0,8 và x 2 = 0,4 trong biểu thức

chúng ta có các giá trị lớn hơn 0 và theo điều kiện

Theo điều kiện, λ 1 có thể nhận giá trị khác 0, vì

Theo (2.16), đạo hàm

phải lấy giá trị bằng 0, vì tọa độ của vectơ X(0) khác với số không. Chúng tôi tìm thấy λ 1 = 0,8. Do đó, tại điểm ( X(0),Λ (0)) điều kiện Kuhn-Tucker được thỏa mãn và nó thực sự là một điểm cực trị.

Hãy xem xét các điều kiện Kuhn-Tucker ở một dạng hơi khác.

Giả sử chúng ta có một bài toán tối ưu hóa với các ràng buộc ở dạng đẳng thức:

z= f(x 1 , x 2 , …, xn) → phút

trong những điều kiện:

g 1 ( x 1 , x 2 , ... , x n) = 0,

g 2 ( x 1 , x 2 , ... , x n) = 0,

g N(x 1 , x 2 , . . . , x n) = 0.

Điểm tối thiểu có điều kiện của hàm f trùng với điểm yên của hàm Lagrange:

Trong trường hợp này, điểm yên ngựa phải cung cấp mức tối thiểu cho các biến của nó. x tôi và tối đa trên các biến λ j.

Điều kiện cần cho một điểm dừng là đạo hàm riêng cấp một đối với mọi biến đều bằng 0:

Lưu ý rằng phương trình thứ hai ngụ ý rằng chỉ những điểm hợp lệ mới thỏa mãn các điều kiện cần thiết.

Để có được đủ điều kiệnĐể tồn tại cực tiểu cần thêm yêu cầu Hessian của hàm mục tiêu phải xác định dương.

Hãy xem xét tổng quan vấn đề lập trình toán học:

Z= f(X) → phút,

trong những điều kiện:

Các ràng buộc bất đẳng thức có thể được chuyển đổi thành các ràng buộc đẳng thức bằng cách thêm vào từng ràng buộc đó suy yếu biến

Hãy xây dựng hàm Lagrange:

Sau đó những điều kiện cần thiết tối thiểu có dạng:

Phương trình thứ hai có thể được biến đổi bằng cách loại bỏ các biến suy giảm và chuyển sang ràng buộc bất đẳng thức. Ta thu được các ràng buộc của bài toán ban đầu. Phương trình thứ ba có thể được nhân với ui/2 và thay thế các biến suy yếu bằng cách biểu thị chúng từ phương trình thứ hai của hệ.

Còn một điều kiện nữa phải được đáp ứng ở mức tối thiểu. Điều kiện này: λ Tôi= 0, đó là hệ quả của việc phân tích ý nghĩa vật lý các hệ số của hàm Lagrange.

Nó có thể được hiển thị rằng

Hệ số Lagrange tại điểm cực tiểu;

f* - giá trị tối ưu chức năng.

Rõ ràng, khi b tăng Tôi vùng chấp nhận được mở rộng, có nghĩa là giá trị tối thiểu chỉ có thể giảm, tức là đạo hàm phải âm (không dương). Do đó, tại điểm tối thiểu có điều kiện

Cuối cùng chúng ta thu được điều kiện cần thiết cho điều kiện tối thiểu:

Các biểu thức ở dòng thứ hai đảm bảo rằng điểm tối ưu là hợp lệ.

Dòng thứ ba chứa các thông tin sau: Nếu ràng buộc có hiệu lực (tức là biểu thức trong ngoặc bằng 0), thì hệ số Lagrange tương ứng hoàn toàn dương. Độ dương của hệ số Lagrange có nghĩa là ràng buộc tương ứng đang hoạt động, tức là. Thực tế là hạn chế này còn thiếu là nguyên nhân ngăn cản sự cải thiện hơn nữa của chức năng mục tiêu. Nếu ràng buộc không hoạt động (tức là biểu thức trong ngoặc không bằng 0), thì hệ số Lagrange tương ứng phải bằng 0, tức là. Hạn chế này không phải là thiếu sót; nó không ảnh hưởng đến việc cải thiện hơn nữa chức năng mục tiêu.

Đối với điểm cực đại có điều kiện, các hệ số Lagrange đổi dấu ngược lại (vì giá trị tối ưu của hàm mục tiêu tại điểm cực đại có điều kiện sẽ tăng).

Các điều kiện trên là tương đương Định lý Kuhn-Tucker và thường được gọi giống nhau.

Điều kiện đủ để đạt cực tiểu (cực đại) là độ lồi (lõm) của hàm mục tiêu tại một điểm đứng yên. Điều này có nghĩa là Hessian phải xác định dương (âm).

Một bản tóm tắt của tài liệu trong chương này có thể được xem trong hai bài trình bày:

tập tin “Lập trình phi tuyến”;

tập tin "Định lý Kuhn-Tucker".

Các slide 10-14 của bài thuyết trình “Định lý Kuhn-Tucker” trình bày một ví dụ về cách giải bài toán Kuhn-Tucker.

4.5. Câu hỏi kiểm soát

(Được phát triển bởi Afanasyev M.Yu. và Suvorov B.P.)

Câu hỏi 1. Cho một hàm thực f(X S= . Cho phép X 1 và X 2 - điểm của phân khúc này và 0 £ l £ 1.

Bất đẳng thức nào sau đây là điều kiện của hàm số lồi?

Câu trả lời có thể:

Câu hỏi 2. Cho một hàm thực f(x), được xác định trên đoạn số thực S=. Cho phép x 1 và x 2 là các điểm của đoạn này và 0 £ l £ 1.

Bất đẳng thức nào sau đây là điều kiện để hàm số lõm chặt?

Câu trả lời có thể:

Câu hỏi 3. Chức năng

1) lồi;

2) lồi chặt;

3) lõm;

4) lõm hoàn toàn;

5) lồi và lõm.

Câu hỏi 4. Chức năng

3) lõm; 4) lõm hoàn toàn;

5) lồi và lõm.

Câu hỏi 5. Chức năng

1) lồi; 2) không lồi cũng không lõm;

3) lồi chặt; 4) lõm:

5) lồi và lõm.

Câu hỏi 6. Người mẫu mới xe máy tốc độ cao “Ốc” được công ty bán với giá (30 – 2 x) nghìn đô la mỗi mảnh, trong đó X- số lượng xe máy đã bán. Chi phí sản xuất biến đổi là 6.000 USD mỗi đơn vị và chi phí cố định là 30.000 USD. Hãy tối đa hóa lợi nhuận kinh doanh của bạn trong tuần.

Giả sử sự thay đổi về thuế suất bán hàng dẫn đến thuế bán hàng tăng thêm 4.000 USD cho mỗi chiếc xe máy được bán.

Sản lượng xe máy tối ưu sẽ thay đổi như thế nào so với tình hình ban đầu?

(Giải bằng hàm Lagrange.)

Câu trả lời có thể:

1) sẽ tăng thêm 2 ; 2) sẽ giảm đi 2 ;

3) sẽ không thay đổi; 4) sẽ tăng thêm 1 ;

5) sẽ giảm đi 1 .

Câu hỏi 7. Giả sử bạn có 2 tuần (14 ngày) kỳ nghỉ ở Quần đảo Canary và Nice. Hãy để hàm tiện ích của bạn có dạng 2 KN – 3K 2 – 4N2,Ở đâu ĐẾN Và N- số ngày bạn ở Quần đảo Canary và Nice tương ứng.

Bạn nên dành bao nhiêu ngày ở Nice để tối đa hóa chức năng tiện ích của mình?

(Để giải, hãy sử dụng hàm Lagrange. Làm tròn kết quả đến số nguyên gần nhất. Kiểm tra xem các điều kiện tối ưu Kuhn-Tucker có đáp ứng hay không.)

Câu trả lời có thể:

1) 3 ; 2) 4 ; 3) 5 ; 4) 6 ; 5) 7 .

Câu hỏi 8.Đối với bài toán ở Câu hỏi 7, hãy tìm giá trị ước lượng kép của ràng buộc.

(Làm tròn kết quả đến số nguyên gần nhất.)

Câu trả lời có thể:

1) 41 ; 2) 34; 3) 29 ; 4) 39 ; 5) 44 .

Câu hỏi 9. Nhà độc quyền lên kế hoạch sản xuất và bán hàng cho giai đoạn tiếp theo. Giá: R 1 = 14 – 0,25x 1 (mỗi sản phẩm 1); R 2 = 14 – 0,5X 2 (mỗi sản phẩm 2), trong đó x 1 và X 2 - doanh số bán sản phẩm. Giả sử rằng tất cả các sản phẩm sản xuất ra đều được bán. Tổng khối lượng bán hàng tối đa là 57.

Việc phát hành sản phẩm 2 tối ưu là gì?

Câu trả lời có thể:

1) 36,4 ; 2) 30,7 ; 3) 26,3 ; 4) 20,6 ; 5) 41,8 .

Câu hỏi 10. Chủ một doanh nghiệp nhỏ có 100 nghìn rúp cho tháng tiếp theo, số tiền này anh ta có thể chi để tăng tài sản cố định ĐẾN(mua thiết bị) với mức giá 1 nghìn rúp mỗi chiếc hoặc để mua thêm lao động L với mức giá 50 rúp./giờ. Tăng số lượng thành phẩm có thể bán được với giá 10 nghìn rúp. trên mỗi đơn vị, được xác định bởi hàm sản xuất F(K, L)= L 2/7 K 2/5.

Cần chi bao nhiêu tiền để tăng tài sản cố định?

Câu trả lời có thể:

1) 74,36 nghìn chà.; 2) 58,33 nghìn rúp.; 3) 63,44 nghìn rúp.;

4) 45,66 nghìn rúp.; 5) 39,77 nghìn rúp.

Câu trả lời cho các câu hỏi:

1 -4,2 - 1,3 -4,4 - 5,

5 -2, 6 -5,7- 4,8- 2,9- 4,10- 2.

Trong phần trước, điều kiện Kuhn đã được xây dựng-Tucker cho nhiệm vụ tối ưu hóa có điều kiện. Sử dụng phương pháp nhân tử Lagrange, người ta thu được một ý tưởng trực quan rằng các điều kiện Kuhn-Tanker có liên quan chặt chẽ với các điều kiện tối ưu cần thiết. TRONG phần này Các công thức chặt chẽ về điều kiện cần và đủ để giải quyết tối ưu một bài toán quy hoạch phi tuyến được xem xét.

Định lý 1. Sự cần thiết của điều kiện Kuhn-Tucker

Xét bài toán quy hoạch phi tuyến (0) - (2). Cho là các hàm khả vi và x* là nghiệm chấp nhận được cho bài toán này. Hãy đặt nó. Hơn nữa, hãy để chúng độc lập tuyến tính. Nếu x* - giải pháp tối ưu bài toán quy hoạch phi tuyến thì tồn tại một cặp vectơ là nghiệm của bài toán Kuhn-Tucker (3) - (7).

Điều kiện để chúng độc lập tuyến tính được gọi là điều kiện độc lập tuyến tính và về cơ bản đại diện cho một điều kiện nhất định về tính đều đặn của vùng chấp nhận được, điều này hầu như luôn được thỏa mãn đối với các vấn đề tối ưu hóa gặp phải trong thực tế. Tuy nhiên, nói chung, việc kiểm tra sự thỏa mãn điều kiện độc lập tuyến tính là rất khó khăn, vì yêu cầu phải biết trước lời giải tối ưu của bài toán. Đồng thời, điều kiện độc lập tuyến tính luôn được thỏa mãn đối với các bài toán quy hoạch phi tuyến có các tính chất sau.

  • 1. Mọi ràng buộc dưới dạng đẳng thức và bất đẳng thức đều chứa hàm tuyến tính.
  • 2. Tất cả các ràng buộc bất đẳng thức đều chứa các hàm lõm, tất cả các ràng buộc đẳng thức đều chứa các hàm tuyến tính và có ít nhất một điểm khả thi x, nằm bên trong vùng được xác định bởi các ràng buộc bất đẳng thức. Nói cách khác, tồn tại một điểm x sao cho

Nếu điều kiện độc lập tuyến tính tại điểm tối ưu không được thỏa mãn thì bài toán Kuhn-Tucker có thể không có lời giải.

Giảm thiểu

dưới những hạn chế

Trong bộ lễ phục. Hình 1 cho thấy vùng giải pháp khả thi cho bài toán phi tuyến được xây dựng ở trên. Rõ ràng là có một giải pháp tối ưu cho vấn đề này. Hãy chứng minh rằng điều kiện độc lập tuyến tính không được thỏa mãn tại điểm tối ưu.

Cơm.

Dễ dàng thấy rằng các vectơ phụ thuộc tuyến tính, tức là điều kiện độc lập tuyến tính tại điểm không được thỏa mãn.

Hãy viết các điều kiện Kuhn-Tucker và kiểm tra xem chúng có thỏa mãn tại điểm (1, 0) hay không. Điều kiện (3), (6) và (7) có dạng sau;

Tại, theo phương trình (11), trong khi phương trình (14) cho, Do đó, điểm tối ưu không phải là điểm Kuhn-Tucker.

Lưu ý rằng việc vi phạm điều kiện độc lập tuyến tính không nhất thiết có nghĩa là điểm Kuhn-Tucker không tồn tại. Để xác nhận điều này, hãy thay thế hàm mục tiêu từ hàm ví dụ này. Trong trường hợp này, điểm tối ưu vẫn đạt được tại điểm (1.0), tại đó điều kiện độc lập tuyến tính không được thỏa mãn. Điều kiện Kuhn-Tucker (12) - (16) không thay đổi và phương trình (11) có dạng

Thật dễ dàng để kiểm tra xem điểm đó có phải là điểm Kuhn-Tucker hay không, tức là. thỏa mãn điều kiện Kuhn-Tucker.

Định lý về sự cần thiết của điều kiện Kuhn-Tucker cho phép chúng ta xác định các điểm không tối ưu. Nói cách khác, Định lý 1 có thể được sử dụng để chứng minh rằng một điểm khả thi nhất định thỏa mãn điều kiện độc lập tuyến tính sẽ không tối ưu nếu nó không thỏa mãn các điều kiện Kuhn-Tucker. Mặt khác, nếu tại thời điểm này các điều kiện Kuhn-Tucker được thỏa mãn thì không có gì đảm bảo rằng giải pháp tối ưu cho bài toán phi tuyến đã được tìm thấy. Ví dụ, hãy xem xét bài toán lập trình phi tuyến sau đây.

Định lý sau đây thiết lập các điều kiện để điểm Kuhn-Tucker tự động tương ứng với lời giải tối ưu cho bài toán quy hoạch phi tuyến.

Định lý 2. Tính đầy đủ của điều kiện Kuhn-Tucker

Xét bài toán quy hoạch phi tuyến (0) - (2). Giả sử hàm mục tiêu là lồi, tất cả các ràng buộc bất đẳng thức đều chứa các hàm lõm và các ràng buộc đẳng thức chứa các hàm tuyến tính. Khi đó nếu tồn tại lời giải thỏa mãn điều kiện Kuhn-Tucker (3) - (7) thì x* là lời giải tối ưu cho bài toán quy hoạch phi tuyến.

Nếu các điều kiện của Định lý 2 được đáp ứng thì việc tìm điểm Kuhn-Tucker sẽ mang lại giải pháp tối ưu cho bài toán quy hoạch phi tuyến.

Định lý 2 cũng có thể được sử dụng để chứng minh tính tối ưu quyết định này các bài toán quy hoạch phi tuyến. Để minh họa, hãy xem xét lại ví dụ:

Giảm thiểu

dưới những hạn chế

Sử dụng Định lý 2, chúng ta chứng minh rằng nghiệm này là tối ưu. Chúng ta có

Vì ma trận là nửa xác định dương với mọi x nên hàm này là lồi. Ràng buộc bất đẳng thức đầu tiên chứa hàm tuyến tính, vừa lồi vừa lõm cùng một lúc. Vì điều đó

để chứng tỏ hàm số lõm, ta tính

Vì ma trận xác định âm nên hàm số lõm. Hàm được bao gồm trong ràng buộc tuyến tính trong phương trình đẳng thức. Do đó, mọi điều kiện của Định lý 2 đều được thỏa mãn; nếu chúng ta chứng minh được đó là điểm Kuhn-Tucker thì chúng ta thực sự sẽ thiết lập được tính tối ưu của lời giải. Các điều kiện Kuhn-Tucker trong ví dụ 2 có dạng

Điểm thỏa mãn các ràng buộc (24) - (26) và do đó được chấp nhận. Các phương trình (22) và (23) có dạng sau:

Đặt nó, chúng tôi nhận được và. Do đó, nghiệm x*=(1, 5) thỏa mãn điều kiện Kuhn-Tucker. Vì các điều kiện của Định lý 2 được thỏa mãn nên nghiệm tối ưu của bài toán từ Ví dụ 3. Lưu ý rằng còn có các giá trị khác của và thỏa mãn hệ (22) - (29).

Ghi chú

  • 1. Đối với các bài toán gặp trong thực tế, điều kiện độc lập tuyến tính thường được thỏa mãn. Nếu tất cả các hàm trong bài toán đều khả vi thì điểm Kuhn-Tucker được coi là điểm có thể tối ưu. Do đó, nhiều phương pháp quy hoạch phi tuyến hội tụ về điểm Kuhn-Tucker. (Ở đây, thật thích hợp để rút ra một sự tương tự với trường hợp tối ưu hóa không bị ràng buộc, khi các thuật toán tương ứng có thể xác định được điểm dừng.)
  • 2. Nếu các điều kiện của Định lý 2 được đáp ứng thì điểm Kuhn-Tucker đồng thời trở thành điểm cực tiểu toàn cục. Thật không may, việc kiểm tra các điều kiện đủ là rất khó khăn, và ngoài ra, bài toán ứng dụng thường không có những đặc tính cần thiết. Cần lưu ý rằng sự hiện diện của ít nhất một ràng buộc phi tuyến ở dạng đẳng thức dẫn đến vi phạm các giả định của Định lý 2.
  • 3. Các điều kiện đủ do Định lý 2 thiết lập có thể khái quát hóa cho trường hợp các bài toán có hàm không lồi nằm trong các ràng buộc dưới dạng bất đẳng thức, hàm mục tiêu không lồi và ràng buộc đẳng thức phi tuyến. Trong trường hợp này, việc tổng quát hóa các hàm lồi như hàm gần lồi và giả lồi được sử dụng.

Định lý 7.2.Đối với bài toán quy hoạch lồi (7.4)–(7.6), tập hợp các nghiệm khả thi có tính chất chính quy, một phương án là phương án tối ưu khi và chỉ khi tồn tại một vectơ sao cho
– điểm yên của hàm Lagrange.

Giả sử hàm mục tiêu
và chức năng là liên tục và khả vi, khi đó định lý Kuhn-Tucker có thể được bổ sung bằng các biểu thức giải tích xác định điều kiện cần và đủ cho điểm
là điểm yên của hàm Lagrange, tức là là lời giải cho bài toán quy hoạch lồi. Các biểu thức này có dạng sau:

Ở đâu Và là các giá trị đạo hàm riêng tương ứng của hàm Lagrange tính tại điểm yên ngựa.

Định lý Kuhn-Tucker chiếm vị trí trung tâm trong lý thuyết quy hoạch phi tuyến. Nó cũng đúng cho cái gọi là các bài toán quy hoạch bậc hai, tức là hàm mục tiêu ở đâu
với những hạn chế:

.

TRONG trường hợp chung Không có phương pháp tính toán hiệu quả nào để giải các bài toán quy hoạch phi tuyến nhằm xác định cực trị toàn cục của bài toán nếu không biết cực trị cục bộ nào cũng là cực trị toàn cục. Như vậy, trong bài toán quy hoạch lồi và bậc hai, tập nghiệm khả thi là tập lồi, khi đó nếu hàm mục tiêu là lõm thì mọi cực đại cục bộ cũng có tính toàn cục.

Ví dụ 7.3. Sử dụng định lý Kuhn-Tucker chúng ta tìm thấy
dưới những hạn chế

Chúng tôi giải quyết bằng đồ họa (Hình 7.2) và tìm thấy:
;
;
(xem giải pháp bên dưới để biết thêm chi tiết). Hãy chứng minh rằng có một vectơ Y 0 0, tại đó điều kiện Kuhn-Tucker được thỏa mãn ở điểm tối ưu. Hãy soạn hàm Lagrange:

Giải pháp
chúng tôi tìm thấy từ hệ thống:
. Từ phương trình thứ hai
thay thế vào phương trình đầu tiên của hệ thống. Phân biệt bằng :
. Trong biểu thức Và thay thế các giá trị
Và
. Ta có các giá trị đạo hàm riêng lớn hơn 0 và theo điều kiện chúng phải bằng 0 thì =0 Và = 0. Mặt khác, có thể nhận các giá trị khác 0, bởi vì
từ đây
; Tất cả
những thứ kia. điều kiện Kuhn-Tucker được thỏa mãn nên điểm này là điểm cực trị.

Hình.7.2. Giải pháp đồ họa cho vấn đề phi tuyến

ví dụ lập trình 7.3

Điều kiện cần để tối ưu cho một bài toán quy hoạch phi tuyến có thể được phát biểu như sau. Cho phép
là nghiệm tối ưu của bài toán (7.4)–(7.6), và hàm
,
,
có thể phân biệt được ở thời điểm này Nếu như
là điểm không suy biến của tập bài toán chấp nhận được (7.4)–(7.6), thì nó là điểm Kuhn-Tucker của bài toán này.

Vì vậy, nếu một tập hợp được chấp nhận
bài toán (7.4)-(7.6) không có điểm kỳ dị và hàm số F(M),g Tôi (M), (
) khả vi tại mọi điểm
, thì giải pháp tối ưu cho vấn đề này nên được tìm kiếm trong số các điểm Kuhn-Tucker.

Như đã biết từ phân tích toán học, điểm đặc biệt tập hợp nghiệm có thể chấp nhận được của hệ phương trình tuyến tính và bất phương trình dạng

tức là tập hợp các giải pháp khả thi

nếu tại thời điểm
độ dốc của các hàm đó phụ thuộc tuyến tính
, trong đó biến thành . Ví dụ,
- điểm kỳ dị của tập hợp

Thật sự,

Vì vậy, nó là một hệ thống phụ thuộc tuyến tính.

Hàm chuyển màu
là một vectơ có tọa độ tương ứng bằng các giá trị đạo hàm riêng của hàm số
tại điểm M 0 . Vectơ này cho thấy hướng tăng trưởng nhanh nhất của hàm.

Điều kiện tối ưu cần thiết ít được sử dụng để giải hầu hết các bài toán quy hoạch phi tuyến, bởi vì Chỉ trong một số trường hợp hiếm hoi mới có thể tìm thấy tất cả các điểm Kuhn-Tucker của một bài toán quy hoạch phi tuyến.

Điều kiện đủ để tối ưuđối với bài toán quy hoạch phi tuyến: nếu
là điểm yên của hàm Lagrange của bài toán (7.4)–(7.6), khi đó
là giải pháp tối ưu cho vấn đề này.

Điều kiện này không cần thiết trong trường hợp tổng quát: hàm Lagrange có thể không có điểm yên ngựa, đồng thời vấn đề ban đầu quy hoạch phi tuyến có một giải pháp tối ưu.

Nhiều phương pháp khác nhau đã được biết đến cho phép người ta tìm ra giải pháp tối ưu cho bài toán quy hoạch phi tuyến một cách gần đúng. Tuy nhiên, những phương pháp này chỉ cung cấp một xấp xỉ khá tốt cho bài toán quy hoạch lồi, trong đó mọi cực trị cục bộ cũng là toàn cục. Nhìn chung, dưới dốc các phương thức hiểu các phương thức trong đó chuyển động đến điểm tối ưu của hàm trùng với hướng gradient của hàm này, tức là. bắt đầu từ một điểm nào đó
quá trình chuyển đổi tuần tự được thực hiện tới một số điểm khác cho đến khi xác định được giải pháp có thể chấp nhận được cho vấn đề ban đầu. Trong trường hợp này, các phương pháp gradient có thể được chia thành 2 các nhóm.

ĐẾN Đầu tiên Nhóm này bao gồm các phương pháp trong đó các điểm đang nghiên cứu không vượt quá phạm vi các giải pháp khả thi cho vấn đề. Phổ biến nhất trong số các phương pháp này là phương pháp Frank-Wolf (Sói). Các phương pháp như vậy bao gồm phương pháp độ dốc Rosen dự kiến, phương pháp hướng dẫn hợp lệ của Zeutendijk.

Công ty thứ hai Nhóm này bao gồm các phương pháp trong đó các điểm đang nghiên cứu có thể thuộc hoặc không thuộc vùng của các giải pháp khả thi. Tuy nhiên, do việc thực hiện quy trình lặp lại, một điểm trong vùng các giải pháp khả thi được tìm thấy để xác định một giải pháp có thể chấp nhận được.

Trong các phương pháp này, phương pháp được sử dụng phổ biến nhất là chức năng phạt hoặc phương pháp Mũi tên-Hurwitz.

Khi tìm giải pháp cho các bài toán bằng phương pháp gradient, bao gồm cả các phương pháp nêu trên, quá trình lặp được thực hiện cho đến khi khoảng khắc đó, trong khi độ dốc của hàm
tại điểm tiếp theo
sẽ không trở thành bằng 0 hoặc cho đến khi
, Ở đâu – một số dương khá nhỏ đặc trưng cho độ chính xác của lời giải thu được.

Việc giải các bài toán lập trình phi tuyến phức tạp bằng phương pháp gradient đòi hỏi một lượng lớn phép tính và chỉ nên sử dụng máy tính.

Bằng một ví dụ, chúng tôi sẽ chỉ ra ý nghĩa chung của các phương pháp gradient để giải các bài toán quy hoạch phi tuyến.

Giả sử có hàm hai biến
. Đặt giá trị ban đầu của các biến là
, và giá trị của hàm
. Nếu như
không phải là cực trị thì giá trị mới đó của biến được xác định
Và
sao cho giá trị tiếp theo của hàm
hóa ra gần với mức tối ưu hơn so với trước đó.

Kích thước của số gia tăng được xác định như thế nào? Và ? Để làm được điều này, tại các điểm Và Hướng thay đổi của hàm về phía cực trị được xác định bằng cách sử dụng gradient. Làm sao nhiều giá trị hơnđạo hàm riêng thì hàm số thay đổi về cực trị càng nhanh. Do đó số gia tăng Và được chọn tỷ lệ thuận với giá trị của đạo hàm riêng Và tại các điểm
Và
. Như vậy,
Và
, Ở đâu – một giá trị được gọi là bước, đặt ra thang đo thay đổi Và .

Ví dụ 7.4.

Hãy để nó là cần thiết để tối đa hóa chức năng

(tối đa tại điểm (3;2))


.

Tại điểm
,
Tại
chúng ta có

;
,

Hãy thực hiện thêm một lần lặp nữa. Tại điểm
,
Tại
chúng ta có

;
,

Hình.7.3. Giải thích hình học của hai bước

phương pháp gradient ví dụ 7.4

Trong bộ lễ phục. 7.3 cho thấy sự chuyển động dọc theo gradient, được thực hiện trong trong ví dụ này. Thái độ cho biết chiều thay đổi của hàm số theo hướng cực đại. Nếu chúng ta lấy gradient bằng dấu trừ thì chúng ta sẽ tiến về mức tối thiểu.

Một vấn đề cụ thể với phương pháp gradient là việc lựa chọn kích thước bước t. Nếu chúng ta thực hiện từng bước nhỏ, chúng ta sẽ tìm kiếm điều tối ưu trong một thời gian rất dài. Nếu bạn chọn giá trị của nó quá lớn thì giá trị tối ưu có thể bị “vượt qua”. Vấn đề trung gian trong việc chọn kích thước bước tối ưu được giải quyết bằng các phương pháp thích hợp. Nếu bước tđược xác định gần đúng, thì theo quy luật, chúng không rơi vào mức tối ưu mà rơi vào vùng của nó. Các phương pháp gradient cung cấp việc xác định tối ưu cục bộ. Khi tìm kiếm mức tối ưu toàn cục bằng cách sử dụng gradient, thường có nghi ngờ rằng mức tối ưu tìm được có tính chất tối ưu toàn cục. Đây chính là nhược điểm của phương pháp này khi giải các bài toán quy hoạch không lồi.

Câu hỏi tự kiểm tra

    Phát biểu bài toán quy hoạch phi tuyến.

    Quá trình tìm lời giải cho một bài toán lập trình phi tuyến bằng cách sử dụng diễn giải hình học của nó.

    Thuật toán phương pháp Lagrange giải bài toán quy hoạch phi tuyến.

    Ứng dụng phương pháp Lagrange để giải bài toán quy hoạch phi tuyến trong trường hợp điều kiện kết nối là bất đẳng thức.

    Các định nghĩa và định lý bổ trợ cần thiết để xem xét định lý trung tâm của quy hoạch phi tuyến - định lý Kuhn-Tucker.

    Định lý Kuhn-Tucker.

    Điều kiện tối ưu cần và đủ cho bài toán quy hoạch phi tuyến.

    Ý nghĩa chung của phương pháp gradient trong giải pháp gần đúng của các bài toán quy hoạch phi tuyến.

    Các nhóm phương pháp gradient để giải gần đúng các bài toán quy hoạch phi tuyến.

Định lý Kuhn-Tucker là tên gọi chung cho các phát biểu biểu thị sự khái quát hóa

ứng dụng định lý Lagrange vào trường hợp bài toán tối ưu hóa có ràng buộc dưới dạng bất đẳng thức, tức là bài toán

loại sau:

gj(x) > 0, j = 1, .

M, (?)

x = (x1, . . , xn) 2 X.

Đây f:X 7! R - (theo thuật ngữ đã được thiết lập) hàm mục tiêu, gr: X 7! R,

r = 1, . . . ,m là các hàm ràng buộc, X _ Rn là tập mở.

Định lý 196 (Định lý John dưới dạng điểm yên ngựa):

Cho các hàm f( ), g1( ), . . . , gn( ) là lõm và?x là nghiệm của bài toán (?), sao cho?x 2 intX.

Khi đó có các số nhân Lagrange _j >

X là giải pháp cho vấn đề

Chúng tôi trình bày các phát biểu này cho trường hợp các hàm f, gr khả vi (định lý Ku-

on-Tucker ở dạng vi phân).

Hãy nhớ lại rằng hàm

L(x,_) = _0f(x) +

được gọi là hàm Lagrange (Lagrange) của bài toán này, và các hệ số _j là các bội số

Lagrange.

Tuyên bố sau đây được giữ.

Định lý 197 (Định lý John cho hàm số khả vi):

Giả sử?x là nghiệm của bài toán (?), sao cho?x 2 intX và các hàm f( ), g1( ), . . . , gn( ) vi phân

có thể định lượng được tại điểm?x.

Khi đó có các số nhân Lagrange _j > 0, j = 0, . . . ,m, không phải tất cả bằng 0, như vậy mà

các mối quan hệ sau được thỏa mãn (điều kiện Kuhn-Tucker):

0, tôi = 1, . . . , N

J = 0 (điều kiện bổ sung

không cứng nhắc).

Lưu ý rằng các điều kiện cho độ chùng bổ sung có thể được viết dưới dạng

gj(?x)_j = 0, j = 1, . . . , m.

Từ những điều kiện này, suy ra rằng nếu số nhân Lagrange dương (_j > 0), thì hệ số tương ứng

ràng buộc trong việc giải bài toán (tại x = ?x) được thỏa mãn dưới dạng đẳng thức (tức là gj(?x) = 0). Người khác

nói cách khác, hạn chế này đang hoạt động. Mặt khác, trong trường hợp khi gj(?x) > 0 thì tương ứng

hệ số nhân Lagrange _j bằng 0.

Nếu trong bài toán (?) một số hạn chế có dạng hạn chế về tính không âm của một số xi,

thì đối với họ, bạn không thể giới thiệu hệ số nhân Lagrange bằng cách viết riêng các hạn chế sau:

gj(x) > 0, j = 1, . . . , tôi, (??)

xi > 0, i 2 P _ (1, . . ., n). Tại điểm bên trong (theo nghĩa là1 ?x 2 intX), điều kiện bậc nhất của i 2 P là

sẽ trông như thế này:

Với i /2 P ở đây, như trong trường hợp biểu diễn bài toán dưới dạng (?), đạo hàm của hàm Lagrange

đối với biến đó sẽ trông giống như @L(?x,_)

Ngoài ra, điều kiện không cứng nhắc bổ sung cũng được thỏa mãn

Từ điều kiện thứ hai, suy ra rằng với?xi > 0 (i 2 P)

Mặt khác, if @L(?x,_)/@xi Một sửa đổi khác của định lý có liên quan đến sự hiện diện của các ràng buộc dưới dạng đẳng thức trong bài toán. chỉ định

chúng ta hãy xác định tập hợp các chỉ số tương ứng thông qua E. Bài toán có dạng sau:

gj(x) > 0, j 2 (1, . . . ,m)\E,

gj(x) = 0, j 2 E, (???)

xi > 0, i 2 P _ (1, . . ., n).

Đồng thời, định lý John loại bỏ điều kiện mọi số nhân Lagrange đều không âm -

Các số nhân Lagrange _j với j 2 E có thể có dấu tùy ý.

Định lý John không đảm bảo rằng hệ số nhân Lagrange của hàm mục tiêu _0, khác 0.

Tuy nhiên, nếu _0 = 0 thì điều kiện Kuhn-Tucker không đặc trưng cho lời giải của bài toán đang xem xét mà là

cấu trúc của tập giới hạn tại điểm?x và định lý không có mối liên hệ trực tiếp nào với lãi suất

Nhiệm vụ hiện tại của chúng ta là cực đại hóa hàm f( ), vì gradient của hàm f( ) biến mất. từ

điều kiện Kuhn-Tucker.

Vì vậy, điều quan trọng là phải mô tả các điều kiện đảm bảo rằng _0 > 0.

Những điều kiện như vậy được gọi là điều kiện đều đặn.

Trong trường hợp bài toán đang xét là lồi, một trong những điều kiện của tính chính quy là

cái gọi là điều kiện Slater có dạng:

Trong trường hợp hàm mục tiêu và các ràng buộc của bài toán là khả vi, phương pháp đơn giản nhất

Điều kiện đều đặn được xây dựng dưới dạng gradient của các hàm ràng buộc và có dạng:

gradient của các ràng buộc tích cực tại điểm?x độc lập tuyến tính. (Trong số những hạn chế được xem xét là

những hạn chế về tính không tiêu cực cũng nên được đưa vào.)

Chúng ta hãy biểu thị bằng A tập hợp các chỉ số của các ràng buộc đó đang hoạt động ở điểm tối ưu?x

(bao gồm các chỉ số của tất cả các ràng buộc ở dạng đẳng thức), tức là

gj(?x) = 0, j 2 A.

Sau đó, nếu độ dốc ràng buộc là vectơ

độc lập tuyến tính2 thì _0 > 0. Điều kiện này được gọi là điều kiện chính quy Kuhn-Tucker.

Lưu ý rằng nếu _0 > 0 thì không mất tính tổng quát, chúng ta có thể giả sử _0 = 1, điều này thường được thực hiện.

Định lý tương ứng được gọi là định lý Kuhn-Tucker (trực tiếp). Định lý 198 (Định lý trực tiếp Kuhn-Tucker, điều kiện cần để tối ưu):

Cho các hàm f( ), g1( ), . . . , gn( ) khả vi và?x là nghiệm của bài toán (?), sao cho

X 2 intX và điều kiện chính quy Kuhn-Tucker được thỏa mãn.

Khi đó có các số nhân Lagrange _j > 0, j = 1, . . . ,m, sao cho khi _0 = 1 thỏa mãn

các tỉ số sau:

0, tôi = 1, . . . , N

Có thể dễ dàng phát biểu lại định lý này cho các bài toán (??) và (???). Các khả năng tương tự được yêu cầu ở đây.

sửa đổi các điều kiện Kuhn-Tucker, như trong định lý John.

0, tôi = 1, . . . , N

có thể được viết lại như sau:

Mối quan hệ này cho thấy rằng tại điểm tối ưu, độ dốc của hàm mục tiêu là một hàm tuyến tính.

sự kết hợp của các phản gradient của các giới hạn và tất cả các hệ số của tổ hợp tuyến tính này đều không âm

có giá trị lớn. Cơm. Hình 17.1 minh họa tính chất này. Theo trực giác, ý tưởng đằng sau tính chất này là

nếu bất kỳ hệ số nào của tổ hợp tuyến tính đều âm thì có thể xảy ra

tăng giá trị của hàm mục tiêu bằng cách di chuyển dọc theo ràng buộc này. Một trong những phiên bản nghịch đảo của định lý Kuhn-Tucker phát biểu rằng khi hàm số lõm

f( ), (gk( )) đáp ứng các điều kiện này trong một nghiệm chấp nhận được?x (tức là một điểm thỏa mãn ràng buộc

giá trị) đối với một số nhân Lagrange thỏa mãn yêu cầu của định lý trực tiếp,

đảm bảo rằng?x là giải pháp cho vấn đề.

Định lý 199 (Định lý Kuhn-Tucker nghịch đảo/điều kiện đủ để tối ưu/):

Cho f( ) là hàm lõm khả vi, g1( ), . . . , gn( ) - khả vi

các hàm tựa lõm, tập X là lồi và điểm?x được chấp nhận trong bài toán (?), và?x 2

Ngoài ra, giả sử tồn tại các số nhân Lagrange _j > 0, j = 1, . . . ,m, sao cho khi

0 = 1 các mối quan hệ sau được thỏa mãn:

0, tôi = 1, . . . , N

Khi đó?x chính là lời giải của bài toán (?).

Định lý có thể được phát biểu lại một cách rõ ràng cho các bài toán (??) và (???). Đối với nhiệm vụ (???)

các ràng buộc ở dạng đẳng thức chỉ có thể là tuyến tính (điều này là do thực tế là các ràng buộc ở dạng đẳng thức

các đẳng thức, gj(x) = 0, nên được biểu diễn bằng hai ràng buộc dưới dạng bất đẳng thức, gj(x) > 0

và?gj(x) > 0, mỗi giá trị này được cho bởi một hàm tựa lõm; điều này chỉ có thể xảy ra nếu

ràng buộc là tuyến tính).

Trong một phiên bản khác của điều kiện đủ tối ưu, giả định rằng mục tiêu là lõm

hàm được thay thế bằng giả định gần như lõm với việc bổ sung điều kiện rf(?x) 6= 0.

Định lý Kuhn-Tucker là sự tổng quát hóa các phương pháp giải bài toán tối ưu hóa theo hai hướng:

Lập trình tuyến tínhđến trường hợp phi tuyến, bằng cách tương tự, nhận được cái tên không mấy thành công là “lập trình phi tuyến”;

Ràng buộc đẳng thức phi tuyến trên ràng buộc bất đẳng thức.

Phương pháp và điều kiện Karush-Kuhn-Tucker ( Điều kiện Karush-Kuhn-Tucker, KKT) là các điều kiện chính thức cần thiết cho sự tối ưu của một bài toán quy hoạch phi tuyến. Ngoài ra, các điều kiện cần thiết bao gồm cái gọi là điều kiện chính quy cho các điểm dừng - tính không suy biến của tập hợp các gradient ràng buộc. Phương pháp này là sự tổng quát hóa của phương pháp nhân Lagrange cho trường hợp ràng buộc bất đẳng thức.

Kuhn và Tucker đã khái quát hóa phương pháp nhân tử Lagrange (dùng trong việc xây dựng tiêu chí tối ưu cho các bài toán có ràng buộc ở dạng đẳng thức) cho trường hợp nhiệm vụ chung lập trình phi tuyến với các hạn chế, cả ở dạng đẳng thức và bất đẳng thức.

Phương pháp chính trong lập trình phi tuyến vẫn là sử dụng hàm Lagrange thu được bằng cách chuyển các giới hạn sang hàm mục tiêu. Điều kiện Kuhn-Tucker cũng bắt nguồn từ nguyên lý này.

William Karush trong công việc tốt nghiệp năm 1931 ông đã tìm ra những điều kiện cần thiết trong trường hợp tổng quát của các hạn chế về đẳng thức và bất bình đẳng. Một cách độc lập, Harold Kuhn và Albert Tucker đã đi đến kết luận tương tự vào cuối năm 1941. Kết quả của họ tổng quát hơn.

Nếu, theo các hạn chế áp đặt, là một nghiệm của bài toán thì tồn tại một vectơ nhân tử Lagrange sao cho hàm Lagrange Các điều kiện được đáp ứng:

- tính cố định: ;

- sự mềm mại bổ sung: ;

- không tiêu cực:.

Các điều kiện cần thiết được liệt kê để có giá trị cực tiểu của hàm là không đủ trong trường hợp tổng quát. Có một số lựa chọn điều kiện bổ sung, điều đó làm cho chúng đủ:

- điều kiện đơn giản – 1) điểm đứng yên, 2) thỏa mãn điều kiện không cứng nhắc bổ sung, 3) Hệ số nhân Lagrange;

- tình trạng của Slater (yếu hơn) – 1) điểm đứng yên, 2) thỏa mãn điều kiện không cứng nhắc bổ sung, 3) .

Chúng ta hãy tiến hành trực tiếp đến việc chứng minh định lý Kuhn-Tucker.

Nếu hàm số liên tục n biến x = (x1,...,xn) F(x) có tại điểm X chọn tối đa thì tồn tại ε > 0 sao cho với mọi x từ lân cận ε của điểm X bán sỉ

F(x)

F(x)-F(x tùy chọn)<0.

Hãy chọn hai loại tăng xj dọc theo j tọa độ thứ

Δx j =x j -x jopt >0,

Δx j =x j -x jopt<0.



Chuyển các quan hệ này tới giới hạn tại Δ xj→ 0, chúng tôi nhận được:

Từ những mối quan hệ này suy ra rằng

(3.6.1)

Một mối quan hệ tương tự có thể thu được cho trường hợp hàm tối thiểu. Như vậy, sự cần thiết của các điều kiện (3.6.1) để đạt được tại điểm x bán buôn hàm tối đa hoặc tối thiểu f(x), tức là nếu có một cực trị thì điều kiện (3.6.1) được thỏa mãn. Nhưng đẳng thức bằng 0 của mọi đạo hàm tại điểm x bán buôn vẫn chưa đảm bảo sự tồn tại của cực trị trong đó, tức là các điều kiện (3.6.1) là không đủ. Về mặt hình học, điều này có nghĩa là trong trường hợp đạo hàm bằng 0 của hàm một biến thì có thể có một điểm uốn chứ không phải là cực đại (hoặc cực tiểu), và trong trường hợp hàm hai biến, có thể có một điểm yên, và không phải là cực trị, v.v. Do đó, các điểm x bán buôn, trong đó các quan hệ (3.6.1) được thỏa mãn được gọi là dừng.

Lưu ý rằng điều kiện (3.6.1) đạt được nhờ khả năng gán biến X số gia của hai dấu, đó là nơi xuất hiện hai bất đẳng thức tại và tại . Nếu phạm vi hợp lệ X giới hạn ở các giá trị không âm X≥0 thì nằm trong vùng nơi X> 0, điều kiện (3.6.1) vẫn hợp lệ vì cho phép tăng cả hai dấu ở đó. Ở ranh giới của khu vực X≥ 0, trong đó X= 0, chỉ cho phép tăng dương Δ X>0, chúng ta chỉ có thể nói về đạo hàm một phía, và từ (3.6.1) điều kiện cần thiết sau để đạt cực đại như sau:

Theo đó, điều kiện cần để có cực tiểu tại ranh giới của vùng xj= 0 sẽ được viết là

b) Bài toán cực trị có điều kiện

Khi xác định cực trị có điều kiện hàm khi bạn cần xác định giá trị lớn nhất (hoặc nhỏ nhất) của hàm F(x)ở điều kiện giới hạn:

g i (x) = b i , i = 1, ..., m,

f(x)=max;

g tôi (x)=b tôi ;

Phương pháp nhân tử Lagrange cũng được sử dụng, giống như trong trường hợp phép tính biến phân cổ điển, bao gồm việc giới thiệu hàm Lagrange

(3.6.2)

ở đâu λ tôi - yếu tố không xác định Lagrange.



Giả sử hàm số là trường hợp đặc biệt của hàm số, ta thu được các điều kiện cần thiết cho cực trị được tìm bằng đạo hàm trực tiếp của quan hệ (3.6.2) và được viết dưới dạng


Nếu chúng ta giới thiệu các vectơ

quan hệ (17-8) và (17-9) sẽ được viết lại thành

cấp Φ = cấp F - λ cấp φ = 0; (3.6.6)

trong đó đẳng thức của vectơ bằng 0 được hiểu theo từng thành phần.



 Hình 3.6.1 - Giải thích bài toán cực trị có điều kiện

Khi N= 2 và tôi= 1, bài toán hình học tìm cực trị có điều kiện được rút gọn (Hình 17-6) thành tìm điểm tiếp tuyến A của đường cong φ = bđến một trong những đường cong mức không đổi f= hằng số