Tối ưu hóa ràng buộc: Các điều kiện tối ưu

Xét bài toán quy hoạch phi tuyến tổng quát với mục tiêu phi tuyến:

Minimize f(x) (4.5.1a)

với các ràng buộc là:

gi(x) = 0 i = 1, 2,..., m (4.5.1b) và

j j j

x x x j = 1, 2, ..., n (4.5.1c) trong đó phương trình (4.5.1c) là một ràng buộc biên cho biến quyết định thứ j là xj với xjvà xj tương ứng là biên trên và biên dưới.

Trong một bài toán tối ưu hóa có ràng buộc, không gian khả thi không

được mở rộng vô hạn như một bài toán không ràng buộc. Như một hệ quả, nghiệm thỏa mãn điều kiện tối ưu của bài toán tối ưu hóa có ràng buộc không bảo đảm là khả thi trong các bài toán ràng buộc. Nói cách khác, một tối ưu địa phương cho một bài toán có ràng buộc có thể được đặt trên biên hay một góc của không gian khả thi mà tại đó vector gradient không bằng 0, Do đó, phải tiến hành những sự hiệu chỉnh các điều kiện tối ưu cho bài toán không ràng buéc.

H×nh 4.4.3

Dạng tìm kiếm của phương pháp hướng dốc nhất (theo Edgar và Himmelblau, 1988).

Những kết quả lý thuyết quan trọng nhất cho sự tối ưu hóa ràng buộc phi tuyến là các điều kiện Kuhn-Tucker. Những điều kiện này phải được thỏa mãn tại bất kỳ điểm tối ưu có ràng buộc nào, địa phương hay toàn cục, của bất kỳ bài toán quy hoạch tuyến tính và phi tuyến nào. Chúng hình thành nên cơ

sở cho sự phát triển của nhiều thuật toán tính toán.

Không mất tính tổng quát, xét một bài toán ràng buộc phi tuyến đã phát biểu trong phương trình (4.5.1) mà không có các ràng buộc về biên. Chú ý rằng phương trình ràng buộc (4.5.1b) đều là các ràng buộc đẳng thức. Theo

điều kiện này, phương pháp nhân tử Lagrange chuyển bài toán quy hoạch phi tuyến có ràng buộc sang một bài toán không ràng buộc bằng việc thiết lập thêm một hàm mục tiêu, gọi là hàm Lagrange. Với một sự tối ưu hóa, hàm Lagrange L(x,) được xác định bằng:

 ,    T  

L x   f x  g x (4.5.2) trong đó  là vector của các nhân tử Lagrange và g(x) là một vector của các phương trình ràng buộc. Về mặt đại số, phương trình (4.5.2) có thể được viết thành:

 1 1   1   1 

1

,..., , ,... ,..., ,...,

m

n m n i i n

i

L x x   f x x g x x



  (4.5.3)

trong đó L(x,) là hàm mục tiêu với m + n biến cần được cực tiểu hóa. Các

điều kiện cần và đủ để x* là nghiệm của cực tiểu hóa là:

1. f  x* là lồi và g(x*) là lồi trong vùng lân cận của x*; 2.

 

1

0 1,..., ;

m i i i

j j j

L f g

j n

x x  x



  

   

   

x*

(4.5.4a) 3.

  0 1,... ;

i i

L g x i m



   

 (4.5.4b)

4.

ikhông hạn chế về dấu i=1,...,m.

(4.5.4c) Việc giải các phương trình (4.5.4a) và (4.5.4b) đồng thời đưa ra nghiệm tối

­u.

Các nhân tử Lagrange có một sự thể hiện quan trọng trong tối ưu hóa. Với một ràng buộc cho trước, những nhân tử này chỉ ra giá trị hàm mục tiêu tối ưu sẽ thay đổi bao nhiêu với một thay đổi vi phân trong RHS của ràng buộc đó.

Đó là:

i i

f

b 

 

 x=x*

chứng tỏ rằng nhân tử Lagrange i là tốc độ thay đổi giá trị tối ưu của hàm mục tiêu gốc đối với một thay đổi giá trị của vế phải của ràng buộc thứ i. Các

i được gọi là các biến đối ngẫu hay giá mờ trong lĩnh vực kinh tế được đưa ra trong Môc 3.5.

Ví dụ 4.5.1. Xét bài toán sau:

Minimize (x1 - 1)2 + (x2 - 2)2 (a) víi

x1 - 2x2 =0 (b) Sử dụng phương pháp nhân tử Lagrange để giải bài toán này.

Lời giải. Hàm Lagrange là

 1, 2,   1 12  2 22  1 2 2

L x x   x   x   x  x (c)

áp dụng các phương trình (4.5.4a) và (4.5.4b), nghiệm tối ưu phải thỏa mãn các phương trình sau:

 1 

1

2 1 0

L x

x 

    

 (d)

 2 

2

2 2 2 0

L x

x 

    

 (e)

1 2 2 0

L x x



   

 (f) Giải những phương trình này, các nghiệm tối ưu của bài toán là x1*1, 6x*20,8 và *1.2. 4.5.2. Điều kiện Kuhn-Tucker

Các phương trình (4.5.4a)-(4.5.4c) tạo nên các điều kiện tối ưu cho một bài toán tối ưu chỉ gồm các ràng buộc đẳng thức. Các nhân tử Lagrange cùng với các ràng buộc đẳng thức là không hạn chế về dấu. Sử dụng phương pháp nhân tử Lagrange, các điều kiện tối ưu cho bài toán quy hoạch phi tuyến tổng quát có thể nhận được như sau:

Minimize f(x) víi

gi(x) = 0 i = 1, ..., m và

j j

j x x

x   j = 1, 2, ..., n

Dưới các dạng phương pháp Lagrange, bài toán cực tiểu hóa phi tuyến ở trên có thể được viết thành

Min L f  x Tg x Tx x Tx x  (4.5.5) trong đó , , và  là các vector của các nhân tử Lagrange tương ứng với các ràng buộc gi(x) =0, x x 0 và x x 0. Các điều kiện Kuhn-Tucker cho tính tối ưu của bài toán trên là:

T 0

xL xf x

     g (4.5.6a)

  0, 1, 2,...

gi x  i m (4.5.6b)

  j j 0, 1, 2,...,

j xj xj xj x j n

      (4.5.6c) - không hạn chế về dấu, 0,0 (4.5.6d)