Các định nghĩa và kết quả bổ trợ
Nón cực của Ω ⊂ R n là tập
Cho ánh xạ đa trị F :R n ⇒ R n , ta kí hiệu:
F(x) là giới hạn trên (ngoài) Painlevé - Kuratowski dãy của F khi x tiến tới x Một tập Ω ⊂ R n được gọi là đóng xung quanh x ∈ Ω nếu tồn tại một lân cận U của x sao cho Ω∩clU là tập đóng Tập Ω được xem là đóng địa phương nếu điều này đúng với mọi x ∈ Ω Đối với tập Ω ⊂ R n là đóng xung quanh x ∈ Ω, nón pháp tuyến Fréchet của Ω tại x được định nghĩa như sau.
Nb(x,Ω) :( x ∗ ∈ R n | Lim sup x −→x Ω hx ∗ , x−xi kx−xk ≤ 0
, (1.2) trong đó x−→ Ω x nghĩa là x→ x với x ∈ Ω.
Nón pháp tuyến Mordukhovich Nb(x,Ω) của Ω tại x ∈ Ω nhận được từ các nón pháp tuyến Fréchet bằng việc lấy giới hạn trên Painlevé - Kuratowski dãy như sau
Nếu x /∈ Ω ta đặt N(x,Ω) := ∅ Đặc biệt, nếu Ω là tập lồi địa phương xung quanh x, nghĩa là có một lân cận U ⊂ R n của x sao cho Ω∩U là tập lồi thì ta có
N(x,Ω) := {x ∗ ∈ R n | hx ∗ , x−xi ≤ 0, ∀x ∈ Ω∩U} (1.4) Với một hàm giá trị thực mở rộng ϕ : R n → R :=R n ∪ {∞}, ta đặt domϕ :={x∈ R n |ϕ(x) 0 sao cho
(iii) Điểm x ∈ C được gọi là nghiệm hữu hiệu chính thường địa phương của bài toán (1.11) nếu tồn tại một lân cận U của x và λ ∈ intR m + sao cho
Ta ký hiệu các tập nghiệm hữu hiệu địa phương, nghiệm hữu hiệu cô lập địa phương và nghiệm hữu hiệu chính thường địa phương của bài toán (1.11) lần lượt là locS(P), locS iv (P) và locS p (P) Khi không gian U được định nghĩa là R n, các tập nghiệm này được ký hiệu tương ứng là S(P), S iv (P) và S p (P).
Theo tài liệu [4], ta có locS iv (P) thuộc tập con của locS(P) và locS p (P) cũng thuộc tập con của locS(P) Tuy nhiên, điều ngược lại không đúng, nghĩa là các tập locS iv (P) và locS p (P) có thể khác nhau.
Xét hai ví dụ sau:
Ví dụ 1.1 Cho f :R → R 2 xác định bởi f(x) := (f1(x), f2(x)) với f1(x) :( x, nếu x ≥ 0, 3x, nếu x < 0, f2(x) :( −3x, nếu x≥ 0,
−x, nếu x < 0, và cho g, h : R → R được xác định bởi g(x) := −|x| và h(x) := 0 với x∈ R Ta xét bài toán (1.11) với m= 2,Ω =R Chọn x= 0 ∈ C =R và ν = 1 ta có max{f 1 (x)−f 1 (x), f 2 (x)−f 2 (x)} = |x| ≥ ν|x|= ν|x−x|,∀x∈ C.
Như vậy, x thuộc vào tập hợp locS iv (P) nhưng không thuộc vào locS p (P) Giả sử ngược lại, tồn tại một lân cận U của x và điểm (λ 1 , λ 2 ) trong intR 2 + sao cho λ 1 f 1 (x) + λ 2 f 2 (x) lớn hơn hoặc bằng 0, tức là λ 1 f 1 (x) + λ 2 f 2 (x) = 0 cho mọi x trong U ∩ C Điều này dẫn đến một sự tương đương quan trọng.
( λ1x−3λ2x≥ 0, nếu x∈ U ∩(0,+∞), 3λ 1 x−λ 2 x≥ 0, nếu x∈ U ∩(−∞,0). Điều này cho ta λ2 ≥ 9λ2 (mâu thuẫn).
Ví dụ 1.2 Cho f : R → R 2 được xác định bởi f(x) := (f 1 (x), f 2 (x)) trong đó f1(x) := −x 4 , f2(x) := x 4 , và chog, h :R → Rxác định bởi g(x) := x−1, h(x) := 0 với x ∈ R Ta xét bài toán (1.11) với m = 2,Ω = R Chọn x= 0 ∈ C = (−∞,1] và λ :1
2f2(x), ∀x∈ C. Điều này cho thấy x ∈ locS p (P), trong khi đó x /∈ locS iv (P) với ν > 0. Thật vậy, với v > 0 cố định bất kì, bất đẳng thức max{f 1 (x)−f1(x), f2(x)−f2(x)} = x 4 ≥ ν|x|= ν|x−x|.
(không thỏa mãn ∀x ∈ C gần x) Do đó, x /∈ locS iv (P).
Vớix ∈ Ω, ta đặt I(x) = {i ∈ I|gi(x) = 0} và J(x) = {j ∈ J|hj(x) = 0}. Định nghĩa 1.2 Ta nói điều kiện chính quy (CQ) được thỏa mãn tại x∈ Ω nếu khụng tồn tại à i ≥ 0, i ∈I(x) và γ j ≥ 0 ∈ J(x) sao cho
Khi xem xét x ∈ C trong (1.12) với Ω = R n, điều kiện (CQ) được nêu sẽ đúng nếu điều kiện chính quy Mangasarian - Fromovitz được thỏa mãn trong trường hợp trơn Định lý sau đây cung cấp một điều kiện cần thiết cho nghiệm hữu hiệu cô lập của bài toán (1.11) theo định nghĩa (CQ) Định lý 1.1 khẳng định rằng (CQ) xác định trong Định nghĩa 1.2 sẽ thỏa mãn tại x ∈.
Ω Nếu x ∈locS iv (P) với ν > 0 nào đó thì νB R n ⊂ X k∈K λk∂fk(x) +X i∈I ài∂gi(x)
Lấy x ∈ locS iv (P) Đặt ϕ(x) = max
Xét bài toán tối ưu sau: minx∈C ϕ(x).
Nếu x thuộc tập hợp locS iv (P), thì tồn tại một lân cận U của x sao cho ϕ(x) ≥ 0 và ϕ(x) = 0 với mọi x trong giao điểm U và C Điều này chứng tỏ rằng x là một cực tiểu địa phương của phương trình (1.14) Do đó, x cũng là một cực tiểu địa phương trong bài toán tối ưu hóa vô hướng không có ràng buộc, được thể hiện qua (1.15) Khi áp dụng dạng không trơn của quy tắc Fermat cho bài toán (1.15), chúng ta có thể tiếp tục phân tích.
1≤k≤m{f k (x)−f k (x)}+δ(x, C) và ϕ 2 (x) := −kkx−xk Khi đó, ϕ+δ(., C) = ϕ1 +ϕ2 Do (1.16) nên ta có
Dễ thấy −ϕ2 là hàm lồi nên
Sử dụng Bổ đề 1.1 và (1.17) ta có
. Điều này dẫn dến νB R n ⊂ ∂ϕb 1(x) Như vậy, νB R n ⊂ ∂ϕ1(x) =∂
Hàm \( f_k(.) - f_k(x) \) là hàm Lipschitz liên tục quanh điểm \( x \) với \( 1 \leq k \leq m \), trong khi hàm \( \delta(., C) \) là nửa liên tục dưới quanh điểm này Áp dụng quy tắc tổng (1.10) vào (1.18) và từ mối quan hệ trong (1.7), ta có thể suy ra rằng \( \nu B R^n \subset \partial \).
(x) +N(x, C) (1.19) Đặt Ω :=e {x ∈ R n |g i (x) ≤ 0, i ∈ I, h i = 0, j ∈ J} Ta có C = Ωe ∩Ω. Điều kiện (CQ) thỏa món tại x kộo theo khụng tồn tại ài ≥ 0, i ∈ I(x) và γ j ≥ 0, j ∈J(x) = J sao cho P i∈I (x) à i + P j∈J(x) γ j 6= 0 và
Do đó, từ Mordukhovich [7, Hệ quả 4.36] ta có
Vì điều kiện (CQ) được thỏa mãn tại x, từ [7, Hệ quả 3.37] ta có
Bên cạnh đó, sử dụng công thức cho dưới vi phân cơ bản của hàm max (xem [7], Định lý 3.46(ii)) và quy tắc tổng (1.10) ta thu được
Đặt ài = 0 với i /∈ I(x) và áp dụng (1.13) từ (1.20) - (1.21), ta có thể chứng minh định lý Tuy nhiên, Định lý 1.1 có thể không đúng nếu điều kiện (CQ) không được thỏa mãn tại điểm xem xét, như minh họa trong ví dụ sau.
Cho hàm f: R → R^2 được xác định bởi f(x) = (f1(x), f2(x)) với f1(x) = f2(x) = x, cùng với các hàm g, h: R → R được định nghĩa bởi g(x) = x^2 và h(x) = 0 cho mọi x ∈ R Trong bài toán (1.11) với m = 2 và Ω = R, ta nhận thấy rằng C = {0} và x = 0 thuộc S iv (P) với ν > 0 bất kỳ Điều kiện (CQ) không được thỏa mãn tại x, dẫn đến việc (1.13) cũng không thỏa mãn Để thiết lập điều kiện đủ cho cực tiểu cô lập địa phương trong bài toán (1.11), định lý tiếp theo sẽ nhắc lại rằng một hàm ϕ: Ω ⊂ R^n → R là hàm lồi địa phương (hoặc affine địa phương) tại x ∈ Ω nếu tồn tại một lân cận.
Để U của x đảm bảo rằng Ω∩U là tập lồi và ϕ là hàm lồi (affine) trên Ω∩U, theo Định lý 1.2, nếu x thuộc C và fk (k ∈ K), gi (i ∈ I) là các hàm lồi địa phương tại x, cùng với hj (j ∈ J) là các hàm affine địa phương tại x, thì nếu x thỏa mãn điều kiện (1.13), ta có x thuộc locS iv (P).
Từ giả thiết của định lý, có một lân cận U của x sao cho U ∩ Ω là tập lồi, với f k (k ∈ K) và g i (i ∈ I) là các hàm lồi trên U ∩ Ω, trong khi h j (j ∈ J) là hàm affine trên cùng tập này Đặc biệt, với mọi z ∈ R n, ta có kzk = max z∈B R n (z ∗, z) Do đó, tồn tại z ∗ ∈ B R n sao cho kzk = h(z ∗, z).
Lấy bất kì x ∈U ∩C, tồn tại z ∗ ∈ B R n sao cho kx−xk =hx ∗ , x−xi (1.22)
Vì x∈ C thỏa mãn (1.13) nên tồn tại λ k ≥ 0, k ∈ K với P k∈K λ k = 1, z k ∗ ∈
∂fk(x), k ∈ K, ài ≥ 0, x ∗ i ∈ ∂gi(x) với àigi(x) = 0, i ∈ I, γj ≥ 0, y i ∗ ∈
∂h j (x)∪∂(−h j )(x), j ∈ J sao cho vx ∗ − X k∈K λkz k ∗ +X i∈I àix ∗ i +X i∈J γjy j ∗
Từ (1.4) suy ra νhx ∗ , x−xi − X k∈K λ k hz k ∗ , x−xi+X i∈I à i hx ∗ i , x−xi
Từ tính chất lồi địa phương của fk, gi và tính chất affine địa phương của h j ta có
X k∈K λkhz k ∗ , x−xi+X i∈I àihx ∗ i , x−xi+X i∈J γjhy j ∗ , x−xi
≤ X k∈K λk[fk(x)−fk(x)] +X i∈I ài[gi(x)−gi(x)]
(1.24) trong đó ωj ∈ {−1,1} và bất đẳng thức sau đúng vì à i g i (x) = 0, à i g i (x)≤ 0, i ∈ I và h j (x) = 0, h j (x) = 0, j ∈ J.
Kết hợp (1.22) với (1.23) và (1.24) ta nhận được νkx−xk ≤ X k∈K λk[fk(x)−fk(x)].
Suy ra x ∈ locS iv (P) vì x bất kì trong U ∩C
Tính lồi địa phương của hàm mục tiêu f tại điểm x là yếu tố quan trọng trong Định lý 1.2 Cụ thể, một điểm khả thi x thỏa mãn điều kiện (1.13) không nhất thiết phải là cực tiểu cô lập của bài toán (1.11) nếu hàm f không có tính lồi địa phương tại x.
Ví dụ 1.4 Cho f :R → R 2 được xác định bởi f(x) := (f 1 (x), f 2 (x)) với f1(x) = f2(x) :
0, nếu x= 0, và gọi g, h : R → R được xác định bởi g(x) := x− 1 và h(x) := 0 với x∈ R Xét bài toán (1.11) vớim = 2,Ω = RthìC = (−∞,1] Chú ý rằng f1, f2 là Lipschitz địa phương tại x= 0 ∈ C và∂f1(x) = ∂f2(x) = [−1,1].
Chúng ta thấy rằng điều kiện (1.13) được thỏa mãn với mọi ν ∈ (0,1] Tuy nhiên, điểm x không thuộc tập hợp lân cận địa phương S iv (P), vì các hàm f 1 và f 2 không lồi tại x Định lý 1.3 đưa ra điều kiện cần thiết cho nghiệm hữu hiệu chính thường địa phương của bài toán (1.11) với điều kiện (CQ) theo Định nghĩa 1.2 Cụ thể, nếu điều kiện (CQ) được thỏa mãn tại x ∈ Ω và x thuộc tập lân cận địa phương S p (P), thì tồn tại các giá trị λk > 0, k ∈ K, ai ≥ 0, i ∈ I và γj ≥ 0, j ∈ J.
Giả sử x ∈ locS p (P) Khi đó tồn tại một lân cận U của x và λ : (λ1, λm)∈ intR m + sao cho
X k∈K λ k [f k (x)−f k (x)]≥ 0, ∀x∈ U ∩C. Điều đó có nghĩa là x là một cực tiểu địa phương của bài toán tối ưu không có ràng buộc sau: minx∈C θ(x), trong đó θ(x) = X k∈K λkfk(x) (1.26)
X là cực tiểu địa phương trong bài toán tối ưu không ràng buộc, với x thuộc minR n θ(x) + δ(x, C) Áp dụng quy tắc Fermat không trơn cho bài toán này, ta có kết quả như sau.
Vì θ là Lipschitz địa phương tại x và δ(., C)) là nửa liên tục dưới quanh x, từ (1.10) và (1.7), ta có
0 ∈ ∂θ(x) +∂δ(x, C)) =∂θ(x) +N(x, C) (1.29) Tương tự chứng minh của Định lý 1.3 ta nhận được
(1.30) Áp dụng quy tắc tổng (1.10), từ (1.30) ta nhận được
0 ∈ X k∈K λk∂fk(x) +X i∈I ài∂gi(x) +X j∈J γj(∂hj(x)∪∂(−hj(x)) +N(x, Ω), à i ≥ 0, i ∈I(x), γ i ≥ 0, j ∈J(x).
Lấy à i = 0, i ∈ I(x) trong (1.31) ta nhận được (1.25) Định lý được chứng minh
Kết quả của Định lý 1.3 có thể không chính xác nếu điều kiện (CQ) không được thỏa mãn, như đã chỉ ra trong Ví dụ 1.3 Để xác định điều kiện đủ cho nghiệm hữu hiệu chính của bài toán (1.11) trong định lý tiếp theo, cần khái niệm về lồi bất biến vô hạn (suy rộng) cho hàm Lipschitz địa phương Theo Định nghĩa 1.3, một bộ ba (f, g, h) được gọi là L - lồi bất biến trên Ω tại x ∈ Ω nếu với mọi x ∈ Ω, z k ∗ thuộc ∂f k (x), k ∈ K, x ∗ i thuộc ∂g i (x), i ∈ I và y j ∗ thuộc (∂h j (x) ∪).
∂(−hj)(x)), j ∈J thì tồn tại v ∈ N(x,Ω) o sao cho f k (x)−f k (x) ≥ hz ∗ k , vi, k ∈ K, g i (x)−g i (x) ≥ hx ∗ i , vi, i ∈ I, hj(x)−hj(x) =ωjhy ∗ j , vi, j ∈ J. trong đó ω j = 1 (tương ứng ω j = −1) với y ∗ j ∈ ∂h j (x) (tương ứng y j ∗ ∈ ∂(−hj)(x).)
Nếu Ω lồi và các hàm f k (k ∈ K), g i (i ∈ I) và h j (j ∈ J) là affine, thì bộ ba (f, g, h) sẽ là L-lồi bất biến trên Ω cho mọi x ∈ Ω với v = x − x, x ∈ Ω Theo Định lý 1.4, nếu x ∈ C và (f, g, h) là L-lồi bất biến tại x, đồng thời x thỏa mãn điều kiện (1.25), thì x thuộc S p (P).
Giả sử tồn tại λ k > 0, k ∈ K, à i ≥ 0, i ∈ I và γ j ≥ 0, j ∈ Ω thỏa món (1.25) Khi đú, tồn tại z k ∗ ∈ ∂f k (x), k ∈ K, x ∗ i ∈ ∂g i (x) với à i g i (x) 0, i ∈ I và y j ∗ ∈ (∂hj(x)∪∂(−hj)(x)), j ∈ J sao cho
Do tính chất L - lồi bất biến của (f, g, h) trên Ω tại x, với mỗi x ∈Ω ta có v ∈ N(x,Ω) o sao cho
P k∈K λ k hz k ∗ , vi+P i∈I à i hx ∗ i , vi+ P j∈J γ j hy j ∗ , vi
≤ X k∈K λk[fk(x)−fk(x)] +X i∈I ài[gi(x)−gi(x)] +X j∈J
1 ω j γj[hj(x)−hj(x)], trong đó ωj ∈ {−1,1} Từ định nghĩa của nón cực (1.1), từ (1.32) và v ∈ N(x,Ω) o ta suy ra
0 ≤ X k∈K λkhz k ∗ , vi+X i∈I àihx ∗ i , vi+X j∈J γjhy j ∗ , vi
X k∈K λkfk(x)+X i∈I àigi(x)+X j∈J σjhj(x) ≤ X k∈K λkfk(x)+X i∈I àigi(x)+X j∈J σjhj(x), trong đó σ j = γ j ωj
∈ R, j ∈ J Chỳ ý rằng à i g i (x) = 0, i ∈ I và h j (x) 0, j ∈ J Do đó, khi x∈ C,
Từ đó suy ra x ∈ S p (P) Định lý được chứng minh
Đối ngẫu cho nghiệm hữu hiệu chính thường
Đối với z ∈ R n, với λ := (λ k), λ k > 0, k ∈ K và à := (à i), à i ≥ 0, i ∈ I, ta định nghĩa hàm fe(z, λ, à, γ) := f(z) + hà, g(z)ie + hγ, h(z)ie, trong đó e := (1,1, ,1) ∈ R m Trong bối cảnh bài toán tối ưu đa mục tiêu có ràng buộc (P) theo phương trình (1.11), chúng ta sẽ xem xét bài toán đối ngẫu đa mục tiêu D w theo nghĩa Wolfe max.
Tập chấp nhận được C w được xác định bởi
Một nghiệm hữu hiệu địa phương của bài toán đối ngẫu (1.33) được định nghĩa tương tự như trong định nghĩa (1.11) bằng cách thay đổi các ký hiệu liên quan Tập hợp các nghiệm hữu hiệu của bài toán (1.33) được ký hiệu là S(D w ) Để đơn giản hóa, ký hiệu u v được sử dụng để biểu thị mối quan hệ giữa u và v Định lý 1.5 mô tả quan hệ đối ngẫu yếu giữa bài toán cơ sở (P) và bài toán đối ngẫu Dw, với điều kiện rằng nếu (f, g, h) là L - lồi bất biến trên Ω tại z, thì f(x) fe(z, λ, à, γ).
K, à = ài, ài ≥ 0, x ∗ i ∈ ∂gi(z), i ∈ I và γ := (γj), γj ≥ 0, y j ∗ ∈ ∂hj(z)∪
Giả sử ngược lại, f(x) fe(z, λ, à, γ) (1.37)
Do λ∈ int R m +, ta cú hλ, f(x)−fe(z, λ, à, γ)i < 0 Điều này tương đương với bất đẳng thức sau hλ, f(x)−f(z)i − hà, g(z)i − hγ, h(z)i < 0 (1.38)
Do tính chất L - lồi bất biến của (f, g, h) trên Ω tại z, với mỗi x như vậy tồn tại v ∈ N(z,Ω) o sao cho
P k∈K λkhz k ∗ , vi+P i∈I àihx ∗ i , vi+ P j∈J γjhy j ∗ , vi
1 ω j γ j [h j (x)−h j (z)], trong đó ωj ∈ {−1,1} Từ định nghĩa của nón cực (1.1), từ (1.34) và v ∈ N(z,Ω), ta suy ra
0 ≤ X k∈K λ k hz k ∗ , vi+X i∈I à i hx ∗ i , vi+X j∈J γ j hy j ∗ , vi.
Như vậy, bằng cách đặt σj := γj ω j ∈R, j ∈ J, ta có
0 ≤ hλ, f(x)−f(z)i+hà, g(x)−g(z)i+hσ, h(x)−h(z)i (1.39) trong đúσ = (σ j ), j ∈ J Do x∈ C, ta suy ra hà, g(x)i ≤ 0 và hσ, h(x)i 0 Vì vậy, (1.39) trở thành
Chú ý rằng kσk = kγk, do kσjk = kγjk, với mọi j ∈ J Kết hợp (1.36), (1.38), (1.40) ta đi đến mâu thuẫn Định lý được chứng minh
Ví dụ sau chỉ ra rằng tính chất L - lồi bất biến của (f, g, h) trên Ω ở định lý trên không thể bỏ được.
Ví dụ 1.6 Cho f : R → R 2 được xác định bởi f(x) := (f 1 (x), f 2 (x)) với f1(x) = f2(x) := x 5 và gọi g, h : R → R được xác định bởi g(x) := −|x| và h(x) := x 2 +x với x ∈ R Xét bài toán (1.11) với m = 2, Ω = R Khi đó, C = {−1,0} và ta lấy x =−1 ∈C.
Xét bài toán đối ngẫu D w trong (1.33) Chọn z = 0 ∈ Ω, λ 1
, à = 1 và γ = 1 ta cú (z, λ, à, γ) ∈ C w Ta thấy (f, g, h) khụng là L - lồi bất biến trên Ω tại x Khi đó, f(x) = (−1,−1) (0,0) = fe(z, λ, à, γ)i.
Trong bài viết này, chúng tôi phân tích mối quan hệ giữa bài toán tối ưu đa mục tiêu và bài toán đối ngẫu, đặc biệt là trong trường hợp có ràng buộc Cụ thể, chúng tôi chỉ ra rằng quan hệ h(z)∈ (γ−S(0, kγk)) trong biểu diễn của tập ràng buộc Cw là một yếu tố quan trọng trong bài toán đối ngẫu, không giống như các bài toán không có ràng buộc đẳng thức Định lý 1.6 cũng được trình bày, cho thấy mối quan hệ đối ngẫu mạnh giữa bài toán xuất phát (P) và bài toán đối ngẫu (Dw), với điều kiện rằng x ∈ locS p (P) và thỏa mãn điều kiện xác định trong Định nghĩa 2.1.
0, j ∈ J sao cho (x, λ, à, γ) ∈ C w và f(x) := f(x, λ, à, γ) Hơn nữa, nếu (f, g, h) là L - lồi bất biến trờn Ω tại mọi z ∈ Ω, thỡ (x, λ, à, γ) ∈ S(D w ).
Theo Định lý 1.3, x thỏa mãn (1.25) nghĩa là tồn tại λk > 0, k ∈
Giả sử j ∈ J ta có λ = (λ k ), với λ k > 0, k ∈ K, hλ, ei = 1, à := (à i ), à i ≥ 0, i ∈ I và γ = (γ j ), γ j > 0, j ∈ J Khẳng định (1.42) vẫn đúng khi thay thế λk, ài, γj tương ứng bằng λk, à i , γ j Do x ∈ C nên h j (x) = 0, ∀j ∈ J, từ đó suy ra hγ j − σ, h(x)i = 0 ∀σ (σj), σj ∈ R, j ∈ J với kσk = kγk, nghĩa là h(x) ∈ (γ −S(0, kγk)) o, do đó x, λ, à, γ) ∈Cw Nếu g(x)i = hγ, h(x)i = 0 thì f(x) = f(x) + hà, g(x)ie + hγ, h(x)ie = fe(x, λ, à, γ)i Giả sử (f, g, h) là L - lồi bất biến trên Ω với mọi z ∈ Ω, sử dụng kết quả đối ngẫu yếu trong Định lý 1.5, ta khẳng định f(x) f(z, λ, à, γ), ∀(z, λ, à, γ) ∈.
Cw Từ đú và (1.43) ta suy ra (x, λ, à, γ) ∈ S(Dw)
Điều kiện (CQ) trong định lý đóng vai trò quan trọng, vì nếu x là nghiệm hữu hiệu chính thường địa phương mà không thỏa mãn (CQ), thì không thể tìm được bộ ba (λ, à, γ) như mô tả trong Định lý 1.6 để (x, λ, à, γ) thuộc tập chấp nhận được của bài toán đối ngẫu Do đó, trong trường hợp này, quan hệ đối ngẫu mạnh sẽ không tồn tại.
Kết quả đối ngẫu mạnh trong Định lý 1.6 không xuất hiện theo cách thông thường, khi mà nghiệm của bài toán đối ngẫu chỉ là nghiệm hữu hiệu, không phải là nghiệm hữu hiệu chính thường, trong khi nghiệm của bài toán xuất phát lại là nghiệm hữu hiệu chính thường Một ví dụ minh họa rằng, nói chung, không thể đạt được nghiệm hữu hiệu chính thường cho bài toán đối ngẫu, ngay cả trong trường hợp lồi Tuy nhiên, với một số giả thiết bổ sung, có khả năng thu được nghiệm hữu hiệu chính thường cho bài toán đối ngẫu.
Ví dụ 1.7 Cho f : R → R 2 được xác định bởi f(x) := (f1(x), f2(x)), trong đó f 1 (x) := x, f 2 (x) := −x và g : R → R được xác định bởi g(x) = x − 1 với x ∈ R Xét bài toán (1.11) với m = 2, Ω = R, I {1}, J = ∅ thì C = (−∞,1] và chọn x= 0 ∈ C Suy ra x := 0 ∈ S p (P), vì 1
Xét bài toán đối ngẫu (Dw) trong (1.33) Tập ràng buộc
Cw := {(z, λ, à)|λ1 − λ2 + à = 0, λ1 + λ2 = 1}, với z ∈ R, λ := (λ1, λ2), λ1 > 0, λ2 > 0, à ≥ 0 Hàm mục tiêu fe(z, λ, à) được định nghĩa là (fe1(z, λ, à), fe2(z, λ, à)), trong đó fe1(z, λ, à) := z + à(z − 1) và fe2(z, λ, à) := −z + à(z − 1) Điều kiện (CQ) được thỏa mãn tại x, và vì fk, k = 1,2 và g là hàm lồi, nên (f, g) là L-lồi bất biến trên Ω tại mọi z ∈ Ω Theo Định lý 1.6, tồn tại λ := (λ1, λ2) với λ1 > 0, λ2 > 0 và à ≥ 0 sao cho (x, λ, à) thuộc S(Dw).
Ta sẽ chỉ ra rằng (x, λ, à) ∈ S/ p (Dw) Thật vậy, giả sử ngược lại, (x, λ, à)∈ S p (D w ), nghĩa là tồn tại (β 1 , β 2 )∈ intR 2 + sao cho β1fe1(z, λ, à) +β2fe2(z, λ, à) ≤ β1fe1(x, λ, à)
Với bất kỡ à ∈ (0,1), lấy λ = (λ 1 , λ 2 ) với λ 1 = 1−à
2 ta có (z, λ, à) ∈ Cw, ∀z ∈ R Hơn nữa, với mọi z ∈R đủ lớn, fe 1 (z, λ, à)−fe 1 (x, λ, à) =z(1 +à)−à+à > 0, fe2(x, λ, à)−fe2(z, λ, à) = z(1−à) +à−à > 0,
Do đó và từ (1.44) ta thu được β1 β 2 ≥ fe1(z, λ, à)−fe1(x, λ, à) fe 2 (x, λ, à)−fe 2 (z, λ, à) = z(1 +à)−à+à z(1−à) +à−à (1.45)
Vỡ phõn số cuối trong (1.45) tiến đến vụ cựng khi à → 1 và z → ∞ nờn ta thu được mâu thuẫn.
Chương 2 Điều kiện tối ưu và đối ngẫu cho các nghiệm hữu hiệu và nghiệm hữu hiệu yếu của bài toán tối ưu đa mục tiêu không trơn
Chương 2 giới thiệu các điều kiện cần thiết cho nghiệm hữu hiệu yếu và nghiệm hữu hiệu trong bài toán tối ưu đa mục tiêu với ràng buộc đẳng thức và bất đẳng thức, dựa trên công cụ giải tích biến phân Các điều kiện đủ cho nghiệm hữu hiệu yếu và nghiệm hữu hiệu được nêu rõ với giả thiết về tính lồi suy rộng dưới ngôn ngữ dưới vi phân giới hạn Ngoài ra, chương này cũng trình bày các định lý đối ngẫu yếu và mạnh kiểu Wolfe cùng với Mond - Weir.
2.1 Các kết quả bổ trợ
Ta kí hiệu chuẩn trong không gian tuyến tính định chuẩn là k.k Trong không gianX×Y thì chuẩn được xác định bởik(x, y)k =kxk+kyk, ∀x∈
Trong không gian X, với y ∈ Y, cặp chính tắc giữa X và đối ngẫu X ∗ được ký hiệu là h., i Hình cầu đóng trong X với tâm x ∈ X và bán kính r > 0 được ký hiệu là B X (x, r), trong đó hình cầu đơn vị đóng thường được ký hiệu là BX Bao đóng tôpô của tập hợp Ω ⊂ X được ký hiệu là clΩ, trong khi phần trong tôpô được ký hiệu là intΩ Nón cực của Ω ⊂ X là tập hợp các điểm liên quan đến Ω.
Trong chương này, không gian X được giả định là không gian Ausplund, nghĩa là đây là một không gian Banach trong đó mọi không gian con tách được của X đều sở hữu đối ngẫu tách được.
Nhắc lại: Không gian định chuẩn X (vô hạn chiều) được gọi là tách được nếu X có một tập con đếm được trù mật trong X.
Kí hiệu R m + là orthant không âm của R m với m ∈N, m :={1,2, }. Cho hàm đa trị F :X ⇒X ∗ từ X vào X ∗ Ta kí hiệu
−→ x ∗ , x ∗ n ∈F(xn), ∀n ∈ N} là giới hạn trên/ ngoài Painlevé - Kuratowski dãy củaF khi x→ x, trong đó kí hiệu w
−→ chỉ sự hội tụ theo tôpô yếu của X ∗
Tập hợp Ω ⊂ X được xem là tập đóng quanh điểm x ∈ Ω nếu tồn tại một lân cận U của x sao cho giao của Ω với bù của U là tập đóng Hơn nữa, Ω được gọi là đóng địa phương nếu điều này xảy ra với mọi điểm x thuộc Ω.
Các nón pháp tuyến Fréchet của Ω quanh x∈ Ω được xác định bởi
Nb(x,Ω) :( x ∗ ∈ X ∗ | Lim sup x −→x Ω hx ∗ , x−xi kx−xk ≤ 0
, (2.1) trong đó x−→ Ω x nghĩa là x→ x với x ∈ Ω.
Nón pháp tuyến Mordukhovich Nb(x,Ω) của Ω tại x ∈ Ω nhận được từ nón pháp tuyến Fréchet bằng cách lấy giới hạn trên Painlevé - Kuratowski dãy như sau
Điểm x ∈ Ω 1 ∩ Ω 2 được coi là một điểm cực trị địa phương của hai tập hợp Ω 1 và Ω 2 trong không gian X nếu tồn tại một lân cận U của x, trong đó với mọi ε > 0, luôn tồn tại một điểm a thuộc εBX.
Chú ý rằng điều kiện Ω1 ∩ Ω2 = {x} không nhất thiết kéo theo x là một điểm cực trị địa phương của {Ω 1 ,Ω2} Để minh họa điều này, ta xét
Giả sử X là không gian Asplund, nguyên lý cực trị xấp xỉ trong X chỉ ra rằng nếu x ∈ Ω 1 ∩ Ω 2 là một điểm cực trị địa phương của Ω 1 và Ω 2, thì với mọi ε > 0, tồn tại x 1 ∈ Ω 1 ∩ B X (x, ε) và x 2 ∈ Ω 2 ∩ B X (x, ε).
Cho hàm thực mở rộng ϕ :X →R := [−∞,∞] Ta đặt domϕ :={x∈ X |ϕ(x) < ∞}, epiϕ :={(x, à) ∈X ìR|à ≥ ϕ(x)}.
Dưới vi phân Mordukhovich và dưới vi phân Fréchet của ϕ tại x∈ X với
Cho f : X → R m và y ∗ ∈ R m , ta định nghĩa hy ∗ , fi(x) := hy ∗ , f(x)i, x ∈
Các kết quả tiếp theo là các công thức vô hướng hóa của đối đạo hàm.
Bổ đề 2.1 [7, 8] Cho y ∗ ∈R m và f : X → R m là hàm liên tục Lipschitz quanh x∈ X Ta có
Quy tắc tổng dưới vi phân giới hạn sau là cần thiết có các chứng minh tiếp theo.
Theo Bổ đề 2.2 và Định lý 3.36, cho các hàm ϕ_i: X → R, với i = 1, 2, , n và n ≥ 2, là các hàm nửa liên tục dưới tại x ∈ X Tất cả các hàm này, ngoại trừ một hàm, đều liên tục Lipschitz tại x.
Bổ đề 2.3 khẳng định rằng cho hai hàm ϕ i : X → R, với i = 1,2, là chính thường, trong đó ϕ1 là hàm liên tục Lipschitz quanh điểm x thuộc domϕ1∩domϕ2 và ϕ2 là hàm nửa liên tục dưới tại điểm này Nếu tổng ϕ 1 + ϕ 2 đạt cực tiểu địa phương tại x, thì với mọi η > 0, tồn tại một điểm xi thuộc x + ηBX.
Nhắc lại [7]: Một tập đóng địa phương Ω ⊂ X là compact pháp tuyến dãy (SNC) tại x∈ Ω nếu với bất kì dãy xk
Điều kiện tối ưu
Phần này trình bày các điều kiện tối ưu cho bài toán tối ưu đa mục tiêu.
ChoΩlà tập con khác rỗng, đóng địa phương của X vàK :={1,2, , m};
Trong bài viết này, chúng ta xem xét các tập chỉ số I và J, với I := {1,2, , p} ∪ ∅ và J := {1,2, , q} ∪ ∅ Giả sử có các hàm vectơ f := (f 1 , f 2 , , f m ); g := (g 1 , g 2 , , g p ) và h := (h 1 , h 2 , , h q ) có thành phần Lipschitz địa phương trên không gian X Chúng ta cũng giả định rằng Ω là (SNC) tại điểm đang được xem xét, và giả định này được thỏa mãn tự động khi không gian X là hữu hạn chiều.
Xét bài toán tối ưu đa mục tiêu có ràng buộc (P) sau: min
{f(x)|x∈ C}. Ở đây, tập C được xác định bởi
C := {x ∈ Ω|g i (x) ≤ 0, i ∈ I, h j (x) = 0, j ∈J} (2.7) Định nghĩa 2.1 (i) Ta nói rằng x ∈C được gọi là nghiệm hữu hiệu của bài toán (P) và viết x ∈ S(P), nếu
(ii) Điểmx ∈ C được gọi là nghiệm hữu hiệu yếu của bài toán (P) và viết x∈ S w (P), nếu
I(x) := {i ∈ I |gi(x) = 0}, J(x) := {j ∈ J |hj(x) = 0}. Định nghĩa 2.2 Ta nói điều kiện (CQ) thỏa mãn tại x ∈ Ω nếu không tồn tại βi ≥ 0, i ∈I(x) và γj ≥ 0, j ∈J(x) sao cho
Khi xét x ∈ C trong (2.7) với Ω = X, điều kiện (CQ) thỏa mãn do điều kiện chính quy Mangasarian - Fromovitz trong bài toán trơn.
Bây giờ ta phát biểu điều kiện Karush - Kuhn - Tucker (KKT) Điểmx∈ C thỏa mãn điều kiện (KKT) nếu tồn tại λ := (λ1, λ2, , λm) ∈
Khi f, g, h là các hàm trơn, điều kiện (2.8) trở thành điều kiện Karush - Kuhn - Tucker cổ điển Định lý 2.1 chỉ ra rằng nếu điều kiện (CQ) được thỏa mãn tại x ∈ Ω và x thuộc tập S w (P), thì x sẽ thỏa mãn điều kiện KKT, cung cấp một điều kiện cần cho nghiệm hữu hiệu (yếu) của bài toán (P).
Chứng minh Đặt y := f(x) và giả sử f là hàm Lipschitz quanh x với hằng số
` > 0 Trước hết, ta chứng minh rằng với mỗi k ∈ N, tồn tại x 1k ∈
Nb(x 1k ;C) với kx ∗k k ≤`+ 1 và λ k ∈ Nb(y k ;y −R m +) với kλ k k = 1 sao cho
Ta thấy rằng, (x, y) là một diểm cực trị địa phương của {Ω 1 ,Ω 2 } Nếu không, đối với bất kì lân cận U nào của (x, y) tồn tại εU >0 sao cho với mỗi a∈ ε U B X × R m ,
Do đó, ta chọn a := (a 1 , a 2 ) ∈ ε U B X × R m với a 1 := 0 ∈ X, a 2 ∈ − intR m +.
Do (2.10), tồn tại (x, f(x)) ∈ U thỏa mãn
(x, f(x))∈ C ×(y−R m +) + (0, a 2 ). Điều này kéo theo x ∈C và f(x)−y ∈a 2 −R m + Mối quan hệ thứ hai cho ta f(x)−f(x) ∈ −intR m +, mâu thuẫn vớix ∈ S w (P) Vậy, (x, y) là một điểm cực trị địa phương của {Ω1,Ω2}.
Ta chọn ε k > 0 thỏa mãn εk 0, ta tiến hành chia phương trình (2.16) cho ky k 1∗ k Đặt x ∗k = x 1∗ k ky 1∗ k, với k thuộc Nb(x 1k ;C), và λ k = y k 1∗ ky k 1∗ k, trong đó k thuộc Nb(y k ;y − R m +) Ta có kλ k k = 1 và kx ∗k k ≤ ` + 1, điều này được xác nhận bởi bất đẳng thức trong (2.17) và (2.11) Áp dụng (2.11) một lần nữa, ta rút ra được (2.9) từ (2.16).
Tiếp theo, ta chỉ ra sự tồn tại của λ ∈ N(y, y −R m +) với kλk = 1 sao cho
Theo sự khẳng định trong (2.9), chuỗi {x ∗k } và {λ k } bị chặn Hơn thế, do X là Asplund, không mất tính chất tổng quát ta giả sử rằng x ∗k w
Khi xem xét các yếu tố x ∗ ∈ X ∗ và λ k → λ ∈ R m với k → ∞ và kλk = 1, theo định nghĩa của nón pháp tuyến Mordukhovich, ta có thể kết luận rằng x ∗ thuộc N(x, C) và λ thuộc N(y; y − R m +) Hơn nữa, từ (2.9) suy ra rằng với mỗi k ∈ N, x ∗k thuộc ∂hλb k, fi(x 2k) và b ∗k thuộc BX ∗, sao cho ex ∗k = −x ∗k − 1 kb ∗k Như vậy, không mất tính chất tổng quát, ta giả sử rằng b ∗k w.
−→∗ b ∗ ∈BX khi k → ∞, và do đó xe ∗k −→ −x w ∗ ∗ khi k → ∞ Theo Bổ đề 2.1 bao hàm thức x ∗k ∈∂hλb k , fi(x 2k ) tương đương với
, k ∈ N (2.20) Cho k → ∞ trong (2.20) và lưu ý (2.2) ta nhận được
(−x ∗ ,−λ) ∈ N((x, f(x)); gphf). Điều này tương đương với
−x ∗ ∈ ∂hλ, fi(x) do Bổ đề 2.1 Vì thế, (2.19) được chứng minh. Đặt
Khi đó, ta cóC = Ω∩Ω Điều kiện (CQ) thỏa mãn tạie x, cho nên không tồn tạiβi ≥ 0, i ∈ I(x)và γj ≥ 0, j ∈ J(x) =J sao cho P i∈I(x) βi+ P j∈J (x) γj 6= 0 và
(2.21) bởi vì điều kiện (CQ) thỏa mãn tại x vàΩ được giả thiết là SNC tại điểm này, áp dụng Bổ đề 2.4 ta có
N(x;C) = N(x;Ωe ∩Ω) ⊂ N(x;Ω) +e N(x; Ω). Điều này cùng với (2.19) và (2.21) dẫn đến
Do λ∈ N(y;y−R m +) = R m +, ta có thể giả định rằng λ := (λ 1 , λ 2 , , λ m ) ∈
R m + Sử dụng quy tắc tổng (2.6), do (2.22) ta nhận được
Cuối cùng, lấy βi := 0 với i /∈ I(x), từ (2.23) ta suy ra x thỏa mãn điều kiện (KKT) Định lý được chứng minh
Một ví dụ đơn giản dưới đây minh họa rằng kết luận của Định lý 2.1 có thể không đúng nếu điều kiện (CQ) không được thỏa mãn tại điểm đang xem xét.
Cho hàm f : R → R² được xác định bởi f(x) = (f₁(x), f₂(x)) với f₁(x) = f₂(x) = x, x ∈ R Hàm g và h được xác định bởi g(x) = x² và h(x) = 0, x ∈ R Xét bài toán (P) với m = 2 và Ω = R, trong trường hợp này, C = {0}, dẫn đến x = 0 ∈ S w (P) (= S(P)) Tuy nhiên, điều kiện (CQ) không thỏa mãn tại x, và x cũng không thỏa mãn điều kiện (KKT).
Một điểm thỏa mãn (KKT) trong (2.8) không nhất thiết là nghiệm hữu hiệu yếu của bài toán (P), ngay cả khi điều kiện trơn được thỏa mãn Ví dụ dưới đây sẽ minh họa rõ ràng cho trường hợp này.
Ví dụ 2.2 cho hàm f : R → R² được xác định bởi f(x) := (f₁(x), f₂(x)) với f₁(x) = f₂(x) := x³, x ∈ R, và các hàm g, h : R → R được xác định bởi g(x) := -x², h(x) := 0, x ∈ R Trong bài toán tối ưu (P) với m = 2 và Ω = R, ta có C = R, do đó x = 0 ∈ C thỏa mãn điều kiện KKT, nhưng x lại không thuộc S w (P) Để trình bày các điều kiện đủ tối ưu cho nghiệm hữu hiệu (yếu) của bài toán (P), trong định lý tiếp theo, cần áp dụng các khái niệm lồi affine mở rộng cho hàm Lipschitz địa phương Định nghĩa 2.3 (i) cho biết rằng (f, g, h) là L-lồi bất biến trên Ω tại x ∈ Ω nếu với mọi x ∈ Ω, zₖ* ∈ ∂fₖ(x), k ∈ K, xᵢ* ∈ ∂gᵢ(x), i ∈ I, và yⱼ* ∈ ∂hⱼ(x).
∂(−hj)(x)j ∈J, tồn tại v ∈ N(x; Ω) o sao cho fk(x)−fk(x) ≥ hz ∗ k , vi, k ∈ K, g i (x)−g i (x) ≥ hx ∗ i , vi, i ∈ I, hj(x)−hj(x) =ωjhy ∗ j , vi, j ∈ J, trong đó ω j = 1 (tương ứng ω j = −1) khi y j ∗ ∈ ∂h j (x) (tương ứng y j ∗ ∈ ∂(−hj)(x)).
(ii) Ta nói (f, g, h) là L - lồi bất biến chặt trên Ω tại x ∈ Ω nếu với mọi x ∈ Ω\ {x}, z k ∗ ∈ ∂f k (x), k ∈ K, x ∗ i ∈ ∂g i (x)i ∈ I, y ∗ j ∈ ∂h j (x)∪
∂(−hj)(x)j ∈J, tồn tại v ∈ N(x; Ω) o sao cho f k (x)−f k (x) > hz k ∗ , vi, k ∈ K, gi(x)−gi(x) ≥ hx ∗ i , vi, i ∈ I, h j (x)−h j (x) =ω j hy ∗ j , vi, j ∈ J, trong đó ωj = 1 (tương ứng ωj = −1) khi y j ∗ ∈ ∂hj(x) (tương ứng y j ∗ ∈ ∂(−h j )(x)).
Nếu Ω là tập lồi và f k, g i là các hàm lồi trong khi hj là hàm affine, thì bộ ba hàm (f, g, h) sẽ là L-lồi bất biến trên Ω tại điểm x ∈ Ω với v := x−x cho mọi x ∈ Ω Theo Định lý 2.2, nếu x thuộc tập C và thỏa mãn điều kiện KKT, thì các tính chất trên sẽ được duy trì.
(i) Nếu (f, g, h) là L - lồi bất biến trên Ω tại x thì x ∈S w (P).
(ii) Nếu (f, g, h) là L - lồi bất biến chặt trên Ω tại x thì x∈ S(P). Chứng minh
Do x∈ C thỏa mãn điều kiện (KKT) nên tồn tại λ := (λ 1 , λ 2 , , λ m ) ∈
∂fk(x), k ∈ K, x ∗ i ∈ ∂gi(x), i ∈ I với àigi(x) = 0 và y j ∗ ∈ ∂hj(x) ∪
Trước hết ta chứng minh (i) Giả sử ngược lại x /∈ S w (P) Điều này có nghĩa là tồn tại xb∈ C sao cho f(x)b −f(x) ∈ −intR m + (2.25)
Theo định nghĩa của nón cực và do (f, g, h) là L - lồi bất biến, từ (2.24) ta suy ra với xbnhư vậy thì tồn tại v ∈ N(x; Ω) o sao cho
0 ≤ P k∈K λ k hz k ∗ , vi+P i∈I à i hx ∗ i , vi+ P j∈J γ j hy j ∗ , vi
≤ P k∈K λk[fk(x)b −fk(x)]+P i∈I ài[gi(x)b −gi(x)]+P j∈J
≤ X k∈K λ k f k (bx) +X i∈I à i g i (x) +b X j∈J σ j h j (x).b trong đó, σj = γj ω j ∈ R, j ∈ J Để ý rằng àigi(x) = 0, àigi(bx) ≤ 0i ∈ I và hj(x) = 0, hj(x) = 0, jb ∈ J Vì vậy, ta có
Do đó, tồn tại k 0 ∈ K sao cho f k 0 (x) ≤ f k 0 (x),b (2.26) bởi vì λ ∈ R m + \ {0} Kết hợp (2.26) với (2.25) dẫn đến một mâu thuẫn. Điều đó chứng tỏ (i) đúng.
Giờ ta sẽ chứng minh (ii) Giả sử ngược lại, x /∈ S(P) Điều đó có nghĩa là tồn tại bx∈ C sao cho f(bx)−f(x) ∈ −R m + \ {0} (2.27)
Theo định nghĩa của nón cực và do (f, g, h) là L - lồi bất biến chặt, và λ ∈R m + \ {0}, ta suy ra từ (2.24) rằng với xbnhư vậy, tồn tại v ∈ N(x; Ω) o sao cho
0 ≤ P k∈K λ k hz k ∗ , vi+P i∈I à i hx ∗ i , vi+ P j∈J γ j hy j ∗ , vi
< P k∈K λk[fk(bx)−fk(x)]+P i∈I ài[gi(bx)−gi(x)]+P j∈J
X k∈K λ k f k (x)+X i∈I à i g i (x)+X j∈J σ j h j (x) < X k∈K λ k f k (bx)+X i∈I à i g i (bx)+X j∈J σ j h j (bx), trong đó, σj = γ j ωj
∈ R, j ∈ J Ta cú àigi(x) = 0, àigi(x)b ≤ 0i ∈ I và hj(x) = 0, hj(x) = 0b j ∈J Vì vậy, ta có
≤ P k∈K λ k f k (x).b Điều này kéo theo tồn tại k0 ∈K sao cho f k 0 (x) < f k 0 (x).b
Cùng với (2.27) ta đẫn đến mâu thuẫn Do đó (ii) đúng Định lý được chứng minh.
Các định lý đối ngẫu
Đối ngẫu kiểu Wolfe
Cho z ∈ X, λ := (λ1, , λm) ∈ R m +, à := (à1, à2, , àp) ∈ R p +, γ : (γ1, γ2, , γq) ∈ R q + và e := (1, ,1) ∈ R m Trong bài toán (P), ta xem xét bài toán tối ưu đa mục tiêu đối ngẫu kiểu Wolfe của bài toán (P): max
{fe(z, λ, à, γ) := f(z)+hà, g(z)ie+hγ, h(z)ie|(z, λ, à, γ) ∈Cw} (Dw) Ở đây, tập ràng buộc Cw được xác định bởi
Cw :(z, λ, à, γ) ∈ ΩìR m + ìR p +ìR q + |0 ∈ X k∈K λk∂fk(z)
+X i∈I ài∂gi(z) +X j∈J γj(∂hj(z)∪∂(−hj)(z)) +N(z,Ω), hλ, ei = 1, h(z) ∈ (γ−S(0,kγk)) o
Một nghiệm hữu hiệu (nghiệm hữu hiệu yếu) của bài toán "max" như đối ngẫu (D w) được định nghĩa bằng cách thay thế −R m + (-intR m +) bởi R m + (intR m +), và tập nghiệm hữu hiệu được kí hiệu là S(D w) (S w(D w)) Để thuận tiện, ta sử dụng các kí hiệu: u ≺ v nếu u−v ∈ -intR m + và u ⊀ v là phủ định của u≺ v; u v nếu u−v ∈ −R m + \ {0} và u v là phủ định của u v Định lý 2.3 mô tả mối quan hệ tính đối ngẫu yếu giữa bài toán xuất phát (P) và bài toán (D w), trong đó nếu (f, g, h) là L-lồi bất biến trên Ω tại z thì f(x) ⊀ fe(z, λ, à, γ).
(ii) Nếu (f, g, h) là L - lồi bất biến chặt trên Ω tại z thì f(x) fe(z, λ, à, γ).
Do (z, λ, à, γ) ∈ Cw, tồn tại λ := (λ1, , λm) ∈R m +, à := (à1, à2, , àp)
∈ R p +, γ := (γ 1 , γ 2 , , γ q ) ∈ R q +, z k ∗ ∈ ∂f k (z), k ∈ K, x ∗ i ∈ ∂g i (z), i ∈ I và y j ∗ ∈ ∂hj(z)∪∂(−hj)(z), j ∈ j, sao cho
∈ N(z; Ω) (2.29) hλ, ei, hγ −σ, h(z)i ≤ 0, ∀σ ∈ R q , kσk = kγk (2.30) Đầu tiên ta chứng minh (i) Giả sử ngược lại, f(x) ≺ fe(z, λ, à, γ).
Vỡ thế,hλ, f(x)− fe(z, λ, à, γ)i < 0 Điều này tương đương với bất đẳng thức sau: hλ, f(x)−f(z)i − hà, g(z)i − hγ, h(z)i < 0 (2.31)
Theo định nghĩa của nón cực và tính chất L - lồi bất biến của (f, g, h) trên Ω tại z, từ (2.29) ta suy ra với mỗi x, tồn tại v ∈ N(z,Ω) o sao cho
0 ≤ P k∈K λkhz k ∗ , vi+P i∈I àihx ∗ i , vi+ P j∈J γjhy j ∗ , vi
≤ P k∈K λk[fk(x)−fk(z)]+P i∈I ài[gi(x)−gi(z)]+P j∈J
1 ωj γj[hj(x)−hj(z)]. Đặt σj := γj ω j ∈ R, j ∈J, ta có
0 ≤ hλ, f(x)−f(z)i+ hà, g(x)−g(z)i+ hσ, h(x)−h(z)i, (2.32) trong đú, σ := (σ1, , σq) ∈ R q Do x ∈ C nờn ta cú hà, g(x)i ≤ 0, hσ, h(x)i = 0 Vì vậy, (2.32) dẫn đến
Vì kσk =kγk, kết hợp (2.30), (2.31) và (2.33) ta dẫn đến mâu thuẫn Vì vậy (i) đã được chứng minh.
Giờ ta chứng minh (ii) Giả sử ngược lại, f(x) fe(z, λ, à, γ) (2.34)
Vỡ thế, hλ, f(x)−fe(z, λ, à, γ)i ≤ 0 tương đương với bất đẳng thức sau hλ, f(x)−f(z)i − hà, g(z)i − hγ, h(z)i ≤ 0 (2.35)
Từ (2.34) ta có x 6=z Thật vậy, nếu x =z thì f(x)−fe(z, λ, à, γ) =−hà, g(x)ie− hγ, h(x)ie.
Do x ∈ C,hà, g(x)i ≤ 0 và hγ, h(x)i = 0 Vỡ vậy, (2.34) kộo theo
Trong không gian R m + \ {0}, nếu hàm g(x)ie ∈ −R m + \ {0}, điều này không thể xảy ra, dẫn đến x khác z Theo định nghĩa của nón cực và tính chất L-lồi bất biến chặt của (f, g, h) trên miền Ω tại điểm z, từ (2.29) suy ra rằng với mỗi x, tồn tại v ∈ N(z, Ω) thỏa mãn điều kiện cần thiết.
0 ≤ P k∈K λkhz k ∗ , vi+P i∈I àihx ∗ i , vi+ P j∈J γjhy j ∗ , vi
0