1
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC SƯ PHẠM
PHẠM PHÚC LONG
VỀ NGUYÊN LÝ NHÂN TỬ LAGRANGE
Chuyên ngành: Giải tích
Mã số: 60 46 01
LUẬN VĂN THẠC SỸ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS. TS. TRƯƠNG XUÂN ĐỨC HÀ
Thái Nguyên- Năm 2010
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2
MỤC LỤC
Mở đầu: ................................................................................................... 2
Chương I. NGUYÊN LÝ NHÂN TỬ LAGRANGE CHO BÀI TOÁN TỐI ƯU TRƠN.
1.1 Một số kiến thức chuẩn bị .................................................................5 1.1.1 Khả vi Gateaux và khả vi Frechet .................................................5 1.1.2 Định lý Hahn-Banach, bổ đề về linh hóa tử ..................................9 1.1.3 Định lý Ljusternik, định lý hàm ẩn .............................................10
1.2 Điều kiện cần đủ cho bài toán tối ưu trơn ......................................12 1.2.1 Phát biểu bài toán ........................................................................12 1.2.2 Trường hợp hữu hạn chiều ..........................................................17 1.2.3 Trường hợp tổng quát .................................................................27
Chương II. NGUYÊN LÝ NHÂN TỬ LAGRANGE CHO BÀI TOÁN TỐI ƯU LỒI.
2.1 Một số kiến thức cơ bản của giải tích lồi ........................................31 2.1.1 Tập lồi .........................................................................................31 2.1.2 Hàm lồi .......................................................................................32 2.1.3 Tập Affine ...................................................................................34 2.1.3 Các định lý tách ...........................................................................35 2.1.4 Dưới vi phân của hàm lồi ............................................................36 2.1.6 Định lý cơ bản về dưới vi phân của tổng các hàm lồi ...................38
2.2 Điều kiện cần đủ cho bài toán tối ưu lồi .........................................43 2.2.1 Bài toán không có ràng buộc .......................................................44 2.2.2 Bài toán với ràng buộc đẳng thức ................................................44 2.2.3 Bài toán với ràng buộc bất đẳng thức ..........................................47
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
KẾT LUẬN ..............................................................................................55 TÀI LIỆU THAM KHẢO ......................................................................56
3
MỞ ĐẦU
Trong cuộc sống, ai cũng mong muốn công việc hàng ngày của mình được hoàn thành một cách tốt nhất. Ai cũng tự đặt ra hai câu hỏi chính: Làm thế nào để công việc hoàn thành tốt nhất, và khi tốt nhất thì được cái gì? Như vậy, chẳng qua mọi người cũng phải giải các bài toán tối ưu của mình theo một nghĩa nào đó. Một vấn đề quan trọng nhất đặt ra cho mỗi bài toán tối ưu là: Với điều kiện nào, bài toán có nghiệm, và nếu có nghiệm điều gì sẽ xảy ra. Tất nhiên, điều kiện càng đơn giản thì việc tìm nghiệm càng dễ. Biết được điều gì xảy ra nếu có lời giải, thì việc tìm ra lời giải càng dễ dàng hơn.
Ta biết trong bài toán tối ưu có hai đối tượng quan trọng: Tập chấp nhận được (hay tập ràng buộc) và Hàm mục tiêu xác định trên tập đó. Vậy thì khi xét đến điều kiện để tồn tại nghiệm tối ưu, ta phải quan tâm tới các điều kiện, tính chất của hai đối tượng ấy. Để nghiên cứu sự tồn tại nghiệm và tìm ra phương pháp giải nghiệm, người ta thường phân loại các bài toán theo cấu trúc của tập chấp nhận được và tính chất hàm mục tiêu của bài toán. Trong luận văn này, tác giả đề cập tới hai loại bài toán chính sau:
1. Bài toán tối ưu trơn với ràng buộc đẳng thức.
Cụ thể: Cho X, Y là các không gian Banach, hàm f xác định trên X, ánh xạ F : X Y . Bài toán: −→
in f
f (x) −→ F(x) = 0. (cid:26)
được gọi là bài toán tối ưu trơn với ràng buộc đẳng thức nếu hàm f và ánh xạ F thỏa mãn tính trơn.
2. Bài toán tối ưu lồi.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
¥ ⊂ và h j : X R = R ∪ {± −→ } Cụ thể: X là một Cho X là không gian tôpô tuyến tính lồi địa phương, A tập lồi đóng không rỗng. f , gi : X R −→ là những hàm affine. Bài toán quy hoạch lồi tổng quát cho dưới dạng
4
sau:
≤ min f(x) x A ∈ gi(x) 0 (i = 1, 2, . . . , m) h j(x) = 0 ( j = 1, 2, . . . , p).
Trong giải tích cổ điển, ta đã biết định lý Weierstrass nổi tiếng: “ Một hàm số liên tục trên tập compact luôn đạt cực đại và cực tiểu”. Những mở rộng hay biến dạng khác nhau của định lý này chỉ ra nhiều điều kiện đủ cho sự tồn tại nghiệm của bài toán tối ưu. Khi hàm số khả vi, một điểm là nghiệm tối ưu của bài toán không có ràng buộc, thì đạo hàm của nó tại điểm này phải bằng không. Đó là điều kiện cần tối ưu. Khẳng định này vẫn còn đúng cho hàm lồi với đạo hàm được thay bằng dưới vi phân. Với ý tưởng như vậy, khi nghiên cứu một bài toán tối ưu có ràng buộc, người ta tìm cách đưa nó về một bài toán không có ràng buộc hoặc chỉ có những ràng buộc tương đối đơn giản. Có thể thấy điều đó trong các công trình nghiên cứu của Lagrange về tính biến phân từ cuối thế kỷ XVIII. Đó là:
Xây dựng hàm Lagrange cho bài toán tối ưu. •
Tìm các điều kiện để hàm Lagrange đạt cực trị. •
Chính việc áp dụng rộng rãi nguyên lý nhân tử Lagrange trong các bài toán tối ưu đã khiến tác giả chọn đề tài nghiên cứu này.
4], và có tham khảo thêm các tài liệu [5 − −
Luận văn trình bày hệ thống và chi tiết một số điều kiện tối ưu cho các bài toán tối ưu trơn, và bài toán tối ưu lồi được trình bày từ các tài liệu chuyên đề chính [1 7]. Các điều kiện này được thể hiện thông qua các nhân tử Lagrange. Luận văn bao gồm: Phần mở đầu, hai chương và phần tài liệu tham khảo.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Chương I: Dành để trình bày các kết quả về điều kiện cần đủ của bài toán tối ưu trơn. Đầu tiên chúng ta nhắc lại một số kiến thức về khả vi Gateaux, khả vi Frechet, định lý Ljusternik, định lý hàm ẩn, sau đó trình bày điều kiện cần cấp một và điều kiện cần đủ cấp hai thông qua sự tồn tại của vi phân cấp hai và nhân tử Lagrange.
5
Chương II: Dành để trình bày các kết quả về điều kiện cần đủ của bài toán tối ưu lồi. Tác giả trình bày một số kiến thức cơ bản về giải tích lồi, định lý Moreau-Rockafellar, và định lý cổ điển Kuhn-Tucker về điều kiện cần và đủ của bài toán tối ưu lồi thông qua sự tồn tại của nhân tử Lagrange tương ứng với dưới vi phân tại điểm đó.
Nhân dịp này, tác giả xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS Trương Xuân Đức Hà, người đã trực tiếp giúp đỡ và chỉ bảo tận tình tác giả trong suốt quá trình học tập, nghiên cứu và viết bản luận văn này. Tác giả cũng bày tỏ tình cảm của mình trước sự giúp đỡ, động viên của gia đình, bạn bè, và tập thể học viên cao học Toán K16-ĐHSPTN.
Trong quá trình viết luận văn cũng như trong việc xử lý văn bản chắc chắn không tránh khỏi những hạn chế và thiếu sót. Rất mong nhận được sự góp ý của thầy cô, các bạn đồng nghiệp để luận văn được hoàn thiện hơn.
Thái Nguyên, tháng 8, năm 2010.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Phạm Phúc Long
6
CHƯƠNG I: NGUYÊN LÝ NHÂN TỬ LAGRANGE CHO BÀI TOÁN TỐI ƯU TRƠN
Chương này dành để trình bày các kết quả về điều kiện cần đủ của bài toán tối ưu trơn thông qua sự tồn tại của các nhân tử Lagrange. Những kết quả này được tham khảo từ những tài liệu chuyên đề chính [1 4]. −
1.1. Một số kiến thức chuẩn bị.
Trong mục này, chúng ta nhắc lại một số khái niệm về khả vi Gateaux, khả vi Frechet, định lý Hahn-Banach, định lý Ljusternik và định lý hàm ẩn.
1.1.1. Khả vi Gateaux và khả vi Frechet.
Định Nghĩa 1.1.
Cho X, Y là các không gian tôpô tuyến tính, U là lân cận của x ∈ X, ánh Y . Ánh xạ F được gọi là khả vi Gateaux tại x nếu tồn tại toán −→ Y thỏa mãn: xạ F : U tử tuyến tính liên tục F 0(x) : X −→
F(x + th) tF 0(x)h = 0. X. − − F(x) t h ∀ ∈ lim 0 t →
Định Nghĩa 1.2.
Cho X, Y là các không gian Banach, U là lân cận của x ∈ X, ánh xạ Y . Ánh xạ F được gọi là khả vi Frechet tại x nếu tồn tại toán tử −→ Y thỏa mãn: F : U tuyến tính liên tục F 0(x) : X
−→ F(x + h) F 0(x)h = 0. −
lim 0 h → F(x) − h || ||
Định Nghĩa 1.3.
Cho U là tập con mở trong không gian X, ánh xạ F : X −→
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
−→ Y với X,Y là các không gian Banach. Nếu với mọi điểm của tập U, tồn tại đạo hàm F 0(x) là liên tục trong không gian L(X,Y ) trên U thì F 0(x) và ánh xạ x F gọi là khả vi liên tục trên U , hoặc ánh xạ thuộc lớp C1 trên U .
7
Định Nghĩa 1.4.
Ta nói rằng, ánh xạ F : X Y là chính quy tại điểm x nếu nó khả vi −→ Frechet tại điểm đó, và Im F 0(x) = Y .
Định Nghĩa 1.5.
x Cho hàm số f (x) xác định trên không gian tôpô tuyến tính X. Điểm X thỏa mãn f 0(x) = 0 được gọi là điểm dừng. ∈
¶ f ¶ xi
Định Nghĩa 1.6. W Cho W là miền mở, giới nội trong Rn. Hàm số f : W R với x −→ ∈ , (x), (i = 1, . . . , n), thì x = (x1, . . . , xn). Giả sử f có các đạo hàm riêng
¶ f ¶ x1
¶ f ¶ xn
gọi là Gradient của f tại x. Kí hiệu: vectơ (x), . . . , (x)
¶ f ¶ xn
¶ f ¶ x1
(cid:16) (cid:209) (x) . (x), . . . , (cid:17) f (x) = ¶ f ¶ xn ¶ f ¶ x1 (cid:17) gọi là Jacobian của f tại x. (x), . . . , (cid:16) (x) Ma trận J =
¶ f ¶ xi
(cid:17) (cid:16) Nếu
¶ 2 f ¶ xi¶ x j
(x) có các đạo hàm riêng thứ j với ( j = 1, . . . , n), đạo hàm riêng này được gọi là đạo hàm riêng cấp hai theo các biến i, j của f tại x, và được kí hiệu là i, j = 1, . . . , n. Ma trận (x),
¶ 2 f ¶ xi¶ x j
H = , i, j = 1, . . . , n. (x)
(cid:16) (cid:17) được gọi là Hessian của f tại x.
Ví Dụ 1.1. Tính khả vi của một số hàm và ánh xạ.
1) Trong R2 hàm f (x1, x2) được cho bởi công thức.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1 nếu x1 = x2 2 0 Trong các trường hợp còn lại. (cid:26) là khả vi Gateaux tại gốc tọa độ.
8
2) Ánh xạ affine. Một ánh xạ A : X Y với X,Y là các không gian tuyến tính được gọi −→ là affine nếu:
: X A(x) = l x + a. Y là ánh xạ tuyến tính. trong đó a Y và l −→ ∈
là ánh xạ tuyến tính liên tục,
Nếu X,Y là các không gian Banach, l thì ánh xạ A là khả vi Frechet tại mọi điểm và
A0(x) = l .
Đạo hàm cấp hai của A là:
A00(x) = 0.
(điều này được suy ra trực tiếp từ định nghĩa).
Nói riêng, đạo hàm Frechet của hàm affine
a(x) = x∗, x . i h
là
tại x. a0(x) = x∗ ∀
trên X 3) Hàm Bậc Hai. Cho X là không gian Banach, B(x1, x2) là hàm song tuyến tính liên tục X, và Q(x) = B(x, x) là một dạng toàn phương. Về bản chất: ×
Q(x + h) = B(x + h, x + h)
= B(x, x) + B(x, h) + B(h, x) + B(h, h)
= Q(x) + B(x, h) + B(h, x) + o( ), (khi h 0). h || || −→ Do đó hàm Q(x) là khả vi Frechet và:
Q0(x)h = B(x, h) + B(h, x).
Nói riêng, nếu X là không gian Hilbert thì mọi dạng bậc hai có thể biểu
diễn dưới dạng
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
với l Q(x) = L(X,Y ), l ∗ = l . 1 2h l x, x , i ∈
9
Và
Q0(x) = l x.
Trong không gian hilbert, tổng của một dạng bậc hai với một hàm affine
K(x) = + + a . 1 2h l x, x i x, a h i
gọi là hàm bậc hai. Khi đó
K0(x) = l x + a.
và
K00(x) = l .
các đạo hàm còn lại bằng không.
Đặc biệt, nếu hàm
e(x) = 1 2 = x 2 || || 1 2h x, x . i
thì
e0(x) = x.
e00(x) = I.
= 0. e000(x) = · · ·
4) Chuẩn trong không gian Hilbert.
là khả vi Frechet tại mọi điểm khác không và Hàm số f (x) = x || ||
. f 0(x) =
x x || ||
Tiếp theo chúng ta nhắc lại định lý Hahn-Banach, toán tử liên hợp, và
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
một bổ đề quan trọng đó là, bổ đề về linh hóa tử (annihilator).
10
1.1.2. Định lý Hahn-Banach, bổ đề về linh hóa tử.
Định Lý 1.1. (Hahn-Banach).
Cho X là không gian tôpô tuyến tính, A X là tập lồi mở, L ⊂ ⊂
X là một không gian con rời A. Khi đó, tồn tại một phiếm hàm tuyến tính liên tục x∗ trên X thỏa mãn
A. > 0 với • h ∈
L. = 0 với x∗, x i x∗, x i • h x ∀ x ∀ ∈
L} được gọi là = 0, x∗ ∈ { X ∗ | h x∗, x i x ∀ ∈ Chúng ta chú ý rằng, tập L⊥ = linh hóa tử của L.
Hệ Quả 1.1.
Cho L là một không gian con đóng của một không gian tôpô tuyến tính lồi địa phương, thì linh hóa tử của L chứa ít nhất một phần tử khác không.
Định Nghĩa 1.7. (Toán tử liên hợp)
Y là −→ X ∗ được
Cho X,Y là các không gian tuyến tính lồi địa phương, l : X toán tử tuyến tính liên tục. Khi đó, toán tử liên hợp l ∗ : Y ∗ −→ xác định bởi
với = X. y∗ Y ∗, x l ∗y∗, x i h y∗, l x h i ∀ ∈ ∈
Bổ Đề 1.1. (Bổ đề về linh hóa tử)
: X Y là toán tử tuyến tính Cho X,Y là các không gian Banach, l −→ liên tục thỏa mãn Im l = Y . Khi đó
(Ker l )⊥ = Im l ∗.
Định Lý 1.2.
Cho ánh xạ F : X là khả vi Frechet f1(x), . . . , fn(x) Rn và F(x) = −→ tại x0. Ánh xạ F là chính quy tại x0 nếu và chỉ nếu các vectơ (cid:0) (cid:1)
f 01(x0), . . . , f 0n(x0)
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
là độc lập tuyến tính.
11
Để chứng minh điều kiện tối ưu của bài toán trơn với ràng buộc đẳng
thức, ta cần tới các định lý quan trọng sau.
1.1.3. Định lý Ljusternik, Định lý hàm ẩn.
Giả sử X là không gian Banach, tập M X. ⊂
Định Nghĩa 1.8. (Vectơ tiếp xúc)
X gọi là tiếp xúc với tập M tại điểm x0, nếu tồn tại số ∈ Một vectơ x e > 0 và ánh xạ
X −→ r : [0, e ] t r(t) 7−→ thỏa mãn
M, [0, e ] x0 + tx + r(t) ∈ t ∀ ∈ trong đó
r(t) 0 t khi 0. || || t −→ −→
Nhận Xét 1.1.
Tập tất cả các vectơ tiếp xúc với tập M tại x0 là một hình nón đóng, được gọi là nón tiếp tuyến của M tại x0 và được kí hiệu là TM(x0). Trong nhiều trường hợp, TM(x0) là một không gian con và được gọi là không gian tiếp xúc với tập M tại x0.
Do 0 = /0 TM(x0) nên TM(x0) ∈ 6
Định Lý 1.3. (Định Lý Ljusternik)
Giả sử X,Y là các không gian Banach, U là một lân cận của điểm x0 ∈ X. Y . Giả thiết rằng, F khả vi liên tục theo nghĩa Frechet −→ Ánh xạ F : U tại x0 và
Im F 0(x0) = Y
Đặt
x M = . U : F(x) = F(x0) } { ∈
Khi đó, không gian tiếp xúc với tập M tại x0 trùng với Ker F 0(x0), tức là
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
TM(x0) = Ker F 0(x0).
12 x(x )
−→ từ U 0 vào X sao cho: với mọi x
U của x0, số K > 0 và ánh xạ x Đồng thời, tồn tại lân cận U 0 ⊂ U 0 ∈ x + x(x ) = F(x0),
K . F x(x ) (cid:0) || ≤ || F(x ) (cid:1) || F(x0) || −
Nhận Xét 1.2.
Thực ra, không cần các điều kiện của định lý (1.3) mà chỉ dựa vào định
nghĩa của vectơ tiếp xúc với tập M tại x0, ta có thể chứng minh được:
TM(x0) Ker F 0(x0). ⊂
Ý nghĩa thực tế của định lý Ljusternik là chuyển công việc tìm không gian tiếp xúc của một tập (điều mà không dễ dàng tìm được theo định nghĩa) về việc tìm hạch của một toán tử.
Giả sử ta có hệ gồm m phương trình với n biến số: hi(x) = 0,
n. Nếu cố định (n ≤
i = 1, . . . , m và m m) ẩn, thì hệ phương trình được giải − với m ẩn còn lại. Do đó, nếu ta chọn m biến đầu tiên là x1, x2, . . . , xm và giả sử rằng các biến này có thể được biểu diễn thông qua các biến còn lại dưới dạng
i = 1, . . . , m. xi = f i(xm+1, xm+2, . . . , xn),
các hàm f i (nếu tồn tại) được gọi là các hàm ẩn.
Định lý 1.4. (Định lý hàm ẩn).
1, . . . , x0
n) là một điểm trong Rn thỏa mãn: C p,
Cho x0 = (x0
i = 1, . . . , m, p 1 trong lân cận của x0. ∈ ≥
i = 1, . . . , m. 1. Các hàm số hi 2. hi(x0) = 0,
3. Ma trận Jacobian cấp m ×
· · · J =
¶ h1(x0) ¶ xm ... ¶ hm(x0) ¶ xm
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
m ¶ h1(x0) ¶ x1 ... ¶ hm(x0) ¶ x1 · · · là không suy biến.
m+1, . . . , x0 n)
13 m thỏa mãn: với ˆx = i = 1, . . . , m
Rn − ∈
Khi đó, có lân cận của ˆx0 = (x0 (xm+1, . . . , xn) trong lân cận này thì tồn tại các hàm f i( ˆx), sao cho
1. f i
2. x0 i = 1, . . . , m. C p. ∈ i = f i( ˆx0),
i = 1, . . . , m. 3. hi(f i( ˆx), f 2( ˆx), . . . , f m( ˆx), ˆx) = 0,
Định lý hàm ẩn sẽ giúp ta chứng minh cách xác định không gian tiếp xúc của mặt ràng buộc sẽ được trình bày ở phần sau.
1.2. Điều kiện cần đủ cho bài toán tối ưu trơn .
Trong mục này chúng ta trình bày điều kiện cần cấp một và điều kiện cần đủ cấp hai thông qua sự tồn tại của vi phân cấp hai và nhân tử La- grange. Đây chính là trường hợp ta hay gặp trong thực tiễn.
1.2.1. Phát biểu bài toán.
Cho X, Y là các không gian Banach, hàm f xác định trên X, ánh xạ
F : X Y . Xét bài toán: −→
in f (P1) f (x) −→ F(x) = 0 (1.1) (1.2) (cid:26)
bài toán (P1) được gọi là bài toán tối ưu trơn với ràng buộc đẳng thức nếu hàm f và ánh xạ F thỏa mãn tính trơn. Trong đó:
F(x) = 0 gọi là ràng buộc đẳng thức. •
x gọi là tập chấp nhận được. W = X : F(x) = 0 { • ∈
} Hàm Lagrange của bài toán (P1) được thiết lập như sau
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Y ∗. L(x, l 0, y∗) = l 0 f (x) + với l 0 R, y∗ y∗, F(x) i h ∈ ∈
14
trong đó l 0 và y∗ gọi là các nhân tử Lagrange.
Để có một cái nhìn trực quan, chúng ta xét bài toán trong trường hợp cụ
thể sau
(P2) min f (x, y) h(x, y) = 0 x, y R. (cid:26) ∈ trong đó các hàm số f , h khả vi liên tục tới cấp 2, và f là chính quy.
Chú ý rằng, nếu f và h là các hàm tuyến tính, thì bài toán trên chính là bài toán quy hoạch tuyến tính. Khi đó, ta có thể giải quyết bài toán bằng các thuật toán đơn hình. Vì vậy, chúng ta chỉ xét trường hợp các hàm này là phi tuyến.
Hình 1.
Ràng buộc h(x, y) = 0 xác định một đường cong như hình 1
Lấy vi phân của phương trình h(x, y) = 0 với ẩn x, ta có
(1.3) + . = 0. ¶ h ¶ x ¶ h ¶ y dy dx
Tiếp tuyến của đường cong là
T (x, y) = 1, . dy dx (cid:16) (cid:17) và gradient của đường cong là
, . (cid:209) h = ¶ h ¶ y (cid:17) (cid:16)
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
¶ h ¶ x Vì vậy, phương trình (1.3) có nghĩa là: T.(cid:209) h = 0. Nói cách khác, tiếp tuyến của đường cong phải vuông góc với gradient tại mọi điểm.
15
Giả sử ta đang ở một điểm trên đường cong, để điểm này nằm trên đường cong thì bất kì chuyển động nào cũng phải theo tiếp tuyến T . Để tăng hoặc giảm f (x, y) thì chuyển động dọc theo đường cong phải có một thành phần dọc theo gradient của f . Tức là
Hình 2.
(cid:209) f . T = 0. 6
Tại điểm cực trị, chuyển động lúc này là đặc biệt. Khi đó, T trực giao
với (cid:209) f , nói cách khác (cid:209) f . T = 0.
f và (cid:209) h phải song song với nhau. Do đó, tồn tại l f và (cid:209) h tại điểm cực trị, điều đó có R sao ∈ Như vậy, T trực giao với cả gradient (cid:209) nghĩa rằng (cid:209) cho
(cid:209) (cid:209) h = 0. (1.4) f + l
(cid:209)
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Hình (3) minh họa cho điều kiện (1.4) bằng cách chồng lên đường cong h(x, y) = 0 họ các đường mức của hàm f (x, y), đó là tập các đường cong f (x, y) = c, trong đó c là số thực bất kì trong khoảng biến thiên của f . Trong hình (3) ta có c5 > c4 > c3 > c∗ > c1. Nếu di chuyển dọc theo đường cong sẽ cho kết quả tăng hoặc giảm giá trị của f . Hãy tưởng tượng, một điểm di chuyển trên đường cong h(x, y) từ (x1, y1) đến (x2, y2). Ban đầu, chuyển động có một thành phần dọc theo hướng của f dẫn đến giảm giá trị của f . Giá trị này nhỏ dần, khi di chuyển tới − (x∗, y∗), chuyển động là trực giao với gradient. Từ điểm này, chuyển động bắt đầu có một thành phần dọc theo hướng gradient (cid:209) f , như vậy giá trị của f tăng lên. Do đó, tại (x∗, y∗) hàm f đạt cực tiểu địa phương. Chuyển động này theo hướng tiếp tuyến của đường cong h(x, y) = 0, đó là trực giao
16
Hình 3.
với gradient (cid:209) h. Như vậy, tại (x∗, y∗) thì hai gradient (cid:209) f và (cid:209) h phải cộng tuyến với nhau. Đây chính là những gì mà phương trình (1.4) đã thể hiện.
Cho c∗ là đường mức mà tại đó hàm f đạt cực tiểu địa phương tại (x∗, y∗), rõ ràng hai đường cong f (x, y) = c∗ và h(x, y) = 0 tiếp xúc nhau tại (x∗, y∗). Giả sử ta tìm được tập S các điểm thỏa mãn hệ phương trình
(cid:209) (cid:209) h = 0. (1.5) h(x, y) = 0 f + l (cid:26)
Khi đó, tập S chứa các điểm cực trị của hàm f đối với ràng buộc h(x, y) = 0. Hệ phương trình trên là hệ phi tuyến với các biến số x, y, l và ta có thể giải quyết bằng nhiều phương pháp.
Hàm Lagrange của bài toán (P2) có dạng
T
¶
f
¶
f
L(x, y, l ) = f (x, y) + l h(x, y).
¶ h ¶ x ¶ h ¶ y
¶ x + l ¶ y + l h(x, y)
(cid:209) h, h). = ((cid:209) f + l
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
(cid:209) L = Suy ra (cid:209) L = 0 do hệ phương trình phi tuyến (1.5).
17 Giá trị l gọi là nhân tử Lagrange. Phương pháp xây dựng hàm Lagrange và thiết lập để các gradient của nó bằng không, gọi là phương pháp nhân tử Lagrange.
Ví Dụ 1.2.
Tìm các giá trị cực trị của hàm f (x, y) = xy với ràng buộc
+ 1 = 0. h(x, y) = x2 8 y2 2 −
Giải
Đầu tiên, ta xây dựng hàm Lagrange và tìm gradient của nó.
L(x, y, l ) = xy + l ( + 1). x2 8 y2 2 −
l x y + 4 x + l y 8 + y2 x2
2 −
= 0. 1
(cid:209) L(x, y, l ) =
= 0. (1.6) y + Từ đó dẫn đến ba phương trình l x 4
(1.7)
x + l y = 0. x2 + 4y2 = 8. (1.8)
Kết hợp (1.6) và (1.7) ta có
suy ra l = 2. l 2 = 4 ±
Do đó x = 2y. Thế phương trình này vào (1.8), ta được ±
1 suy ra y = x = 2. ± ±
Vì vậy, có bốn điểm cực trị của hàm f thỏa mãn ràng buộc h là
(2, 1); 2, 1); (2, 1); 2, 1). ( − − ( − −
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Giá trị cực đại đạt được tại hai điểm đầu tiên, trong khi giá trị cực tiểu đạt được ở hai điểm cuối.
18
Hình 4.
Về mặt đồ thị, ràng buộc h là hình elip. Đường mức của hàm f là hy-
tăng khi đường cong di chuyển ra xa gốc tọa độ. perbolas xy = c, với c | |
1.2.2. Trường hợp hữu hạn chiều.
Bây giờ, ta mở rộng bài toán (P2) tới trường hợp với nhiều ràng buộc.
n. ≤ Cho h = (h1, . . . , hm)T là một hàm số từ Rn vào Rm, trong đó m Xét bài toán tối ưu
(P3) min f (x) h(x) = 0.
(cid:26) Mỗi ràng buộc h j(x) = 0, ( j = 1, . . . , m) gọi là một siêu diện trong không gian Rn. Nếu h j(x) C1 và chính quy thì siêu diện gọi là trơn. Chúng ta có ∈ một số khái niệm sau:
Giao của tất cả các siêu diện được gọi là mặt ràng buộc, kí hiệu là S. •
t S, với a b. Một đường cong trên S là tập các điểm x(t) • ∈ ≤
Đường cong gọi là khả vi nếu tồn tại dx •
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
≤ dt , kí hiệu x0 := dx dt . t b. Đường cong gọi là đi qua điểm x nếu x = x(t) với a • ≤ ≤
19
•
Không gian tiếp xúc tại điểm x của siêu diện S là không gian con của Rn, tạo bởi tập các tiếp tuyến dx dt (t) của tất cả các đường cong x(t) trên S thỏa mãn x = x(t).
Từ các khái niệm trên, ta có thể phát biểu khái niệm điểm chính quy như sau:
“Một điểm x thỏa mãn h(x) = 0, gọi là điểm chính quy nếu các vectơ
gradient (cid:209) h1(x), . . . , (cid:209) hm(x) là độc lập tuyến tính”.
Định lý sau đây cho phép ta xác định không gian tiếp xúc của mặt ràng
buộc.
Định Lý 1.5.
Tại một điểm chính quy x của mặt S được xác định bởi h(x) = 0, thì
không gian tiếp xúc tại x là
M = (cid:209) h(x)y = 0 . y | { }
trong đó ma trận
. (cid:209) h1 ... (cid:209) hm
(cid:209) h = Các hàng của ma trận (cid:209) h(x) là các vectơ gradient (cid:209) h j(x), ( j = 1, . . . , m).
Chứng minh
Cho T là không gian tiếp xúc tại x. Rõ ràng T ⊂
6 M với x là điểm chính quy. Nếu một đường cong bất kì x(t) đi qua điểm x tại t = t, và có đạo hàm x0(t) thỏa mãn (cid:209) h(x)x0(t) Để chứng minh M = 0 thì đường cong đó không nằm trên S. T , ta phải chứng tỏ rằng, nếu y ⊂ ∈
M thì có một đường cong trên S qua x với đạo hàm tương ứng là y. Để xác định đường cong như vậy, ta xét hệ phương trình
(1.9) h(x + ty + (cid:209) h(x)T u(t)) = 0.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Rm là ẩn. Đây là một hệ phi tuyến với m ∈ trong đó t cố định, và u(t) phương trình và m ẩn, được biểu diễn theo tham số t.
20
m Tại t = 0 có nghiệm u(0) = 0. Ma trận Jacobian của hệ đối với u tại t = 0 là ma trận cấp m × (cid:209) h(x)(cid:209) h(x)T .
a − không suy biến. Do đó, theo định lý hàm ẩn thì có nghiệm u(t) khả vi liên tục trên t ≤ ≤ a. Đường cong x(t) = x + ty + (cid:209) h(x)T u(t) theo cách xác định như vậy là
một đường cong trên S. Lấy vi phân của (1.9) đối với t tại t = 0, ta có
t=0
h(x(t)) 0 = = (cid:209) h(x)y + (cid:209) h(x)(cid:209) h(x)T u0(0). d dt
(cid:12) (cid:12) (cid:12) Theo định nghĩa của y, ta có (cid:209) h(x)y = 0. Do đó, khi (cid:209) h(x)(cid:209) h(x)T là không suy biến, ta suy ra u0(0) = 0. Như vậy
(cid:3) x0(0) = y + (cid:209) h(x)T u0(0) = y.
Định lý sau nêu lên mối quan hệ giữa gradient của hàm mục tiêu với vectơ nằm trên không gian tiếp xúc.
Định Lý 1.6.
Cho x là cực trị của hàm f , và là điểm chính quy của ràng buộc h(x) = 0.
Khi đó, với Rn thỏa mãn (cid:209) h(x)y = 0, ta có y ∀ ∈ (cid:209) f (x)y = 0.
Chứng minh.
Giả sử mặt ràng buộc h(x) = 0 xác định một siêu diện S. x(t) là một đường cong bất kì trên S, và đi qua điểm x. Gọi y là một vectơ bất kì trên không gian tiếp xúc tại x của S. Khi đó: x(0) = x, x0(0) = y, và h(x(t)) = 0 với a, a] , a > 0. [ − ∈ t ∀ Vì x là điểm chính quy nên không gian tiếp xúc là
. M = } (cid:209) h(x)y = 0 y | {
Do đó, nếu x là cực trị địa phương thì
t=0
(cid:3) (cid:209) hay f (x(t)) = 0 f (x)y = 0. d dt
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
(cid:12) (cid:12) (cid:12)
21
Định Lý 1.7. (Điều Kiện Cần Cấp Một)
Cho x là cực trị địa phương của bài toán (P3). Giả sử rằng x là điểm chính Rm sao ∈ quy của các ràng buộc h j(x) = 0, j = 1, . . . , m. Khi đó, tồn tại l cho (cid:209) f (x) + l T (cid:209) h(x) = 0.
Chứng minh.
Từ định lý (1.6) ta suy ra rằng, giá trị của bài toán
max (cid:209) f (x)y (cid:209) h(x)y = 0. (cid:26)
là bằng không. Theo định lý đối ngẫu của quy hoạch tuyến tính thì bài toán đối ngẫu là giải được. Từ đó, tồn tại l
(cid:209) (cid:3) Rm sao cho ∈ f (x) + l T (cid:209) h(x) = 0.
Nhận Xét 1.3.
Điều kiện cần cấp một cùng với ràng buộc h(x) = 0, cho ta hệ gồm . Do đó, ta có thể xác định được
(m + n) phương trình với (m + n) ẩn x và l nghiệm duy nhất của hệ phương trình.
Ví Dụ 1.3.
Chúng ta xây dựng một khối hộp có thể tích lớn nhất từ bìa cứng, khi
cho trước một diện tích bìa cố định.
Giải
Giả sử kích thước của khối hộp cần dựng là x, y, z. Bài toán có thể biểu
thị như sau
(P4) (1.10) max xyz xy + yz + zx = c 2.
(cid:26) trong đó c > 0 là diện tích cho trước của tấm bìa.
Hàm Lagrange của bài toán
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
). L(x, y, z, l ) = xyz + l (xy + yz + zx c 2 −
22
Từ điều kiện cần cấp một ta thấy rằng
(1.11) yz+ l (y+ z) = 0.
(1.12)
(1.13) xz+ l (x+ z) = 0. xy+ l (x+ y) = 0.
Do đó
(xy + yz + xz) + 2l (x + y + z) = 0.
Từ ràng buộc (1.10) ta có
+ 2l (x + y + z) = 0. c 2
Suy ra l = 0. 6
Chú ý rằng x, y, z không thể nhận giá trị bằng không (vì nếu một trong ba số bằng không, thì do (1.11), (1.12), (1.13) ta được những số khác cũng bằng không).
Để giải hệ gồm ba phương trình (1.11), (1.12), (1.13), ta nhân (1.11)
với x và (1.12) với y, sau đó trừ hai phương trình cho nhau ta được
l (x y)z = 0. −
Tương tự cho (1.12) và (1.13) ta được
l (y z)x = 0. −
Do các biến không thể bằng không nên
và . x = y = z = 1 l = − 2 c 6 r
6 và l = − 1 c 2 .
Như vậy, hàm Lagrange có điểm dừng tại x = y = z =
p
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Tuy nhiên, kết quả ta tìm được ở trong ví dụ (1.3) chỉ là điều kiện cần cấp một, có nghĩa rằng, ta chưa biết liệu tại điểm này khối hộp đã cho đạt thể tích lớn nhất hay nhỏ nhất. Muốn thế, ta cần xét tới điều kiện cấp hai sau.
23
Định Lý 1.8. (Điều kiện cần cấp hai).
Giả sử rằng x là cực tiểu địa phương của hàm f thỏa mãn h(x) = 0, và Rm ∈ x là một điểm chính quy của các ràng buộc này. Khi đó, có một số l sao cho (cid:209) f (x) + l T (cid:209) h(x) = 0.
m
Ma trận
i=1
(cid:229) HL(x) = H f (x) + l iHhi(x).
, tức } (cid:209) h(x)y = 0 y | { 0, là nửa xác định dương trên không gian tiếp xúc M = là yT HL(x)y M. ≥ y ∀ ∈
Chứng minh.
Với mọi đường cong x(t) khả vi cấp hai trên mặt ràng buộc S, và đi qua
x thỏa mãn x(0) = x, thì ta có
t=0 ≥
(1.14) 0.
Mặt khác d2 dt2 f (x(t)) (cid:12) (cid:12) (cid:12)
t=0
(1.15) f (x)x00(0). = x0(0)T H f (x) x0(0) + (cid:209)
Lấy vi phân cấp hai của phương trình l T h(x(t)) = 0, ta có d2 dt2 f (x(t)) (cid:12) (cid:12) (cid:12)
(1.16) x0(0)T l T Hh(x) x0(0) + l T (cid:209) h(x) x00(0) = 0.
Cộng (1.16) vào (1.15) và từ (1.14) ta suy ra
t=0
0. = x0(0)T HL(x) x0(0) ≥
(cid:3) M nên ta suy ra điều cần chứng minh. Do x0(0) d2 dt2 f (x(t)) (cid:12) (cid:12) (cid:12) ∈
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Chú ý rằng, khi sử dụng điều kiện cần ta chỉ xác định được điểm mà tại đó bài toán đạt cực trị. Do đó để xác định đó là cực đại hay cực tiểu ta cần tới điều kiện đủ cấp hai sau.
24
Định Lý 1.9. (Điều kiện đủ cấp hai).
Giả sử có điểm x thỏa mãn h(x) = 0 và số l Rm sao cho ∈
(cid:209) (1.17) f (x)+ l T (cid:209) h(x) = 0.
m
Cũng giả sử rằng, ma trận
i=1
(cid:229) HL(x) = H f (x) + l iHhi(x).
là xác định dương trên không gian tiếp xúc M = (cid:209) h(x)y = 0 y | { } , (tức là: = 0 thì yT HL(x) y > 0) . Khi đó, x là cực tiểu địa phương ngặt M, y ∈ 6 y ∀ của hàm f thỏa mãn h(x) = 0.
Chứng minh.
f (x), hội tụ tới x thỏa mãn f (yk) Nếu x không phải là cực tiểu địa phương ngặt, thì tồn tại dãy các điểm k. Biểu diễn yk ∀ yk} ≤ { chấp nhận được dưới dạng
yk = x + d ksk.
k. = 1 và d k > 0, ∀ bị chặn, nên phải có một dãy con hội tụ sk} { hội tụ tới s. trong đó sk ∈ tới s. Để tiện cho việc kí hiệu, chúng ta giả sử rằng, dãy sk} { Rn, sk| | Rõ ràng d k −→ 0, và dãy Mặt khác
(1.18) h(x) = 0. h(yk) −
¥ , ta được chia hai vế của phương trình (1.18) cho d k và cho k −→ (cid:209) h(x)s = 0.
Theo định lý Taylor, với mỗi j ta có
j)sk.
(1.19) (cid:209) 2h j(h 0 = h j(yk) = h j(x) + d k(cid:209) h j(x)sk + sT k d 2 k 2
Và
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
0 (1.20) f (yk) f (x)sk + (cid:209) 2 f (h 0)sk. f (x) = d k(cid:209) sT k d 2 k 2 ≥ −
25
j là một điểm trên đoạn thẳng nối x và yk.
j và cộng vào với (1.20), kết hợp với (1.17), ta được
m
trong đó h Nhân (1.19) với l
i)
i=1
(cid:229) 0 l i(cid:209) 2hi(h (cid:209) 2 f (h 0) + sk. sT k d 2 k 2 ≥ o n (cid:3) ¥ Cho k ta gặp mâu thuẫn. −→
Chú ý rằng, với các giả thiết như trong định lý thì: khi ma trận HL(x) là xác định âm ta có x là cực đại địa phương ngặt của hàm f thỏa mãn h(x) = 0.
Ví Dụ 1.4.
Giải bài toán sau
max x1x2 + x2x3 + x3x1 : x1 + x2 + x3 = 3 } {
Giải
Trước tiên, ta xây dựng hàm Lagrange cho bài toán
3) L(x1, x2, x3, l ) = x1x2 + x2x3 + x3x1 + l (x1 + x2 + x3 −
Từ điều kiện cần thứ nhất, ta có
, , ) = 0. (cid:209) L(x1, x2, x3, l ) = ( ¶ L ¶ x1 ¶ L ¶ x2 ¶ L ¶ x3
Suy ra
2. Do đó x2 + x3 + l = 0 x1 + x3 + l = 0 x1 + x2 + l = 0 Chúng ta giải ba phương trình này cùng với ràng buộc của bài toán, ta được x1 = x2 = x3 = 1 và l = −
x = 1 1 1
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
26
Bây giờ, ta cần sử dụng đến điều kiện đủ cấp hai để xác định xem bài
toán đạt cực đại hay cực tiểu tại x. Ta có:
= = = 0, ¶ 2L ¶ x2 1 ¶ 2L ¶ x2 2 ¶ 2L ¶ x2 3
= = 1, = = 1, = = 1. ¶ 2L ¶ x2x1 ¶ 2L ¶ x1x3 ¶ 2L ¶ x3x1 ¶ 2L ¶ x2x3 ¶ 2L ¶ x3x2
¶ 2L ¶ x1x2 Như vậy, ta xác định được ma trận
HL(x) = H f (x) + l Hh(x)
= 0 1 1 1 0 1 1 1 0
Mặt khác
= (1, 1, 1) , , (cid:209) h = ¶ h ¶ x1 ¶ h ¶ x3
(cid:1) (cid:0) ¶ h ¶ x2 Do đó, theo định lý (1.5) không gian tiếp xúc với mặt rằng buộc tại x là
M = , với y = (y1, y2, y3). { }
y1 + y2 + y3 = 0 y | Tuy nhiên ta lưu ý là
yT HLy = (y1, y2, y3) 0 1 1 1 0 1 1 1 0 y1 y2 y3
3) < 0,
1 + y2
(y2 = = 0. y ∀ − 6 2 + y2 Do đó, HL là xác định âm trên M và nghiệm ta tìm được là cực đại địa
phương.
Giải bài toán quy hoạch sau Ví Dụ 1.5.
1 + bx2
2 : x1 + x2
ax2 min 1 = 0 { } −
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
trong đó a > 0, b > 0.
27
Giải
Trước hết ta xây dựng hàm Lagrange
1 + bx2
2) + l (x1 + x2
1) L(x1, x2, l ) = (ax2 −
= 2ax1 + l = 0
= 2bx2 + l = 0 Từ điều kiện cần thứ nhất, ta có ¶ L ¶ x1 ¶ L ¶ x2
Giải hai phương trình trên cùng với ràng buộc của bài toán, ta được
, l = x1 = , x2 = b a + b a a + b 2a a + b −
Nhớ rằng nếu chỉ dựa vào điều kiện cần cấp một thì ta chưa thể biết
được giá trị hàm mục tiêu tại điểm
( , ) b a + b a a + b
là lớn nhất hay nhỏ nhất khi có ràng buộc.
Từ điều kiện đủ cấp hai, ta có
= 2a, = 2b, = = 0. ¶ 2L ¶ x1¶ x2 ¶ 2L ¶ x2¶ x1 ¶ 2L ¶ x2 1 ¶ 2L ¶ x2 2
Do đó
HL(x) = H f (x) + l Hh(x)
= 2a 0 0 2b
Trên không gian tiếp xúc M = với y = (y1, y2), ta xét (cid:18) (cid:19) y1 + y2 = 0 y | } {
yT HLy = (y1, y2) 2a 0 0 2b
2 > 0,
y1 y2 (cid:19) = 0. = 2ay2 (cid:19) (cid:18) y ∀ 6
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
(cid:18) 1 + 2by2 Như vậy, HL xác định dương trên M. Do đó, nghiệm ta tìm được là cực tiểu địa phương.
28
1.2.3. Trường hợp tổng quát.
Trở lại bài toán (P1), những kết quả sau là tổng quát từ những trường hợp cụ thể, và được thể hiện thông qua định lý (1.10) và hai hệ quả quan trọng sau.
Định Lý 1.10. (Nguyên Lý Nhân Tử Lagrange)
−→
Cho hàm f và ánh xạ F khả vi Frechet tại x thỏa mãn F(x) = 0, với các đạo hàm Frechet tại f 0(x) và F 0(x). Ảnh của không gian X qua ánh xạ F 0(x)x là đóng. Khi đó, nếu x là cực tiểu địa phương của bài toán x (P1) thì tồn tại các nhân tử Lagrange l 0 và y∗ không đồng thời bằng không sao cho
(1.21) L0x(x, l 0, y∗) = l 0 f 0(x) + F 0∗(x)y∗ = 0
Hơn nữa, nếu F khả vi liên tục theo nghĩa Frechet tại x và F 0(x)X = Y = 0 và có thể xem như l 0 = 1. (F là chính quy), thì l 0 6
Chứng Minh
Theo giả thiết, F 0(x)X là không gian con đóng của không gian Y . Có
thể xảy ra một trong hai trường hợp: F 0(x)X = Y hoặc F 0(x)X $ Y .
a) Trường hợp F 0(x)X = Y . Theo định lý Ljusternik, không gian tiếp xúc với tập
x M = X : F(x) = 0 { ∈
v } Ker F 0(x), thì Ker F 0(x), và − ∈ ∈ X sao cho tại x trùng với Ker F 0(x). Do đó, nếu v tồn tại số e > 0, ánh xạ r : [ e , e ] − −→
M t x(t, v) = x + tv + r(t) e , e ]) ∈ ( ∀ [ − ∈
r(t) || t −→
t 0 khi 0. Suy ra trong đó || −→
F t = 0 [ − ∈ ∀
e , e ] x (t, v) . Khi đó, j (t) đạt cực tiểu địa phương tại t = 0. Đặt j (t) = f (cid:1) x (t, v) (cid:0)
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Do đó (cid:0) j v Ker F 0(x)). f 0(x), v i ( ∀ ∈ (cid:1) 0(0) = h
29
Vì thế f 0(x) (Ker F 0(x))⊥. ∈ Do F 0(x) là toán tử tuyến tính liên tục từ không gian Banach X lên
không gian Banach Y , nên theo bổ đề (1.1) ta có
(Ker F 0(x))⊥ = Im F 0∗(x)
Y ∗ sao cho f 0(x) = F 0∗(x)y∗. ∈ Im F 0∗(x), tức là, tồn tại y∗ ∈ − Vì vậy f 0(x) Điều này có nghĩa là
f 0(x) + F0∗(x)y∗ = 0.
Vậy, ta có
với l 0 = 1. L0x(x, l 0, y∗) = l 0 f 0(x) + F 0∗(x)y∗ = 0
b) Trường hợp F 0(x)X $ Y .
Y Khi đó, tồn tại y0 F 0(x)X là tập mở, nên tồn tại lân F0(x)X. Do Y ∈ \ F 0(x)X = /0. ∩ \ cận mở V của y0 sao cho V Theo định lý Hahn-Banach và hệ quả (1.1) thì = 0 sao cho Y ∗, y∗ 6
> 0 y∗ ∈ ∃ V ). y ( ∀
∈ F 0(x)X). y∗, y i h = 0 y∗, z h i z ( ∀ ∈ Do đó, ta có
= = 0 X). F 0∗(x)y∗, x i h x ( ∀ ∈
y∗, F 0(x)x h i Suy ra F 0∗(x)y∗ = 0. Chọn l 0 = 1 thì
(cid:3) L0x(x, 0, y∗) = F 0∗(x)y∗ = 0.
Nhận Xét 1.4.
= 0. Thật vậy, nếu l 0 = 0 • 6 Trong trường hợp F 0(x)X = Y ta luôn có l 0 thì ta có
= = 0 X) F 0∗(x)y∗, x i h x ( ∀ ∈ y∗, F 0(x)x i h
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Từ các điều kiện chính quy, suy ra y∗ = 0. Điều này mâu thuẫn với điều kiện của các nhân tử Lagrange là không đồng thời bằng không.
30
•
Phương trình (1.21) được gọi là phương trình Euler-Lagrange của bài toán (P1). Từ phương trình này ta thấy, x là điểm dừng của hàm Lagrange.
Chúng ta có hai trường hợp đặc biệt của bài toán (P1)
1) Trường hợp 1: Cho X,Y là các không gian hữu hạn chiều, khi đó
bài toán có dạng
−→ (P5) in f f0(x) f1(x) = 0, . . . , fn(x) = 0 (cid:26)
n
(1.22) trong đó, các nhân tử Lagrange là các số l 0, . . . , l n sao cho hàm Lagrange có dạng
i=0
(cid:229) l i fi(x). L(x, l 0, . . . , l n) =
Hệ Quả 1.2.
Cho các hàm số f0, . . . , fn thuộc lớp C1 tại x thỏa mãn điều kiện (1.22). Khi đó, nếu x là cực tiểu địa phương của bài toán (P5) thì tồn tại các số l 0, . . . , l n không đồng thời bằng không sao cho
+ l n f 0n(x) = 0. l 0 f 00(x) +
= 0, và 6 · · · Hơn nữa, nếu các hàm f 01(x), . . . , f 0n(x) là độc lập tuyến tính thì l 0 có thể coi l 0 = 1.
Nhận Xét 1.5.
f1(x), . . . , fn(x) −→ Chứng minh của hệ quả (1.2) được suy ra trực tiếp từ định lý (1.10), và như đã nêu trong định lý (1.2) thì điều kiện chính quy của ánh xạ có nghĩa đơn giản là các hàm f 01, . . . , f 0n độc lập x tuyến tính. (cid:0) (cid:1)
2) Trường hợp thứ hai phát sinh khi ánh xạ F trong bài toán (P1) có thể phân tích thành một ánh xạ chính quy vào một không gian Banach và một ánh xạ vào Rn. Khi đó, bài toán có dạng
in f
(P6)
(1.23) (1.24) f0(x) −→ F(x) = 0 f1(x) = 0, . . . , fn(x) = 0
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
31
Hệ Quả 1.3.
Cho các hàm số f0, . . . , fn và ánh xạ F thuộc lớp C1 tại x thỏa mãn đẳng thức (1.23) và (1.24). Giả thiết rằng ánh xạ F là chính quy tại điểm x. Nếu x là cực tiểu địa phương của bài toán (P6) thì tồn tại các số l 0, . . . , l n và một vectơ y∗ không đồng thời bằng không sao cho
l 0 f 00(x) + . . . + l n f 0n(x) + F 0∗(x)y∗ = 0.
Chứng minh của hệ quả (1.3) cũng được suy ra trực tiếp từ định lý
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
(1.10).
32
CHƯƠNG II: NGUYÊN LÝ NHÂN TỬ LAGRANGE CHO BÀI TOÁN TỐI ƯU LỒI.
Chương này dành để trình bày các kết quả về điều kiện cần đủ của bài toán tối ưu lồi, thông qua việc sử dụng các nhân tử Lagrange và khái niệm về dưới vi phân. Các kết quả của chương này là của A. D. Ioffe [1], Đỗ Văn Lưu và Phan Huy Khải [4].
2.1. Một số kiến thức cơ bản của giải tích lồi
Trong mục này chúng ta sẽ nhắc lại một số kiến thức cơ bản của giải tích lồi, đặc biệt là định lý Moreau-Rockafellar về phép tính dưới vi phân của tổng các hàm lồi.
2.1.1. Tập lồi.
Định Nghĩa 2.1.
Tập A X được gọi là lồi nếu
l A, A. 1 thì l x1 + (1 l )x2 R : 0 ⊂ x1, x2 ∀ ∈ l ∀ ∈ ≤ ≤ − ∈
X, x1, x2 A. Đoạn thẳng nối hai điểm x1, x2 được định ∈ Định Nghĩa 2.2. Giả sử A ⊂ nghĩa như sau
l x 1 . [x1, x2] = A : x = l x1 + (1 l )x2, 0 { ∈ − ≤ } ≤
Định Nghĩa 2.3.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Cho A X, x1, x2 ⊂ l A. Khi đó, đường thẳng đi qua x1, x2 là tập các điểm ∈ x = l x1 + (1 l )x2, R. − ∈
33
Ví Dụ 2.1.
1. Các nửa không gian trong R2 và R3 là các tập lồi.
2. Các tam giác, hình tròn trong mặt phẳng, hình cầu đơn vị trong không
gian Banach là các tập lồi.
Định Nghĩa 2.4.
Tập K X được gọi là nón có đỉnh tại 0 nếu: ⊂
K, K. x ∀ ∈ l > 0 thì l x ∀ ∈
K được gọi là nón có đỉnh tại x0 nếu K x0 là nón có đỉnh tại 0. −
Định Nghĩa 2.5.
Nón K có đỉnh tại 0 được gọi là nón lồi, nếu K là một tập lồi. Điều này
có nghĩa là
K. x, y K, ∈ ∀ ∈ l , m > 0 thì l x + m y ∀ Một ví dụ quan trọng về nón lồi trong Rn là nón orthant dương
n + = R
0, i = 1, 2, . . . , n . (x1, x2, . . . , xn) : xi { ≥ }
Định Nghĩa 2.6.
Giả sử X là một không gian lồi địa phương, X ∗ là không gian các phiếm X ∗ được gọi là pháp tuyến của
hàm tuyến tính liên tục trên X. Vectơ x∗ ∈ tập lồi A tại x nếu
A. 0, x i ≤ x ∀ ∈ − x∗, x h Tập tất cả các vectơ pháp tuyến của tập lồi A tại x A được gọi là nón ∈ pháp tuyến của A tại x. Kí hiệu là N(x A). Như vậy
A) = 0, . N(x x∗ X ∗ : | { ∈ x i ≤ − x ∀ A } ∈ | x∗, x h
2.1.2. Hàm lồi.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Giả sử X là không gian lồi địa phương, D X và ⊂ ¥ f : D . R = R −→ ∪ {± }
34
Định nghĩa 2.7.
Trên đồ thị của hàm f , kí hiệu là epi f , được định nghĩa như sau
D r epi f = (x, r) . R : f (x) { ∈ × } ≤
Định Nghĩa 2.8.
Miền hữu hiệu của hàm f , kí hiệu là dom f , được định nghĩa bởi
x dom f = D : f (x) < +¥ . { ∈ }
Định Nghĩa 2.9. ¥ = /0 và f (x) > 6 − D). Hàm không chính thường được gọi là hàm phi chính. Hàm f được gọi là chính thường, nếu dom f x ( ∀ ∈
Định Nghĩa 2.10.
Giả sử D X là tập lồi. Khi đó, hàm f được gọi là ⊂
Hàm lồi nếu • l f (l x1 + (1 l )x2) f (x1) + (1 l ) f (x2) − l với ≤ D và 0 1. ∈ ≤ ≤
− x1, x2 ∀ f là hàm lồi. Hàm Lõm nếu − •
Hàm affine nếu f vừa là hàm lõm vừa là hàm lồi. •
Ví Dụ 2.2. Một số ví dụ về hàm lồi.
1. Hàm affine
+ a f (x) = X ∗, a (x∗ R) . ∈ ∈ x∗, x i h
1
là hàm lồi trên X, trong đó X ∗ là không gian các phiếm hàm tuyến tính liên tục trên X.
1 2 .
1 + . . . + x2 n)
= 2. Chuẩn Euclide là một hàm lồi trên Rn 2 = (x2 x || ||
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
trong đó x = (x1, . . . , xn) x, x i h Rn. ∈
35
X là hàm lồi 3. Hàm Chỉ d (x A) của tập lồi A |
⊂ 0 +¥ A A. d (x A) = | (cid:26) nếu x ∈ nếu x / ∈
X ∗ là một hàm lồi. 4. Hàm Tựa S(x A) của tập lồi A | ∈
A h
. x∗, x i A) = sup S(x | x∗∈
2.1.3. Tập Affine.
Định Nghĩa 2.11.
Tập A Rn được gọi là tập affine, nếu ⊂
(1 l )x + l y A, x, y A, R). − ∈ ( ∀ ∈ l ∀ ∈
Nhận xét 2.1.
Nếu A là tập affine, thì với a Rn
∈ A + a = x + a : x . { A } ∈
là tập affine.
Mệnh Đề 2.1. Tập M Rn là một không gian con khi và chỉ khi M là tập affine chứa ⊂ không.
Định Nghĩa 2.12.
Tập affine A được gọi là song song với tập affine M nếu tồn tại a Rn ∈ sao cho
A = M + a.
Kí hiệu A//M.
Mệnh Đề 2.2.
Mỗi tập affine A = /0 song song với một không gian con duy nhất L được 6 xác định bởi
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
x y : x L = A A = A, y . − { − ∈ A } ∈
36
2.1.4. Các định lý tách.
Giả sử X là không gian lồi địa phương, X ∗ là không gian liên hợp của
X, tức là không gian các phiếm hàm tuyến tính liên tục trên X.
Định Nghĩa 2.13.
Tập M X thỏa mãn: bất cứ đường thẳng nào đi qua hai điểm của M ⊂ cũng nằm trọn trong M được gọi là một đa tạp tuyến tính trong X.
Nhận Xét 2.2.
Khái niệm đa tạp tuyến tính chính là khái niệm tập affine trong không
gian hữu hạn chiều.
= 0, b R và kí hiệu Lấy x∗ ∈ X ∗, x∗ 6
x X : = b . ∈ H(x∗, b ) = { ∈ }
b x X : . { ∈ i ≤ } b x X : . H+(x∗, b ) = H−(x∗, b ) = { ∈ x∗, x i h x∗, x h x∗, x h i ≥ }
Với 0 X ∗, b R thì Định Nghĩa 2.14. = x∗ ∈ 6 ∈
•
• Tập H(x∗, b ) được gọi là một siêu phẳng trong X. Tập H+(x∗, b ) và H−(x∗, b ) được gọi là các nửa không gian sinh bởi siêu phẳng H(x∗, b ).
Định Nghĩa 2.15.
= 0
X. Ta nói phiếm hàm tuyến tính liên tục x∗ 6 sao cho Cho các tập hợp A, B ⊂ tách A và B, nếu tồn tại số a
a A, B). (2.1) x∗, y h i ≤ x∗, x i ≤ h x ( ∀ y ∀ ∈ ∈
Nếu (2.1) có dạng
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
A, B). x∗, x i h x ( ∀ y ∀ ∈ ∈ x∗, y < a < h
37
thì ta nói x∗ tách ngặt A và B.
Siêu phẳng đóng
x X : = a . H(x∗, a ) = } { x∗, x i h
∈ được gọi là siêu phẳng tách A và B. Các tập A và B được gọi là tách được.
Định Lý 2.1. (Định Lí Tách Thứ Nhất).
B = /0, int A 6 Giả Sử A và B là hai tập lồi, khác rỗng trong không gian lồi địa phương = /0 (trong đó kí hiệu intA là phần trong của A). Khi X ∗ sao cho
B). A, = 0 tách A và B. Tức là, tồn tại x∗ ∈ X ∗, x∗ 6 x với ( ∀ X, A ∩ đó, tồn tại x∗ ∈ x∗, y x∗, x i i ≥ h h y ∀ ∈ ∈
Định Lý 2.2. (Định Lý Tách Thứ Hai).
Giả sử A là tập con lồi đóng, khác rỗng trong không gian lồi địa phương
X ∗ tách ngặt A và x0. X, x0 / ∈ A. Khi đó, tồn tại x∗ 6 = 0, x∗ ∈
2.1.5. Dưới vi phân của hàm lồi.
Cho f là hàm lồi chính thường trên X.
X ∗ được gọi là dưới gradient của hàm số f tại điểm
x
Định Nghĩa 2.16. Phiếm hàm x∗ ∈ X nếu ∈ f (x) f (x) X). x∗, x ≥ h − ∈ x , i x ( ∀
của hàm f tại điểm x, kí hiệu là ¶ − Tập tất cả các dưới gradient của hàm số f tại x được gọi là dưới vi phân f (x), tức là:
¶ X f (x) = f (x) . x∗ X ∗ : f (x) x∗, x { ∈ − x , i x ∀ − ∈ } ≥ h
Nhận Xét 2.3.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Trong giải tích lồi, dưới vi phân đóng vai trò giống với đạo hàm trong giải tích cổ điển. Nếu hàm f là khả vi Gateaux tại mọi điểm, thì ta có thể chứng minh được rằng: dưới vi phân của hàm f chỉ có một giá trị, và đó chính là đạo hàm Gateaux.
38
Mệnh Đề 2.3.
Nếu hàm f khả vi tại x thì: ¶ f (x) = (cid:209) f (x).
Chứng minh
Nếu p ¶ x thì với mọi u X,t > 0, ta có ∈
t f (x) p, u ∈ f (x + tu) ≥ h . i −
Từ đó suy ra
f (x) p, u (vì t > 0). − f (x + tu) t i ≥ h
Cho t 0 ta được −→ f ( ¯x), u p, u . i i ≥ h h5 Điều đó có nghĩa là
0 f ( ¯x) p, u X. − i ≥ h5 u ∀ ∈
(cid:3) Vậy: p = f (x). 5
Ví Dụ 2.3. Một số ví dụ về dưới vi phân.
1. Cho hàm affine
f (x) := + a X ∗, a (x∗ R) . ∈ ∈
thì ¶ f (x) = , x∗, x i h X. x ∀ ∈ x∗} {
2. Giả sử X là không gian Banach thì dưới vi phân của hàm:
là f (x) = x || ||
¶ f (x) = 1 = 1, = Khi x = 0 = 0. Khi x X ∗ : X ∗ : x∗ ∈ x∗ ∈ x || || 6
x∗, x h i thì x∗|| ≤ || x∗|| (cid:26) || Nói riêng, nếu X = R, f (x) =
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
¶ 6 f (x) = = 0 Khi x 1, 1] Khi x = 0. ( x | | x x | | [ −
39
¶d 0, X ∗ : x∗ 3. Dưới vi phân của hàm chỉ d (x A) của một tập lồi A là | x∗, x h A) = (x | ¯x i ≤ A } x ∀ − ∈ A). = N(x |
Thật vậy, với x ∈ { A thì
¶d ¶d ¶d x X x∗ ∈ A) (x | A) + (x | ⇔ − ∈ , i x ∀ ∈
x∗, x h A. 0, A) (x | x∗, x ⇔ h − x ∀ ∈
≥ x i ≤ Điều này có nghĩa rằng, x∗ là vectơ pháp tuyến của A tại x. Như vậy, ¶d (x A) là nón pháp tuyến của A tại x. Do đó | ¶d A) = N(x (x | A). |
Chú ý rằng
• ¶d A thì ¶d A thì ¶d A kéo theo 0 = /0, vì khi x Với x / ∈ x Với ∀ ∈ • A) = /0 (x | A) (x | ∈ ∈ A). (x | 6
Nếu A = L là một không gian con thì
¶d
. = 0, trong đó L⊥ = X ∗ : x∗ ∈ { L) = L⊥ L) = N(x (x | | x x∗, x ∀ i h L } ∈
2.1.6. Định lý cơ bản về dưới vi phân của tổng các hàm lồi.
Định Lý 2.3. (Moreau-Rockafellar).
a) Cho các hàm f1 và f2 là những hàm lồi chính thường trên X.
Khi đó ¶ ¶ ( f1 + f2)(x) f1(x) + ¶ f2(x). ⊃ b) Nếu một trong các hàm này mà liên tục tại một điểm thuộc miền hữu
hiệu của hàm kia thì ta có
¶ ( f1 + f2)(x) = ¶ f1(x) + ¶ f2(x).
Chứng Minh ¶ X ta có fi(x), i = 1, 2. Khi đó, với a) Lấy x∗i ∈
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
∈ i = 1, 2. fi(z) z ∀ fi(x), x∗i , z h − x i ≤ −
40
Suy ra
. f1(z) + f2(z) f1(x) + f2(x) x∗1 + x∗2, z h − x i ≤ − do đó (cid:0) (cid:1)
¶ ( f1 + f2)(x). x∗1 + x∗2 ⊃ Như vậy ¶ ¶ ( f1 + f2)(x) f1(x) + ¶ f2(x). ⊃
dom f2 thì b) Ta chứng minh rằng, nếu f1 liên tục tại x
¶ ( f1 + f2)(x) = ¶ f1(x) + ¶ ∈ f2(x).
= /0 Ta có, int(epi f1) 6 Thật vậy, e > 0, tồn tại lân cận U mở của x sao cho
< e U). f1(x) f1(x) | x ( ∀ ∈ − |
Do đó tập
X U A = (x, a ) epi f1. R : a > f1(x) + e , x { ∈ ∈ } ⊂
× và A mở. Suy ra int(epi f1) = /0. 6 ¶ ( f1 + f2)(x). Xét các tập sau Lấy x∗ ∈
X (z, a ) . C1 = f1(x + z) ∈ f1(x) } −
X . { (z, a ) C2 = R : a × R : a < × ∈ ≥ x∗, z h f2(x + z) + f2(x) } i − { Khi đó
C1 = epi f1 (x, f1(x)). − = 0. Vì vậy: C1 lồi và intC1 6
[0, 1], ta có Mặt khác, ta cũng có tập C2 là lồi. i) Thật vậy, lấy (zi, a C2, (i = 1, 2) và l
i <
a (2.2) ∈ f2(x + zi) + f2(x), (i = 1, 2). i −
∈ x∗, zi h Do f2 là hàm lồi nên
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
f2 l (x + z1) + (1 l )(x + z2) − ≤ l (cid:0) (2.3) f2(x + z1) + (1 l ) f2(x + z2). (cid:1) −
41
Từ (2.2) và (2.3) suy ra
1 + (1
la l )z2 l )a 2 < x∗, l z1 + (1 h −
. l (x + z1) + (1 i− − l )(x + z2) + f2(x) f2 − − Do đó (cid:1) (cid:0)
C2. l (z1, a 1) + (1 l )(z2, a 2) − ∈
Vậy: C2 lồi.
Ta lại có: C1
Thật vậy, nếu C1 C2, thì C2 = /0. ∩ (z0, a 0) ∈ ∩
f2(x + z0) + f2(x) > f1(x + z0) f1(x). ∃ x∗, z0 h i − −
Suy ra
. > f1(x + z0) + f2(x + z0) f1(x) + f2(x) x∗, z0 h i
(cid:0) (cid:1) − ¶ ( f1 + f2)(x)
C2 = /0. ∩ Theo định lý tách thứ nhất = 0 sao cho Điều này mâu thuẫn với giả thiết rằng: x∗ ∈ Vậy C1 X ∗ và 6 x∗1 ∈ ∃
C1 {h ∈
+ ba R với (x∗1, b ) + ba . (2.4) x∗1, z i b ∈ ∃ x∗1, z i } ≤ } sup (z,a )
, còn cận inf C2 {h (z,a ) ∈ 0, bởi vì nếu b > 0 thì, cận trên trong (2.4) là +¥ ¥ Rõ ràng b dưới là
≤ . − Hơn nữa, b = 0, vì nếu b = 0 thì bất đẳng (2.4) có dạng 6
x h
x h
z ∈
−
−
z ∈ = 0 (do b = 0). Vì thế:
. (2.5) x∗1, z inf dom f2 i ≤ x∗1, z i sup dom f1
Mặt khác, x∗1 6
U
x h
x h
−
z ∈
−
. x∗1, z x∗1, ¯x h − x i i ≤ x∗1, z i sup dom f1 < sup z ∈ Do đó
x h
x h
z ∈
−
z ∈
−
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
. x∗1, ¯x x∗1, z inf dom f2 x∗1, z i x i − i ≤ h < sup dom f1
42
= 0 và ta có b < 0. Điều này mâu thuẫn với (2.5). Vì vậy b 6 Không làm mất tính chất tổng quát, có thể xem b = 1. Như vậy C1 và − C2 tách được bởi siêu phẳng
X a = 0 . H = (z, a ) R : ∈ × x∗1, z h i − } {
Do đó từ (2.4) suy ra
z {h
sup f1(x + z) + f1(x) x∗1, z } ≤
. (2.6) + f2(x + z) i − x∗1 − inf z {h ≤ x∗, z i f2(x) } −
Các biểu thức trong ngoặc của cả hai vế trái và phải của (2.6) sẽ triệt
x∗1, ta nhận được tiêu với z = 0. Do đó, khi đặt x∗2 = x∗ −
X). f1(x + z) f1(x) ∈ ≥ h −
X). f2(x + z) f2(x) ≥ h − x∗1, z , ( i x∗2, z , ( i z ∀ z ∀ ∈ Suy ra ¶ fi(x), (i = 1, 2). x∗i ∈ Vậy
(cid:3) ¶ ( f1 + f2)(x) = ¶ f1(x) + ¶ f2(x).
Bằng phương pháp quy nạp, định lý Moreau-Rockafellar có thể mở rộng
với số lượng các hàm số bất kỳ.
Hệ Quả 2.1.
a) Giả sử f1, . . . , fn là những hàm lồi chính thường trên X. Khi đó
¶ + ¶ X). + fn) fn(x), ( ¶ ( f1 + f1(x) + · · · · · · ∈
⊃ b) Hơn nữa nếu tại điểm ¯x x ∀ n i=1 dom fi, tất cả các hàm số f1, . . . , fn ∈ đều liên tục (có thể trừ ra một hàm), thì với X ta có x ∀
T f1(x) + ¶
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
+ ¶ (2.7) + fn)(x) = ¶ fn(x). ¶ ( f1 + f2 + ∈ f2(x) + · · · · · ·
43
Chứng Minh. ¶ + ¶ fn(x) thì f1(x) + ¶ f2(x) + Giả sử, x∗ ∈
¶ fi(x). x∗ = x∗1 + · · · + x∗n với x∗i ∈ · · ·
Theo định nghĩa dưới vi phân ta có
fi(z) fi(x), i = 1, . . . , n. x∗i , z h − x i ≤ −
Do đó
+ fn(z)] + fn(x)]. [ f1(z) + [ f1(x) + + x∗n, z · · · x∗1 + h · · · x i ≤ − − · · ·
Suy ra
+ fn)(x). ¶ ( f1 + x∗ = x∗1 + · · · + x∗n ∈ · · · Vậy ¶ + ¶ + fn)(x) fn(x). ¶ ( f1 + f1(x) + · · · ⊃ · · · b) Ta chứng minh theo quy nạp.
n
Trường hợp n = 2 chính là định lý Moreau-Rockafellar đã được chứng minh. Giả sử (2.7) đúng với n = k, tức là, nếu mọi hàm số f1, . . . , fk (có thể trừ ra một hàm) đều liên tục tại
\i=1
x dom fi. ∈
thì
+ ¶ ¶ ( f1 + f1(x) + + fk)(x) = ¶ fk(x). · · · · · · Ta cần chứng minh (2.7) đúng với n = k + 1, tức là nếu mọi hàm số
k+1
f1, . . . , fk, fk+1 (có thể trừ ra một hàm) đều liên tục tại
\i=1
x dom fi. ∈
thì
+ ¶ ¶ ( f1 + f1(x) + + fk+1)(x) = ¶ fk+1(x) · · · · · · Thật vậy vì (2.7) đúng với n = 2 và n = k, ta có
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
¶ [( f1 + f2 + + fk)(x) + ¶ + fk) + fk+1](x) = ¶ ( f1 + f2 + fk+1(x) · · · · · ·
44
+ ¶ = ¶ f1(x) + ¶ f2(x) + fk(x) + ¶ fk+1(x). · · ·
(cid:3) Tức là, (2.7) đúng với n = k + 1. Vậy (2.7) đúng với mọi số tự nhiên n.
2.2. Điều kiện cần đủ cho bài toán tối ưu lồi.
Cho X là một không gian tôpô tuyến tính lồi địa phương, A R là những hàm lồi và h j : X ⊂ −→ −→ X là tập lồi đóng không rỗng. f , gi : X R là những hàm afin. Xét bài toán quy hoạch lồi tổng quát cho dưới dạng sau
≤ min f(x) A x ∈ gi(x) 0 (i = 1, 2, . . . , m) h j(x) = 0 ( j = 1, 2, . . . , p)
trong đó:
x A gọi là ràng buộc hình học. •
0 gọi là ràng buộc bất đẳng thức. ∈ gi(x) ≤ •
•
x A : gi(x) • 0 (i = 1, . . . , n), h j(x) = 0 ( j = 1, . . . , p) } ≤ ∈ {
h j(x) = 0 gọi là ràng buộc đẳng thức. W = gọi là tập chấp nhận được. Sử dụng định nghĩa, ta có thể chứng minh tập chấp nhận được là tập lồi.
Định Nghĩa 2.17.
+ ×
p
jh j(x).
i=1
Hàm Lagrange L : A R của bài toán (P) được xác định Rp Rm × như sau −→ m m (cid:229) (cid:229) l igi(x) + L(x, l , m ) = l 0 f (x) +
j=1 +, m = (m 1, . . . , m p)
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
A, l 0 Rm ∈ ∈ ∈ ∈ 0 và m Rp. j ≤ R+, l = (l 1, . . . , l m) trong đó x Khi đó, l i gọi là các nhân tử Lagrange ứng với rằng buộc gi(x) gọi là các nhân tử Lagrange ứng với rằng buộc h j(x) = 0.
45
2.2.1. Bài toán không có ràng buộc.
Giả sử X là không gian lồi địa phương, f là hàm lồi trên X. Xét bài
toán
f (x) in f . (P7) −→
¶ Định Lý 2.4. Để x f (x) X là nghiệm của (P7), điều kiện cần và đủ là 0 ∈ ∈
Chứng minh
Ta có, x là nghiệm của (P2) khi và chỉ khi
f (x) f (x), ( X). ≤ x ∀ ∈
Suy ra
f (x) f (x), ( X). 0 = x i ≤ − x ∀ ∈ 0, x h − (cid:3) ¶ Vậy 0 f (x). ∈
2.2.2. Bài toán với ràng buộc đẳng thức.
Giả sử f là một hàm lồi trên X, C là đa tạp tuyến tính song song với
không gian con M trong X. Xét bài toán
in f (P8) f (x) x −→ C. (cid:26) ∈
Định Lý 2.5.
a) Giả sử f liên tục tại một điểm của C, x là một nghiệm của bài toán
(P8). Khi đó
¶ f (x) = /0. (2.8) M⊥ 6
b) Giả sử (2.8) đúng tại ∩ C. Khi đó x là nghiệm của bài toán (P8). x ∀ ∈
Chứng minh
Ta chú ý rằng
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
M = 0, . M⊥ = x∗ X ∗ : { ∈ x∗, x i h x ∀ } ∈
46
a) Xét hàm
L(x) = f (x) + d (x C). | ) là hàm chỉ của tập C. Khi đó L(x) là hàm lồi trên X. | trong đó: d (x M | Rõ ràng x là nghiệm của bài toán (P8) khi và chỉ khi hàm L(x) đạt cực
tiểu tại x. Theo định lý (2.4) thì
0 ¶ L(x). ∈
Do tính liên tục của f , nên ta có thể áp dụng định lý Moreau-Rockafellar,
và nhận được
0 ¶ L(x) = ¶ f (x) + ¶d C). (x | ∈ Từ ví dụ (2.3.3), ta lại có
¶d C) = M⊥. |
Do đó ta có: ¶ C) = N(x (x | = /0. f (x) ∩
¶ C. Khi đó, = /0 với x f (x) M⊥. ∈ x∗ ∈ ∃ ∩ b) Giả sử ¶ x f (x) M với x M⊥ 6 M⊥ 6 C, cho nên Vì x ∈ −
x ∩ ∈ 0 = = f (x) f (x), ( C). x∗, x h − i 6 − x ∀ ∈
(cid:3) Do đó x là nghiệm của bài toán (P8).
i
Định Lý 2.6. a X ∗, R, (i = 1, . . . , m) và ∈
i, (i = 1, . . . , m) }
X : Cho X là không gian Banach, x∗i ∈ = a x C = . { ∈ x∗i , x i h
Giả sử f là hàm lồi trên X và liên tục tại một điểm của C. Khi đó, x đạt R, (i = 1, . . . , m) ∈ cực tiểu của hàm f trên C khi và chỉ khi tồn tại các số l i sao cho ¶ f (x). l 1x∗1 + + l mx∗m ∈ · · ·
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Để chứng minh định lý (2.6), ta cần bổ đề sau
47
Bổ Đề 2.1.
X ∗, (i = 1, . . . , m).
Đặt
X : x Giả sử X là không gian Banach, x∗i ∈ = 0, M = . { ∈ x∗i , x i h i = 1, . . . , m } Khi đó
. M⊥ = lin x∗1, . . . , x∗m} { trong đó lin là kí hiệu bao tuyến tính.
Chứng minh
Không mất tính tổng quát, ta có thể xem như x∗1, . . . , x∗n là độc lập tuyến : X tính. Xét toán tử tuyến tính l Rm được xác định như sau
x . l x =
−→ x∗1, x , . . . , i h (cid:0) x∗m, x i h −→ Khi đó, Iml = Rm. Theo bổ đề (1.1) ta có (cid:1)
(Kerl )⊥ = Iml ∗.
Ta lại có
. x∗1, . . . , x∗2} { . Do đó M⊥ = lin (Kerl )⊥ = M⊥, Iml ∗ = lin x∗1, . . . , x∗m} {
Chứng minh định lý 2.6.
Đa tạp tuyến tính C song song với không gian con M :
x X : M = = 0, . { ∈ x∗i , x i h i = 1, . . . , m }
x∗ ∈ ∃ Từ định lý (2.5) suy ra: x đạt cực tiểu hàm f trên C khi và chỉ khi ¶ f (x) M⊥. Theo bổ đề (2.1), ta có ∩
. x∗ M⊥ = lin x∗1, . . . , x∗2} ∈
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
¶ (cid:3) f (x). l 1x∗1 + · · · { Do đó, tồn tại các số l 1, . . . , l m sao cho + l mx∗m ∈
48
2.2.3. Bài toán với ràng buộc bất đẳng thức.
Giả sử X là không gian lồi địa phương, A X là một tập lồi đóng không ⊂ rỗng. f0, . . . , fn : X R là các hàm lồi. Xét bài toán −→
(P9)
0 (i = 1, 2, . . . , m). (2.9) (2.10) min f0(x) x A ∈ fi(x) ≤
Nhận Xét 2.4.
Quan hệ (2.9) không có đặc trưng hàm, mặc dù nó có thể được viết dưới
0. dạng hàm, ví dụ như trong dạng bất đẳng thức d (x A) | ≤ Chúng ta xây dựng hàm Lagrange cho bài toán mà không bao gồm ràng
n
buộc dạng (2.9), đó là
i=0
(cid:229) l i fi(x). L(x, l 0, . . . , l n) =
n
Tuy nhiên, chúng ta cũng có thể xét tới việc mở rộng hàm số Lagrange
i=0
(cid:229) L(x, l 0, . . . , l n) = l i fi(x) + d (x A). |
Định lý Kuhn-Tucker dưới đây, sẽ đưa ra điều kiện cần và đủ cho điểm chấp nhận được là nghiệm của bài toán (P9). Định lý này có thể được phát biểu dưới hai dạng: dạng toàn cục (định lý 2.7) và dạng địa phương thông qua dưới vi phân (định lý 2.8).
Định Lý 2.7. (Định Lý Kuhn-Tucker).
Giả sử các hàm f0, . . . , fm và tập A là lồi. x là điểm chấp nhận được của
bài toán (P9). Khi đó
0, (i = 1, . . . , m) a) Nếu x là nghiệm của bài toán (P9), thì tồn tại l i ≥ không đồng thời bằng không sao cho
(2.11) L(x, l 0, . . . , l m).
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
(2.12) L(x, l 0, . . . , l m) = min x A ∈ l i fi(x) = 0, (i = 1, . . . , m).
49
Hơn nữa, nếu điều kiện Slater sau đây được thỏa mãn:
A : fi(x0) < 0, (i = 1, . . . , m). ∈
x0 ∃ thì l 0 > 0 và có thể xem như l 0 = 1.
b) Nếu (2.11) và (2.12) thỏa mãn với l 0 = 1, thì x là nghiệm của bài
toán (P9).
Chứng minh
a) Giả sử x là nghiệm của (P9). Đặt
C = A) (m 0, . . . , m m) R {
m+1 : ( x ∈ ∀ m 1, . . . , fm(x)
. m m } ≤ ≤ ∈ f0(x) < m 0, f1(x) C.
m+1 + . Khi đó, m i > 0, (i = 0, . . . , m).
f0(x) − Ta có int Rm+1 + ⊂ Thật vậy, lấy (m 0, . . . , m m) int R
Với x = x, ta có:
f0(x) = 0, ∈ m 0 > f0(x) −
fi(x), (i = 1, . . . , m).
+ ⊂
C. m i > 0 ≥ C, do đó int Rm+1 ∈ Suy ra (m 0, . . . , m m) Vậy int C = /0. 6
C. C thì A thỏa mãn ∈
0, (i = 1, . . . , m). fi(x) Do f0, . . . , fm là hàm lồi, nên tập C là lồi. Hơn nữa, 0 / ∈ x Thật vậy, nếu 0 ∃ ∈ f0(x) < f0(x), ≤
C. Do đó, x không phải là nghiệm của (P9). Điều này mâu thuẫn với giả thiết. Vì vậy 0 / ∈ 0 Theo định lý tách thứ nhất, có thể tách các tập C và { }
m
bởi một phiếm hàm tuyến tính khác không, tức là tồn tại các số l 0, . . . , l m không đồng thời bằng không, sao cho
i=0
(cid:229) C 0, . (2.13) l im i ≥ (m 0, . . . , m m) ∀ ∈
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
(cid:0) (cid:1)
50
m+1 + ⊂ ∈
0, (i = 0, . . . , m). C, ta suy ra l i ≥ Do int R Lấy x A sao cho
m i = fi(x), (i = 1, . . . , m).
m
. m 0 f0(x) f0(x) ↓ − Từ (2.13) ta nhận được (cid:0) (cid:1)
i=0
(cid:229) (2.14) A). l i fi(x) l 0 f0(x), ( x ∀ ∈ ≥
Do x là điểm chấp nhận được, ta có fi(x) : Nếu ≤ a < 0, thì fi(x) = i ∃ ∈ { −
0 < e 0, (i = 1, . . . , m). e > 0, ∀ f0(x) < e , f j(x) 1, . . . , m } 0 = f0(x) − ≤
( j = 1, . . . , i 1, i + 1, . . . , m). − Do đó a ở vị trí thứ i). (e , . . . , e , ( − ∈
− a , e , . . . , e ) C, − (do (2.13) và cho e (do l i l ia Suy ra Từ đó ta có l i → ≥ ≥ ≤ 0 ). 0, 0, nên l i = 0, 0). Như vậy là, nếu fi(x) < 0 thì l i = 0. Do đó
l i fi(x) = 0, (i = 1, . . . , m).
m
m
Vì vậy, từ (2.14) ta nhận được
i=0
i=0
(cid:229) (cid:229) l i fi(x) l i fi(x). ≥
Vậy ta có
L(x, l 0, . . . , l m).
m
L(x, l 0, . . . , l m) = min A x ∈ Bây giờ, giả sử điều kiện Slater đúng. Khi đó, nếu l 0 = 0, thì trong các
số l 1, . . . , l m phải có ít nhất một l i > 0. Do đó m
i=0
i=0
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
(cid:229) (cid:229) l i fi(x) < 0 = l i fi(x).
51
Điều này mâu thuẫn với (2.11). Vậy l 0 = 0, tức là l 0 > 0. Không mất tính tổng quát, ta có thể coi l 0 = 1. 6
b) Giả sử x là điểm chấp nhận được, thỏa mãn (2.11) và (2.12) với (i = 1, . . . , m). Lấy x là điểm chấp nhận được, tức là
m
l 0 = 1, l i A, x 0, 0, (i = 1, . . . , m). Khi đó ≥ fi(x) ∈ ≤
i=1
m
(cid:229) l i fi(x). f0(x) = f0(x) +
i=1
(cid:229) l i fi(x). f0(x) + ≤
f0(x). ≤ (cid:3) Điều này có nghĩa x là nghiệm của bài toán (P9).
Nhận Xét 2.5.
Mối quan hệ (2.11) gọi là điều kiện Kuhn-Tucker, và đẳng thức (2.12) gọi là điều kiện bù. Điều kiện bù cho thấy, các nhân tử Lagrange l i tương ứng với ràng buộc tích cực tại điểm x0, (tức là fi(x0) < 0) thì bằng không.
Định Lý 2.8.
Giả sử các hàm số f0, . . . , fm và tập A là lồi, f0, . . . , fm liên tục tại một
điểm của A. x là điểm chấp nhận được của bài toán (P9). Khi đó
a) Nếu x là nghiệm của bài toán (P9), thì tồn tại các nhân tử Lagrange
0, (i = 0, . . . , m), sao cho không đồng thời bằng không: l i
0 (2.15) ≥ +l m¶ fm(x)+N(x f0(x)+ l 0¶ A). |
(2.16)
trong đó N(x ∈ · · · l i fi(x) = 0, (i = 1, . . . , m). A) là nón pháp tuyến của A tại x. | Hơn nữa, nếu điều kiện Slater đúng, thì l 0 = 0 và có thể xem như l 0 = 1. 6
b) Nếu (2.15) và (2.16) thỏa mãn với l 0 = 1, thì x là nghiệm của bài
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
toán (P9).
52
Chứng minh
m
a) Xét hàm Lagrange của (P9) có dạng
i=0
(cid:229) L1(x, l 0, . . . , l m) = l i fi(x) + d (x A). |
trong đó d (x A) là hàm chỉ của tập A. |
Do x là nghiệm của bài toán (P9), ta thu được điều kiện cần dạng (2.11) và (2.12) (định lý (2.7)). Vì thế, hàm L1(x, l 0, . . . , l m) đạt cực tiểu tại x. Theo định lý (2.4) thì
0 ¶ L1(x, l 0, . . . , l m). ∈
Vì ¶d (x A) = N(x | A). Theo định lý Moreau-Rockafellar, ta có |
0 + l m¶ f0(x) + l 0¶ · · · A). fm(x) + N(x | ∈
m+1
¶ b) Giả sử (2.15) và (2.16) thỏa mãn với l 0 = 1. Khi đó, tồn tại x∗i ∈ A) sao cho N(x fi(x), (i = 0, . . . , m), và x∗m+1 ∈ |
i=1
(cid:229) l ix∗i = 0. x∗0 +
m+1
Suy ra
i=1
m
(cid:229) 0 = l ix∗i , x − x i ≤ x∗0 + h
i=1
(cid:229) , ( A). fi(x) fi(x) l i f0(x) f0(x) + x ∀ ∈ ≤ − −
m
m
(cid:1) (cid:0) Do đó
i=1
i=1
(cid:229) (cid:229) A). l i fi(x) f0(x) + f0(x) + ≥ l i fi(x), ( x ∀ ∈
(cid:3) Theo định lý (2.7.b), ta suy ra x là nghiệm của (P9).
Nhận Xét 2.6.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Quan hệ (2.15) goi là phương trình Euler-Lagrange. Nó có thể được coi là sự mở rộng tự nhiên của phương trình Euler-Lagrange (1.12) trong
53
trường hợp trơn.
Trong trường hợp, tất cả các hàm f0, . . . , fm đều khả vi, X = Rn và điều kiện Slater được thỏa mãn, thì các phương trình (2.15) và (2.16) tạo thành một hệ gồm (m + n) phương trình tuyến tính với (m + n) ẩn. Đây chính là trường hợp định lý Kuhn-Tucker hay được áp dụng trong thực tiễn.
Ví Dụ 2.4. Ví dụ về bài toán tối ưu lồi.
n
n
Giải bài toán quy hoạch sau
i=1
i=1
(cid:229) (cid:229) : min . xi 1, xi > 0 ≤ } { 1 x2 i
2
Giải
là hàm lồi khi xi > 0. Đồng thời Đây là bài toán quy hoạch lồi vì x− i
n
n
bài toán thỏa mãn điều kiện Slater. Hàm Lagrange của bài toán là
i=1
i=1 Theo định lý Kuhn-Tucker, tồn tại l
(cid:229) (cid:229) 1 + l . L(x, l ) = xi − 1 x2 i (cid:0) (cid:1) 0 sao cho
n
(cid:209) ≥ x L(x, l ) = 0
i=1
l (cid:229) 1 = 0. xi − (cid:0) (cid:1) Suy ra
i = 1, . . . , n)
i=1
− l (cid:229) 3 i + l = 0, ( 2x− ∀ n = 0. 1 xi − (cid:0) Do đó l > 0 và i = 1, . . . , n) xi = ( n
i=1
(cid:229) (cid:1) l 2 )3, ( ∀ l 3 = 1. xi = n 8
3
Vậy
. xi = l = 2 n− 1 n
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
54
n > 0,
2 với
3 .
Mặt khác, xi = 1 n. Suy ra, bài toán đạt cực tiểu tại xi = 1 ∀
l = 2 n−
Ví Dụ 2.5.
Giải bài toán quy hoạch sau
1 min x + y : x + y 1, x2 + y2 . { ≤ } ≤
Giải
Đây là bài toán quy hoạch lồi, vì hàm mục tiêu và tập chấp nhận được
là lồi. Đồng thời, bài toán thỏa mãn điều kiện Slater.
Hàm Lagrange của bài toán là
1) + b (x2 + y2 1). L(x, y, l , b ) = x + y + l (x + y − −
Theo định lý Kuhn-Tucker, ta có
(2.17)
1) = 0
¶ Lx(x, y, l , b ) = 1 + l + 2b x = 0 ¶ Ly(x, y, l , b ) = 1 + l + 2b y = 0 l (x + y − b (x2 + y2 1) = 0.
l b − 0 nên Do (l , b ) = 0, ≥ 6
1 1 2b = − √2
0, ≥ = 0) thì từ (2.17) ta được Nếu (l = 0, b 6 •
( x = y = − b = 1 √2
Nếu (l = 0, b = 0) thì từ (2.17) ta được • 6
loại .
l = x + y 1 1 = 0. (cid:0) (cid:1) (cid:26) − −
1
−
l 2b
Nếu (l > 0, b > 0) thì từ (2.17) ta được •
loại .
1 x = y = − b = 0 l = (cid:0) (cid:1) −
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
55
với
1 Vậy theo định lý Kuhn-Tucker, bài toán đạt cực tiểu tại x = y = − √2 l = 0,
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
. b = 1 √2
56
KẾT LUẬN
Trong các định lý về điều kiện cần và đủ cho một điểm là nghiệm tối ưu của bài toán tối ưu trơn và lồi, tác giả đã trình bày thành hai phần. Phần thứ nhất là về các nhân tử Lagrange tổng quát, phần thứ hai là: đối với một số các điều kiện chính quy, thì đảm bảo rằng, hệ số l 0 ứng với hàm mục tiêu là khác 0.
6
6 Nhìn chung, ta không quan tâm nhiều tới trường hợp l 0 = 0 vì khi đó, các điều kiện cần không liên quan tới hàm mục tiêu mà chỉ liên quan tới các ràng buộc. Tuy vậy, việc sử dụng đẳng thức l 0 = 0, đôi khi khá tiện dụng khi xét các bài toán ở dạng chung. Thông thường, l 0 = 0 dù điều kiện chính quy không thỏa mãn. Hơn nữa, việc xác định trực tiếp đẳng thức l 0 = 0 trong nhiều trường hợp dễ dàng hơn so với việc kiểm tra các điều kiện chính quy tương ứng.
∈
0 fn+1(x) ≤ }
≤ = 0. Do đó, để nhân tử Lagrange l 0 6 6
Nói riêng, nếu hệ số l 0 = 0 phụ thuộc vào các ràng buộc được đưa vào trong hàm Lagrange, thì các ràng buộc đó được bỏ qua. Ví dụ như chúng ta không đưa ràng buộc x A vào trong hàm Lagrange của bài toán tối ưu lồi. Như đã nói, ràng buộc này có thể cho dưới dạng hàm như A = . Tuy nhiên, có thể xảy ra rằng, không có điểm x nào x { | thỏa mãn fi(x) < 0, (i = 1, . . . , n + 1). Nếu chúng ta đưa vào ràng buộc 0 trong hàm Lagrange, thì điều kiện Slater sẽ bị vi phạm, và fn+1(x) không thể đảm bảo rằng l 0 = 0, thì nên lựa chọn các ràng buộc đưa vào hàm Lagrange sao cho các điều kiện chính quy không bị vi phạm.
Cuối cùng, chúng ta chú ý rằng, định lý Kuhn-Tucker cho ta một quy tắc đơn giản để xác định dấu của nhân tử Lagrange tương ứng với ràng buộc bất đẳng thức. Trong bài toán cực tiểu, dấu của các nhân tử phải được chọn sao cho hàm Lagrange là lồi.
Tác giả đã cố gắng sắp xếp và trình bày vấn đề theo cách hiểu rõ ràng và trực quan, đưa ra các ví dụ và một số hình vẽ để minh họa cho nhiều khái niệm và sự kiện được đề cập tới trong luận văn.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Hy vọng luận văn này sẽ là một tài liệu tham khảo bổ ích cho những người không chuyên sâu về toán muốn tìm hiểu và vận dụng công cụ giải tích, đặc biệt là các phương pháp tối ưu trong chuyên môn của mình.
57
TÀI LIỆU THAM KHẢO
[1] A. D. Ioffe and V.M. Tikhomirov, Theory of extremal problems, NewYork
1979.
[2] D. G. Luenberger. Linear and Nonlinear Programming. Addison-Wesley,
2nd edition, 1984.
[3] Lagrange Multipliers, Com S 477/577.
[4] Đỗ Văn Lưu và Phan Huy Khải, Giải tích lồi, Nhà xuất bản khoa học
và kỹ thuật, 2000.
[5] Nguyễn Xuân Tấn và Nguyễn Bá Minh, Lý thuyết tối ưu không trơn,
Nhà xuất bản ĐHQGHN.
[6] Hoàng Tụy, Lý thuyết tối ưu, Viện toán học Hà Nội, 2007.
[7] Đỗ Phương Thảo, Nhân tử Lagrange cho bài toán quy hoạch lồi, Luận
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
văn cao học, 2005.
