Hàm lồi và các khái niệm liên quan
Mục này cung cấp một số khái niệm và tính chất của hàm lồi, hàm liên hợp, ánh xạ đơn điệu và ánh xạ đơn điệu cực đại ([9], [17]).
1.1.1 Định nghĩa Cho f : R n → R¯ là một hàm số nhận giá trị thực suy rộng.
(i) Hàmf được gọi là lồi nếu epif là tập lồi trong không gian R n ×R, nghĩa là, nếu (x 1 , α 1 ),(x 2 , α 2 ) ∈ epif và t ∈ (0,1) thì
(1−t)(x 1 , α 1 ) +t(x 2 , α 2 ) ∈ epif, ở đây epif := {(x, α) ∈ R n ×R | f(x) ≤ α} là tập trên đồ thị của f. (ii) Ta gọi f là chính thường nếu domf 6= ∅ và f(x) > −∞ với mọi x ∈ R n , ở đây domf := {x ∈ R n | f(x) < ∞} là miền hữu hiệu của f.
1.1.2 Chú ý Hàm f : R n → R¯ là lồi khi và chỉ khi với mọi x 1 , x 2 ∈ R n và t∈ (0,1), ta có f((1−t)x 1 +tx 2 ) ≤ (1−t)f(x 1 ) +tf(x 2 ).
1.1.3 Vớ dụ 1) Hàm chuẩn k ã k: R n −→ R là một hàm lồi; bởi vỡ, với mọi x 1 , x 2 ∈ R n và t ∈ (0,1), ta có k(1−t)x 1 +tx 2 k ≤ k(1−t)x 1 k+ktx 2 k
2) Hàm f :R → R xác định bởi f(x) :x nếu x ≤ 1,
1 nếu x > 1, không phải là một hàm lồi Thật vậy, lấy x 1 = 0, x 2 = 2 và t = 1 2 , ta có f((1−t)x 1 +tx 2 ) = 1 > 1
Do đó, f không phải là một hàm lồi.
1.1.4 Định nghĩa Cho f : R n → R là một hàm số nhận giá trị thực suy rộng.
Hàm f được gọi là nửa liên tục dưới tại điểm x0 ∈ R n nếu giới hạn dưới khi x tiến đến x0 lớn hơn hoặc bằng giá trị của hàm tại x0, tức là lim inf x→x 0 f(x) ≥ f(x0) Định nghĩa này có thể được diễn đạt bằng cách sử dụng sup của f(x) trong hình cầu Bδ(x0) với bán kính δ, ngoại trừ điểm x0 Nếu f(x0) thuộc R, điều kiện này tương đương với việc với mọi ε > 0, tồn tại δ > 0 sao cho f(x) lớn hơn f(x0) trừ đi ε cho mọi x thuộc Bδ(x0).
Hàm f: R n → R được xem là nửa liên tục dưới tại điểm x 0 ∈ R n nếu nó duy trì tính chất nửa liên tục dưới trong mọi lân cận của x 0 Hơn nữa, hàm f được gọi là nửa liên tục dưới nếu điều này đúng cho mọi điểm x 0 ∈ R n.
1.1.5 Ví dụ Hàm f : R →R cho bởi f(x) 3x 2 −2 nếu x 6= 2,
0 nếu x = 2, là nửa liên tục dưới tại x 0 := 2, dolim inf x→2 f(x) = 10 ≥f(2) Tuy nhiên, dễ thấy f không liên tục tại x 0
1.1.6 Nhận xét Cho f : R n →R¯ Khi đó, ta có
1) Nếu f là lồi thì domf là lồi;
2) Trong trường hợp f = δC, ở đây δC : R n → R¯ cho bởi δC(x) := 0 nếu x ∈ C và δ C (x) := +∞ nếu x ∈ R n \C là hàm chỉ của tập C ⊂R n , ta có:
(a) f là lồi nếu và chỉ nếu C là lồi;
(b) f là nửa liên tục dưới nếu và chỉ nếu C là đóng.
Hàm số f : R n → R được định nghĩa là một hàm nhận giá trị thực suy rộng Hàm liên hợp f ∗ : R n → R được xác định bởi công thức f ∗ (x ∗ ) := sup{hx ∗ , xi −f(x) |x ∈ R n } với mọi x ∗ ∈ R n Hàm f ∗∗ = (f ∗ ) ∗ được gọi là hàm liên hợp cấp hai của f, trong đó hx ∗ , xi là tích vô hướng giữa x ∗ và x.
Sau đây là một số tính chất của hàm liên hợp.
1.1.8 Định lý Cho f : R n → R là một hàm chính thường Khi đó, ta có các khẳng định sau:
(i) f ∗ (x ∗ ) +f(x) ≥ hx ∗ , xi với mọi x ∈ R n và x ∗ ∈ R n (bất đẳng thức Fenchel-Young);
Hàm f ∗∗ được định nghĩa là hàm lồi nửa liên tục dưới lớn nhất không vượt quá hàm f, với epif ∗∗ = cl conv(epif) Điều này cho thấy rằng hàm f là lồi nửa liên tục dưới nếu và chỉ nếu f = f ∗∗.
Hàm liên hợp của hàm chỉ δ C được định nghĩa là δ ∗ C (x ∗ ) = sup x∈C hx ∗ , xi = σ C (x ∗ ) với mọi x ∗ ∈ R n Trong đó, σC(x ∗ ) được gọi là hàm tựa của tập con C Nếu C là tập lồi đóng, thì có mối quan hệ σ ∗ C = δ C ∗∗ = δC.
Ánh xạ đa trị T: R n ⇒ R n được định nghĩa cho mỗi tập con C ⊂ R n, trong đó T(x) là tập hợp các điểm tương ứng với mỗi điểm x ∈ R n T được coi là đơn điệu trên C nếu với mọi x, x 0 ∈ C, và v ∈ T(x), v 0 ∈ T(x 0), điều kiện ≥ 0 được thỏa mãn.
Ánh xạ đơn điệu T : R n ⇒ R n được gọi là đơn điệu cực đại khi đồ thị của nó, ký hiệu gphT := {(x, v) ∈ R n × R n : v ∈ T(x)}, không phải là tập con thực sự của đồ thị của một ánh xạ đơn điệu khác Nói cách khác, ánh xạ đơn điệu T là đơn điệu cực đại nếu với mọi cặp (¯x,v)¯ ∈ (R n × R n ) \gphT, tồn tại (x, v) ∈ gphT sao cho h¯v −v,x¯−xi < 0.
Ánh xạ đa trị T: R n ⇒ R n được xem là đơn điệu địa phương quanh điểm (¯x,v)¯ ∈ gphT nếu tồn tại một lân cận W của (¯x,v)¯, trong đó giao điểm của gphT và W là đồ thị của một ánh xạ đơn điệu.
Ánh xạ đa trị T: R n ⇒ R n được xem là đơn điệu cực đại địa phương tại điểm (¯x,v)¯ ∈ gphT nếu tồn tại một lân cận W của (¯x,v)¯, trong đó mọi ánh xạ đa trị S: R n ⇒ R n thỏa mãn điều kiện gphT ∩ W ⊂ gphS ∩ W đều dẫn đến gphT ∩ W = gphS ∩ W.
1.1.11 Chú ý Cho T : R n ⇒ R m và (¯x,y)¯ ∈ gphT Ta gọi ánh xạ trị
S : R n ⇒ R m được coi là một địa phương hóa của T quanh điểm (¯x,y)¯ nếu tồn tại một lân cận W của (¯x,y)¯ sao cho gphS = gphT ∩ W Trong trường hợp W = U × V, ta có S(x) = T(x) ∩ V cho mọi x thuộc U, và S(x) = ∅ cho mọi x thuộc R n \ U Do đó, S : U ⇒ V cũng được xem là một địa phương hóa của T.
Nón pháp tuyến, đối đạo hàm và dưới vi phân
Mục này nhắc lại một số cấu trúc vi phân suy rộng đã được dùng rộng rãi trong giải tích biến phân (xem [8], [17]).
1.2.1 Định nghĩa Cho f: R n → R¯ là một hàm số nhận giá trị thực suy rộng và x¯∈ R n thỏa mãn f(¯x) ∈ R.
(i) Dưới vi phân chính quy (hoặc dưới vi phân Fréchet) của f tại x¯ là
∂fb (¯x) :n v ∈ R n lim inf x→¯ x f(x)−f(¯x)− hv, x−xi¯ k x−x¯ k ≥ 0 o (1.1)
(ii) Dưới vi phân qua giới hạn (hoặc dưới vi phân Mordukhovich) của f tại x¯ được định nghĩa là giới hạn trên Painlevé-Kuratowski của dưới vi phân chính quy:
∂fb (x), (1.2) nghĩa là, x ∗ ∈ ∂f(¯x) khi và chỉ khi tồn tạix k → x, x¯ ∗ k ∈ ∂fb (x k ) sao cho x ∗ k → x ∗ và f(x k ) → f(¯x) Nếu | f(¯x) |= +∞ thì đặt ∂f(¯x) := ∅.
1.2.2 Chú ý Nếu f là một hàm lồi hữu hạn tại x,¯ thì
Trong trường hợp hàm lồi, dưới vi phân Fréchet và dưới vi phân qua giới hạn đều trùng với dưới vi phân theo nghĩa của giải tích lồi Cụ thể, điều này được diễn đạt bằng công thức ∂f(¯x) = ∂fb (¯x) := v ∈ R n, với điều kiện f(x)−f(¯x)−hv, x−¯xi ≥ 0 cho mọi x ∈ R n.
Nón pháp tuyến chính quy và nón pháp tuyến qua giới hạn của một tập con không rỗng Ω trong không gian R n tại điểm x¯ được định nghĩa lần lượt là Nb(¯x; Ω) = ∂δb Ω (¯x) và N(¯x; Ω) = ∂δ Ω (¯x).
1.2.4 Định nghĩa Giả sử F : R n ⇒ R m là một ánh xạ đa trị và (¯x,y)¯ ∈ R n ×R m
(i) Đối đạo hàm chính quy (hoặc đối đạo hàm Fréchet) của F tại (¯x,y)¯ là ánh xạ đa trị Db ∗ F(¯x,y) :¯ R m ⇒ R n được xác định bởi
Db ∗ F(¯x,y)(ω) :=¯ z ∈ R n | (z,−ω) ∈ Nb (¯x,y); gphF¯ , (1.3) với mọi ω ∈ R m , ở đây gphF := {(x, y) ∈ R n ×R m | y ∈ F(x)} được gọi là đồ thị của F.
(ii) Đối đạo hàm qua giới hạn (hoặc đối đạo hàm Mordukhovich) của
F tại (¯x,y)¯ là ánh xạ đa trị D ∗ F(¯x,y) :¯ R m ⇒ R n được xác định bởi
1.2.5 Định nghĩa ([8]) Ta nói ánh xạ đa trị F : R n ⇒ R m là giả- Lipschitz (hoặc Lipschitz-like) quanh (¯x,y)¯ ∈ gphF với modulus ` > 0 nếu tồn tại các lận cận U của x¯ và V của y¯ sao cho
Trong toán học, tập hợp F(x)∩V được chứa trong F(u) + k xưu k B R m cho mọi x, u thuộc U Cận dưới đúng của các số như vậy được gọi là modulus tính giả-Lipschitz (Lipschitz-like) của F quanh điểm (¯x,y) và được ký hiệu là lipF(¯x,y) Nếu F(¯x) = {¯y}, thì ký hiệu lipF(¯x) sẽ thay thế cho lipF(¯x,y).
Nếu F là một ánh xạ đơn trị, khái niệm giả-Lipschitz tương đương với Lipschitz địa phương quanh x¯ với modulus ` > 0 Điều này có nghĩa là tồn tại một lân cận U của x¯ sao cho k f(x) - f(u) k ≤ ` k x - u k với mọi x, u ∈ U.
(i) Dưới vi phân bậc hai của f tại x¯ liên quan đến v¯ là ánh xạ đa trị
(ii) Dưới vi phân bậc hai kết hợp của f tại x¯ liên quan đến v¯ là ánh xạ đa trị ∂ˇ 2 f(¯x,v) :¯ R n ⇒ R n được xác định bởi
Hàm chính quy gần kề
Mục này được dành để trình bày khái niệm hàm chính quy gần kề và một số tính chất của hàm chính quy gần kề ([14], [17]).
1.3.1 Định nghĩa Cho f : R n → R, x¯ ∈ domf và v¯∈ ∂f(¯x) Hàm f được gọi là chính quy gần kề tại x¯ đối với v¯ nếu tồn tại r, ε >0 sao cho với mọi x, u ∈ B ε (¯x) thỏa mãn | f(u)−f(¯x) |≤ ε, ta có f(x) ≥ f(u)+hv, xưuiưr
Hàm f: R n → R được coi là liên tục dưới vi phân tại điểm x¯ ∈ domf nếu tồn tại v¯∈ ∂f(¯x) và hàm (x, v) → f(x) là liên tục đối với đồ thị của ánh xạ dưới vi phân của ∂f: R n ⇒ R n tại (¯x, v¯).
1.3.3 Nhận xét Mọi hàm liên tục đều liên tục dưới vi phân Điều ngược lại là không đúng.
Hàm f: R n → R¯ được xác định là một hàm lồi chính thường nửa liên tục dưới, với f(¯x) ∈ R Do đó, f được xem là một hàm chính quy gần kề và có tính liên tục dưới vi phân tại điểm x.¯
Mệnh đề 1.3.4 cùng với ví dụ sau đây cho thấy lớp hàm chính quy gần kề rộng hơn thực sự lớp hàm lồi chính thường nửa liên tục dưới.
1.3.5 Ví dụ Hàm f : R → R xác định bởi f(x) := x 3 là một hàm chính quy gần kề và liên tục dưới vi phân tại x¯ = 0, nhưng không phải là một hàm lồi.
Mọi hàm f: R n → R khả vi với đạo hàm ∇f là Lipschitz địa phương tại điểm x¯, tức là f thuộc lớp C 1,1 quanh x¯, đều là hàm chính quy gần kề và liên tục dưới vi phân tại x¯ Ở đây, ∇f đại diện cho ma trận cột các đạo hàm riêng của f.
Chương 2 Đặc trưng của tính ổn định xiên và ứng dụng
Chương này trình bày một số kết quả về đặc trưng của tính ổn định xiên và ứng dụng của nó vào quy hoạch phi tuyến.
Cực tiểu địa phương ổn định xiên
Mục này trình bày một số kết quả về đặc trưng của tính ổn định xiên của các điểm cực tiểu địa phương.
2.1.1 Định nghĩa ([15, Definition 1.1]) Cho f: R n → Rvà x¯ ∈ domf.
Ta nói x¯ là một điểm cực tiểu địa phương ổn định xiên của f nếu tồn tại γ > 0 và một lân cận V của 0 ∈ R n sao cho ánh xạ
M γ : v 7→argmin f(x)− hv, xi | x ∈ B γ (¯x) , v ∈ R n , (2.1) là đơn trị và liên tục Lipschitz trên V và M γ (0) = ¯x, ở đây argmin f(x)− hv, xi | x ∈ B γ (¯x)
Nếu thêm điều kiện M γ liên tục Lipschitz với hằng số κ ta nói x¯ là một điểm cực tiểu địa phương ổn định xiên với modulus κ.
Ánh xạ g: X → Y từ không gian mêtric X vào không gian mêtric Y được gọi là liên tục Lipschitz trên tập U ⊂ X nếu tồn tại một hằng số κ > 0 sao cho d(g(x1), g(x2)) ≤ κd(x1, x2) với mọi x1, x2 thuộc U Hằng số κ này được gọi là modulus Lipschitz của g trên U, và g được xem là liên tục Lipschitz trên U với modulus κ.
2.1.3 Ví dụ (xem [3, p 256]) Cho f : R 2 → R là hàm số được xác định bởi f(x) = (|x 1 |+ |x 2 |) 2 với mọi x = (x 1 , x 2 ) ∈ R 2 Khi đó, điểm ¯ x := (0,0) là một điểm cực tiểu địa phương không ổn định xiên của f.
2.1.4 Ví dụ Điểmx¯:= 0 là một điểm cực tiểu địa phương ổn định xiên của hàm f : R →R cho bởi f(x) := x 2
Một hàm số khả vi liên tục hai lần f: R^n → R có một điểm cực tiểu địa phương ổn định xiên tại ¯x ∈ R^n nếu và chỉ nếu ∇f(¯x) = 0 và ma trận Hessian ∇²f(¯x) là xác định dương Điều này có nghĩa là điều kiện đủ bậc hai cổ điển được thỏa mãn tại điểm ¯x, trong đó ∇²f(¯x) là ma trận vuông chứa các đạo hàm từng phần bậc hai của hàm số f.
Bổ đề 2.1.6 khẳng định rằng nếu h: R n → R là một hàm lồi nửa liên tục dưới và có hàm liên hợp h ∗ khả vi trong một lân cận O của ¯v thuộc domh ∗, đồng thời ∇h ∗ là liên tục Lipschitz trên O với hằng số κ > 0, thì tồn tại lân cận U của x¯ và lân cận V của ¯v với ¯x := ∇h ∗ (¯v) sao cho h(x) ≥ h(u) + hv,xưui + 1.
2κ k xưu k 2 , (2.2) với mọi (u, v) ∈ gph∂h ∩(U ×V) và x ∈ U.
Kết quả sau cung cấp một đặc trưng của điểm cực tiểu địa phương ổn định xiên qua điều kiện tăng trưởng bậc hai đều.
Định lý 2.1.7 cho biết rằng, với hàm f: R n → R nửa liên tục dưới tại điểm x¯ ∈ R n, nếu 0 thuộc ∂f(¯x) và f là chính quy gần kề cùng với liên tục dưới vi phân tại x¯ với v¯ = 0, thì các khẳng định liên quan đến điều kiện này là tương đương.
(i) Điểm x¯ là một cực tiểu địa phương ổn định xiên của hàm f với modulus κ >0;
Tồn tại các lân cận U của x¯ và V của v¯, sao cho ánh xạ đa trị (∂f) −1 : R n ⇒ R n có một địa phương hóa đơn trị ϑ: V → U quanh (¯x,v)¯ Điều này thỏa mãn điều kiện tăng trưởng bậc hai đều, cụ thể là f(x) ≥ f(u) + hv, xưui + 1.
2κ k xưu k 2 , (2.3) với mọi (v, u) ∈ gphϑ = gph(∂f) −1 ∩(V ×U) và x ∈ U.
Giả sử x¯ là một điểm cực tiểu địa phương ổn định của hàm f với modulus κ > 0 Theo định nghĩa, tồn tại γ > 0 sao cho Mγ(v) là ánh xạ đơn trị và liên tục Lipschitz trên lân cận lồi mở V của v¯ và M γ (¯v) = ¯x Nếu cần, chúng ta có thể thu nhỏ lân cận V để giả định M γ (v) thuộc U, tức là intB γ (¯x) với mọi v ∈ V Tiếp theo, chúng ta chứng minh rằng M γ là một ánh xạ đơn điệu Lấy bất kỳ v1, v2 ∈ Rn, với x1 ∈ M γ (v1) và x2 ∈ M γ (v2), ta có x1, x2 đều thuộc B γ (¯x).
f(x)− hv 1 , xi ≥ f(x1)− hv 1 , x1i f(x)− hv 2 , xi ≥ f(x 2 )− hv 2 , x 2 i, với mọi x ∈ B γ (¯x) Do đó,
Bằng cách cộng từng vế của hai bất đẳng thức trên và sau đó rút gọn, ta thu được hv 1 −v 2 , x 1 −x 2 i ≥ 0, với mọi v 1 , v 2 ∈ R n , x 1 ∈ M γ (v 1 ) và x 2 ∈ M γ (v 2 ) Điều này chứng tỏ
Ánh xạ M γ được xác định là một ánh xạ đơn điệu Chúng ta sẽ chứng minh rằng M γ là đơn điệu cực đại trong không gian V × U Giả sử S : R n ⇒ R n là một ánh xạ đa trị đơn điệu, với điều kiện rằng giao điểm của đồ thị M γ và (V × U) nằm trong đồ thị của S.
Ta cần chứng minh gphS ∩ (V ×U) ⊂ gphM γ ∩(V ×U) Lấy bất kỳ (v, u) ∈ gphS ∩ (V × U) và x ∈ R n Vì V là một tập mở và v ∈ V nên tồn tại t 0 > 0 sao cho v +tx ∈ V với mọi t ∈ (0, t 0 ) Từ đó suy ra
M γ (v + tx) thuộc U với mọi t trong khoảng (0, t0) Do đó, v + tx và M γ (v + tx) nằm trong gphM γ ∩ (V × U) cho mọi t trong khoảng (0, t0) Sự kết hợp này với (2.4) dẫn đến v + tx và M γ (v + tx) thuộc gphS cho mọi t trong (0, t0) Lưu ý rằng (v, u) thuộc gphS và S là một ánh xạ đơn điệu Chúng ta có v + tx - v và M γ (v + tx) - u lớn hơn hoặc bằng 0 cho mọi t trong khoảng (0, t0).
Do đó, x, Mγ(v +tx)−u ≥ 0 với mọi t ∈ (0, t0).
Nhờ tính liên tục của M γ , cho t ↓0, ta thu được x, Mγ(v)−u ≥0.
Với mọi x ∈ R n, từ bất đẳng thức đã cho, ta có thể suy ra rằng u = M γ (v) Điều này chứng minh rằng (v, u) thuộc giao của gphM γ và (V × U) Do đó, M γ là một hàm đơn điệu cực đại trong không gian V × U Đặt g là hàm liên hợp của f + δ U, với định nghĩa g(v) := (f + δ U) ∗ (v) = sup x∈U.
Ta có g là một hàm lồi chính thường nửa liên tục dưới và thỏa mãn
g(v) = hv, M γ (v)i −f Mγ(v) g(ω) ≥ hω, M γ (v)i −f Mγ(v) , với mọi v ∈ V và ω ∈ R n Do đó, g(ω)−g(v) ≥ hω, M γ (v)i −f M γ (v) − hv, M γ (v)i −f M γ (v)
Đối với mọi v ∈ V và ω ∈ R n, ta có hω − v, M γ (v)i, từ đó suy ra M γ (v) thuộc ∂g(v) Cần lưu ý rằng, vì g là một hàm lồi, nên ∂g là một ánh xạ đơn điệu Tính đơn điệu cực đại của M γ đối với V × U dẫn đến việc gphM γ ∩ (V × U) = gph∂g ∩ (V × U).
Bây giờ chúng ta chứng minh rằng ∂g(v) = Mγ(v) với mọi v ∈ V Lấy bất kỳ u ∈ ∂g(v) Vì U là một tập lồi mở, ∂g(v) là một tập lồi và
M γ (v) ∈ ∂g(v), nên tồn tại t 0 ∈ (0,1) sao cho
Từ u = M γ (v), ta suy ra rằng ∂g(v) = M γ (v) với mọi v ∈ V Điều này dẫn đến ∇g(v) = M γ (v) cho mọi v ∈ V, chứng tỏ rằng ∂g là một ánh xạ đơn trị và liên tục Lipschitz trên V Do đó, g là một ánh xạ khả vi và có đạo hàm liên tục Lipschitz với hằng số κ trên V.
Mγ(v) ∈ argmin{f(x)− hv, xi |x ∈ B γ (¯x)} và Mγ(v) ∈ intB γ(¯x) Theo quy tắc Fermat, ta có v ∈ ∂f Mγ(v) Do đó,
Đối với mọi v ∈ V, ta có ∇g(v) = M γ (v) ∈ (∂f) −1 (v) Giả thiết rằng f là chính quy gần kề và liên tục dưới vi phân tại x¯ đối với v,¯ cho phép ta thu nhỏ các lân cận U và V nếu cần Do đó, có thể giả sử rằng tồn tại r > 0 sao cho f(x) ≥ f(u) + hv, xưui ư r.
Xét ánh xạ đa trị T: R^n ⇒ R^n được xác định bởi gphT := gph∂f ∩(U × V), với mọi x ∈ U và (u, v) ∈ gph∂f ∩(U × V) Gọi I là ánh xạ đồng nhất trên R^n Nếu lấy bất kỳ (u_i, v_i) ∈ gphT, với i = 1, 2, ta có thể suy ra từ (2.5).
f(u 2 ) ≥ f(u 1 ) +hv 1 , u 2 −u 1 i − r 2 k u 2 −u 1 k 2 f(u 1 ) ≥ f(u 2 ) +hv 2 , u 1 −u 2 i − r 2 k u 1 −u 2 k 2 Cộng từng vế của hai bất đẳng thức trên và rút gọn, ta thu được
Lưu ý rằng v i + ru i ∈ (T + rI)(u i ), với i = 1,2, cho thấy T + rI là một ánh xạ đơn điệu Chúng ta sẽ chứng minh rằng M γ −1 và T trùng nhau quanh điểm (¯x,¯v) Đặt S : R n ⇒ R n là một mở rộng đơn điệu cực đại của M γ −1, đảm bảo rằng gphM γ −1 ⊂ gphS, theo [17, Proposition 12.6] Vì M γ −1 là đơn điệu cực đại đối với U × V, nên gphM γ −1 ∩(U × V) = gphS ∩(U × V) Do đó, ta có gph(M γ −1 + rI)∩(U × V + rU) = gph(S + rI)∩(U × V + rU).
Theo [17, Corollary 12.44], ánh xạ S + rI là đơn điệu cực đại, tồn tại lân cận W ⊂ U × V + rU của (¯x, ¯v + rx)¯ sao cho S + rI giữ tính đơn điệu cực đại trong W Do đó, ta có gph(S + rI) ∩ W = gph(M γ −1 + rI) ∩ W ⊂ gph(T + rI).
Mặt khác, T +rI là đơn điệu và S +rI là đơn điệu cực đại đối với W.
Ta có gph(S +rI)∩W = gph(M γ −1 +rI)∩W = gph(T +rI)∩ W.
Tính ổn định xiên trong quy hoạch phi tuyến
Xét bài toán quy hoạch phi tuyến sau: min ϕ 0 (x) | ϕ i (x) ≤ 0, i = 1,2, , m , (2.31) ở đây ϕ i : R n → R là khả vi liên tục hai lần (được viết là ϕ i ∈ C 2 ), i = 0,1, , m.
2.2.1 Định nghĩa (i)Hàmϕ 0 và tậpΩ := x|ϕ i (x) ≤ 0, i = 1,2, , m tương ứng được gọi là hàm mục tiêu và tập ràng buộc(tập các điểm chấp nhận được) của (2.31).
Điểm x¯ ∈ Ω được coi là một điểm cực tiểu địa phương ổn định xiên của (2.31) nếu nó là điểm cực tiểu địa phương ổn định xiên của hàm f := ϕ 0 + δ Ω, trong đó δ Ω là hàm chỉ của tập Ω.
2.2.2 Chú ý (i) Rõ ràng ta có
Ω ={x ∈ R n | ϕ(x) ∈ Θ}, (2.32) với Θ := R m − và ϕ(x) := ϕ1(x), ϕ2(x), , ϕm(x) Hơn nữa, (2.31) có thể viết một cách tương đương dưới dạng min f(x)|x ∈ R n , (2.33) ở đây f(x) := ϕ 0 (x) +δ Ω (x) với δ Ω (x) là hàm chỉ của Ω.
(ii) Nếu x¯ ∈ Ω là một cực tiểu địa phương của (2.31), thì nó thỏa mãn điều kiện cần tối ưu bậc nhất
2.2.3 Định nghĩa ([11]) Cho x¯ là một điểm chấp nhận được, tức là ¯ x ∈ Ω Khi đó, ta nói:
(i) Ω thỏa mãn chuẩn hóa ràng buộc độc lập tuyến tính (LICQ) tại x¯ nếu {∇ϕ i (¯x) | i ∈ I(¯x)} là độc lập tuyến tính, ở đây
I(¯x) := {i ∈ {1,2, , m} | ϕ i (¯x) = 0} là tập chỉ số hoạt tại x;¯
(ii) Ωthỏa mãnchuẩn hóa ràng buộc Mangasarian - Fromovitz(MFCQ) tại x¯ ∈ Ω nếu tồn tại d ∈ R n sao cho h∇ϕ i (¯x), di < 0 với mọi i ∈ I(¯x); (2.35)
(iii) Ω thỏa mãn chuẩn hóa ràng buộc hạng hằng (CRCQ) tại x¯ nếu tồn tại δ > 0 sao cho với mỗi J ⊂ I(¯x) hệ {∇ϕ i (x) | i ∈ J} có hạng không đổi khi x biến thiên trong B δ (¯x).
Các điều kiện LICQ, MFCQ và CRCQ đều có tính chất vững, nghĩa là nếu chúng đúng tại điểm x¯, thì chúng cũng phải thỏa mãn tại mọi điểm x thuộc tập Ω trong một lân cận O nào đó của x¯ Hơn nữa, trong trường hợp này, với mọi x thuộc Ω∩ O, ta có
MFCQ và CRCQ không thể so sánh với nhau, vì không có điều kiện nào dẫn đến điều kiện còn lại; tuy nhiên, cả hai đều yếu hơn LICQ.
(iii) MFCQ đúng tại x¯ ∈ Ω nếu và chỉ nếu {∇ϕ(¯x)} i∈I(¯ x) là độc lập tuyến tính dương, nghĩa là:
2.2.5 Định nghĩa ([11]) Hàm L : R n ×R m →R cho bởi
X i=1 λ i ϕ i (x), x ∈ R n , λ ∈ R m , được gọi là hàm Lagrange ứng với bài toán (2.31).
Trong phần sau, ta ký hiệu Ψ : R n ⇒ R n là ánh xạ đa trị cho bởi Ψ(x) := ∇ x L(x, λ) | λ ∈ N(ϕ(x); Θ) (2.37) và gọi Λ(¯x) := {λ ∈ R m + |0 = ∇ x L(¯x, λ), hλ, ϕ(¯x)i = 0} (2.38) là tập nhân tử Lagrange của (2.31) tại x.¯ Hơn nữa, đặt Λ(x, v) := λ ∈ R m + |v = ∇ x L(x, λ), hλ, ϕ(x)i = 0 (2.39) với mỗi v ∈ Ψ(x).
2.2.6 Chú ý (i) Với mỗi x ∈ Ω, ta có Λ(x) = Λ(x,0) Nếu LICQ đúng tại x¯ thì tồn tại lân cận O của x¯ sao cho Λ(x, v) là tập có một phần tử khi x ∈ O ∩Ω và v ∈ Ψ(x).
Điều kiện KKT, ký hiệu là Λ(¯x) 6= ∅, không phải là điều kiện cần thiết để tối ưu, trừ khi một chuẩn hóa ràng buộc được thỏa mãn Khi Λ(¯x) 6= ∅, điểm x¯ được xem là điểm dừng của phương trình (2.31) Để so sánh, chúng ta sẽ nhắc lại một số điều kiện đủ tối ưu bậc hai trong lý thuyết tối ưu.
2.2.7 Định nghĩa Cho x¯ ∈ Ω và Λ(¯x) là tập nhân tử Lagrange của (2.31) tại x.¯ Ta nói rằng:
(i)Điều kiện đủ bậc hai mạnh (SSOSC) cho bài toán (2.31) được thỏa mãn tại x¯ nếu, với mỗi λ ∈ Λ(¯x), ta có hω,∇ 2 xx L(¯x, λ)ωi > 0 (2.40) với bất kỳ ω 6= 0 thỏa mãn h∇ϕ i (¯x), wi = 0 với mọi i ∈ I + (¯x, λ), ở đây
(ii) Điều kiện đủ bậc hai (SOSC) cho bài toán (2.31) được thỏa mãn tại x¯ nếu, với mọi λ ∈ Λ(¯x), (2.40) đúng với bất kỳ ω 6= 0 thỏa mãn h∇ϕ i (¯x), ωi = 0 khi i ∈ I+(¯x, λ), h∇ϕ i (¯x), ωi ≥ 0 khi i ∈ I(¯x)\I+(¯x, λ).
Điều kiện đủ bậc hai mạnh dẫn đến điều kiện đủ bậc hai, nhưng chiều ngược lại không đúng trong nhiều trường hợp Hơn nữa, điều kiện (2.40) có thể được thay thế tương đương bởi điều kiện hω,∇ 2 xx L(¯x, λ)ωi ≥ ` kω k 2 với một ` > 0 nào đó.
Các điều kiện đủ bậc hai chỉ có giá trị khi tập nhân tử Lagrange Λ(¯x) không rỗng, tức là chúng chỉ có ý nghĩa khi các điều kiện KKT được thỏa mãn.
Điều kiện đủ bậc hai mạnh, được Robinson giới thiệu năm 1980, nhằm nghiên cứu tính chính quy mêtric mạnh của hệ KKT kết hợp với quy hoạch phi tuyến Hệ KKT này được xác định là chính quy mêtric mạnh nếu và chỉ nếu LICQ và SSOSC đều đúng Gần đây, Mordukhovich và Rockafellar đã chứng minh rằng nếu LICQ đúng, thì SSOSC sẽ được thỏa mãn tại điểm x¯ ∈ Ω khi và chỉ khi x¯ là một điểm cực tiểu địa phương ổn định xiên Tuy nhiên, LICQ không phải là điều kiện cần cho cực tiểu địa phương ổn định xiên, vì vẫn tồn tại những điểm như vậy mà LICQ không đúng Kết quả chính của nghiên cứu này cung cấp một đặc trưng cho điểm cực tiểu địa phương ổn định xiên, dưới điều kiện ràng buộc yếu hơn LICQ.
Điều kiện đủ bậc hai đều (USOSC) của (2.31) được xác định tại x¯ ∈ Ω với modulus ` > 0 nếu tồn tại η > 0 sao cho hω,∇ 2 xx L(x, λ)ωi ≥ ` k ω k 2 Điều này đúng với bất kỳ (x, v) ∈ gphΨ∩B η (¯x,0), λ ∈ Λ(x, v) và ω thỏa mãn h∇ϕ i (x), ωi = 0 khi i ∈ I + (x, λ), đồng thời h∇ϕ i (x), ωi ≥ 0 khi i ∈ I(x)\I + (x, λ).
Kết quả chính của mục này được phát biểu như sau:
Định lý 2.2.10 nêu rõ rằng nếu x¯ là một điểm chấp nhận được của (2.31) và thỏa mãn (2.34), đồng thời cả hai điều kiện MFCQ và CRCQ đều đúng tại x¯, thì các khẳng định liên quan đến nó là tương đương.
(i) Điểm x¯ là một cực tiểu địa phương ổn định xiên của (2.31) với modulus κ >0;
(ii) Điều kiện đủ bậc hai đều (USOSC) trong Định nghĩa 2.2.9 đúng tại x¯ với modulus ` = κ −1
Chứng minh rằng tồn tại η > 0 sao cho cả MFCQ và CRCQ đều đúng tại mỗi x ∈ B η (¯x)∩ Ω Cố định z ∈ ∂ˇ 2 f(x, v)(ω) với (x, v) ∈ gph∂f ∩B η (¯x,0) và λ ∈ Λ(x, x ∗ ) Áp dụng quy tắc tính dưới vi phân bậc hai của hàm tổng ([8, Theorem 1.62]), ta có thể thu được kết quả cần thiết.
Do đó, từ công thức tính đối đạo hàm Fréchet của ánh xạ nón pháp tuyến Db ∗ N(ã; Ω) x, v− ∇ϕ 0 (x) (ω) ([6, Corollary 3.1]), ta suy ra z ∈ ∂ˇ 2 f(x, v)(ω) khi và chỉ khi tồn tại λ ∈ Λ(x, v) sao cho
Giả sử(ii)đúng Để kiểm chứng (i)đúng, theo Định lý 2.1.9, ta sẽ chứng minh hz, ωi ≥ 1 κ k ω k 2 Thật vậy, nhờ (2.43) và USOSC, ta có h∇ 2 xx L(¯x, λ)ω, ωi ≥ 1 κ kω k 2 (2.44)
Hơn nữa, theo (2.42) và định nghĩa về nón đối ngẫu, ta có hz − ∇ 2 xx L(¯x, λ)ω, ωi ≥ 0.
Kết hợp (2.44), ta có hz, ωi ≥ κ 1 k ω k 2 Theo Định lý 2.1.9, (i) đúng. Ngược lại, giả sử (i) đúng Lấy λ ∈ Λ(x, v) và ω thỏa mãn
h∇ϕ i (x), ωi = 0 khi i ∈ I + (x, λ), h∇ϕ i (x), ωi ≥ 0 khi i ∈ I(x)\I + (x, λ). Đặt z := ∇ 2 xx L(x, λ)ω +v− ∇ϕ 0 (x) Rõ ràng, ta có v− ∇ϕ 0 (x) ∈ K(x, v− ∇ϕ 0 (x)) ∗
Vì vậy, kết hợp với (2.42) và (2.43), ta suy ra z ∈ ∂ˇ 2 f(x, v)(ω) và hv − ∇ϕ 0 (x), ωi = 0 Do đó, nhờ (2.10), ta có h∇ 2 xx L(x, λ)ω, ωi = hz, ωi − hv − ∇ϕ 0 (x), ωi = hz, ωi ≥ 1 κ k ω k 2 Điều này chứng tỏ USOSC đúng tại x¯ với modulus ` = κ −1 2
Mordukhovich và Outrata [12] đã chứng minh rằng khi cả điều kiện MFCQ và CRCQ được thỏa mãn, thì SSOSC là điều kiện đủ để xác định một điểm dừng là cực tiểu địa phương ổn định xiên Tuy nhiên, khác với trường hợp LICQ, SSOSC không phải là điều kiện cần thiết trong trường hợp này.
2.2.12 Ví dụ ([11, Example 4.5]) Xét bài toán quy hoạch phi tuyến sau: min ϕ 0 (x) | ϕ i (x) ≤ 0, i = 1,2,3,4 , (2.45) trong đó ϕi : R 3 →R, i= 0,1,2,3,4 là các hàm số cho bởi ϕ 0 (x) := x 3 + 1 4 x 1 +x 2 3 −x 1 x 2 , ϕ 1 (x) := x 1 −x 3 ≤ 0, ϕ 2 (x) := −x 1 −x 3 ≤ 0, ϕ 3 (x) := x 2 −x 3 ≤ 0, ϕ 4 (x) := −x 2 −x 3 ≤ 0, ở đây x = (x 1 , x 2 , x 3 ) ∈ R 3 Xét tại x¯:= (0,0,0) Ta có tập chỉ số hoạt
Tập hợp I(¯x) = {1,2,3,4} cho thấy rằng các hàm ràng buộc ϕ i, với i = 1,2,3,4, là tuyến tính, do đó điều kiện CRCQ được thỏa mãn tại điểm x Để kiểm tra điều kiện MFCQ tại x, cần xác minh tính độc lập tuyến tính dương của hệ {∇ϕ i (¯x)} với i thuộc I(¯ x).
Do đó, nếu λi ≥0, i = 1,2,3,4, thỏa mãn λ 1 ∇ϕ 1 (¯x) +λ 2 ∇ϕ 2 (¯x) + λ 3 ∇ϕ 3 (¯x) +λ 4 ∇ϕ 4 (¯x) = 0 R 3 thì λ 1 = λ 2 = λ 3 = λ 4 = 0 Điều này chứng tỏ MFCQ đúng tại x.¯ Lấy bất kỳ v = (v 1 , v 2 , v 3 ) thỏa mãn | v 1 |< 12 1 , | v 2 |< 1 3 và v 3 < 1 3 Ta có
= x = (x 1 , x 2 , x 3 ) ∈ R 3 : 0 ≤ max{| x 1 |,| x 2 |} ≤ x 3 Đặt f(x) := ϕ 0 (x) +δ Ω (x) Khi đó, với mỗi x ∈ Ω, f(x)− hv, xi = x 3 + 1 4 x 1 + x 2 3 −x 1 x 2 −v 1 x 1 −v 2 x 2 −v 3 x 3
Đối với bất kỳ v ∈ R³ đủ gần 0, ta có Mγ(v) = {¯x}, điều này cho thấy x¯ là một cực tiểu địa phương ổn định của (2.45) Tiếp theo, chúng ta sẽ chứng minh rằng điều kiện SSOSC không được thỏa mãn tại x¯.
Do đó, (3 8, 5 8, 0, 0) thuộc Λ(¯x) và I + (¯x, λ) = {1, 2} Đặt ω := (0, 1, 0) khác 0 Qua kiểm tra trực tiếp, ta thấy h∇ϕ i (¯x), ωi = 0 cho mọi i thuộc I + (¯x, λ), và hω,∇ 2 xx L(¯x, λ)ωi = 0 Điều này chứng tỏ điều kiện SSOSC đúng tại x¯ Vì vậy, dưới giả thiết cả MFCQ và CRCQ đều thỏa mãn, SSOSC không còn là điều kiện cần cho điểm cực tiểu địa phương ổn định xiên.
Dựa trên việc tổng hợp các tài liệu tham khảo, luận văn đã trình bày lại một cách có hệ thống các vấn đề sau:
1 Khái niệm điểm cực tiểu địa phương ổn định xiên và các ví dụ về điểm cực tiểu địa phương ổn định xiên, không ổn định xiên.
Điểm cực tiểu địa phương ổn định xiên có ba đặc trưng chính: đầu tiên, nó được xác định qua điều kiện tăng trưởng bậc hai đều (Định lý 2.1.7); thứ hai, tính xác định dương của dưới vi phân bậc hai kết hợp cũng góp phần xác định điểm cực tiểu này (Định lý 2.1.9); cuối cùng, đặc trưng của từng điểm cực tiểu địa phương ổn định xiên còn được thể hiện qua tính xác định dương của dưới vi phân bậc hai qua giới hạn (Định lý 2.1.10).