Luận văn Thạc sĩ Toán học: Điều kiện cần cực trị của bài toán biến phân

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:67

Thêm vào BST

Báo xấu

32
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích của luận văn là trình bày các khái niệm nghiệm yếu và nghiệm mạnh địa phương và toàn cục của bài toán biến phân, các điều kiện cực trị cấp một và cấp hai của bài toán biến phân. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Điều kiện cần cực trị của bài toán biến phân

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HOÀNG THỊ QUỲNH NHƯ ĐIỀU KIỆN CẦN CỰC TRỊ CỦA BÀI TOÁN BIẾN PHÂN Chuyên ngành: Toán ứng dụng Mã số: 60.46.01.12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TS. TẠ DUY PHƯỢNG Thái Nguyên - 2017
2 Mục lục Chương 1. Kiến thức chuẩn bị 5 1.1 Không gian tuyến tính định chuẩn . . . . . . . . . . . . . 5 1.1.1 Khái niệm về không gian tuyến tính . . . . . . . . 5 1.1.2 Khái niệm về không gian tuyến tính định chuẩn . 6 1.2 Phép tính vi phân . . . . . . . . . . . . . . . . . . . . . . 7 1.2.1 Dưới vi phân của hàm lồi . . . . . . . . . . . . . 7 1.2.2 Đạo hàm Gâteaux . . . . . . . . . . . . . . . . . 7 1.2.3 Đạo hàm Fréchet . . . . . . . . . . . . . . . . . . 8 Chương 2. Điều kiện cần cực trị cho bài toán tối ưu trong không gian vô hạn chiều 13 2.1 Định lí Fermat . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.1 Bài toán trơn không có ràng buộc . . . . . . . . . 14 2.1.2 Bài toán lồi không có ràng buộc . . . . . . . . . . 16 2.2 Qui tắc nhân tử Lagrange . . . . . . . . . . . . . . . . . 19 Chương 3. Điều kiện cần cho bài toán biến phân 30 3.1 Bài toán biến phân cơ sở . . . . . . . . . . . . . . . . . . 33 3.2 Phương trình Euler . . . . . . . . . . . . . . . . . . . . . 34 3.3 Bổ đề Du Bois-Reymond và bài toán Bolza . . . . . . . . 42 3.4 Ví dụ của Hilbert . . . . . . . . . . . . . . . . . . . . . . 49 3.5 Điều kiện Weierstrass . . . . . . . . . . . . . . . . . . . . 51 3.6 Điều kiện Legendre . . . . . . . . . . . . . . . . . . . . . 53 3.7 Điều kiên Jacobi . . . . . . . . . . . . . . . . . . . . . . 55 3.8 Bài toán đẳng chu . . . . . . . . . . . . . . . . . . . . . 59 3.9 Bài toán điều khiển tối ưu và nguyên lý cực đại Pontriagin 62 3.9.1 Dẫn tới bài toán điều khiển tối ưu . . . . . . . . . 62 3.9.2 Bài toán điều khiển tối ưu . . . . . . . . . . . . . 63
3 Tài liệu tham khảo 66
3 Lời nói đầu Điều kiện cần cực trị cho bài toán tối ưu được Fermat phát biểu cách đây hơn 300 năm. Lí thuyết điều kiện cần cực trị trong không gian hữu hạn chiều cho bài toán có hạn chế được phát triển qua nhiều thời kì bởi các nhà toán học Lagrange, Euler, Kuhn, Tucker,... Năm 1696, Johann I. Bernoulli đã phát biểu bài toán đường đoản thời (brachistochrone): Cho trước hai điểm A và B trên một mặt phẳng thẳng đứng. Hãy xác định đường AM B để dưới tác động của lực trọng trường một vật thể M chuyển động trên đó từ A đến B trong thời gian ngắn nhất. Vấn đề này bắt nguồn từ thực nghiệm của G. Galilei: Nếu cho hai viên bi giống nhau lăn trên dây cung và trên cung tròn thì viên bi lăn trên cung tròn có thể đến điểm cuối nhanh hơn (mặc dù đường đi dài hơn, nhưng tốc độ lớn hơn). Giả sử y(x) là hàm mô tả đường cong chuyển động của viên bi trên hệ trục tọa độ (x, y) với y(x0 ) = 0, y(x) ≤ 0 khi x ≥ x0 . Điểm A có tọa độ là A(x0 , 0) và điểm B có tọa độ là B(x1 , y1 ) cho trước. Giả thiết lực ma sát là không đáng kể, theo định luật rơi Galilei, ta p có vận tốc của viên bi là −2gy(x), trong đó g ≈ 9, 8m/s2 là gia tốc p rơi tự do. Quãng đường đi được sau thời gian dt là ds = 1 + y 02 (x)dx. p p 2 ds p 0 1 + y (x)dx 1 + y 0 2 (x) Vì v(t) = nên −2gy(x) = hay dt = p dx. dt dt −2gy(x) Zx1 p 1 + y 0 2 (x) Thời gian đi từ A(x0 , 0) đến B(x1 , y1 ) sẽ là: T = p dx. −2gy(x) x0 Bài toán trở thành: Trong số tất cả các quỹ đạo (đường cong) y(x) nối hai điểm A(x0 , 0) đến B(x1 , y1 ) cho trước, hãy tìm đường cong
4 Zx1 p 1 + y 0 2 (x) làm cực tiểu phiếm hàm p dx. −2gy(x) x0 Đây là bài toán cực trị có ràng buộc: Zx1 p 1 + y 0 2 (x) T = p dx → inf (1) −2gy(x) x0 y(x0 ) = 0, y(x1 ) = y1 . (2) Bài toán (1)–(2) là bài toán tối ưu trong không gian vô hạn chiều (không gian tất cả các đường cong trơn nối hai điểm cho trước). Sau Bernoulli, bài toán này được tổng quát thành bài toán biến phân: Zt1 J(x(.)) = L(t, x(t), x(t))dt ˙ → inf t0 (x(t0 ), x(t1 )) ∈ Γ, trong đó [t0 , t1 ] ⊂ R cho trước, Γ ⊂ Rn × Rn , L là hàm liên tục trên miền nào đó của R × Rn × Rn . Mục đích của luận văn là trình bày các khái niệm nghiệm yếu và nghiệm mạnh địa phương và toàn cục của bài toán biến phân, các điều kiện cực trị cấp một và cấp hai của bài toán biến phân. Tác giả xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS. Tạ Duy Phượng đã tận tình hướng dẫn và giúp đỡ em trong suốt quá tình học tập và nghiên cứu. Em cũng xin bày tỏ lòng biết ơn chân thành tới các Giáo sư, Phó giáo sư, Tiến sĩ, quý thầy cô giáo giảng dạy tại Đại học Khoa học, Đại học Thái Nguyên và tại Viện Toán học, Viện Hàn lâm Khoa học và Công nghệ Việt Nam, đã mang đến cho em nhiều kiến thức bổ ích trong nghiên cứu khoa học. Đồng thời, tôi xin gửi lời cảm ơn tới gia đình và các bạn đồng môn đã luôn giúp đỡ và động viên tôi trong thời gian học tập và trong quá trình hoàn thành luận văn. Thái Nguyên, tháng 05 năm 2017. Tác giả Hoàng Thị Quỳnh Như
5 Chương 1 Kiến thức chuẩn bị 1.1 Không gian tuyến tính định chuẩn 1.1.1 Khái niệm về không gian tuyến tính Định nghĩa 1.1.1 Tập X 6= ∅ gồm các đối tượng nào đó được gọi là một không gian tuyến tính trên trường số thực R, nếu trên đó: (I) Có qui tắc cho ứng với hai phần tử x, y bất kỳ thuộc X một phần tử z cũng thuộc X được gọi là “tổng” của x và y, ký hiệu z = x + y; (II) Có qui tắc cho ứng với một phần tử α ∈ R và một phần tử x ∈ X một phần tử p cũng thuộc X gọi là tích giữa α với x, ký hiệu là p = αx. (III) Các qui tắc cho ở (I) và (II) phải thỏa mãn tám tiên đề sau đây: (1) ∀x, y ∈ X : x + y = y + x (tính giao hoán); (2) ∀x, y, z ∈ X : (x + y) + z = x + (y + z) (tính kết hợp); (3) ∃θ (phần tử 0) sao cho ∀x ∈ X : θ + x = x + θ = x; (4) ∀x ∈ X : ∃x0 (phần tử đối) sao cho: x + x0 = x0 + x = θ; (5) ∀x ∈ X : 1x = x; (1 ∈ R); (6) ∀α ∈ R, ∀x, y ∈ X : α(x + y) = αx + αy; (7) ∀α, β ∈ R, ∀x ∈ X : (αβ)x = α(βx); (8) ∀α, β ∈ R, ∀x ∈ X : (α + β)x = αx + βx. Ví dụ 1.1.2 Không gian các hàm liên tục từ [a, b] vào R, kí hiệu là C[a, b] là một không gian tuyến tính. Tương tự, không gian các hàm khả vi liên tục trên [a, b], kí hiệu là C1 [a, b] cũng là không gian tuyến tính.
6 Thật vậy, với định nghĩa (i) z = x + y ⇔ z(t) = x(t) + y(t) ∀t ∈ [a, b]; (ii) z = λ.x ⇔ z(t) = λx(t) ∀t ∈ [a, b]. thì tám tiên đề trên được thỏa mãn. Vậy không gian các hàm liên tục hoặc các hàm khả vi liên tục trên [a, b] là một không gian tuyến tính. 1.1.2 Khái niệm về không gian tuyến tính định chuẩn Không gian tuyến tính X trên R được gọi là không gian (tuyến tính) định chuẩn, nếu trên đó có qui tắc cho ứng với mỗi phần tử x ∈ X bất kỳ một số thực không âm gọi là chuẩn (hoặc độ dài) của x, ký hiệu là kxk, thỏa mãn các tính chất sau đây: (i) ∀x ∈ X : kxk ≥ 0 và kxk = 0 ⇔ x = 0 (tính không âm); (ii) ∀x ∈ X, ∀λ ∈ R : kλxk = |λ|kxk (tính đồng nhất); (iii) ∀x, y ∈ X : kx + yk ≤ kxk + kyk (Bất đẳng thức tam giác). Ví dụ 1.1.3 Không gian C[a, b] các hàm liên tục ϕ : R → R và không gian C1 [a, b] là không gian tuyến tính định chuẩn với chuẩn tương ứng là kxkC[a,b] = max |x(t)| và a≤t≤b kxkC1n [a,b] = max{k x kC[a,b] , k x˙ kC[a,b] = max{max |x(t)|, max |x(t)|}. ˙ a≤t≤b a≤t≤b Khi ấy ba tiên đề về chuẩn được thỏa mãn.   x1 (t)  ...  n Ví dụ 1.1.4 Giả sử: x(·) : [a, b] → R , tức là: x(t) =   ∈    ...  xn (t)   x˙ 1 (t)  ...  Rn ∀t ∈ [a, b], ta định nghĩa x(t)˙ = .    ...  x˙ n (t) Kí hiệu: C n [a, b] và C1n [a, b] là các không gian tuyến tính trên [a, b] với định nghĩa thông thường về phép toán cộng véctơ và nhân một số
7 với một véctơ. Ta định nghĩa: kxkC n [a,b] = max {kxi kC[a,b] } 1≤i≤n và kxkC1n [a,b] = max {kxi kC1 [a,b] }. 1≤i≤n Khi ấy C n [a, b] và C1n [a, b] là các không gian tuyến tính định chuẩn. 1.2 Phép tính vi phân 1.2.1 Dưới vi phân của hàm lồi Cho f là một hàm lồi thật (hàm lồi chính thường) trên X. Tập ∂f (x) := {x∗ ∈ X ∗ | f (z) − f (x) ≥ hx∗ , z − xi ∀z ∈ X}. (1.1) được gọi là dưới vi phân của f tại x. Ví dụ 1.2.1 (Dưới vi phân của hàm chỉ) Với mọi x ∈ A thì ∂δ(x|A) khác rỗng vì nó đều chứa 0. Từ định nghĩa ta suy ra ∂δ(x | A) = N (x | A), (1.2) trong đó N (x|A) := {x∗ ∈ X ∗ |hx∗ , z − xi ≤ 0 ∀z ∈ A} (1.3) là nón pháp tuyến (normal cone) của tập A tại điểm x. 1.2.2 Đạo hàm Gâteaux Cho X và Y là hai không gian tô pô tuyến tính, V là một lân cận của x ∈ X và F : X → Y. Nếu δF (x, h) := lim t−1 (F (x + th) − F (x)) t→0 tồn tại với mọi h ∈ X thì ánh xạ h → δF (x, h) được gọi là biến phân bậc nhất của F tại x. Nếu tồn tại một toán tử tuyến tính liên tục Λ : X → Y sao cho Λh = δF (x, h) ∀h ∈ X
8 thì Λ được gọi là đạo hàm Gâteaux, ký hiệu là FG0 (x). Khi ấy ta nói: F khả vi Gâteaux tại x. Điều này xảy ra khi và chỉ khi tồn tại toán tử tuyến tính liên tục Λ : X → Y sao cho F (x + th) = F (x) + tΛh + o(t) ∀h ∈ X. Ví dụ 1.2.2 Cho r và ϕ là tọa độ cực của x ∈ R2 và f (x) = r cos 3ϕ. Ta có δf (0.h) = f (h). Vì δf (0.h) không tuyến tính nên f không khả vi Gâteaux tại 0 ∈ R2 . Trong Giải tích lồi, dưới vi phân đóng vai trò của đạo hàm. Nếu một hàm lồi khả vi Gâteaux tại một điểm thì dưới vi phân tại điểm đó có một phần tử duy nhất là đạo hàm Gâteaux. 1.2.3 Đạo hàm Fréchet Nếu X và Y là không gian Banach, F : X → Y khả vi Fréchet tại x nếu tồn tại toán tử tuyến tính liên tục Λ : X → Y sao cho kr(h)kY F (x + h) = F (x) + Λh + r(h) với lim = 0. khkX →0 khkX Khi đó Γ là đạo hàm Fréchet, ký hiệu là FF0 (x) hay F 0 (x). Ánh xạ F được gọi là chính qui tại x nếu nó khả vi Fréchet tại x và ImF 0 (x) = Y. Kí hiệu L(X, Y ) không gian của các toán tử tuyến tính liên tục từ X và Y, trang bị chuẩn kΛk = sup kΛxkY . kxkX =1 Nếu F : X → Y khả vi Fréchet tại mọi điểm trong tập mở V và ánh xạ x → F 0 (x) liên tục trên V (hay tại x0 ∈ V ) theo tô pô L(X, Y ) thì ta nói F khả vi liên tục trên V (hay tại x0 ,) hay F thuộc vào lớp C1 . Nếu F là một phiếm hàm và F 0 (x) = 0 thì x được gọi là một điểm dừng. Ví dụ 1.2.3 (Đạo hàm Fréchet của ánh xạ afin) Một ánh xạ A : X → Y từ không gian tuyến tính X vào không gian tuyến tính Y có dạng A(x) = Λx + a,
9 với a ∈ X và Λ là một ánh xạ tuyến tính từ X vào Y , được gọi là ánh xạ afin. Nếu X và Y là không gian Banach và Λ liên tục thì A khả vi Fréchet khắp nơi và A0F (x) = Λ. Mệnh đề 1.2.4 a) Nếu F khả vi Fréchet tại x thì F liên tục và khả vi Gâteaux tại đây FG0 (x) = FF0 (x). b) Nếu F khả vi Gâteaux tại x thì F biến phân bậc nhất tồn tại ở đó và δF (x, h) = FG0 (x)h. Chứng minh: Xem [4], p. 35. Ví dụ 1.2.5 Hàm  1 nếu x = (x )2 và x 6= 0, 1 2 2 f (x1 , x2 ) = 0 trường hợp còn lại khả vi Gâteaux tại (0, 0) ∈ R2 nhưng không liên tục tại đó nên theo Mệnh đề 1.2.4 thì nó không thể khả vi Fréchet được. Ta có Định lý 1.2.6 (Định lí giá trị trung bình) Cho X và Y là các không gian tô pô tuyến tính, U là một tập mở của X, ánh xạ F : U → Y khả vi Gâteaux tại mọi điểm trên đoạn nối [x, x + h] ⊂ U. Khi đó ta có: a) Nếu ánh xạ z → FG0 (z) là một ánh xạ liên tục của [x, x + h] vào Y thì Z 1 F (x + h) − F (x) = FG0 (x + th)h dt. 0 b) Nếu X và Y là không gian Banach thì kF (x + h) − F (x)k ≤ sup kFG0 (x + th)k · khk 0≤t≤1 và với mỗi Λ ∈ L(X, Y ) : kF (x + h) − F (x) − Λhk ≤ sup kFG0 (x + th) − Λk · khk. 0≤t≤1
10 Đặc biệt, với mọi z ∈ [x, x + h] thì kF (x + h) − F (x) − FG0 (z)hk ≤ sup kFG0 (x + th) − FG0 (z)k · khk. 0≤t≤1 Chứng minh: Xem [4], p. 38. Mệnh đề 1.2.7 Cho X là một không gian Banach và F là một ánh xạ liên tục từ một lân cận U của x0 ∈ X vào không gian Banach Y. Giả thiết rằng F khả vi Gâteaux tại mọi điểm của U và ánh xạ x → FG0 (x) từ U vào L(X, Y ) liên tục. Khi đó F khả vi Fréchet trên U và FG0 (x) = FF0 (x) ∀x ∈ U. Chứng minh: Xem [4], p. 39. Ví dụ 1.2.8 (Đạo hàm Fréchet của hàm vector) Cho g1 (t, x), . . . , gm (t, x) là các hàm thực, liên tục trên U ⊂ R × Rn và khả vi liên tục theo x. Đặt (g(t, x) = g1 (t, x), . . . , gm (t, x)) [G(x(·))](t) = g(t, x(t)), t0 ≤ t ≤ t1 . Như vậy G : C n ([t0 , t1 ]) → C m ([t0 , t1 ]). Gọi x0 (·) là một hàm liên tục [t0 , t1 ] → Rn có ảnh nằm trong U. Ta sẽ chỉ ra rằng G khả vi Fréchet tại x0 (·). Vì U là tập mở nên tồn tại > 0 sao cho |x0 (t) − x| < kéo theo (t, x) ∈ U. Nếu kx(·) − x0 (·)kC < ta có G(x(·) + λz(·)) − G(x(·)) lim (t) = gx (t, x(t))z(t), λ→0 λ nghĩa là [G0G (x(·))z(·)](t) = gx (t, x(t))z(t). Vì (t, x) → gx (t, x) liên tục nên x(·) → G0G (x(·)) cũng liên tục. Áp dụng Mệnh đề 1.2.7 ta nhận được tính khả vi Fréchet tại x0 (·) và [G0F (x0 (·))z(·)](t) = gx (t, x0 (t))z(t).
11 Nếu với mọi h ∈ X, hàm ϕh (t) := F (x + th) khả vi ít nhất n lần tại t = 0 thì n dn δ F (x, h) := n ϕh (t)|t=0 (1.4) dt được gọi là biến phân bậc n của F tại x. Đạo hàm Fréchet bậc n có thể được định nghĩa qui nạp: Nếu đạo hàm Fréchet (bậc nhất) F 0 của F tồn tại trong một lân cận của x thì đạo hàm Fréchet của F 0 tại x là Đạo hàm Fréchet bậc hai của F tại x. Nếu ánh xạ x → F 00 (x) tồn tại và liên tục trong lân cận của một điểm thì ta nói F khả vi liên tục hai lần tại điểm đó. Định lý 1.2.9 (Qui tắc dây chuyền) Cho X, Y và Z là các không gian Banach, U là một tập mở của X, V là một tập mở của Y, F : U → Y và G : V → Z. Cho x ∈ U với F (x) ∈ V. Nếu F khả vi Fréchet tại x và G khả vi Fréchet tại F (x) thì ánh xạ H = G ◦ F cũng khả vi Fréchet tại x, tức là H(x) = G ◦ F (x) = G(F (x)). Thì H 0 (x) = G0 (F (x)) ◦ F 0 (x). Ví dụ 1.2.10 (Đạo hàm Fréchet của hàm Lagrange) Cho L(t, x, y) là một ánh xạ từ W ⊂ R × Rn × Rn vào Rm , liên tục và khả vi liên tục theo x và y. x0 (·) là một hàm liên tục trên [t0 , t1 ] sao cho (t, x0 (t), x˙ 0 (t)) ∈ W với mọi t ∈ [t0 , t1 ]. Xét ánh xạ M : C1n ([t0 , t1 ]) → C m ([t0 , t1 ]), [M (x(·))](t) = L(t, x(t), x(t)), ˙ t ∈ [t0 , t1 ]. Ta có M = M2 ◦ M1 , trong đó [M1 (x(·))](t) = (x(t), x(t)), ˙ t0 ≤ t ≤ t1
12 và [M2 (x(·), y(·))](t) = L(t, x(t), y(t)), t0 ≤ t ≤ t1 . Ví dụ 1.2.8 cho ta [M20 (x(·), y(·))(r(·), s(·))](t) = Lx (t, x(t), y(t))r(t) + Ly (t, x(t), y(t))s(t). Mặt khác dễ dàng nhận thấy [M10 (x(·))z(·)](t) = (z(t), z(t)). ˙ Áp dụng Định lí 1.2.9 ta có [M 0 (x0 (·))z(·)](t) = Lx (t, x0 (t), x˙ 0 (t))z(t) + Ly (t, x0 (t), x˙ 0 (t))z(t). ˙ Ví dụ 1.2.11 (Đạo hàm Fréchet của tích phân hàm Lagrange) Với giả thiết như trong Ví dụ 1.2.10, ta xét phiếm hàm Z t1 F(x(·)) = L(t, x(t), x(t))dt. ˙ t0 Có thể tách F thành F = F2 ◦ F1 , trong đó [F1 (x(·))](t) = L(t, x(t), x(t)), ˙ t0 ≤ t ≤ t1 và Z t1 F2 (α(·)) = α(t)dt. t0 F2 là một ánh xạ tuyến tính, nên sử dụng kết quả của Ví dụ 1.2.3 và 1.2.10 cùng với Định lí 1.2.9 ta thu được Z t1 0 F (x(·))z(·) = [Lx (t, x(t), x(t))z(t) ˙ + Ly (t, x(t), x(t)) ˙ z(t)]dt. ˙ (1.5) t0
13 Chương 2 Điều kiện cần cực trị cho bài toán tối ưu trong không gian vô hạn chiều Chương này trình bày điều kiện cần cực trị cho bài toán tối ưu trong không gian hữu hạn chiều, như là những kiến thức chuẩn bị và là cầu nối để hiểu bài toán tối ưu trong không gian vô hạn chiều trong Chương 3. Khoảng năm 1629, P. de Fermat đã đưa ra phương pháp tìm điểm cực đại và cực tiểu của một số hàm đơn giản. Theo ngôn ngữ toán học ngày nay, có thể phát biểu điều kiện này như sau: Nếu một đa thức có các điểm cực trị thì đạo hàm của nó tại đó phải bằng 0. Đây là một trong những phát hiện quan trọng nhất của toán học. Điều đáng nói là lúc đó khái niệm đạo hàm chưa ra đời. Mãi sau này, G. W. Leibniz mới đưa ra khái niệm đạo hàm và chứng minh f 0 (x∗ ) = 0 nếu x∗ là điểm cực trị địa phương. Ngày nay, những kết quả kiểu này được gọi là Định lí Fermat. Những điều kiện cần cực trị đầu tiên chỉ phát biểu cho bài toán trơn (cho các hàm mục tiêu khả vi) và không có ràng buộc. Năm 1744, L. Euler giải Bài toán đẳng chu, đưa ra cách tiếp cận đầu tiên cho bài toán tối ưu có ràng buộc. Để giải quyết một số vấn đề cơ học dưới dạng bài toán cực trị có ràng buộc đẳng thức, Lagrange đã xây dựng Qui tắc nhân tử Lagrange. Trong khuôn khổ Qui hoạch lồi, Kuhn và Tucker chứng minh điều
14 kiện cần cực trị (Định lí Kuhn-Tucker) cho bài toán có ràng buộc bất đẳng thức. 2.1 Định lí Fermat 2.1.1 Bài toán trơn không có ràng buộc Cho X là một không gian tô pô và f : X → R. Xét bài toán f (x) → inf . (2.1) Định lý 2.1.1 (Định lí Fermat) Giả thiết rằng x∗ là một nghiệm cực tiểu địa phương của (2.1) và tồn tại biến phân bậc nhất δf (x∗ , h). Khi đó δf (x∗ , h) = 0 ∀h ∈ X. Nếu X là một không gian Banach và f khả vi Fréchet tại x∗ thì f 0 (x∗ ) = 0. Chứng minh:(xem [1], trang 31) Ta có δf (x∗ , h) ≥ 0 và δf (x∗ , h) = −δf (x∗ , −h) ∀h ∈ X. Điều này kéo theo δf (x∗ , h) = 0 ∀h ∈ X. Nếu X là một không gian Banach và f khả vi Fréchet tại x∗ thì theo Mệnh đề 1.2.4 ta có f 0 (x∗ )h = fF0 (x∗ )h = fG0 (x∗ )h = δf (x∗ )h = 0 ∀h ∈ X. Ví dụ 2.1.2 (Fermat, Huygens, l’Hospital) Cho hai môi trường đồng chất, nằm hai phía của một mặt phẳng, và hai điểm a, b nằm trong lòng hai môi trường đó. Tìm đường đi của ánh sáng từ a tới b.
15 Không làm mất tính tổng quát, cho a = (a1 , 0, 0), b = (b1 , b2 , 0), a1 > 0 > b1 , b2 ≥ 0 và mặt phẳng ngăn cách là {x = (x1 , x2 , x3 ) ∈ R3 |x1 = 0}. Theo Nguyên lí Fermat, ánh sáng truyền theo đường mà thời gian đi là ngắn nhất. Vì trong môi trường đồng chất, vận tốc ánh sáng không thay đổi, nên nó phải truyền theo đường thẳng. Như vậy, chỉ còn việc xác định điểm z = (0, z2 , z3 ), nơi mà ánh sáng truyền từ môi trường này sang môi trường kia. Gọi v1 và v2 là vận tốc ánh sáng trong hai môi trường ấy, thì thời gian truyền trong môi trường là |z − a|/v1 và |z − b|/v2 . Do đó, ta phải giải bài toán: |z − a| |z − b| + → inf . v1 v2 Dễ nhận thấy nghiệm tối ưu tồn tại. Theo Định lí Fermat, z2 z2 − b2 z3 z3 + = 0, + = 0. v1 |z − a| v2 |z − b| v1 |z − a| v2 |z − b| Từ phương trình thứ hai suy ra z3 = 0 và z2 được xác định duy nhất từ phương trình đầu. Gọi α1 và α2 là góc giữa pháp tuyến và tia sáng. Khi đó z2 z2 − b2 sin α1 = . sin α2 = − . |z − a| |z − b| Cho nên sin α1 v1 = . sin α2 v2 Đây chính là một kết luận quen biết của quang học. Ví dụ 2.1.3 Xét bài toán Fermat về tìm điểm có tổng khoảng cách ngắn nhất tới ba điểm đã cho (xem [1], trang 13). Cho ba điểm y1 , y2 và y3 thuộc R2 . Tìm điểm thuộc R2 có tổng bình phương khoảng cách (Euclid) từ nó tới ba điểm kia là nhỏ nhất. Tức là f (x) = |x − y1 |2 + |x − y2 |2 + |x − y3 |2 → inf; x ∈ R2 . (2.2) Nếu x∗ là điểm tối ưu của bài toán (2.2) thì theo Định lí Fermat ta
16 có f 0 (x∗ ) = 2(3x∗ − y1 − y2 − y3 ) = 0. Bài toán (2.2) có nghiệm tối ưu (xem [1], trang 13), nên 1 x∗ = (y1 + y2 + y3 ) 3 chính là điểm cần tìm. Sử dụng kiến thức về hàm một biến và định nghĩa của biến phân bậc cao, có thể chứng minh dễ dàng điều kiện cần bậc cao sau đây. Định lý 2.1.4 Giả thiết rằng x∗ là một nghiệm cực tiểu địa phương của 2.1 và tồn tại biến phân bậc n > 1. Khi đó tồn tại một số tự nhiên l sao cho 2l ≤ n và δf (x∗ , h) = 0, . . . , δ 2l−1 f (x∗ , h) = 0, δ 2l f (x∗ , h) ≥ 0 với mọi h ∈ X. Nếu X là một không gian Banach và f khả vi Fréchet liên tục hai lần tại x∗ thì f ”(x∗ ) ≥ 0 1 . 2.1.2 Bài toán lồi không có ràng buộc Cho hàm lồi f : X → R. Xét bài toán f (x) → inf . (2.3) Định lý 2.1.5 (Định lí Fermat cho bài toán lồi) Hàm lồi f nhận giá trị cực tiểu (toàn cục) tại x∗ khi và chỉ khi 0 ∈ ∂f (x∗ ). (2.4)
17 Chứng minh: Từ (1.1) ta có f (x∗ ) ≤ f (x) ∀x ∈ X ⇐⇒ f (x) − f (x∗ ) − h0, x − x∗ i ≥ 0 ∀x ∈ X ⇐⇒ 0 ∈ ∂f (x∗ ). Ví dụ 2.1.6 (Bài toán Fermat-Torricelli) Cho ba điểm trên một mặt phẳng. Tìm điểm trên mặt phẳng đó sao cho tổng khoảng cách tới ba điểm kia là nhỏ nhất. Mô hình toán học là f (x) = |x − y1 | + |x − y2 | + |x − y3 | → inf; x ∈ R2 . (2.5) Ở đây hàm f biểu diễn tổng các khoảng cách tới ba điểm y1 , y2 và y3 cho trước. Có thể chỉ ra rằng bài toán cực trị (2.5) có nghiệm tối ưu (xem [1], trang 13). Hàm f lồi, nhưng không trơn. Theo Định lí 2.1.5 thì điều kiện cần và đủ để x∗ là nghiệm tối ưu là 0 ∈ ∂f (x∗ ). Áp dụng Định lí Moreau-Rockafellar (xem [1], trang 26) ta có 0 ∈ ∂x |x∗ − y1 | + ∂x |x∗ − y2 | + ∂x |x∗ − y3 |. (2.6) Ta đã biết rằng (xem [1], trang 25): Dưới vi phân của chuẩn trong không gian Euclid tại 0 là hình tròn đơn vị, còn tại điểm khác 0 là véc tơ đơn vị từ 0 hướng tới điểm ấy. Do đó, nếu x∗ 6= yi , i = 1, 2, 3, thì (2.6) kéo theo x ∗ − yi e1 + e2 + e3 = 0, trong đó ei = , i = 1, 2, 3. |x∗ − yi | Có nghĩa là: góc giữa ba đoạn [x∗ , y1 ], [x∗ , y2 ] và [x∗ , y3 ] đều là 120o . Điểm X∗ có tính chất này được gọi là điểm Torricelli. Nếu x∗ trùng với một trong ba điểm yi , chẳng hạn với y3 , thì (2.6) cho ta e1 + e2 + z = 0, trong đó |z| ≤ 1.
18 Có nghĩa là: góc giữa [y3 , y1 ], [y3 , y2 ] không nhỏ hơn 120o . Như vậy, nghiệm của (2.5) là: Nếu một trong ba góc của tam giác tạo bởi ba điểm đã cho không nhỏ hơn 120o thì điểm cần tìm chính là đỉnh đó; trong trường hợp còn lại, nghiệm tối ưu là điểm Torricelli. Bài toán lồi có ràng buộc bao hàm thức Xét bài toán f0 (x) → inf; x ∈ A. (2.7) Định lý 2.1.7 Cho X là một không gian tôpô tuyến tính lồi địa phương, f0 : X → R là một hàm lồi trên X và liên tục tại x∗ , và A ⊂ X là một tập lồi. Khi đó, x∗ là nghiệm cực tiểu (toàn cục) của bài toán (2.7) nếu và chỉ nếu 0 ∈ ∂f0 (x∗ ) + ∂(δ(x∗ | A)). (2.8) Điều này tương đương với ∃y ∗ ∈ ∂f0 (x∗ ) : −y ∗ ∈ N (x∗ | A). (2.9) Chứng minh: Áp dụng Định lí Moreau-Rockafellar (xem [1], trang 26) ta có: ∂(f0 (x∗ ) + δ(x∗ | A)) = ∂f0 (x∗ ) + ∂(δ(x∗ | A)). Thêm vào đó, (1.2) chỉ ra rằng ∂(δ(x∗ | A)) = N (x∗ | A). Vì hàm f (x) = f0 (x) + δ(x | A) lồi và có cùng nghiệm cực tiểu như f0 nên điều phải chứng minh suy ra từ Định lí 2.1.5. Hệ quả 2.1.8 Cho y ∗ ∈ X ∗ và A ⊂ X lồi. Điều kiện cần và đủ để x∗ là nghiệm cực tiểu (toàn cục) của bài toán hy ∗ , xi → inf; x∈A là −y ∗ ∈ N (x∗ | A).
19 2.2 Qui tắc nhân tử Lagrange Bài toán trơn với ràng buộc đẳng thức Ta xét một bài toán tối ưu đơn giản sau đây: f0 (x) := x21 + 4x22 → min, (2.10) trong đó x := (x1 , x2 )T ∈ R2 . Để xác định nghiệm cực tiểu của bài toán tối ưu lồi này, ta áp dụng Định lí Fermat: f00 (x) = (2x1 , 8x2 )T = (0, 0)T . (2.11) Dễ thấy rằng điều kiện cần cực trị này cho một nghiệm duy nhất x∗ = (x1∗ , x2∗ )T = (0, 0)T , đó cũng chính là điểm cực tiểu toàn cục của f0 (·). Nếu thêm ràng buộc vào phương trình (2.10), ví dụ: f1 (x) := −x1 − x2 + 5 = 0, (2.12) thì không có điểm x ∈ R2 nào thỏa mãn cả ràng buộc này cùng với (2.11), nghĩa là (2.11) không còn là điều kiện cần cực trị nữa. Vì hai điểm này tiếp xúc nên hai véc tơ f00 (∗) và f10 (∗) phải song song với nhau: f0 (x) = x21 + 4x22 → inf với x = (0, 0) nên f0 (0, 0) ≤ f0 (x) với mọi x ∈ R2 . Từ ràng buộc (2.12) ta có: x2 = −x1 + 5 thay vào (2.10) ta được f0 (x) = x21 + 4[−x1 + 5]2 = x21 + 4x21 − 40x1 + 100 = 5x21 − 40x1 + 100 = 5[x21 − 8x1 + 20] = 5(x1 − 4)2 ≥ 20 có nghiệm x1 = 4, x2 = 1. Vì f0 (0, 0) = 0, f0 (x) > 0 với mọi x thỏa mãn fx (x) = 0 và vì giá trị của f0 (x) tăng dần khi tiến từ x = 0 đến đường thẳng f1 (x) = 0, f0 (·) sẽ đạt được giá trị cực tiểu tại điểm tiếp xúc x∗ giữa đường thẳng f1 (x) = 0 và một đường mức của f0 (·). Vì hai đường này tiếp xúc nên