pc_lee2010
New Member
Download miễn phí Luận văn Về nguyên lý nhân tử Lagrange
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
KẾT LUẬN .55
TÀI LIỆU THAM KHẢO .56
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
ái Nguyên16
Hình 3.
với gradient ∇h. Như vậy, tại (x∗,y∗) thì hai gradient ∇ f và ∇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{
h(x,y) = 0
∇ f +λ ∇h = 0. (1.5)
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,λ 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
L(x,y,λ ) = f (x,y)+λ h(x,y).
∇L=
∂ f
∂x +λ
∂h
∂x∂ f
∂y +λ
∂h
∂y
h(x,y)
T
= (∇ f +λ ∇h, h).
Suy ra ∇L= 0 do hệ phương trình phi tuyến (1.5).
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
17
Giá trị λ 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
h(x,y) = x
2
8 +
y2
2
−1 = 0.
Giải
Đầu tiên, ta xây dựng hàm Lagrange và tìm gradient của nó.
L(x,y,λ ) = xy+λ (x
2
8 +
y2
2
−1).
∇L(x,y,λ ) =
y+
λx
4
x+λ y
x2
8 +
y2
2 −1
= 0.
Từ đó dẫn đến ba phương trình
y+
λ x
4
= 0. (1.6)
x+λ y = 0. (1.7)
x2+4y2 = 8. (1.8)
Kết hợp (1.6) và (1.7) ta có
λ 2 = 4 suy ra λ =± 2.
Do đó x =± 2y. Thế phương trình này vào (1.8), ta được
y =± 1 suy ra 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).
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.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
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-
perbolas xy = c, với |c| tăng khi đường cong di chuyển ra xa gốc tọa độ.
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.
Cho h = (h1, . . . ,hm)T là một hàm số từ Rn vào Rm, trong đó m ≤ n.
Xét bài toán tối ưu
(P3)
{
min f (x)
h(x) = 0.
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.
• Một đường cong trên S là tập các điểm x(t) ∈ S, với a ≤ t ≤ b.
• Đường cong gọi là khả vi nếu tồn tại dxdt , kí hiệu x′ := dxdt .
• Đường cong gọi là đi qua điểm x nếu x = x(t) với a ≤ t ≤ b.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
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 dxdt (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 ∇h1(x), . . . ,∇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 = {y| ∇h(x)y = 0}.
trong đó ma trận
∇h =
∇h1...
∇hm
.
Các hàng của ma trận ∇h(x) là các vectơ gradient ∇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 ⊂ 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
x′(t) thỏa mãn ∇h(x)x′(t) 6= 0 thì đường cong đó không nằm trên S.
Để chứng minh M ⊂ 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
h(x+ ty+∇h(x)T u(t)) = 0. (1.9)
trong đó t cố định, và u(t) ∈ Rm là ẩn. Đây là một hệ phi tuyến với m
phương trình và m ẩn, được biểu diễn theo tham số t.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
20
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×m
∇h(x)∇h(x)T .
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 −a ≤
t ≤ a.
Đường cong x(t) = x+ ty+∇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ó
0 = ddt h(x(t))
∣∣∣
t=0
= ∇h(x)y+∇h(x)∇h(x)T u′(0).
Theo định nghĩa của y, ta có ∇h(x)y= 0. Do đó, khi ∇h(x)∇h(x)T là không
suy biến, ta suy ra u′(0) = 0. Như vậy
x′(0) = y+∇h(x)T u′(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 ∀y ∈ Rn thỏa mãn ∇h(x)y = 0, ta có
∇ 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, x′(0) = y, và h(x(t)) = 0
với ∀t ∈ [−a,a] , a > 0.
Vì x là điểm chính quy nên không gian tiếp xúc là
M = {y|∇h(x)y = 0}.
Do đó, nếu x là cực trị địa phương thì
d
dt f (x(t))
∣∣∣
t=0
= 0 hay ∇ f (x)y = 0.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
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
quy của các ràng buộc h j(x) = 0, j = 1, . . . ,m. Khi đó, tồn tại λ ∈ Rm sao
cho
∇ f (x)+λ T ∇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 ∇ f (x)y
∇h(x)y = 0.
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 λ ∈ Rm sao cho
∇ f (x)+λ T ∇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
(m+n) phương trình với (m+n) ẩn x và λ . Do đó, ta có thể xác định được
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)
{
max xyz
xy+ yz+ zx = c2 . (1.10)
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
L(x,y,z,λ ) = xyz+λ (xy+ yz+ zx− c
2
).
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
22
Từ điều kiện cần cấp một ta thấy rằng
yz+λ (y+z)= 0. (1.11)
xz+λ (x+z)= 0. (1.12)
xy+λ (x+y)= 0. (1.13)
Do đó
(xy+ yz+ xz)+2λ (x+ y+ z) = 0.
Từ ràng buộc (1.10) ta có
c
2
+2λ (x+ y+ z) = 0.
Suy ra λ 6= 0.
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
λ (x− y)z = 0.
Tương tự cho (1.12) và (1.13) ta được
λ (y− z)x = 0.
Do các biến không thể bằng không nên
x = y ...