Tối ưu hóa lồi - Điều kiện Fritz-John
Điều kiện cần thiết
Định lý
Xem xét vấn đề - $ min f \ left (x \ right) $ sao cho $ x \ in X $ trong đó X là một tập hợp mở trong $ \ mathbb {R} ^ n $ và đặt $ g_i \ left (x \ right) \ leq 0, \ forall i = 1,2, .... m $.
Cho $ f: X \ rightarrow \ mathbb {R} $ và $ g_i: X \ rightarrow \ mathbb {R} $
Hãy để $ \ hat {x} $ là một giải pháp khả thi và để cho f và $ g_i, i \ in I $ là phân biệt ở $ \ hat {x} $ và $ g_i, i \ in J $ liên tục ở $ \ hat { x} $.
Nếu $ \ hat {x} $ giải quyết cục bộ vấn đề trên thì tồn tại $ u_0, u_i \ in \ mathbb {R}, i \ in I $ sao cho $ u_0 \ bigtriangledown f \ left (\ hat {x} \ phải) + \ displaystyle \ sum \ limit_ {i \ in I} u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) $ = 0
trong đó $ u_0, u_i \ geq 0, i \ in I $ và $ \ left (u_0, u_I \ right) \ neq \ left (0,0 \ right) $
Hơn nữa, nếu $ g_i, i \ in J $ cũng có thể phân biệt được ở $ \ hat {x} $, thì các điều kiện trên có thể được viết là:
$ u_0 \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limit_ {i = 1} ^ m u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) = 0 $
$ u_ig_i \ left (\ hat {x} \ right) $ = 0
$ u_0, u_i \ geq 0, \ forall i = 1,2, ...., m $
$ \ left (u_0, u \ right) \ neq \ left (0,0 \ right), u = \ left (u_1, u_2, s, u_m \ right) \ in \ mathbb {R} ^ m $
Nhận xét
$ u_i $ được gọi là số nhân Lagrangian.
Điều kiện $ \ hat {x} $ khả thi cho bài toán đã cho được gọi là điều kiện khả thi ban đầu.
Yêu cầu $ u_0 \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limit_ {i = 1} ^ m ui \ bigtriangledown g_i \ left (x \ right) = 0 $ được gọi là tính khả thi kép tình trạng.
Điều kiện $ u_ig_i \ left (\ hat {x} \ right) = 0, i = 1, 2, ... m $ được gọi là điều kiện độ chùng bổ sung. Điều kiện này yêu cầu $ u_i = 0, i \ in J $
Cùng với điều kiện khả thi ban đầu, điều kiện khả thi kép và độ trễ bổ sung được gọi là Điều kiện Fritz-John.
Điều kiện đủ
Định lý
Nếu tồn tại $ \ varepsilon $ -neighbourhood $ \ hat {x} N_ \ varepsilon \ left (\ hat {x} \ right), \ varepsilon> 0 $ sao cho f là giả lồi trên $ N_ \ varepsilon \ left ( \ hat {x} \ right) \ cap S $ và $ g_i, i \ in I $ hoàn toàn là lồi giả trên $ N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $, rồi $ \ hat { x} $ là giải pháp tối ưu cục bộ cho vấn đề được mô tả ở trên. Nếu f là giả lồi tại $ \ hat {x} $ và nếu $ g_i, i \ in I $ đều là hàm giả lồi và chuẩn thực tại $ \ hat {x}, \ hat {x} $ là giải pháp tối ưu toàn cục cho vấn đề miêu tả trên.
Thí dụ
$ min \: f \ left (x_1, x_2 \ right) = \ left (x_1-3 \ right) ^ 2 + \ left (x_2-2 \ right) ^ 2 $
sao cho $ x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 5, x_1 + 2x_2 \ leq 4, x_1, x_2 \ geq 0 $ Và $ \ hat {x} = \ left (2 , 1 \ phải) $
Cho $ g_1 \ left (x_1, x_2 \ right) = x_ {1} ^ {2} + x_ {2} ^ {2} -5, $
$ g_2 \ left (x_1, x_2 \ right) = x_1 + 2x_2-4, $
$ g_3 \ left (x_1, x_2 \ right) = - x_1 $ và $ g_4 \ left (x_1, x_2 \ right) = -x_2 $.
Do đó, các ràng buộc trên có thể được viết là:
$ g_1 \ left (x_1, x_2 \ right) \ leq 0, $
$ g_2 \ left (x_1, x_2 \ right) \ leq 0, $
$ g_3 \ left (x_1, x_2 \ right) \ leq 0 $ và
$ g_4 \ left (x_1, x_2 \ right) \ leq 0 $ Do đó, $ I = \ left \ {1,2 \ right \} $, do đó, $ u_3 = 0, u_4 = 0 $
$ \ bigtriangledown f \ left (\ hat {x} \ right) = \ left (2, -2 \ right), \ bigtriangledown g_1 \ left (\ hat {x} \ right) = \ left (4,2 \ right ) $ và $ \ bigtriangledown g_2 \ left (\ hat {x} \ right) = \ left (1,2 \ right) $
Do đó, đặt các giá trị này trong điều kiện đầu tiên của điều kiện Fritz-John, chúng ta nhận được -
$ u_0 = \ frac {3} {2} u_2, \: \: u_1 = \ frac {1} {2} u_2, $ và đặt $ u_2 = 1 $, do đó $ u_0 = \ frac {3} {2} , \: \: u_1 = \ frac {1} {2} $
Như vậy điều kiện Fritz John được thỏa mãn.
$ min f \ left (x_1, x_2 \ right) = - x_1 $.
sao cho $ x_2- \ left (1-x_1 \ right) ^ 3 \ leq 0 $,
$ -x_2 \ leq 0 $ và $ \ hat {x} = \ left (1,0 \ right) $
Cho $ g_1 \ left (x_1, x_2 \ right) = x_2- \ left (1-x_1 \ right) ^ 3 $,
$ g_2 \ left (x_1, x_2 \ right) = - x_2 $
Do đó, các ràng buộc trên có thể được viết thành:
$ g_1 \ left (x_1, x_2 \ right) \ leq 0, $
$ g_2 \ left (x_1, x_2 \ right) \ leq 0, $
Do đó, $ I = \ left \ {1,2 \ right \} $
$ \ bigtriangledown f \ left (\ hat {x} \ right) = \ left (-1,0 \ right) $
$ \ bigtriangledown g_1 \ left (\ hat {x} \ right) = \ left (0,1 \ right) $ và $ g_2 \ left (\ hat {x} \ right) = \ left (0, -1 \ right ) $
Do đó, đặt các giá trị này trong điều kiện đầu tiên của điều kiện Fritz-John, chúng ta nhận được -
$ u_0 = 0, \: \: u_1 = u_2 = a> 0 $
Như vậy điều kiện Fritz John được thỏa mãn.