Tập lồi và hàm lồi
Tập lồi
Tập S ⊂ R n được gọi là tập lồi nếu mọi đoạn thẳng nối hai điểm bất kỳ trong S đều nằm trong S, tức là S lồi khi và chỉ khi x = λx 1 + (1−λ)x 2 ∈ S với ∀λ ∈ [0,1] và ∀x 1 , x 2 ∈ S Ngoài ra, siêu phẳng H được định nghĩa là H :={x : p T x = a, p ∈ R n \{0}, a∈ R}, chia không gian thành hai nửa không gian H + := {x :p T x ≥ a} và H − := {x : p T x ≤ a}.
Ví dụ 1.1.1 Ta có một số ví dụ về tập lồi:
• Mỗi hình cầu trong R n là tập lồi.
• Các siêu phẳng H :={x : p T x = a, p ∈ R n \{0}, a ∈ R} là các tập lồi.
• Các nữa không gian H + := {x : p T x ≥ a, p ∈ R n \{0}, a ∈ R} và
• Tập D = {(x, y, z) ∈ R 3 : x ≥ 0, y ≥ 0, z ≥ 0, x +y +z −1 ≤ 0} là khối tứ diện với các đỉnh O(0,0,0), A(1,0,0), B(0,1,0), C(0,0,1) và là tập lồi. Định nghĩa 1.1.3 Cho x 1 , x 2 , , x k ∈ R n , ta gọi x k
Tập hợp các tổ hợp lồi của các điểm x₁, x₂, , xₖ, được ký hiệu là P i=1 λ i = 1, tạo thành bao lồi của các điểm này Bao lồi là một khái niệm quan trọng trong hình học, thể hiện tất cả các tổ hợp lồi có thể được hình thành từ các điểm đã cho.
Ví dụ 1.1.2 Một số ví dụ về bao lồi:
• Bao lồi của ba điểm không thẳng hàng là miền giới hạn bởi tam giác với ba đỉnh là ba điểm đó.
• Bao lồi của một hình vành khăn là hình tròn.
• Bao lồi của mặt cầu là hình cầu. Định nghĩa 1.1.4 Một tập S ⊂ R n được gọi là nón nếu
Nón lồi là nón có tính chất đồng thời là tập lồi, trong khi nón nhọn là nón không chứa đường thẳng Nếu nón này là một đa diện lồi, chúng ta gọi nó là nón lồi đa diện.
Một số tính chất cơ bản của tập lồi được liệt kê trong các mệnh đề sau: Mệnh đề 1.1.1 Giao của các tập lồi là tập lồi.
Mệnh đề 1.1.2 Tổng đại số hữu hạn của các tập lồi là tập lồi.
Mệnh đề 1.1.3 Tích đề các của các tập lồi là tập lồi.
Mệnh đề 1.1.4 Ảnh và tạo ảnh của các tập lồi qua ánh xạ tuyến tính là các tập lồi.
Mệnh đề 1.1.5 Bao lồi của một tập hợp là tập lồi nhỏ nhất chứa tập đó.
Ký hiệu bao đóng của S là S, miền trong của S là S o , biên của S là
∂S. Định lí 1.1.1 Cho S ⊂ R n là tập lồi, S o 6= ∅ ∀x 1 ∈ S, x 2 ∈ S o , ta luôn có x =λx 1 + (1−λ)x 2 ∈ S o ,∀λ ∈ (0,1).
Từ định lí trên ta có thể suy ra các hệ quả sau:
Hệ quả 1.1.1 Nếu S là tập lồi và S o khác rỗng thì S o cũng là tập lồi.
Hệ quả 1.1.2 Nếu S là tập lồi thì S cũng là tập lồi.
Nếu S là một tập lồi và miền trong của S không rỗng, thì bao đóng của miền trong S trùng với bao đóng của S, tức là S o ≡ S Hơn nữa, bao đóng của S cũng tương đương với bao đóng của miền trong của S, ký hiệu là (S) o ≡ S o Định nghĩa về tập affine được đưa ra cho một tập không rỗng S ⊂ R n, với điều kiện cụ thể mà tập này phải thỏa mãn.
Mọi tập affine đều là tập lồi, có nghĩa là với bất kỳ hai điểm nào trong tập S, đường thẳng nối hai điểm đó luôn nằm trong S.
Siêu phẳng tách, siêu phẳng tựa của tập lồi
Ký hiệu d(x, y) là khoảng cách giữa hai điểm x, y ∈ R n , tức là d(x, y) s n
(x i −y i ) 2 , trong đó x = (x 1 , x 2 , , x n ), y = (y 1 , y 2 , , y n ). Định lí 1.1.3 Xét tập lồi, đóng, không rỗng S ⊂ R n và một điểm y ∈
Trong không gian R^n, với y không thuộc S, tồn tại duy nhất một điểm x_o thuộc S sao cho khoảng cách d(x_o, y) là nhỏ nhất, tức là d(x_o, y) = min_{x∈S} d(x, y) Điểm x_o được định nghĩa là điểm cực tiểu của S đối với y Hơn nữa, x_o sẽ là điểm cực tiểu của S đối với y nếu và chỉ nếu nó nằm trong S.
(x−x o ) T (x o −y) ≥ 0,∀x ∈ S. Định nghĩa 1.1.6 Xét hai tập hợp không rỗng S 1 , S 2 ⊂R n Siêu phẳng
H := {x : p T x = a, p ∈ R n , a ∈ R} được gọi là siêu phẳng tách S 1 và S 2 nếu p T x ≥ a,∀x ∈ S 1 và p T x ≤ a,∀x∈ S 2
Hơn nữa, nếu S 1 ∩S 2 * H thì H được gọi là siêu phẳng tách chỉnh S 1 và
H được gọi là siêu phẳng tách chặt S 1 và S 2 nếu p T x > a,∀x ∈ S1 và p T x < a,∀x ∈ S2.
H được gọi là siêu phẳng tách mạnh S1 và S2 nếu tồn tại một giá trị dương > 0 sao cho p^T x ≥ a+ với mọi x thuộc S1 và p^T x ≤ a+ với mọi x thuộc S2 Định lý 1.1.4 khẳng định rằng, với tập lồi, đóng, không rỗng S ⊂ R^n và một điểm y ∈ R^n không thuộc S, sẽ tồn tại một vector p ∈ R^n \{0} và một giá trị a ∈ R sao cho p^T y > a và p^T x ≤ a với mọi x thuộc S.
Hệ quả 1.1.4 Mỗi tập lồi, đóng, không rỗng là giao của tất cả các nửa không gian chứa tập đó.
Hệ quả 1.1.5 Cho S ⊂ R n , S 6=∅ và y ∈ R n sao cho y /∈ S Lúc đó, các mệnh đề sau luôn đúng:
1 Tồn tại một siêu phẳng tách chặt S và y.
2 Tồn tại một siêu phẳng tách mạnh S và y.
4 ∃p ∈ R n \{0}: p T y < inf{p T x, x ∈ S}. Định lí 1.1.5 Cho A là ma trận cấp m×n, c ∈ R n Khi đó, chỉ có một trong hai hệ sau có nghiệm:
Từ Định lí 1.1.5 ta có thể suy ra các hệ quả sau:
Hệ quả 1.1.6 Cho A là ma trận cấp m×n, c ∈ R n Khi đó, chỉ có một trong hai hệ sau có nghiệm:
Hệ quả 1.1.7 Cho A là ma trận cấp m × n, B là ma trận cỡ 1 × n, c ∈ R n Lúc đó chỉ có một trong các hệ sau có nghiệm:
A T y +B T z = c y ≥ 0, y, z ∈ R m Định nghĩa 1.1.7 Cho tập không rỗngS ∈ R n , x ∈ ∂S Vớip ∈ R n \{0}, siêu phẳng H := {x ∈ R n : p T (x−x) = 0} được gọi là siêu phẳng tựa của
S tại x nếu một trong hai trường hợp sau luôn xảy ra:
Siêu phẳng tựa gọi là siêu phẳng tựa chỉnh nếu S * H Định lí 1.1.6 Cho tập lồi, không rỗng S ⊂ R n , x ∈ ∂S Lúc đó tồn tại một siêu phẳng tựa của S tại x, tức là
Hệ quả 1.1.8 Cho tập lồi, không rỗng S ⊂ R n , x /∈ S Lúc đó ∃p ∈
Định lý 1.1.7 khẳng định rằng, với hai tập lồi không rỗng và không giao nhau S1 và S2 trong không gian Rn, tồn tại một siêu phẳng tách H có thể phân chia hai tập này Cụ thể, có một vector p thuộc Rn \{0} sao cho giá trị nhỏ nhất của pT x với x thuộc S1 lớn hơn hoặc bằng giá trị lớn nhất của pT x với x thuộc S2.
Hệ quả 1.1.9 Cho hai tập lồi, không rỗng S 1 , S 2 ⊂R n thỏa điều kiện
S 1 o 6= ∅, S 1 ∩S 2 o 6= ∅, lúc đó tồn tại p∈ R n \{0} sao cho inf{p T x, x ∈ S1} ≤ sup{p T x, x ∈ S2}.
Hàm lồi và một số tính chất của hàm lồi
Định nghĩa 1.1.8 Cho tập lồi, không rỗng S ⊂ R n , hàm số f : S −→ R
• f được gọi là hàm lồi trên S nếu với bất kỳ hai điểm x 1 , x 2 ∈ S, ta có f(λx 1 + (1−λ)x 2 ) ≤ λf(x 1 ) + (1−λ)f(x 2 ),∀λ ∈ [0,1].
• f được gọi là hàm lồi chặt trên S nếu với bất kỳ hai điểm x1, x2 ∈
• f được gọi là hàm lồi mạnh trên S với hệ số η > 0 nếu với bất kỳ hai điểm x 1 , x 2 ∈ S, ta có f(λx 1 + (1−λ)x 2 ) ≤λf(x 1 ) + (1−λ)f(x 2 )− 1
Chú ý rằng, hàm f được gọi là hàm lõm trên S nếu −f là hàm lồi trên
Ví dụ 1.1.3 Một số hàm lồi, lõm thường gặp.
1 Hàm f(x) = x 2 là hàm lồi trên R Thật vậy, ∀x 1 , x 2 ∈ R, λ 1 , λ 2 ≥
2 Hàm f(x) = sinx là hàm lõm trên [0, π].
Mệnh đề 1.1.6 Cho f, g là các hàm lồi trên các tập lồi tương ứng A và
B Khi đó, αf +βg,∀α, β ∈ R + và max{f, g} là các hàm lồi trên A∩B. Định nghĩa 1.1.9 Xét hàm lồi f : S −→ R Lúc đó tập
S α := {x ∈ S :f(x) ≤ α, α ∈ R}, được gọi là tập mức dưới α tương ứng với hàm lồi f.
Cho Sα là tập mức dưới tương ứng với hàm lồi f : S −→ R Khi đó,
Vậy x ∈ S α Điều này có nghĩa là tập mức dưới S α là tập lồi Ta có mệnh đề sau:
Mệnh đề 1.1.7 ∀α ∈ R, S α lồi nếu f là hàm lồi.
Mệnh đề 1.1.8 Nếu f : S −→ R là hàm lồi thì f là hàm liên tục trên
S o Định lí 1.1.8 Cho f : S −→ R là một hàm khả vi trên tập lồi, mở
1 Hàm f là hàm lồi khi và chỉ khi f(x) +h∇f(x), y −xi ≤ f(y),∀x, y ∈ S.
2 Hàm f là hàm lồi chặt khi và chỉ khi f(x) +h∇f(x), y−xi < f(y),∀x, y ∈ S, x 6= y.
3 Hàm f là hàm lồi mạnh với hệ số η > 0 khi và chỉ khi f(x) +h∇f(x), y −xi+ η 2 kx−yk 2 ≤f(y),∀x, y ∈ S. Định lí 1.1.9 Cho f : S −→ R khả vi liên tục đến cấp hai trên tập lồi, mở S ⊂R n Khi đó:
1 Hàm f là hàm lồi trên S khi và chỉ khi ma trận Hessian H(x) của f(x) là ma trận nửa xác định dương trên S, tức là: y T H(x)y ≥0,∀x ∈ S,∀y ∈ R n
2 Hàm f là hàm lồi chặt trên S khi và chỉ khi ma trận Hessian H(x) của f(x) là ma trận xác định dương trên S, tức là: y T H(x)y > 0,∀x∈ S,∀y ∈ R n \{0}.
3 Hàm f là hàm lồi mạnh trên S với hệ số η > 0 khi và chỉ khi ma trận Hessian H(x) của f(x) thỏa mãn y T H(x)y ≥ ηkyk 2 ,∀x ∈ S,∀y ∈ R n
Đối với hàm một biến xác định trên tập lồi S ⊂ R, hàm f được coi là lồi chặt khi đạo hàm bậc hai f''(x) > 0 cho mọi x ∈ S, và là lồi mạnh với hệ số η > 0 khi f''(x) ≥ η cho mọi x ∈ S Ngoài ra, với tập mở không rỗng S ⊂ R^n và hàm f: S → R khả vi, đạo hàm tại x ∈ S theo hướng d ∈ R^n \{0} được định nghĩa bởi f'(x, d) = lim λ→0 + (f(x + λd) - f(x)) / λ = h∇f(x), d i.
Ví dụ 1.1.4 Xét hàm hai biếnf(x 1 , x 2 ) = x 2 1 +x 2 2 Ta có đạo hàm f 0 (x, d) tại điểm x = (1,1) theo hướng d = (2,1/2) được tính như sau f 0 (x, d) = lim λ→0 +
Đối với hàm lồi f: S → R, với S ⊂ R^n là tập lồi không rỗng, tại điểm (1,1), ta có đạo hàm theo hướng f 0 (x, d) = 5 Định lý 1.1.10 khẳng định rằng, với mọi x ∈ S và hướng d ∈ R^n sao cho x + λd ∈ S với λ > 0 đủ nhỏ, luôn tồn tại đạo hàm theo hướng f 0 (x, d) = lim λ→0 + (f(x + λd) − f(x)) / λ.
Chúng ta đang xem xét hàm f: S ⊂ R^n → R với mục tiêu tối ưu hóa hàm f(x) khi x thuộc S Bài toán đặt ra là tìm giá trị tối thiểu (hoặc tối đa) của hàm f, cụ thể là min x∈S f(x) hoặc max x∈S f(x) Đặc biệt, nếu f đạt giá trị lớn nhất tại x₀, thì -f sẽ đạt giá trị nhỏ nhất tại x₀ Do đó, trong các phần tiếp theo của luận văn, chúng tôi sẽ tập trung chủ yếu vào bài toán tối thiểu hóa f(x).
Ví dụ 1.1.5 minf(x 1 , x 2 ) = (x 1 − 3 2 ) 2 + (x 2 −5) 2 , với ràng buộc
Dễ thấy miền ràng buộc S là tập lồi, S là tổ hợp lồi của bốn điểm
Các khái niệm cơ bản của bài toán tối ưu
Phát biểu bài toán tối ưu
Bài toán tối ưu tổng quát có dạng chính tắc như sau
Nếu hàm mục tiêu f(x) hoặc ít nhất một trong các hàm ràng buộc là phi tuyến thì chúng ta có bài toán tối ưu phi tuyến.
Nếu S ≡ R^n và các ràng buộc có tập nghiệm là R^n, thì bài toán tối ưu là không ràng buộc Ngược lại, nếu S hoặc tập nghiệm của các điều kiện ràng buộc là tập con thực sự của R^n, thì bài toán tối ưu là có ràng buộc Bên cạnh đó, còn có một số trường hợp đặc biệt của bài toán tối ưu.
1 Bài toán tối ưu chỉ có ràng buộc đẳng thức:
2 Bài toán tối ưu chỉ có ràng buộc bất đẳng thức:
Ví dụ 1.2.1 Cho các bài toán sau: min f(x) = 2x 2 1 + 3x 2 2 + 4x 1 x 2 −6x 1 −3x 2 , (1.4) và
Ta có Bài toán (1.4) là bài toán tối ưu phi tuyến không có ràng buộc,
Bài toán (1.5) là bài toán tối ưu phi tuyến có ràng buộc. Định nghĩa 1.2.1 Mỗi điểm thuộc tập
Tập hợp D := {x ∈ S : h(x) = 0, g(x) ≤ 0} được định nghĩa là một phương án khả thi của Bài toán (1.1) Điểm x ∈ D được coi là phương án tối ưu địa phương nếu tồn tại lân cận N của x sao cho f(x) ≤ f(x), ∀x ∈ N ∩ D Ngược lại, x ∈ D là phương án tối ưu toàn cục nếu f(x) ≥ f(x), ∀x ∈ D Theo Định lý 1.2.1, nếu D là tập lồi và f là hàm lồi, thì mọi phương án tối ưu địa phương đều là tối ưu toàn cục; nếu hàm f lồi chặt, phương án tối ưu toàn cục (nếu có) là duy nhất Cuối cùng, một vectơ d ∈ R n \{0} được gọi là hướng chấp nhận được của D tại x nếu tồn tại số thực λ 0 > 0 sao cho x + λd ∈ D, ∀λ ∈ (0, λ 0 ].
Tập hợp tất cả các hướng chấp nhận được của D tại x được gọi là nón các hướng chấp nhận được của D tại x, ký hiệu là D x Nếu f là hàm khả vi trên tập mở chứa D và x là cực tiểu địa phương của f trên D, thì điều kiện d T ∇f(x) ≥ 0 cho mọi d ∈ D x sẽ được thỏa mãn Điểm x ∈ D được gọi là điểm dừng của f trên D nếu d T ∇f(x) ≥ 0 cho mọi d ∈ D x Cần lưu ý đến một số trường hợp đặc biệt của điểm dừng.
1 Nếu điểm dừng x ∈ D o thì D x = R n nên ∇f(x) = 0.
2 Theo Định lí 1.2.2 thì mỗi điểm cực tiểu địa phương đều là điểm dừng. Điều ngược lại nói chung là không đúng Tuy nhiên, đối với bài toán tối ưu lồi thì điểm dừng chính là điểm cực trị. Định lí 1.2.3 Cho D là một tập lồi, f là hàm khả vi trên tập mở chứa
D Khi đó, x là điểm cực tiểu của f trên D khi và chỉ khi x là điểm dừng của f trên D.
Điều kiện tối ưu Kuhn-Tucker
Điều kiện tối ưu Kuhn-Tucker đóng vai trò quan trọng trong lý thuyết tối ưu phi tuyến, cung cấp nền tảng cho nhiều phương pháp tối ưu hóa phi tuyến khác nhau.
Xét Bài toán (1.3), lúc đó hàm Lagrange tương ứng với bài toán trên có dạng
Vì λ i ≥ 0, i = 1, , r, đặt s 2 i = λ i , i = 1, , r hàm Lagrange được viết lại dưới dạng
P i=1 s 2 i g i (x) với s = (s 1 , s 2 , , s m ). Điểm (x, λ) = (x, s 2 ) là điểm dừng của hàm Lagrange nếu thỏa mãn hệ điều kiện sau đây
Định lý 1.2.4 khẳng định rằng nếu x là phương án tối ưu cho bài toán tối ưu phi tuyến với hàm mục tiêu f(x) và các hàm ràng buộc gi(x) khả vi, thì tồn tại một tập hợp chỉ số I = {i : gi(x) = 0} Giả sử rằng hệ {∇gi(x)}i∈I là độc lập tuyến tính, thì sẽ có một vectơ λ ∈ R^r với λ ≥ 0, sao cho (x, λ) là điểm dừng của hàm Lagrange.
Việc xem xét các điểm dừng của hàm Lagrange là rất quan trọng Đối với các vectơ x ∈ R n, nếu tồn tại các vectơ λ ∈ R r với λ ≥ 0, thì (x, λ) sẽ là điểm dừng của hàm Lagrange, từ đó cho phép tìm kiếm các phương án tối ưu địa phương cho Bài toán (1.3) Hơn nữa, theo Định lý 1.2.1, nếu Bài toán (1.3) là bài toán quy hoạch lồi, khả năng tìm được phương án tối ưu toàn cục trong số các điểm dừng là rất cao.
Xét hệ điều kiện bao gồm điều kiện điểm dừng của hàm Lagrange và điều kiện ràng buộc của Bài toán (1.3)
Hệ điều kiện trên được gọi làhệ điều kiện Kuhn-Tucker của Bài toán (1.3).
Ví dụ 1.2.2 Xét bài toán tối ưu phi tuyến
Ta có bài toán tối ưu lồi với hàm Lagrange
F(x, λ) = (x 1 + 1) 2 + (x 2 −1) 2 +λ 1 (x 1 −2) +λ 2 (x 2 −1)−λ 3 x 1 −λ 4 x 2 , trong đó λ i ≥ 0,∀i = 1, ,4 Điều kiện Kuhn-Tucker của bài toán này như sau
Từ (1.6a) và (1.6e) ta có x1[2(x1 + 1) +λ1] = 0⇒ x1 = 0, nên theo (1.6c) có λ1 = 0.
Từ (1.6b) và (1.6f) ta có x 2 [2(x 2 −1) +λ 2 ] = 0, nên ta có
• Nếu 2(x2 −1) +λ2 = 0 thì từ (1.6d) ta có x2 = 1, λ2 = 0.
Khi thay λ1 = λ2 = 0 vào phương trình (1.6b), ta nhận được λ4 = 2(x2 − 1) Do λ4 ≥ 0, trong hai điểm (0,0) và (0,1), chỉ có điểm (0,1) thỏa mãn điều kiện dừng của hàm Lagrange Do đó, phương án tối ưu toàn cục là x1 = 0, x2 = 1 với giá trị tối thiểu f min = 1 Theo Định lý 1.2.5, xét Bài toán (1.3) với x thuộc S, ký hiệu I = {i : g i (x) = 0} Giả sử các hàm f và g i, i ∈ I khả vi tại x và g i liên tục tại x với mọi i không thuộc I Hơn nữa, giả sử {∇g i (x)} i∈I là hệ độc lập tuyến tính Khi đó, nếu x là nghiệm tối ưu địa phương của Bài toán (1.3), thì với mọi i ∈ I, tồn tại u i ∈ R và u i ≥ 0.
Hơn nữa, nếu ∀i /∈ I, gi cũng khả vi tại x thì ∀i = 1, r,∃u i ∈ R, ui ≥ 0 sao cho
P i=1 ui∇g i (x) = 0 u i g i (x) = 0,∀i = 1, r Định lí 1.2.6 Xét Bài toán (1.3) Cho x ∈ X, ký hiệu I := {i : gi(x) 0}, giả sử các hàm f, g i , i ∈ I là các hàm lồi, khả vi tại x Lúc đó, nếu
∇f(x) +P i∈I u i ∇g i (x) = 0, thì x là điểm cực tiểu toàn cục của Bài toán (1.3).
Bây giờ chúng ta áp dụng các kết quả trên cho Bài toán tổng quát (1.1). Trước hết, chúng ta thấy rằng hệ điều kiện g(x) ≤ 0 h(x) = 0 ⇔
Do đó, hàm Lagrange cho Bài toán (1.1) có dạng:
F(x, λ, à + , à − ) =f(x) +λg(x) +à + h(x)−à − h(x), trong đú λ, à + , à − ≥ 0. Điều kiện Kuhn-Tucker của bài toán như sau
−h(x) ≤ 0 λ, à + , à − ≥ 0. Đặt à = à + −à − , hàm Lagrange trở thành
Do đó, điều kiện Kuhn-Tucker của bài toán được viết lại như sau
Đối với Bài toán (1.1), khi các ràng buộc là bất đẳng thức và đẳng thức, ta có Định lý 1.2.7 (Điều kiện cần và đủ) Xét x ∈ S với I := {i : g i (x) = 0} Giả sử các hàm f, g i (với i ∈ I) khả vi tại x, g i liên tục tại x với mọi i không thuộc I, và các hàm h i khả vi liên tục tại x cho mọi i từ 1 đến m Hơn nữa, giả sử rằng các vectơ {∇g i (x)} với i ∈ I và {∇h i (x)} với i từ 1 đến m là độc lập tuyến tính.
Lúc đó, nếu x là điểm cực tiểu địa phương của Bài toán (1.1) thì
Nếu ngoài ra, các hàm g i : R n −→ R,∀i /∈ I cũng khả vi tại x ∈ S thì điều kiện Kuhn-Tucker ( điều kiện cần) để x ∈ S là phương án tối ưu có thể được viết như sau
Ngược lại, cho x ∈ S và các điều kiện sau đây được thỏa mãn
• Các hàm f, gi,∀i ∈ I là các hàm lồi và khả vi tại x.
• ∀i : v i > 0, các hàm h i là các hàm lồi, còn ∀i : v i < 0, các hàm −h i là các hàm lồi.
Lúc đó, x là điểm cực tiểu toàn cục của Bài toán (1.1).
Ví dụ 1.2.3 Xét bài toán quy hoạch lồi
Vậy điều kiện Kuhn-Tucker của bài toán như sau
Giải hệ phương trình, bất phương trình trên ta được các nghiệm (4, 0 ),
5,8 5 là phương án tối ưu của bài toán.
Một số phương pháp giải bài toán tối ưu phi tuyến có ràng buộc và ứng dụng
Trong chương này, luận văn giới thiệu hai phương pháp cơ bản để giải quyết Bài toán (1.1), cụ thể là phương pháp Lagrange và phương pháp hàm phạt điểm, bao gồm cả hàm phạt điểm trong và ngoài Nội dung được tham khảo từ các tài liệu [6], [7], [8], [9] Chúng tôi sẽ tập trung vào việc trình bày các phương pháp cùng với các ví dụ minh họa để làm rõ hơn các phương pháp này.
Phương pháp Lagrange
Phương pháp Lagrange cho bài toán tối ưu phi tuyến tổng quát
Cho Bài toán (1.1) Hàm Lagrange của bài toán được xác định như sau
P j=1 à j g j (x), với λ i ∈ R, i= 1, , m, à j ∈ R, à j ≥ 0, j = 1, , r Từ Định lý 1.2.4 ta cú, nếu x ∗ ∈ D là một nghiệm của (1.1) thỡ tồn tại λ ∗ , à ∗ thỏa cỏc điều kiện sau:
Ta có thể tóm tắt quá trình giải Bài toán (1.1) bằng phương pháp Lagrange như sau
- Bước 1: Thiết lập hàm Lagrange
- Bước 2: Giải hệ phương trình
-Bước 3: Thay các nghiệm vừa tìm được vào hàm mục tiêu để tìm f min
Bài tập ứng dụng
Bài tập 2.1.1 Xét bài toán
P i=1 x 2 i +λ 1 (x 1 + 2x 2 +x 3 −1) +λ 2 (x 3 −x 4 +x 5 −3) Điểm dừng của hàm Lagrange là nghiệm của hệ phương trình
Mặt khác ta có hệ ràng buộc x1 + 2x2 +x3 −1 = 0 x 3 −x 4 +x 5 −3 = 0 (2.2)
Một nhà máy sản xuất đồ gia dụng có chi phí công nhân 50.000 đồng mỗi giờ và giá nguyên liệu là 1.700.000 đồng mỗi tấn Lợi nhuận của nhà máy được mô hình hóa theo một công thức nhất định.
R(h, s) = 2.10 6 h 2/3 s 1/3 h: số giờ làm việc, s: số tấn nguyên liệu.
Hãy tính lợi nhuận lớn nhất biết tổng chi phí là 200 000 000 đồng.
Tổng chi phí cho sản xuất được tính theo công thức
C(h, s) = 50000h+ 1700000s tổng kinh phí là 200 000 000 đồng, nên ta có ràng buộc g(h, s) = 50000h+ 1700000s−200000000 = 0 (2.3)
Ta có thể phát biểu bài toán tối ưu tương ứng như sau min [−R(h, s)]
L(h, s, λ) = −2.10 6 h 2/3 s 1/3 +λ(5.10 4 h+ 17.10 5 s−2.10 8 ). Điểm dừng của hàm Lagrange là nghiệm của hệ phương trình sau
Bài tập 2.1.3 Một tổ hợp gồm 3 máy phát cần sinh ra lượng điện là 952
Để tìm phương án phát điện tiết kiệm chi phí nhất trong một giờ, chúng ta cần xem xét chi phí của từng máy phát điện theo các công thức: f1 = x1 + 0,0625x2^2 (đô la/giờ), f2 = x2 + 0,125x2^2 (đô la/giờ), và f3 = x3 + 0,25x2^3 (đô la/giờ) Ở đây, xi (i = 1, 2, 3) là lượng điện phát ra của máy phát thứ i trong một giờ Việc tối ưu hóa các biến này sẽ giúp giảm thiểu chi phí tổng thể cho quá trình phát điện.
Giải: Đặt f(x) = x 1 + 0,0625x 2 1 +x 2 + 0,125x 2 2 +x 3 + 0,25x 2 3 , ta có thể mô hình hóa bài toán trên như sau: minf(x) x1 +x2 +x3 −952 = 0.
Hàm Lagrange của bài toán
L(x, λ) = x 1 +0,0625x 2 1 +x 2 +0,125x 2 2 +x 3 +0,25x 2 3 +λ(x 1 +x 2 +x 3 −952) Điểm dừng của hàm Lagrange là nghiệm của hệ phương trình
0,5x 3 +λ+ 1 = 0 kết hợp với điều kiện x1 + x2 + x3 − 952 = 0 ta được x1 = 544, x2 272, x 3 = 136.
Vậy, phương án phát điện tiết kiệm nhất có chi phí là 33320 ( $/ giờ).
Bài tập 2.1.4 Giải bài toán sau:
Giải: Ta có hàm Lagrange của bài toán đã cho
+λ 1 (x 1 +x 2 −2)−λ 2 x 1 −λ 3 x 2 trong đó λ 1 , λ 2 , λ 3 ≥ 0. Điểm dừng của hàm Lagrange là nghiệm của hệ phương trình
⇒4(x 1 −x 2 ) + (λ 3 −λ 2 ) = 0 (2.5) Nếu x1 = 0 từ ràng buộc x1 + x2 = 2 ta có x2 = 2 ⇒ λ3 = 0 thay vào (2.5) ta có λ 2 = −8 không thỏa mãn λ 2 ≥0.
Tương tự ta có x 2 6= 0 Do đó, λ 2 = λ 3 = 0 ⇒x 1 = x 2 = 1.
Vậy, nghiệm tối ưu của bài toán là(1,1), f min = 1
Bài tập 2.1.5 (British Mathematical Olynpiad 1986) Cho các số thực a, b, c thỏa mãn a+b+c = 0 và a 2 +b 2 +c 2 = 6 Tìm giá trị lớn nhất của biểu thức
Giải: Ta có thể phát biểu bài toán trên theo dạng bài toán tối ưu phi tuyến có ràng buộc như sau
Hàm Lagrange của bài toán trên xác định như sau:
L(a, b, λ 1 , λ 2 ) = a 2 b+b 2 c+c 2 a+λ 1 (a+b+c) +λ 2 (a 2 +b 2 +c 2 −6). Điểm dừng của hàm Lagrange là nghiệm của hệ phương trình
Cộng theo vế các phương trình của hệ trên ta được b(a+c)+a(b+c)+c(a+b)+(a 2 +b 2 +c 2 )+3λ1+2λ2(a+b+c) = 0 ⇒ λ1 = 0, thế vào hệ phương trình (2.6) ta được
Nếu a = 0 thì từ ràng buộc a+b+c = 0 a 2 +b 2 +c 2 −6 = 0, ta cób 2 = c 2 = 3 nên A = 3√
3 Tương tự cho các trường hợp b = 0 và c = 0.
Nếu abc ≠ 0, từ hệ phương trình (2.7) ta có các biểu thức a² + 2bc = b² + 2ac = c² + 2ab = -2λ² (2.8) Điều này chính là điều kiện để dấu "=" xảy ra trong bất đẳng thức Cauchy-Schwarz Do đó, chúng ta sẽ tiến hành chứng minh bài toán này.
Theo bất đẳng thức Cauchy-Schwarz ta có
Mặt khác ta có a(a 2 + 2bc) +b(b 2 + 2ac) +c(c 2 + 2ab) = 3(a 2 b+b 2 c+c 2 a), và
(a 2 + 2bc) 2 + (b 2 + 2ac) 2 + (c 2 + 2ab) 2 = 2(ab+bc+ca) 2 + (a 2 +b 2 +c 2 ) 2 = 54
Dấu "=" xảy ra khi a = 2 cos2π
Bài tập 2.1.6 Cho a, b, c, d là các số thực dương thỏa a+b+c+d = 1. Chứng minh rằng abc+bcd+cda+dab ≤ 176
27. Giải: Đặt f(a, b, c, d) = abc+bcd+cda+dab− 176
Ta có thể chứng minh bất đẳng thức đã cho bằng cách giải bài toán tối ưu phi tuyến sau
max abc+bcd+cda+dab− 176
27 abcd +λ 1 (a+b+c+d−1)−λ 2 a−λ 3 b−λ 4 c−λ 5 d. Điểm dừng của hàm Lagrange là nghiệm của hệ phương trình
Từ hệ trên ta có λ1 = −(bc+cd+db) + 176
Thiết lập tương tự ta có hệ phương trình
27 bd) = 0. Kết hợp với ràng buộc a+b+c+d = 1 ta có hệ phương trình
Giải hệ phương trình trên ta được a = b = c = d= 1
Từ đó ta có điều cần chứng minh.
Bài tập tham khảo: Áp dụng phương pháp Lagrange để giải các bài toán sau
Bài tập 2.1.7 Cho a, b, c là các số thực thỏa a+b+c > 0 Chứng minh rằng a 3 +b 3 +c 3 ≤ (a 2 +b 2 +c 2 ) 2/3 + 3abc.Bài tập 2.1.8 (Bất đẳng thức Schur) Cho a, b, c ≥0 Chứng minh rằng a 3 +b 3 +c 3 + 3abc ≥ ab(a+b) +bc(b+c) +ca(c+a).
Bài tập 2.1.9 Cho x 1 , x 2 , , x n > 0 thỏa x 1 x 2 x n = 1 Chứng minh rằng
Bài tập 2.1.10 Cho a, b, c, x, y, z là các số thực thỏaax+by+cz =xyz. Chứng minh x+y +z ≥ q 4(a+b+c) +p
Bài tập 2.1.11 Cho x, y, z là các số thực thỏa 2x 3 + 2y 3 +z 3 = 4 Tìm giá trị nhỏ nhất của biểu thức
Bài tập 2.1.12 Cho x, y, z là các số thực không âm thỏa x+y +z = 3. Tìm giá trị nhỏ nhất của biểu thức
Phương pháp hàm phạt điểm ngoài
Phương pháp hàm phạt điểm ngoài
Xét Bài toán (1.1), hàm phạt điểm ngoài được xác định như sau p(x) m
X i=1 ψ(h i (x)), (2.9) với φ, ψ là các hàm liên tục trên R thỏa φ(y) = 0,∀y ≤0 φ(y) > 0,∀y > 0 ψ(y) = 0,∀y = 0 ψ(y) > 0,∀y 6= 0 (2.10) Một ví dụ cho các hàm φ, ψ thỏa mãn các điều kiện trên là φ(y) = (max{0, y}) q , ψ(y) = |y| q , với q là một hằng số dương.
Bài toán (1.1) được đơn giản các ràng buộc thành bài toán sau supθ(à) à ≥ 0, với θ(à) = inf{f(x) +àp(x), x ∈ S}, p xỏc định bởi (2.9) và thỏa điều kiện (2.10).
Bổ đề 2.2.1 ([6]) Giả sử f, g, h là các hàm liên tục trên R n , S ⊂R n , S 6∅ Cho hàm p xỏc định bởi (2.9), liờn tục trờn R n và giả sử ∀à,∃x à ∈ S thỏa θ(à) = f(x à ) +àp(x à ).
Khi đó, các mệnh đề sau luôn đúng
2 f(x à ), θ(à) là hàm khụng giảm với mọi à ≥ 0, p(x à ) là hàm khụng tăng với mọi à ≥0.
Chứng minh Ta sẽ chứng minh lần lượt từng mệnh đề
1 ∀x ∈ S thỏa g(x) ≤0, h(x) = 0, p(x) = 0 Xột à ≥ 0 ta cú f(x) = f(x) +àp(x) ≥ inf{f(y) +àp(y), y ∈ S} =θ(à), do vậy mệnh đề 1 đúng.
2 Xột 0 ≤λ ≤à ta cú f(xà) +λp(xà) ≥ f(xλ) +λp(xλ) (2.11) f(xλ) +àp(xλ) ≥ f(xà) +àp(xà) (2.12) Cộng theo vế của (2.11) và (2.12) ta có
Từ (2.11) ta có f(x à ) +àp(x à ) + (λ−à)p(x à ) ≥θ(λ), vỡ à > λ và p(xà) ≥ 0 nờn θ(à) ≥θ(λ).
Trong bài toán (1.1), hàm p được xác định bởi (2.9) và thỏa mãn điều kiện (2.10) Hơn nữa, với mọi giá trị à ≥ 0, tồn tại nghiệm cho bài toán tối thiểu hóa (f(x) + àp(x)), và tập hợp {x à} với à ≥ 0 nằm trong một tập con compact.
S Khi đó inf{f(x) :x ∈ S, g(x) ≥ 0, h(x) = 0} = sup à≥0 θ(à) = lim à→∞θ(à), trong đú θ(à) = inf{f(x) +àp(x), x ∈ S}= f(x à ) +àp(x à ).
Hơn nữa, x = limx à là một nghiệm tối ưu của Bài toỏn (1.1) và àp(xà) →0 khi à →+∞.
Chứng minh Theo mệnh đề 2 của Bổ đề 2.1.1, θ(à) là hàm đơn điệu nờn sup à≥0 θ(à) = lim à≥0θ(à).
Ta sẽ chứng minh p(xà) → 0 khi à→ +∞.
Thật vậy, cho y ∈ S và > 0 Giả sử x 1 là một nghiệm tối ưu của bài toỏn min{f(x) +àp(x), x ∈ S}.
Nếu à ≥ 1 |f(y)−f(x 1 )|+ 2, theo mệnh đề 2 của Bổ đề 2.1.1 ta cú f(xà) ≥ f(x1).
Giả sử p(x à ) > , theo mệnh đề 1 của Bổ đề 2.1.1 ta cú inf{f(x) : x ∈ S, g(x) ≥0, h(x) = 0} ≥ θ(à)
> f(y). Điều này là vụ lý, nờn p(x à ) ≤ Vỡ > 0 lấy tựy ý nờn ta cú à→∞lim p(x à ) = 0.
Xột {x à k} là một dóy con của dóy {x à}, với {x à} chứa trong một tập compact, do đó tồn tại x ∈ S là giới hạn của dóy con {x à k} Ta có sup à≥0 θ(à)≥ θ(àk) = f(xà k) + àkp(xà k) ≥ f(xà k) Khi x à k tiến tới x và f liên tục, ta có sup à≥0 θ(à)≥ f(x).
Khi p(x à) tiến tới 0 khi à tiến tới 0, điều này có nghĩa là p(x) = 0, cho thấy x là một phương án khả thi cho bài toán (1.1) Từ mối liên hệ trong (2.13) và mệnh đề 1 của Bổ đề 2.1.1, ta có thể kết luận rằng x là nghiệm tối ưu của Bài toán (1.1) và sup à≥0 θ(à) = f(x).
Ta có àp(x à ) = θ(à)−f(x à ) và à→∞lim θ(à) = lim à→∞f(x à ) = f(x) nên à→+∞lim àp(xà) = 0.
Hệ quả 2.2.1 ([6]) ∀à ≥ 0 mà p(x à ) = 0 thỡ x à là nghiệm tối ưu của Bài toán (1.1).
Chứng minh ∀à ≥ 0 mà p(x à ) = 0 thỡ x à là phương ỏn khả thi của Bài toán (1.1) Ta có inf{f(x) : x ∈ S, g(x) ≥ 0, h(x) = 0} ≥ θ(à) = f(x à ) +àp(x à ) = f(x à ), vậy x à là nghiệm tối ưu của Bài toỏn (1.1).
Tóm tắt các bước giải Bài toán (1.1) theo phương pháp hàm phạt điểm ngoài:
- Bước khởi tạo: Cho > 0, tham số phạt à 1 > 0, hằng số β > 0, cho k = 1, chuyển sang bước chính.
1 Giải bài toán min [f(x) +à k p(x)], gọi x k là một nghiệm của bài toán trên, chuyển sang bước 2.
2 Nếu à k p(x k ) < , dừng Ngược lại, cho k := k + 1, à k+1 := βà k , quay lại bước 1.
Bài tập ứng dụng
Bài tập 2.2.1 Giải bài toán tối ưu phi tuyến sau
Để xây dựng hàm phạt cho bài toán, ta định nghĩa p(x) = (max{0, g1(x)})² + (max{0, g2(x)})² + (max{0, g3(x)})² Để đơn giản hóa hàm phạt, ta chọn điểm khởi đầu x₀ = (6,7) Tại điểm này, chỉ có điều kiện g₃(x) ≤ 0 là không thỏa mãn, do đó ta sẽ xem xét hàm này.
F(x, λ) =f(x) +λ(max{0, g 3 (x)}) 2 Điểm dừng của F là nghiệm của hệ phương trình
Cho λ −→ +∞ ta có (x 1 , x 2 ) −→ (3,4) Đó chính là nghiệm của bài toán đã cho và fmin = 18.
Bài tập 2.2.2 Giải bài toán sau min
(x 1 −2) 4 + (x 1 −2x 2 ) 2 x 2 1 −x2 = 0 Giải: ∀k ∈ N, tham số phạt àk > 0, ta giải nghiệm tối ưu của bài toỏn min (x 1 −2) 4 + (x 1 −2x 2 ) 2 +à k (x 2 1 −x 2 ) 2
.Quỏ trỡnh giải được túm tắt bởi bảng 2.1, với x 1 = (2,1);à 1 = 0,1;β 10. k à k x à k =x k+1 f(x k+1 ) p(x à k) θ(à k ) à k p(x à k)
0,8934414) Bảng 2.1: Tóm tắt quá trình giải bằng phương pháp hàm phạt
Bài tập tham khảo: Áp dụng phương pháp hàm phạt điểm ngoài để giải các bài toán sau
Bài tập 2.2.3 Tìm giá trị nhỏ nhất của hàm số f(x) = (x 1 −2) 4 + (x 1 −2x 2 ) 2 trong các trường hợp sau
1 (x 1 , x 2 ) thỏa mãn các điều kiện x 1 + 2x 2 −3 ≤ 0,
Bài tập 2.2.4 Giải bài toán
3x 2 2 ) x 1 +x 2 = 1.Bài tập 2.2.5 Giải bài toán sau min 2e x 1 + 3x 2 1 + 2x 1 x 2 + 4x 2 2
3x 1 + 2x 2 −6 = 0 bằng phương phỏp hàm phạt điểm ngoài với tham số à= 10.
Bài tập 2.2.6 Cho bài toán
Giải bài toán trên theo phương pháp hàm phạt điểm ngoài.
Phương pháp hàm phạt điểm trong
Phương pháp hàm phạt điểm trong, giống như phương pháp hàm phạt điểm ngoài, nhằm chuyển đổi bài toán có ràng buộc thành bài toán không ràng buộc hoặc một chuỗi các bài toán không ràng buộc.
2.3.1 Phương pháp hàm phạt điểm trong
Xét Bài toán (1.1), đặt D o = {x ∈ S : g(x) < 0,} Một hàm phụ
B : D o −→R thỏa mãn các điều kiện sau
2 Với mọi dãy {x k } ⊂ D o mà limx k = x /∈ D o thì lim inf B(xk) = +∞ (2.14)
B được gọi là hàm phạt điểm trong của Bài toán (1.1) Để giải Bài toán (1.1) ta xét bài toán sau infθ(à) à > 0 , với θ(à) := inf{f(x) +àB(x), x ∈ S}.
Trong một số trường hợp đặc biệt, hàm B được xác định như sau
P i=1 ϕ(g i (x)) với ϕ là một hàm liên tục trên {y, y < 0} thỏa ϕ(y) ≥ 0, lim y→0 − ϕ(y) = ∞ (2.15)
Ví dụ 2.3.1 Hai hàm phạt điểm trong thường được dùng:
Từ (2.15) ta thấy ϕ chỉ cần xác định trong một lân cận đủ nhỏ của y = 0.
Bổ đề 2.3.1 ([6]) Cho f, g là các hàm liên tục trên S ⊂ R n , S 6= ∅. Giả sử D o := {x|g(x) < 0} 6= ∅ và B thỏa mãn (2.14), liên tục trên
D o Hơn nữa, giả sử cho à > 0, nếu dóy {x k } ⊂ S thỏa g(xk) < 0 và f(x k ) +àB(x k ) −→θ(à) thỡ {x k } cú một dóy con hội tụ Khi đú
1 ∀à > 0,∃x à ∈ S thỏa g(x) < 0 và θ(à) = f(x à ) +àB(x à ) = inf{f(x) +àB(x)|g(x) < 0, x ∈ S}.
3 ∀à > 0, f(x à ) và θ(à) là cỏc hàm khụng giảm đối với à; B(x à ) là hàm khụng tăng đối với à.
Chứng minh Ta chứng minh lần lượt các mệnh đề của định lí.
1 Với à > 0, từ định nghĩa của hàm θ, tồn tại dóy {x k } ⊂ S thỏa g(x k ) < 0 và f(x k ) +àB(x k )−→ θ(à).
Từ giả thiết, {x k } cú một dóy con hội tụ {x k n } −→ x à ∈ S.
Để chứng minh rằng g j (x à) < 0 cho mọi j = 1, , m, giả sử có j ∈ {1, , m} sao cho g j (x à) = 0 Theo điều kiện (2.14), B(x k n) → +∞, dẫn đến θ(à) = +∞, điều này không hợp lý vì D 6= ∅ Do đó, ta có θ(à) = f(x à + àB(x à)).
2 Với à > 0,∀x ∈ S mà g(x) < 0, vỡ B(x) ≥ 0 nờn θ(à) = inf{f(x) +àB(x)|g(x) < 0, x ∈ S}
Cỏc bất đẳng thức trờn đỳng với mọi à > 0 nờn ta cú inf{f(x) : g(x) < 0, x ∈ S} ≤ infθ(à), à > 0.
3 Xột à > λ > 0,∀x ∈ S mà g(x) < 0, B(x) ≥ 0 nờn ta cú f(x) +àB(x) ≥ f(x) +λB(x), nờnθ(à) ≥θ(λ) Từ mệnh đề 1, tồn tạix à , x λ ∈ S thỏag(x à ) < 0, g(x λ )0 nờn B(xà) ≤ B(xλ) và từ (2.17) ta cú f(xλ) ≤ f(xà).
Dựa vào Bổ đề đã nêu, với θ là hàm không tăng, ta có điều kiện à>0 và inf θ(à) = lim à→0 + θ(à) Định lý 2.3.1 chỉ ra rằng, cho f : R n −→ R và g : R n −→ R m là các hàm liên tục, với S ⊂ R n và S 6= ∅, nếu D o := {x ∈ S|g(x) < 0} 6= ∅ thì bài toán sẽ có những điều kiện nhất định.
Nghiệm tối ưu x của bài toán (2.18) có các tính chất đặc trưng: với mọi lân cận V của x, tồn tại x ∈ V ∩ S sao cho g(x) < 0, thì giá trị tối thiểu của f(x) với điều kiện g(x) ≤ 0 và x ∈ S được xác định bởi lim à→0 + θ(à) = inf à>0 θ(à) Đặt θ(à) = f(xà) + àB(xà) với xà ∈ S thỏa mãn g(xà) < 0 Hơn nữa, giới hạn của bất kỳ dãy con nào của dãy {xk} sẽ là nghiệm tối ưu của bài toán (2.18), và àB(xà) sẽ tiến tới 0 khi à tiến tới 0+.
Chứng minh rằng x là nghiệm tối ưu của bài toán (2.18) với các điều kiện đã cho, và > 0 Dựa vào các điều kiện của định lý và tính liên tục của f, tồn tại bx ∈ S sao cho g(xb) < 0, dẫn đến f(x) + > f(xb) Với à > 0, ta có f(x) + àB(bx) > f(xb) + àB(bx) ≥ θ(à).
Vì bất đẳng thức trên đúng với mọi > 0 nên ta có f(x)≥ lim à→0 + θ(à).
Từ mệnh đề 2 của Bổ đề 2.3.1 ta có f(x) = lim à→0 + θ(à).
Ta có θ(à) = f(x à ) +àB(x à ) ≥ f(x à ) ≥ f(x), vì f(x) = lim à→0 + θ(à) nờn à→0lim + f(x à ) = lim à→0 + f(x à ) +àB(x à ) = f(x).
Từ đó ta có lim à→0 + àB(x à ) = 0.
Nếu {x k } có một dãy con có giới hạn là x 0 thì từ tính liên tục của f ta có f(x 0 ) = f(x) hay x 0 là một nghiệm tối ưu của bài toán (2.18).
Các bước giải bài toán tối ưu phi tuyến có ràng buộc theo phương pháp hàm phạt điểm trong:
- Bước khởi tạo: Cho > 0, chọn à 1 > 0, β ∈ (0,1), k = 1, chuyển sang bước chính.
min [f(x) +àkB(x)] h(x) = 0 x ∈ S gọi x k là một nghiệm của bài toán trên, chuyển sang bước 2.
Ngược lại, thay k := k+ 1, đặt à k+1 = βà k , quay lại bước 1.
Bài tập 2.3.1 Giải bài toán sau bằng phương pháp hàm phạt điểm trong
Ta xây dựng hàm phạt
B(x, y) = −[ln(1 +x−y 2 ) + lny],(x, y) ∈ D o Xét bài toán phạt min{F(x, y, à) = x−2y −à[ln(1 +x−y 2 ) + lny]}.
Theo Định lí 1.2.7 về điều kiện tối ưu, nếu (x ∗ , y ∗ ) là nghiệm tối ưu của bài toán trên ta có
Cho à −→0 ta được cỏc nghiệm
Bài tập 2.3.2 Giải bài toán:
Khi đó, ta có bài toán
Hàm Lagrange của bài toán (2.21) là
L(x, y, z, t, à) = (x−2y+ 3z+z 2 )−t(lnx+ lny+ lnz) +à(x+y+z−2). Áp dụng điều kiện Kuhn-Tucker ta có
Giả sử(x(t), y(t), z(t))là nghiệm của hệ Khi đó, chot →0ta được nghiệm của bài toán ban đầu Từ (2.22a) và (2.22e) ta có à+ 1 = t x ≥ 0 ⇒à ≥ −1, với à > −1 ta cú x(t) = t
Từ (2.22b) và (2.22f) ta có à−2 = t y ≥ 0 ⇒ à≥ 2, với à > 2 thỡ y(t) = t à−2 > 0,∀t > 0 (2.24)
Từ các điều kiện trên ta thấy bài toán chỉ có thể có nghiệm với nhân tử Lagrange à ≥ 2 Với à > 2, cho t → 0 trong (2.23), (2.24) (2.25), (2.26) ta được x = 0, y = 0, z 1 = 0, z 2 = −(à+ 3)
Thay x = 0, y = 0 vào (2.22d) ta được z = 2 ⇒ à = −2z −3 = −7 < 2. Nờn bài toỏn (2.21) khụng cú nghiệm với nhõn tử Lagrange à > 2.
Với à = 2, thay vào (2.23) ta cú x = t
Thayà = 2 vào (2.25), (2.26), chot →0 ta được z = 0 hoặc z = − 5 2 (loại). Thay x = 0, z = 0 vào (2.22d) ta được y = 2.
Ta cú nghiệm (0,2,0) ứng với à = 2, f = −4.
Vậy, ta có nghiệm của bài toán là (0,2,0) và f min = −4.
Bài tập 2.3.3 Sử dụng phương pháp hàm phạt điểm trong, giải bài toán sau min
(x1 −2) 4 + (x1 −2x2) 2 x 2 1 −x 2 ≤ 0. Giải: Ta xét hàm phạt
B(x) = −1 x² / (1 − x²) Quá trình giải được mô tả trong bảng (2.2), bắt đầu với a₁ = 10 và bước nhảy β = 0,1 Sau 6 bước, ta có xₜ = (0.94389; 0.89635) và aₖ B(xₐₖ) = 0,0184, tiến gần đến điểm tối ưu Các bước tiếp theo là k, aₖ, xₐₖ = xₖ₊₁, f(xₖ₊₁), B(xₖ₊₁), θ(aₖ), aₖ B(xₐₖ).
6 0,0001 (0,94389; 0,89635) 1,9645 184,4451 1,9829 0,0184 Bảng 2.2: Tóm tắt quá trình giải bằng phương pháp hàm phạt điểm trong
Bài tập tham khảo: Áp dụng phương pháp hàm phạt điểm trong để giải các bài toán sau
Bài tập 2.3.4 Với điểm khởi đầu x 0 = (0,0), giải bài toán sau
−4x1 + 2x2 −4 ≤ 0. Bài tập 2.3.5 Sử dụng hàm phạt
2x 2 1 −x 2 giải bài toán sau min
2x 2 1 −x 2 ≤0,với tham số phạt ban đầu à 1 = 10, bước nhảy β = 0,1.
Với việc bám sát các mục tiêu đã đặt ra, luận văn đã hoàn thành được các vấn đề sau
• Trình bày tổng quan các kiến thức cơ sở về giải tích lồi và một số kiến thức cơ bản của tối ưu phi tuyến.
Bài viết này sẽ khám phá các phương pháp giải bài toán tối ưu phi tuyến có ràng buộc, bao gồm phương pháp Lagrange, phương pháp hàm phạt điểm trong và phương pháp hàm phạt điểm ngoài Những phương pháp này giúp xác định giá trị tối ưu của các hàm mục tiêu trong các bài toán có ràng buộc phức tạp, từ đó ứng dụng hiệu quả trong nhiều lĩnh vực khác nhau Việc hiểu rõ các kỹ thuật này là cần thiết để giải quyết các vấn đề tối ưu hóa một cách chính xác và hiệu quả.
• Giải các bài tập mẫu và đưa ra hệ thống bài tập vận dụng.
Để hiểu sâu về tối ưu phi tuyến, luận văn có thể phát triển các phương pháp giải đa dạng nhằm giải quyết hiệu quả các bài toán tối ưu Việc xây dựng và hoàn thiện quy trình giải cho các phương pháp này không chỉ giúp nâng cao độ chính xác và tốc độ giải quyết vấn đề, mà còn tạo nền tảng cho việc phát triển các thuật toán, từ đó xây dựng các chương trình giải thuật trên máy tính để xử lý các bài toán phức tạp.
[1] N V Mậu, Đ H Ruận, N T Khanh, 2001, Phép tính vi phân và tích phân hàm nhiều biến, Nhà xuất bản Đại học Quốc gia Hà Nội.
[2] Đ T Lục, P H Điển, T D Phượng, 2002, Giải tích các hàm nhiều biến :Những nguyên lý cơ bản và tính toán thực hành, Nhà xuất bản Đại học Quốc gia Hà Nội.
[3] B T Tâm, T V Thiệu, 1998, Các phương pháp tối ưu hóa, NXB Giao thông vận tải.
[4] N H Thanh, 2006, Tối ưu hóa, NXB Bách khoa Hà Nội.
[5] H Tụy, 1985,Lý thuyết tối ưu phi tuyến, Tạp chí Vận trù học và Nghiên cứu hệ thống, số 39, 1-63.
[6] M S Bazaraa, C M Shetty, 1990, Nonlinear programming: Theory and algorithms, John Wiley and Sons, New York.
[7] D P Bertsekas, 1982, Constrained Optimization and Lagrange Multi- plier Methods, Academic Press.
[8] S.Boyd, L Vandenberghe, 2004,Convex Optimization, Cambridge Uni- versity Press.
[9] P Pardalos, J Ben Rosen, 1987, Constrained Global Optimization: Al- gorithms and Applications, Springer.
