Bài toán tối ưu và các khái niệm liên quan
Trong luận văn này, X, U, V được định nghĩa là các không gian Banach thực K là một tập con lồi đóng của V, trong khi L ⊂ U là một nón lồi đóng có phần trong khác rỗng.
1.1.1 Định nghĩa ([9], [11]) Với mỗi u 1 , u 2 ∈ U, ta xác định các quan hệ thứ tự trên U như sau:
(ii) u 1 < L u 2 nếu và chỉ nếu u 2 −u 1 ∈ intL.
Nếu u 1 ≤ L u 2 (hoặc u 1 < L u 2 ) thì ta có thể nói u 1 nhỏ hơn u 2 (tương ứng, u 1 nhỏ hơn hẳn u 2 ) và viết u 2 ≥ L u 1 (tương ứng, u 2 > L u 1 ).
Trong trường hợp U = R và L = R+, quan hệ thứ tự ≤ L tương ứng với quan hệ thứ tự thông thường trên R, tạo ra một quan hệ thứ tự toàn phần, cho phép so sánh mọi cặp phần tử Ngược lại, trong trường hợp tổng quát, quan hệ thứ tự ≤ L chỉ là một quan hệ thứ tự bộ phận, nghĩa là không phải mọi cặp phần tử đều có thể so sánh được với nhau.
Xét bài toán tối ưu vector (P) sau:
L−min{f(x)|g(x) ∈ K}, (1.1) ở đây f : X → U và Ω := {x ∈ X |g(x) ∈ K}= g −1 (K) với g :X →V lần lượt được gọi là hàm mục tiêu và miền ràng buộc của bài toán (1.1).
Điểm x¯ được gọi là một điểm chấp nhận được của (1.1) nếu nó thuộc tập Ω Nếu tồn tại một lân cận N quanh x¯ sao cho f(x) − f(¯x) không thuộc vào -intL với mọi x trong N ∩ Ω, thì x¯ được xem là một cực tiểu địa phương yếu của (P).
Khi đó f(¯x) được gọi là giá trị cực tiểu (địa phương).
(ii) Điểmx¯được gọi là một cực tiểu địa phương chặt của(P) nếu tồn tại một lân cận N của x¯ sao cho f(x)−f(¯x) 6∈ −L với mọi x ∈ (N ∩ Ω)\{¯x}.
Bài toán (1.1) là một bài toán cực tiểu hóa, trong đó mục tiêu là tìm phương án có giá trị hàm mục tiêu nhỏ nhất trong số các phương án chấp nhận được Điểm cực tiểu địa phương yếu là phương án mà không có phương án nào gần đó tốt hơn nó một cách thực sự, trong khi điểm cực tiểu địa phương chặt là phương án không có phương án nào khác gần và khác với nó tốt hơn Cần lưu ý rằng điểm cực tiểu địa phương không nhất thiết là phương án tốt nhất trong số các phương án gần đó, vì có thể tồn tại những phương án chấp nhận được khác có giá trị không so sánh được với giá trị cực tiểu Chúng tôi sẽ cung cấp các ví dụ để minh họa sự khác nhau giữa điểm cực tiểu địa phương yếu và điểm cực tiểu địa phương chặt.
1.1.5 Ví dụ Xét bài toán (P) với X là không gian Banach tùy ý,
U := R, L := R + , V = R, K := {0} ⊂ V và g : X → V là ánh xạ được cho bởi g(x) = 0 với x ∈ X.
1) Hàm mục tiêu f : X → U được cho bởi f(x) = ||x|| 3 với x ∈ X. Khi đó, x¯ = 0 là điểm cực tiểu chặt duy nhất của (P)
2) Hàm mục tiêu f : X → U được cho bởi f(x) = 0 với x ∈ X Khi đó, mọi x¯ ∈ X đều là điểm cực tiểu yếu nhưng không phải là điểm cực tiểu địa phương chặt của (P).
1.1.6 Ví dụ Xét bài toán(P) vớiX := R 2 , U := R 2 , L := R 2 + , V = R 3 ,
Trong không gian R³, hàm g: X → V được định nghĩa bởi g(x) = (−x₁, −x₂, x₁ + x₂ − 1) với x ∈ X Hàm mục tiêu f(x) = x cho bài toán tối ưu (P) có một điểm cực tiểu địa phương duy nhất tại x̄ = (0,0), trong khi tập hợp các điểm cực tiểu địa phương yếu của (P) là ({0} × [0,1]) ∪ ([0,1] × {0}) Hơn nữa, ánh xạ đa trị Γ: X ⇒ Y được xác định bởi Γ(x) = h(x) − C, với h(x) = f(x) − f(x̄), g(x), C = (−L) × K và Y = U × V, trong đó các biến X, Y, U, V, L, K, f, g được nêu trong phát biểu bài toán (P).
Sử dụng hàm khoảng cách, chúng ta có thể thu được một số phát biểu tương đương của điểm cực tiểu chặt.
1.1.7 Mệnh đề ([6, p 974]) Cho x¯ là một điểm chấp nhận được của (P) Khi đó, các khẳng định sau là tương đương:
(i) ¯x là cực tiểu địa phương chặt của (P);
(ii) Tồn tại lân cận N của x¯ sao cho d 0,Γ(x) > 0 với mọi x ∈ N\{¯x}, ở đây d 0,Γ(x) := max{d f(x)−f(¯x),−L , d g(x), K };
(iii) Tồn tại lân cận N của x¯ sao cho d f(x)−f(¯x),−L > 0 với mọi x ∈ g −1 (K)∩N\{¯x}.
Giả sử x¯ là một điểm cực tiểu địa phương chặt của hàm số (P) Theo định nghĩa, tồn tại lân cận N của x¯ sao cho f(x)−f(¯x) không thuộc vào tập hợp −L với mọi x thuộc N ∩ Ω mà không phải là ¯x Đặt d 0,Γ(x) = max{d f(x) − f(¯x),−L , d g(x), K } Nếu x thuộc N nhưng không thuộc ¯x và x không thuộc Ω, thì g(x) không thuộc K, dẫn đến d g(x), K > 0 Do đó, suy ra d 0,Γ(x) > 0 Nếu x thuộc Ω, thì x thuộc g −1 (K) ∩ N\{¯x}, và từ đó, kết hợp với tính đóng của L, ta có d f(x)−f(¯x),−L.
Vì thế, d g(x), K > 0 Như vậy, d 0,Γ(x) > 0 với mọi x ∈ N\{¯x}. (ii) ⇒ (iii) : Với mọi x ∈ g −1 (K)∩N\{¯x}, ta có d f(x)−f(¯x),−L = d 0,Γ(x)
Do đó, (iii) đúng nếu (ii) đúng.
(iii) ⇒ (i) : Giả sử (iii) đúng Khi đó, tồn tại lân cận N của x¯ sao cho d f(x)−f(¯x),−L > 0 với mọi x ∈ g −1 (K)∩N\{¯x}.
Từ đó suy ra f(x)−f(¯x) 6∈ −L với mọi x ∈ (N ∩ Ω)\{¯x}. Điều này có nghĩa x¯ là cực tiểu địa phương chặt của (P) 2
In the context of optimization, let \( \bar{x} \) be an acceptable point of the problem (P) We define \( \bar{x} \) as an essential local minimizer of second-order for (P) if there exists a neighborhood around \( \bar{x} \) that satisfies specific conditions.
N của x¯ và số thực β > 0 sao cho d 0,Γ(x) ≥ βkx−xk¯ 2 với mọi x ∈ N, (1.5) ở đây d 0,Γ(x) := max{d f(x)−f(¯x),−L , d g(x), K }.
Từ Mệnh đề 1.1.7 và định nghĩa đã nêu, có thể kết luận rằng nếu x¯ là một điểm cực tiểu địa phương thiết yếu bậc hai, thì x¯ cũng là một điểm cực tiểu địa phương chặt Tuy nhiên, điều này không đúng với trường hợp ngược lại.
1.1.10 Ví dụ Xét bài toán (P) với X là không gian Banach khác {0},
U := R, L := R + , V = R, K := {0} ⊂ V và g : X → V là ánh xạ được cho bởi g(x) = 0 với x ∈ X.
1) Nếu hàm mục tiêu f : X → U là f(x) = ||x|| 3 với x ∈ X, thì ¯ x = 0 là một điểm cực tiểu chặt, nhưng không phải là một điểm cực tiểu địa phương thiết yếu bậc hai.
2) Nếu hàm mục tiêu f : X → U là f(x) = ||x|| với x ∈ X, thì x¯= 0 là một điểm cực tiểu địa phương thiết yếu bậc hai.
1.1.11 Định nghĩa ([11]) Cho X, Y là các không gian Banach và h : X → Y và x¯ ∈ X.
(i) Ta nói h là một ánh xạ khả vi (Fréchet) tại x¯nếu tồn tại một ánh xạ tuyến tính liên tục ∇h(¯x) : X → Y sao cho x→¯limx kh(x)−h(¯x)− ∇h(¯x)(x−x)k¯ kx−xk¯ = 0.
Khi đó, ∇h(¯x) được gọi là đạo hàm của h tại x.¯ Như thường lệ, chúng ta cũng sử dụng ký hiệu h 0 (¯x) thay cho ∇h(¯x).
(ii) Ta nói h là một ánh xạ khả vi chặt (Fréchet) tại x¯ nếu tồn tại một ánh xạ tuyến tính liên tục ∇h(¯x) : X → Y sao cho x,u→¯limx kh(x)ưh(u)ư ∇h(¯x)(xưu)k kxưuk = 0.
Khi đó, ∇h(¯x) được gọi là đạo hàm chặt của h tại x.¯ Chúng ta cũng sử dụng ký hiệu h 0 (¯x) thay cho ∇h(¯x).
(iii) Ta nói h là Lipschitz quanh (liên tục Lipschitz quanh) x¯nếu tồn tại lân cận N của x¯ và số thực λ ≥0 sao cho kh(x 1 )−h(x2)k ≤ λkx 1 −x2k với mọi x1, x2 ∈ N.
Số λ như thế được gọi là modulus Lipschitz (hoặc hệ số Lipschitz) của h quanh x.¯
Nếu hàm \( h \) khả vi chặt tại điểm \( \bar{x} \), thì hàm \( h \) cũng khả vi tại \( \bar{x} \) và đạo hàm chặt của \( h \) tại \( \bar{x} \) sẽ trùng với đạo hàm của \( h \) tại \( \bar{x} \) Vì vậy, việc sử dụng chung ký hiệu \( \nabla h(\bar{x}) \) và \( h'(\bar{x}) \) cho cả đạo hàm và đạo hàm chặt của \( h \) tại \( \bar{x} \) trong định nghĩa trên là hợp lý và không gây ra mâu thuẫn.
F là một ánh xạ đa trị từ X sang Y, và y¯∈ F(¯x) được gọi là chính quy mêtric quanh điểm (¯x,y)¯ nếu tồn tại κ > 0 và các lân cận N x của x¯ và N y của y¯ sao cho d x, F −1 (y) ≤ κd y, F(x) với mọi (x, y) ∈ N x × N y Cận dưới nhỏ nhất của những số κ như vậy được gọi là modulus tính chính quy mêtric của F quanh (¯x,y)¯ và được ký hiệu là RegF(¯x,y)¯.
Tiếp theo, chúng ta sẽ trình bày một số mô tả tương đương của tính chính quy mêtric cho một lớp ánh xạ đa trị.
Trong không gian Banach X và Y, cho C là tập con lồi đóng khác rỗng của Y, và Γ : X ⇒ Y là ánh xạ đa trị xác định bởi Γ(x) := h(x) − C, với h : X → Y là ánh xạ khả vi chặt tại điểm x¯ ∈ h −1 (C) Các khẳng định sau đây là tương đương với nhau.
(i) Ánh xạ Γ là chính quy mêtric quanh điểm (¯x,0);
(ii) Ánh xạ Ψ : X →Y cho bởi Ψ(x) :=h(¯x) +h 0 (¯x)(x−x)¯ −C là chính quy mêtric quanh điểm (¯x,0);
(iv) Tồn tại κ˜ ≥0 sao cho 0 ∈ int h(¯x) + ˜κh 0 (¯x)B X −C ;
(v) Với mọi κ >0, ta có 0 ∈ int h(¯x+κh 0 (¯x)B X −C
Kết quả tiếp theo cung cấp một số tính chất của điểm cực tiểu địa phương thiết yếu bậc hai.
1.1.15 Mệnh đề ([6]) Cho x¯ là một điểm chấp nhận được của (P). Khi đó, ta có các khẳng định sau:
(i) Nếu x¯ là một điểm cực tiểu địa phương thiết yếu bậc hai, thì tồn tại lân cận N của x¯ và số thực β > 0 sao cho d f(x)−f(¯x),−L ≥ βkx−xk¯ 2 với mọi x ∈ g −1 (K)∩N; (1.6)
Nếu ánh xạ G(x) được định nghĩa là g(x)−K và là chính quy mêtric quanh điểm (¯x,0), đồng thời hàm f là Lipschitz quanh x¯, thì điều này đảm bảo rằng x¯ là một điểm cực tiểu địa phương thiết yếu bậc hai.
Giả sử x¯ là một điểm cực tiểu địa phương thiết yếu bậc hai, tồn tại lân cận N của x¯ và số thực β > 0 sao cho max{d f(x)−f(¯x),−L , d g(x), K } ≥ βkx−xk¯ 2 với mọi x ∈ N Đồng thời, với mọi x ∈ g −1 (K), ta có d g(x), K = 0, dẫn đến max{d f(x)−f(¯x),−L , d g(x), K } = d f(x)−f(¯x),−L.
Vì vậy, từ (1.7) ta suy ra (1.6) đúng.
Giả sử G(x) = g(x) − K là một hàm chính quy mêtric quanh điểm (¯x,0), với f là hàm Lipschitz quanh x¯ và tồn tại lân cận N của x¯ cùng số thực β > 0 thỏa mãn điều kiện (1.6) Khi đó, có tồn tại lân cận Nˆ của x¯ và các số thực κ, λ > 0 sao cho với mỗi x ∈ Nˆ, tồn tại xˆ ∈ g −1 (K) thỏa mãn kˆx−xk ≤ κd(0, g(x)−K) và kf(x 1 )−f(x 1 )k ≤ λkx 1 −x 2 k với mọi x 1 , x 2 ∈ Nˆ Đặt β, r > 0 sao cho β(1+κλ) ≤ β/4, r ≤ 1/(2κβ) và x¯ + 3/2 rB X ⊂ Nˆ ∩ N Chọn bất kỳ x ∈ x¯ + rB X, nếu d(g(x), K) ≥ βkxˆ − xk¯ 2 thì d(0, Γ(x)) ≥ βkxˆ − xk¯ 2 Ngược lại, nếu d(g(x), K) ≤ βkxˆ − xk¯ 2 thì kˆx−xk ≤ κd(g(x), K) ≤ κβkx−xk¯ 2 ≤ 1.
2kx−xk.¯ Điều này dẫn đếnxˆ ∈ N∩Nˆ vàkˆx−xk ≥ kx¯ −xk−kˆ¯ x−xk ≥ 1 2 kx−xk.¯
Do đó, d 0,Γ(x) ≥ βkxˆ −xk¯ 2 với mọi x ∈ x¯+rB X Điều này chứng tỏ x¯ là một điểm cực tiểu địa phương thiết yếu cấp hai của (P) 2
Điểm cực tiểu địa phương chặt cấp hai là điểm x¯∈ Ω thỏa mãn điều kiện (1.6) Trong bài toán tối ưu vô hướng (P), với U := R và L := R +, điều kiện (1.6) tương ứng với điều kiện tăng trưởng bậc hai, hay còn gọi là điều kiện tăng trưởng toàn phương Cụ thể, điều kiện này yêu cầu f(x) ≥ f(¯x) + βk∥x−x¯∥² cho mọi x thuộc g −1 (K)∩N.
Hàm khoảng cách có dấu
Mục này trình bày một số tính chất của hàm khoảng cách có dấu (signed distance function) dˆ D , cần dùng ở chương sau.
1.2.1 Bổ đề ([6, Lemma 2.5]) ChoD là một tập con lồi đóng của không gian định chuẩn Z và dˆ D : Z →R∪ {±∞} được cho bởi dˆ D (z) := sup z ∗ ∈S Z ∗
{hz ∗ , zi −σ D (z ∗ )}, ở đây dˆ D được gọi là hàm khoảng cách có dấu và σD(z ∗ ) := sup{hz ∗ , zi |z ∈ D} với mọiz ∗ ∈ Z ∗ Khi đó, với mọi z ∈ Z, ta có dˆ D (z) d(z, D) nếu z 6∈ D,
Chứng minh Nếu D = ∅ hoặc D = Z, thì σ ∅ (.) ≡ −∞, d(.,∅) ≡ +∞, σ Z (.) ≡ +∞, sup{ρ: z+ρB z ⊂ Z}= ∞ Do đó, trong trường hợp này, ta có dˆ D (z) d(z, D) nếu z 6∈ D,
Tiếp theo, giả sử D 6= ∅ và D 6= Z Nếu z 6∈ D thì, theo định lý đối ngẫu chuẩn cực tiểu ([10, Theorem 1, p 136]), ta có
Vì ánh xạ z ∗ 7→ hz ∗ , zi −σD(z ∗ ) là thuần nhất dương và d(z, D) > 0, nên cực đại phải đạt tại một điểm z ∗ nào đó thuộc SZ ∗ Do đó, dˆ D (z) = d(z, D) với mọi z 6∈ D.
Bây giờ, giả sử z ∈ D và đặt ρ¯:= sup{ρ : z+ρB z ⊂ D} Vì D là đóng nên z+ρB z ⊂D Khi đó, với mỗi z ∗ ∈ S Z ∗ , ta có σD(z ∗ ) ≥ σz+ ¯ ρ B Z(z ∗ ) = hz ∗ , zi + ¯ρ. Điều này dẫn đến dˆ D (z) = sup z ∗ ∈S Z ∗
Mặt khác, với mỗi ρ > ρ,¯ tồn tại z ρ ∈ (z +ρB Z )\D Do đó,
{hz ∗ , zi −σ D (z ∗ )}+ sup z ∗ ∈S Z ∗ hz ∗ , z ρ −zi
Vì vậy, dˆ D (z) > −ρ với mỗi ρ > ρ¯ Cho ρ ↓ ρ¯ta thu được dˆ D (z) ≥ −ρ.¯ (1.9)
Kết hợp (1.8) và (1.9), ta có dˆ D (z) =−ρ.¯ 2
Nếu z thuộc miền D, thì bán kính của hình cầu lớn nhất tâm z nằm trong D là −dˆ D (z), điều này thể hiện "tính mở" của D xung quanh z Ngược lại, nếu z không thuộc D, khoảng cách d(z, D) = ˆd D (z) được coi là thước đo "tính mở" của phần bù của D trong Z quanh z.
Trong phần sau, ký hiệu dˆC : Y ×L(X, Y)×R → R là hàm cho bởi dˆ C (y, A, κ) := sup y ∗ ∈S Y ∗ hy ∗ , yi −σ C (y ∗ )−κkA ∗ y ∗ k , với mọi (y, A, κ) ∈ Y ×L(X, Y)×R, ở đây L(X, Y) là không gian các ánh xạ tuyến tính liên tục từ X vào Y.
Tiếp theo là một kết quả quan trọng trong lý thuyết đối ngẫu, được sử dụng ở phần sau:
1.2.3 Định lý ([6, Proposition 2.6]).Với mỗi A ∈ L(X, Y), y ∈ Y và κ ≥ 0, đặt DC(y, A, κ) := y +κAB X −C Khi đó, ta có dˆ C (y, A, κ)
Chứng minh.LấyA ∈ L(X, Y), y ∈ Y vàκ ≥ 0.ĐặtD := clD C (y, A, κ).
Tiếp theo, xét tập lồi đóng
Vì X là không gian Banach, hình chiếu của M lên X là bị chặn, trong khi hình chiếu M lên Y là D C (y, A, κ) Theo Bổ đề Robinson, ta có intD = intD C (y, A, κ) Hơn nữa, d(0, D) = d 0, D C (y, A, κ) Do đó, từ Bổ đề 1.2.1, ta suy ra điều cần chứng minh.
1.2.4 Nhận xét Kết hợp Mệnh đề 1.1.14 với Định lý 1.2.3 ta suy ra các khẳng định sau là tương đương:
(a)Ánh xạΓ(x) := h(x)−C là chính quy mêtric quanh(¯x,0) ∈ gphΓ; (b) Tồn tại κ˜ ≥ 0 sao cho dˆ C h(¯x), h 0 (¯x),κ˜ < 0;
(c) Với mọi κ >0, ta có dˆ C h(¯x), h 0 (¯x), κ < 0. Đặc biệt, điều kiện chính quy Robinson 0 ∈ int h(¯x) +h 0 (¯x)X − C đúng nếu và chỉ nếu sup y ∗ ∈S Y ∗ hy ∗ , yi −σ C (y ∗ )− k∇h(¯x) ∗ y ∗ k < 0.
Sau đây là một số tính chất cơ bản của hàm dˆ C (y, A, κ).
1.2.5 Bổ đề ([6, Lemma 2.7]).Với mỗiA ∈ L(X, Y) cố định, các khẳng định sau đây là đúng:
(i) ˆdC(ã, A,ã) là mụt hàm số lồi trờn Y ìR;
(ii) Với mỗi y ∈ Y, dˆ C (y, A,ã) là hàm số đơn điệu giảm trờn R; (iii) Với mỗi κ ∈ R, dˆ C (ã, A, κ) là Lipschitz trờn Y với hằng số 1.
1.2.6 Bổ đề ([6, Lemma 2.8]) Cho A ∈ L(X, Y), y ∈ Y và κ ≥ 0 sao cho dˆ C (y, A, κ) < 0 Khi đó, ta có d 0, A −1 (C −y) ≤ κ d(y, C)−dˆ C (y, A, κ)d(y, C) (1.10) Chứng minh Nếu y ∈ C thì d(y, C) = d 0, A −1 (C −y) = 0 và do đó (1.10) đúng Xét trường hợp y 6∈ C Khi đó, ta có d(y, C) =d(0, C −y) = ˆd C (y, A,0) > 0 và ¯ α := d(y, C) d(y, C)−dˆ C (y, A, κ) ∈ (0,1).
Nhờ tớnh lồi của hàm số dˆ C (y, A,ã), với mỗi α ∈ ( ¯α,1], ta cú dˆ C (y, A, ακ) ≤ dˆ C (y, A,0) +α dˆ C (y, A, κ)−dˆ C (y, A,0)
Theo Định lý 1.2.3, ta có
Do đó, với mỗi α ∈ ( ¯α,1], tồn tại x α ∈ ακB X sao cho x α ∈ A −1 (C −y). Điều này dẫn đến d 0, A −1 (C −y) ≤ inf α∈( ¯ α,1] kx α k ≤ inf α∈( ¯ α,1]ακ
Như vậy, chúng ta có điều phải chứng minh 2
Kết quả tiếp theo cung cấp công thức tính modulus tính chính quy mêtric cho một lớp ánh xạ đa trị thông qua hàm khoảng cách có dấu.
1.2.7 Định lý ([6, Lemma 2.9]) Cho A ∈ L(X, Y), y˜ ∈ C và x˜ ∈ X. Giả sử Ψ : X ⇒ Y là ánh xạ đa trị được xác định bởi Ψ(x) := ˜y+ A(x−x)˜ −C với mọi x ∈ X.
Khi đó, nếu Ψ là chính quy mêtric quanh điểm (˜x,0) ∈ gphΨ, thì
Chứng minh Theo Mệnh đề 1.1.14, Ψ là chính quy metric quanh điểm (˜x,0) nếu và chỉ nếu
Theo Định lý 1.2.3, (1.11) tương đương với dˆ C y, A, κ˜ < 0 với mọi κ > 0 Vỡ dˆ C y, A,˜ ã là hàm lồi nờn với mọi κ 1 , κ 2 ∈ (0,+∞), κ 1 < κ 2 , ta có κ1 κ 2 dˆ C y, A, κ˜ 2 + (1− κ1 κ 2 ) ˆd C y, A,˜ 0 ≥dˆ C y, A, κ˜ 1
Kết hợp với dˆ C (˜y, A,0) ≤ 0 và dˆ C y, A, κ˜ < 0 với mọi κ > 0, ta suy ra η(κ) := κ
Hàm số d ˆ C (˜ y,A,κ) là một hàm số tăng trên khoảng (0,+∞), do đó tồn tại giới hạn η¯:= lim κ→0 + η(κ) và η¯ = inf{η(κ) : κ > 0} Vì Ψ là một hàm chính quy mêtric quanh điểm (¯x,0), nên với mỗi > 0, có các số thực k, ρ > 0 thỏa mãn điều kiện k < RegΨ(˜x,0) + và int ρB Y ) ⊂ Ψ ˜x+kρB X.
Do đó, RegΨ(˜x,0) + > k ≥ η(kρ) ≥ η.¯ Vì > 0 được lấy bất kỳ nên ta suy ra
Với mỗi κ > 0 cố định và t ∈ (0,1), định nghĩa := −tdˆ C y, A, κ và k := η(κ)/(1 − t) Chọn các lân cận N x của x và N 0 của 0 sao cho kA(x−x) − yk ≤ cho mọi x ∈ N x và y ∈ N 0 Theo Bổ đề 1.2.5, với mỗi x ∈ N x và y ∈ N 0, ta có dˆ C (ω, A, κ) = ˆd C (y − y + A(x−x), A, κ).
Do đó, RegΨ(˜x,0) ≤ k := η(˜κ)/(1−t) Vì t ∈ (0,1) và ˜k > 0 có thể lấy tùy ý, nên ta suy ra
Kết hợp (1.12) và (1.13) ta có điều phải chứng minh 2
1.2.8 Bổ đề ([7, p 512]) ChoX là một không gian mêtric đầy đủ và f :
X → R¯ là một hàm chính thường nửa liên tục dưới trên X Giả sử rằng tồn tại x¯ ∈ domf := {x ∈ X : f(x) < +∞}, K > 0 và r ∈ (0,+∞] sao cho Kf(¯x) < r và với mọi t > K và x ∈ B(¯x, r)∩f −1 (0,+∞] tồn tại u ∈ X\{x} sao cho max{f(u),0} ≤ f(x)−t −1 d(x, u).
Khi đó, ta có f −1 (−∞,0] 6= ∅ và d(¯x, f −1 (−∞,0])≤ Kmax{f(¯x),0}.
Sau đây là một kết quả về tính giải được của phương trình suy rộng h(x) ∈ C quanh điểm x 0 cho trước.
1.2.9 Định lý ([6, Proposition 2.10]) Cho xˆ ∈ X và giả sử tồn tại
A ∈ L(X, Y), x 0 ∈ X và các số thực R >0, κˆ ≥ 0, γ >0 sao cho: (i) kh(x 0 )−h(x)−A(x 0 −x)k ≤ γkx 0 −xk với mọi x, x 0 ∈ xˆ+RB X , (ii) h(ˆx) +A(x 0 −x) ∈ C, r := kx 0 −xkˆ < R/2,
Khi đó, tồn tại x˜∈ x 0 +rB X sao cho h(˜x) ∈ C và Γ(x) := h(x)−C là chính quy mêtric quanh điểm (˜x,0) Hơn nữa, dˆ C h(˜x), A,κˆ+k˜x−xkˆ ≤dˆ C h(˜x), A,ˆκ +γk˜x−xk.ˆ
Chứng minh Lấy bất kỳ x ∈ x 0 +rintB X ⊂ xˆ+RB X Lưu ý rằng
Nhờ (i) và (iii) chúng ta nhận được dˆ C h(x), A,ˆκ+ kx−xkˆ
= sup y ∗ ∈S Y ∗ hy ∗ , h(x)i −σ C (y ∗ )−(ˆκ+ kx−xk)kAˆ ∗ y ∗ k
Do đó, nhờ Bổ để 1.2.6, tồn tại ∆x ∈ X sao cho h(x) +A∆x ∈ C và k∆xk ≤ ˆκ+kx−xkˆ
Lấy bất kỳ α ∈ (0,1] sao cho u := x+α∆x ∈ xˆ+RB X Khi đó, nhờ (i) và tớnh lồi của hàm d(ã, C), ta cú d h(u), C ≤ d h(x) +Aα∆x, C) +kh(u)−h(x)−αA∆xk
Sử dụng (i) và (ii) ta nhận được d h(x 0 ), C ≤ d h(ˆx) +A(x 0 −x), Cˆ +kh(x 0 )−h(ˆx)−A(x 0 −x)kˆ
Vì vậy, nhờ(iii),ta cóKd h(x 0 ), C ≤ Kγr < r.Đặtf(x) := d h(x), C). Theo Bổ đề 1.2.8, tồn tại x˜ thỏa mãn d h(˜x), C = 0 và k˜x−x 0 k < r. Tiếp theo, chúng ta chứng minh Γlà chính quy metric quanh điểm(˜x,0).
Vì dˆ C h(˜x), A,κˆ + k˜x −xkˆ ≤ dˆ C h(˜x), A,κ) +ˆ γk˜x −xkˆ < 0 nên từ Định lý 1.2.7 ta suy ra Ψ(x) := h(˜x) +A(x−x)˜ −C là chính quy metric quanh điểm (˜x,0) và
Lưu ý rằng bán kính tính chính quy mêtric Rad(˜x,0) của Ψ tại (˜x,0) thỏa mãn
Hơn nữa, h(ã)−h(˜x)−A(ã −x)˜ là Lipschitz quanh điểm x˜với hằng số γ.
Do đó, Γ(x) = Ψ(x) + h(x)− h(˜x) −A(x −x)˜ là chính quy mêtric quanh điểm (˜x,0) 2
Các điều kiện cần và đủ cực trị
Trong chương này, chúng ta trình bày các điều kiện cần và điều kiện đủ để một điểm chấp nhận được là nghiệm tối ưu của bài toán (P).
Điều kiện Fritz John và điều kiện Kuhn-Tucker
Mục này trình bày thông tin về điều kiện Fritz John và Kuhn-Tucker cùng các khái niệm liên quan Trong phần tiếp theo, các ánh xạ f, g và các nón K, L sẽ được hiểu như trong phát biểu của bài toán (P), trong khi Γ và h là các ánh xạ (đa trị và đơn trị) được xác định theo (1.2) và (1.3).
2.1.1 Định nghĩa ([6, Definition 3.7]) Cho h là khả vi tại x¯ ∈ Ω Ta nói x¯ là không suy thoái nếu int(h 0 (¯x)B X −C) 6= ∅, (2.1) ở đây h và C được xác định bởi (1.3).
2.1.2 Chú ý Vì ta giả sử intL 6= ∅, nên (2.1) đúng khi và chỉ khi int(g 0 (¯x)B X −K) 6= ∅ (2.2) Điều kiện này yếu hơn chuẩn hóa ràng buộc Robinson:
0 ∈ int(g(¯x) +g 0 (¯x)X −K) 6= ∅, (2.3) trong khi (2.3) đúng nếu và chỉ nếu ánh xạ ràng buộc G(x) := g(x)−K là chính quy mêtric quanh (¯x,0); xem Mệnh đề 1.1.14.
2.1.3 Định nghĩa ([6, p 986]) Cho x¯ là một điểm chấp nhận được của (P) và ánh xạ h là khả vi chặt tại x.¯
(i) Điều kiện Fritz John cho bài toán (P) tại x¯ là điều kiện tồn tại u ∗ ∈ L ∗ và v ∗ ∈ N K g(¯x) , không đồng thời bằng không, sao cho f 0 (¯x) ∗ u ∗ + g 0 (¯x) ∗ v ∗ = 0, (2.4) ở đây
L ∗ := {u ∗ ∈ U ∗ : hu ∗ , v ∗ i ≥ 0 với mọi u ∈ L} là nón đối ngẫu (dương) của nón L và
NK(z) là nón pháp tuyến của K tại z, được định nghĩa bởi tập hợp các véc-tơ v ∗ thuộc V ∗ sao cho tích vô hướng giữa v ∗ và v−z không vượt quá 0 với mọi v thuộc K Mỗi véc-tơ y ∗ = (u ∗, v ∗) thỏa mãn điều kiện Fritz John được gọi là một nhân tử Fritz John của bài toán (P) tại x.¯.
Điều kiện Kuhn-Tucker cho bài toán (P) tại điểm x¯ yêu cầu tồn tại một u ∗ thuộc L ∗ (với u ∗ khác 0) và một v ∗ thuộc N K g(¯x) sao cho điều kiện (2.4) được thỏa mãn Mỗi cặp y ∗ = (u ∗ , v ∗ ) thoả mãn điều kiện Kuhn-Tucker này được gọi là nhân tử Kuhn-Tucker của bài toán (P) tại x¯.
2.1.4 Chú ý 1) Dưới đây ta ký hiệu ΛF J (tương ứng, ΛKT) là tập tất cả các nhân tử Fritz John (tương ứng, Kuhn-Tucker) của (P) tại x.¯ Rõ ràng ta có Λ F J = y ∗ := (u ∗ , v ∗ ) : h 0 (¯x) ∗ y ∗ = 0, y ∗ ∈ N C (h(¯x)), y ∗ 6= 0 (2.5)
Giả sử x¯ là một điểm cực tiểu địa phương yếu của bài toán (P) Năm 1976, Robinson đã chứng minh rằng tập hợp Λ F J không rỗng nếu điều kiện (2.1) được thỏa mãn; hơn nữa, nếu chuẩn hóa ràng buộc Robinson (2.3) đúng, thì tập hợp Λ KT cũng không rỗng Do đó, dưới những giả thiết thích hợp, điều kiện Fritz John và điều kiện Kuhn-Tucker trở thành những điều kiện cần thiết cho tối ưu (bậc nhất) tại điểm cực tiểu địa phương yếu.
3) Nếu x¯ là một cực tiểu địa phương yếu của bài toán (P), thì, theoMệnh đề 1.1.18, ỏnh xạ h(ã)−C khụng chớnh quy mờtric quanh (¯x,0).
Theo Nhận xột 1.2.4, h(ã)−C khụng chớnh quy mờtric quanh điểm(¯x,0) khi và chỉ khi dˆ C h(¯x), h 0 (¯x),1 = sup y ∗ ∈S Y ∗ hy ∗ , h(¯x)i −σ C (y ∗ )− kh 0 (¯x) ∗ y ∗ k ≥ 0.
Vì h(¯x) ∈ C nên hy ∗ , h(¯x)i − σ C (y ∗ ) ≤ 0 với mọi y ∗ ∈ Y ∗ Do đó, h(ã) − C khụng là chớnh quy mờtric quanh điểm (¯x,0) nếu và chỉ nếu tồn tại một dãy (y n ∗ ) ⊂ S Y ∗ sao cho n→∞lim σ C (y n ∗ )− hy n ∗ , h(¯x)i = 0 và lim n→∞kh 0 (¯x) ∗ y n ∗ k = 0 (2.6)
Điểm chấp nhận được x¯ của bài toán (P) được định nghĩa là một điểm tới hạn bậc hai nếu điều kiện lim inf x→¯ x,τ→0 + dˆ C h(x), h 0 (¯x), τkx−xk¯ kx−xk¯ 2 ≥0 được thỏa mãn.
2.1.6 Bổ đề ([6, Lemma 4.1]) Nếu x¯ là một điểm tới hạn bậc hai của bài toỏn (P), thỡ h(ã)−C khụng chớnh quy mờtric tại (¯x,0).
Giả sử rằng h(ã)−C là chớnh quy mờtric quanh điểm (¯x,0), điều này dẫn đến việc x¯ không phải là một cực tiểu địa phương yếu Do đó, tồn tại một chuỗi xn → x với xn 6= ¯x và h(xn) ∈ C cho mọi n Đặt τn := kx n −xk Theo định nghĩa của điểm tới hạn bậc hai, tồn tại y n ∗ ∈ S Y ∗ sao cho lim inf n→∞ nhy n ∗ , h(x n )i −σ C (y n ∗ ) kx n −xk¯ 2 − kh 0 (¯x) ∗ y n ∗ ko ≥ 0.
Vì h(xn) ∈ C nên hy n ∗ , h(xn)i −σC(y n ∗ ) ≤ 0 Do đó, n→∞lim kh 0 (¯x) ∗ y n ∗ k = lim n→∞ hy n ∗ , h(xn)i −σC(y n ∗ ) = 0.
Kết hợp với tính liên tục của h tại x,¯ ta suy ra dãy y n ∗ thỏa mãn (2.6).
Vỡ vậy, h(ã) − C thỡ khụng chớnh quy mờtric tại điểm (¯x,0) Điều này mâu thuẫn với giả thiết phản chứng Bổ đề được chứng minh 2
2.1.7 Mệnh đề ([6, Proposition 4.2]) Cho x¯ là một điểm không suy thoái và (y n ∗ ) ⊂ S Y ∗ là một dãy thỏa mãn (2.6) Khi đó, nếu y¯ ∗ là một điểm tụ yếu ∗ của dãy (y n ∗ ), thì y¯ ∗ ∈ Λ F J ∩B Y ∗
Giả sử (y n ∗ ) ∈ S Y ∗ là một dãy thỏa mãn (2.6) và ¯ y ∗ là điểm tụ yếu ∗ của dãy này Do y ∗ 7→ σ C (y ∗ ) − hy ∗ , h(¯x)i và y ∗ 7→ kh 0 (¯x) ∗ y ∗ k là các hàm nửa liên tục dưới yếu ∗, ta có h 0 (¯x) ∗ y¯ ∗ = 0 và σ C (¯y ∗ )− h¯y ∗ , h(¯x)i = 0 Điều này tương đương với y¯ ∗ ∈ N C (h(¯x)) Nếu x¯ là điểm không suy thoái, ta lấy y¯∈ h(¯x) + int h 0 (¯x)B X −C.
Cho n → ∞, ta có hy n ∗ , h(¯x)−yi −¯ σ C (y n ∗ )− kh 0 (¯x) ∗ y n ∗ k ≤ −ρ.
Từ đó suy ra hy¯ ∗ ,yi ≥¯ ρ > 0 Như vậy, y¯ ∗ 6= 0, y¯ ∗ ∈ N C (h(¯x)) và h 0 (¯x) ∗ y¯ ∗ = 0 Điều này có nghĩa là y¯ ∗ ∈ Λ F J 2
Định lý 2.1.8 cho biết rằng nếu x¯ là một điểm không suy thoái và Λ F J khác không, thì với mỗi y thuộc vào int h(¯x) + h 0 (¯x)B X − C, tập hợp Λ y F J sẽ là một tập con lồi không rỗng và compact yếu ∗ của Y ∗ Hơn nữa, Λ F J được định nghĩa là (0,+∞)Λ y F J, trong đó Λ y F J là tập hợp các y ∗ thuộc Λ F J sao cho hy ∗ , yi = 1.
Chứng minh Giả sử y ∈ int h(¯x) +h 0 (¯x)B X −C Đặt ϕ y (y ∗ ) := hy ∗ , yi −1 với mọiy ∈ Y.
Ta có các ánh xạ tuyến tính liên tục yếu ∗, bao gồm ϕ y : Y ∗ → R và h 0 (¯x) ∗ : Y ∗ → X ∗ Lưu ý rằng N K h(¯x) là một tập lồi đóng yếu ∗ Do đó, tập Λ y F J = h 0 (¯x) ∗ −1 (0)∩N K h(¯x) ∩ϕ −1 y (0) cũng là một tập lồi đóng yếu ∗ Vì y thuộc vào int h(¯x) + h 0 (¯x)B X −C, nên theo Định lý 1.2.3, ta có những kết luận quan trọng về cấu trúc của các ánh xạ này.
Khi đó, với mọi y ∗ ∈ Λ F J , ta có
D y ∗ ky ∗ k,−yE = D ky y ∗ ∗ k, h(¯x−yE−σ C ky y ∗ ∗ k
Từ đó suy ra hy ∗ , yi ≥ ρky ∗ k Do đó, Λ y F J 6= ∅ nếu và chỉ nếu ΛF J 6= ∅. Hơn nữa, ΛF J := (0,+∞)Λ y F J Rõ ràng với y ∗ ∈ Λ y F J ⊂ ΛF J, ta có
1 = hy ∗ , yi ≥ ρky ∗ k Điều này chứng tỏ Λ y F J là một tập bị chặn Vì vậy,nhờ định lý Banach-Alaoglu-Bourbaki, Λ y F J là một tập compact yếu ∗ 2
Các điều kiện tối ưu bậc hai
Mục này đề cập đến các điều kiện cần và đủ để xác định cực trị cho bài toán (P), trong đó áp dụng thông tin cấp hai của hàm mục tiêu cùng với ánh xạ xác định miền ràng buộc của (P).
Nếu (P) là một bài toán tối ưu vô hướng, thì các khái niệm cực tiểu địa phương yếu và cực tiểu địa phương chặt tương ứng với các khái niệm trong lý thuyết tối ưu vô hướng Cực tiểu địa phương thiết yếu bậc hai là những điểm chấp nhận được, đồng thời thỏa mãn điều kiện tăng trưởng toàn phương.
Trong lý thuyết tối ưu cổ điển, điều kiện cần để xác định cực trị bậc hai được áp dụng cho cực tiểu địa phương, trong khi điều kiện đủ bậc hai chủ yếu được thiết lập cho cực tiểu địa phương mạnh, tức là những điểm thỏa mãn điều kiện tăng trưởng toàn phương Cần lưu ý rằng không có điều kiện đủ bậc hai nào cho các điểm cực tiểu địa phương không đáp ứng điều kiện tăng trưởng toàn phương.
Trong bài toán tối ưu (P), lý thuyết tối ưu cổ điển cho thấy rằng việc thiết lập điều kiện cần bậc hai cho cực tiểu địa phương yếu là hợp lý, trong khi điều kiện đủ bậc hai được áp dụng cho cực tiểu địa phương thiết yếu bậc hai Định lý sau đây sẽ trình bày một số điều kiện tối ưu bậc hai liên quan đến vấn đề này.
2.2.1 Định lý ([6, Theorem 3.2]) Cho x¯ là một điểm chấp nhận được của (P) Giả sử rằng ánh xạ h là khả vi tại x¯ và tồn tại các số thực ¯ r > 0, η ≥ 0 sao cho kh(x 1 )−h(x2)−h 0 (¯x)(x1 −x2)k
≤ηmax{kx 1 −xk,¯ kx 2 −xk}kx¯ 1 −x 2 k,
(2.8) với mọi x 1 , x 2 ∈ x¯+ ¯rB X Khi đó, các khẳng định sau là đúng:
(i) Nếu x¯ là cực tiểu địa phương yếu của (P), thì x¯ là điểm tới hạn bậc hai của (P);
(ii) Điểm x¯ là cực tiểu địa phương thiết yếu bậc hai của (P) nếu và chỉ nếu lim inf x→¯ x,τ →0 + dˆ C h(x), h 0 (¯x), τkx−xk¯ kx−xk¯ 2 > 0 (2.9)
Giả sử x¯ không phải là điểm tới hạn bậc hai của (P), tức là (2.7) không đúng Chúng ta cần chứng minh rằng x¯ không phải là điểm cực tiểu địa phương yếu Vì (2.7) không đúng, tồn tại một dãy xn → x, τ¯ n → 0+ và một số thực β > 0 sao cho dˆ C h(x n ), h 0 (¯x), τ n kx n − xk¯ ≤ −βkx n − xk¯ 2 < 0 với mọi n ∈ N.
Theo Định lý 1.2.3, với mỗi n ∈ N, tồn tại s n ∈ κ n B X thỏa mãn h(x n ) + h 0 (¯x)s n ∈ C, trong đó κ n := τ n k¯x−x n k Chọn r > 0 và η ≥ 0 sao cho (2.8) được thỏa mãn Khi n đủ lớn, ta có k¯x−x n k + 3κ n < r và 8η(kx n −xk¯ + 3κ n)κ n − βkx n −xk¯ 2 < 0.
Sử dụng Định lý 1.2.9 với các ký hiệu xˆ := x n, A := h 0 (¯x), x 0 := x n + s n, R = 3κ n, ˆ κ := κn và γ := η(kx n − xk¯ + 3κn), ta có thể khẳng định tồn tại x˜n ∈ X sao cho h(˜xn) ∈ C, kx n − x˜nk ≤ 2κn và Γ là chính quy mêtric quanh (˜xn,0) Hơn nữa, x˜n hội tụ về x¯, do đó, theo Mệnh đề 1.1.19, x¯ không phải là một cực tiểu địa phương yếu của bài toán (P).
Giả sử (2.9) không đúng, chúng ta sẽ chứng minh rằng x¯ không phải là một cực tiểu địa phương thiết yếu bậc hai Khi (2.9) không đúng, sẽ tồn tại một chuỗi xn hội tụ về x¯ và τn hội tụ về 0+, sao cho dˆ C h(xn), h 0 (¯x), τn kx n −xk¯ ≤ 1 nkx n −xk¯ 2 cho mọi n thuộc N.
Nhờ Định lý 1.2.3, chúng ta có thể giả sử rằng d 0, h(x n ) +τ n kx n −xkh¯ 0 (¯x)B X −C ≤ 1 nkx n −xk¯ 2 với mọi n ∈ N.
Do đó, với mỗi n∈ N, tồn tại s n ∈ τ n kx n −xk¯ B X và c n ∈ C sao cho kh(x n ) +h 0 (¯x)sn −cnk ≤ 2 nkx n −xk¯ 2 Nhờ (2.8), ta có d 0,Γ(x n +s n ) = d h(x n + s n ), C
≤ n 2 kx n −xk¯ 2 +η(kx n −xk¯ + ks n k)ks n k = o(kx n −xk¯ 2 ).
Mặt khác, kx n +s n k ≥ kx n −xk − k¯¯ x−s n k ≥ kx n −xk(1¯ −τ n ).
Khi n tiến tới vô cùng, giới hạn d 0,Γ(xn + sn) kx n + s n k 2 bằng 0, chứng tỏ rằng x¯ không phải là một điểm cực tiểu địa phương thiết yếu bậc hai Nếu x¯ là một điểm cực tiểu địa phương thiết yếu bậc hai, thì điều kiện (2.9) sẽ đúng Ngược lại, giả sử (2.9) đúng, sẽ tồn tại các giá trị β, ε > 0 và lân cận N của x¯ sao cho dˆ C h(x), h 0 (¯x), τkx−xk¯ ≥ βkx−xk¯ 2 với mọi x thuộc N, τ nằm trong khoảng (0, ε) Hơn nữa, ta có d 0,Γ(x) = d h(x), C ≥ dˆ C h(x), h 0 (¯x), τkx−xk¯ với mọi x thuộc X và τ > 0, từ đó suy ra d 0,Γ(x) ≥ βkx−xk¯ 2 với mọi x thuộc N.
Như vậy, x¯ là cực tiểu địa phương thiết yếu cấp hai của (P) 2
Rõ ràng, phương trình (2.8) đảm bảo rằng ánh xạ h là khả vi chặt tại điểm x̄ Hơn nữa, điều kiện này được thỏa mãn nếu hàm h là khả vi liên tục tại x̄ và có đạo hàm h' là Lipschitz quanh điểm x̄, hoặc nếu hàm h là khả vi hai lần tại x̄.
Hệ quả cho thấy rằng nếu x¯ là một điểm chấp nhận được của bài toán (P) và ánh xạ h khả vi tại x¯ với các điều kiện nhất định, thì x¯ sẽ là một điểm tới hạn bậc hai của (P) nếu tồn tại số thực β ≥ 0 sao cho với mỗi dãy {(z n , tn, τn)} ⊂ SX ×R + ×R + thỏa mãn tn → 0+ và τn →0+, giới hạn lim inf n→∞ sup y ∗ ∈S Y ∗ nhy ∗ , h(¯x) +t n h 0 (¯x)z n i −σ C (y ∗ ) t 2 n được thỏa mãn.
Chứng minh Từ (2.10) ta suy ra h 00 (¯x;αz) = α 2 h 00 (¯x;z) với mọi α ≥ 0 và z ∈ X.Hơn nữa, tính chất hội tụ đều theo z của giới hạn trong (2.10) kéo theo khai triển h(x) =h(¯x) +h 0 (¯x)(x−x) +¯ 1
Theo định nghĩa, điểm x¯ được coi là một điểm tới hạn bậc hai của bài toán (P) nếu và chỉ nếu tồn tại một số thực β ≥ 0 (hoặc β > 0) sao cho giới hạn dưới khi x tiến tới x¯ và τ tiến tới 0 dˆ C h(x), h 0 (¯x), τkx−xk¯ kx−xk¯ 2 lớn hơn hoặc bằng β.
Lưu ý rằng lim inf x→¯ x,τ →0 + dˆ C h(x), h 0 (¯x), τkx−xk¯ kx−xk¯ 2
= lim inf x→¯ x,τ →0 + sup y ∗ ∈S Y ∗ hy ∗ , h(x)i −σ C (y ∗ )−τkx−xkkh¯ 0 (¯x) ∗ y ∗ k kx−xk¯ 2
(2.14) Kết hợp (2.12), ta có lim inf x→¯ x,τ →0 + dˆ C h(x), h 0 (¯x), τkx−xk¯ kx−xk¯ 2 lim inf x→¯ x,τ →0 + sup y ∗ ∈S Y ∗ nhy ∗ , h(¯x) +kx−xkh¯ 0 (¯x) kx−xk¯ −1 (x−x)¯ i −σ C (y ∗ ) kx−xk¯ 2
2hy ∗ , h 00 x;¯ kx−xk¯ −1 (x−x)¯ i − τ kx−xk¯ kh 0 (¯x) ∗ y ∗ ko.
Do đó, từ (2.13), (2.15) và định nghĩa của lim inf ta suy ra điều phải chứng minh 2
Hai định lý tiếp theo sẽ cung cấp thêm thông tin về các điều kiện tối ưu đã được trình bày trong Định lý 2.2.1 và Hệ quả 2.2.3.
Định lý 2.2.4 chỉ ra rằng nếu x¯ là một điểm chấp nhận của bài toán (P) nhưng không phải là cực tiểu địa phương thiết yếu bậc hai, thì tồn tại một ánh xạ khả vi liên tục hai lần δh = (δf, δg) với δh(¯x) = 0, δh' (¯x) = 0 và δh'' (¯x) = 0, dẫn đến việc x¯ không phải là cực tiểu địa phương yếu của (P) khi f và g được thay thế bằng f + δf và g + δg.
Chứng minh Vì x¯ không phải là điểm cực tiểu địa phương thiết yếu bậc hai, nên tồn tại x n → x, x¯ n 6= ¯x, thỏa mãn dn := max{d(f(xn)−f(¯x),−L), d(g(x n ), K)} = o(kx n −xk¯ 2 ).
Do đó, tồn tại y n = (u n , v n ) ∈ (−intL)×K sao cho kh(x n )−y n k = max{kf(x n )−f(¯x)−u n k,kg(x n )−v n k}
≤ d n +kx n −xk¯ 3 =: ¯d n , ở đây chuẩn của không gian tích U ×V là chuẩn max Bằng cách chọn dãy con nếu cần, chúng ta có thể giả sử
Bây giờ chúng ta xây dựng một dãy con của (x n ), để đơn giản vẫn sẽ được ký hiệu là (x n ), thỏa mãn τ n := kx n −xk ≤¯ d(¯x, A n−1 )
Đối với mọi n ≥ 2, A n là bao lồi của {x 1, , x n} Ký hiệu m n là số chiều của không gian tuyến tính sinh bởi {x 1 − x, , x n − x} Nếu dãy (m n) bị chặn, thì {x n − x} ∞ n=1 được chứa trong một không gian con hữu hạn chiều E của X Điều này cho phép chúng ta tìm một dãy con (x n) và z ∈ E, với kzk = 1, sao cho (x n − x)/τ n → z Bằng cách chuyển qua dãy con, chúng ta có thể giả sử rằng k(x n − x)/τ n − zk ≤ 1/2 với mọi n và τ n ≤ τ n−1 /8 với mọi n ≥ 2 Với n ≥ 2 và x ∈ A n−1 cố định, có thể biểu diễn x n−1.
Để thỏa mãn điều kiện P n=1 α i τ i ≥ τ n−1 2, ta nhận thấy rằng x ∈ A n−1 được chọn một cách tùy ý dẫn đến d(¯x, A n−1) ≥ τ n−1 /2 ≥ 4τ n Nếu dãy (m n) không bị chặn, ta có thể xác định một dãy con của (x n), vẫn mang ký hiệu là (x n), sao cho m n = n với mọi n, từ đó suy ra x /¯ ∈ A n với mọi n Nếu x¯ ∈ A n, sẽ tồn tại t i ≥ 0 cho i = 1, , n.