Các khái niệm cơ bản 4 1.1 Tập lồi
Tổ hợp lồi
Một đường thẳng nối hai điểm (véc tơ) a và b trong R n là tập hợp tất cả các điểm (véc tơ) x ∈
Một đoạn thẳng nối hai điểm (véc tơ) a và b trong R n là tập hợp tất cả các điểm (véc tơ) x ∈
Một tập C ⊆ R n được gọi là một tập lồi nếu C chứa mọi đoạn thẳng đi qua hai điểm bất kỳ của nó Tức là C lồi khi và chỉ khi
Ta nói véc tơ x ∈ R n gọi là tổ hợp lồi của các véc tơ x
Mệnh đề 1.1 [xem [2], mệnh đề 1.1)
Một tập con của R n là tập lồi khi và chỉ khi nó chứa mọi tổ hợp lồi của các điểm của nó Tức là C lồi khi và chỉ khi: k k
Chứng minh Điều kiện đủ: Suy ra từ định nghĩa tập lồi ứng với k = 2 Điều kiện cần: Ta chứng minh bằng quy nạp theo số điểm.
Với tổ hợp lồi. k = 2 , điều kiện cần chứng minh suy ra ngay từ định nghĩa của tập lồi và
Giả sử mệnh đề đúng với k −1 điểm, ta cần chứng minh mệnh đề đúng với k điểm.
Thật vậy, nếu x là tổ hợp lồi của k điểm x 1 , , x k ∈ C Tức là k k x = ∑ j x j , j ≥ 0, ∀j = 1, , k , ∑ j =1 j =1 j =1
với mọi j = 1, 2, , k −1 nên theo giả thiết quy nạp, điểm y := k 1 j x j ∈ C j =1
Do > 0, k > 0 và + k = ∑ j =1 j = 1 nên x là một tổ hợp lồi của hai điểm y và x k đều thuộc C Vậy x ∈ C
Từ định nghĩa của tập lồi ta suy ra lớp các tập lồi là đóng với phép giao, phép cộng đại số và phép nhân tích Decastes.
Mệnh đề 1.2 (xem [2], mệnh đề 1.2)
Nếu A, B là các tập lồi trong
R m , thì các tập sau là lồi:
Tập a-phin, tập lồi đa diện
Trong giải tích cổ điển, chúng ta đã tiếp xúc với các không gian con và siêu phẳng, đây là những trường hợp đặc biệt của tập a-phin (đa tạp a-phin) Tập a-phin được định nghĩa rõ ràng trong các khái niệm toán học cơ bản.
Một tập C được gọi là tập a-phin nếu nó chứa mọi đường thẳng đi qua hai điểm bất kỳ của nó, tức là
Nhận xét 1.1 a) Mọi tập affin (bao gồm cả tập ∅ và
R n ) đều là tập lồi. b) Mọi siêu phẳng trong R n đều là tập a-phin.
M ệnh đề dưới đây cho ta thấy tập a- phin chính là ảnh tịnh tiến của một không gian con.
Mệnh đề 1.3 (xem [2], mệnh đề 1.3)
Tập M ≠ ∅ được xem là tập a-phin nếu và chỉ nếu nó có dạng M = L + a, trong đó L là một không gian con duy nhất và a thuộc M Điều này cho thấy rằng không gian con L được xác định một cách duy nhất trong tập a-phin.
+ a chứa 0 và là tập a- phin Do đó, L là một không gian con. Điều kiện đủ: Nếu M =
∈ M , L là một không gian con thì
Do x − a, y − a ∈ L và L là một không gian con nên
Không gian con L là duy nhất Thật vậy, nếu M = L + a và
M = L '+ a ' , trong đó L, L ' là những không gian con và a, a ' ∈ M thì
Không gian con L trong mệnh đề trên được gọi là không gian con song song với tập a-phin M Định nghĩa 1.4.
Thứ nguyên(hay chiều) của một tập a- phin M được định nghĩa bởi thứ nguyên của không gian con song song với M và được ký hiệu là dim M Điểm a ∈
R n là tập a-phin có số chiều bằng 0 bởi vì không gian con song song với M = { a } là L = { 0 }
Mệnh đề 1.4 (xem [2], mệnh đề 1.4)
Bất kỳ một tập a-phin M ⊂ R n có số chiều r đều có dạng
Trong đó: A là ma trận cấp m × n, b ∈ R m , và rankA = n − r
Ngược lại, mọi tập hợp có dạng (1.1) với rankA = n − r là r
Để chứng minh rằng tập a-phin M có số chiều r, giả sử M = L + a với a ∈ M Khi đó, L = M - a sẽ là không gian con có số chiều r.
Theo đại số tuyến tính không gian con r - chiều này có dạng
Trong đó, A là ma trận cấp m × n và rankA = n − r
M = { x | A ( x − a ) = 0 } = { x | Ax = Aa } = { x | Ax = b } Điều kiện đủ: Nếu M được cho bởi (1.1) với a ∈ M , ta có Aa = b , do đó
Vậy dim M = r Định nghĩa 1.5 nên L là không gian con có số chiều r
Siêu phẳng trong không gian R n là tập hợp các điểm có dạng trong đó: a ∈ Rn \ { 0 } , ∈
Véc tơ a ở trên được gọi là véc tơ pháp tuyến của siêu phẳng.
Nửa không gian đóng là tập hợp có dạng
Nửa không gian mở là tập hợp có dạng
Một siêu phẳng phân chia không gian thành hai nửa, mỗi nửa nằm ở một bên của siêu phẳng Nếu cả hai nửa không gian này đều đóng lại, phần giao nhau của chúng sẽ chính là siêu phẳng.
Một tập được gọi là tập lồi đa diện nếu nó là giao của một số hữu hạn các nửa không gian đóng. Định nghĩa 1.7
Cho x 0 ∈ C , ta nói siêu phẳng a
= là siêu phẳng tựa tại x 0 nếu a, x 0 =
≤ 0 } là nửa không gian tựa của C tại x 0 Định nghĩa 1.8
Gi ao củ a tất cả các tập lồi ch ứa tập
R n cho trước được gọi là bao lồi của
S , ký hiệu coS , đó là tập lồi nhỏ nhất chứa
Tập C ⊆ R n , giao của tất cả các tập a-phin chứa C là tập a-phin nhỏ nhất chứa C , gọi là bao a-phin của C Ký hiệu affC
Mệnh đề 1.5 (xem [2], mệnh đề 3.2)
Cho C là một tập bất kỳ Khi đó:
(i) Bao lồi của C là tập hợp các tổ hợp lồi của các điểm thuộc C
(ii) Bao a-phin của tập C là tập hợp bao gồm tất cả các điểm có dạng x = x 1 + + x k (1.2) sao cho x i ∈ C, + +
(i) Gọi M là tập hợp các tổ hợp lồi của các điểm thuộc C
Vì C ⊂ coC và coC lồi nên M ⊂ coC Vì thế để chỉ ra M = coC , ta chỉ cần chứng tỏ
Thật vậy, lấy k x, y ∈ M Theo định nghĩa của M , các điểm này có dạng i i =1 h k h y = ∑ y j , với x i , y j ∈ C, ≥ 0, ≥ 0 ∀i, j và ∑ = 1, ∑
Do ∑ i + ∑ ( 1− ) j = 1 i =1 j =1 nên z là một tổ hợp lồi của các điểm thuộc C Vậy z ∈ M Suy ra M lồi, và do đó
(ii) Cho M là tập hợp các điểm có dạng (1.2).Giả sử x, y ∈ M , theo định nghĩa của M ta có: k i i i =1 h j i j =1 k h
1, , h và ∑ = 1, ∑ = 1 Với bất kỳ, ta có i j i =1 j =1 k h i j i j i =1 j =1
Do ∑ i + ∑ ( 1 − ) j = 1 i =1 j =1 nên z ∈ M và do đó M là tập a- phin Suy ra M = aff E
, x k được gọi là độc lập a-phin nếu aff
{ x 1 , , x k } có số chiều là k , tức là, nếu các véc tơ x x 1 k−1 − x − x k , , k là độc lập tuyến tính.
Bao lồi a-phin M của tập k điểm độc lập a-phin { x 1 , , x k } a-phin (k −1) - chiều. tron g R n là tập
Mọi điểm x ∈ M có thể biểu diễn duy nhất dưới dạng: k k x = ∑ x i i , ∑ = 1 i i i =1 x = ∑ x , y = ∑ y z := x + ( 1− ) y = ∑ x + ( 1− )
Một tập C Được gọi là nón nếu
Theo định nghĩa, ta thấy rằng gốc tọa độ có thể thuộc nón hoặc không thuộc nón Dĩ nhiên, một nón không nhất thiết là một tập lồi.
C = { x ∈ R | x ≠ 0 } là một nón nhưng không lồi.
Nón được định nghĩa là nón nhọn khi không chứa đường thẳng, với 0 là đỉnh của nón Nếu nón này là một tập lồi, nó được gọi là nón lồi Khi nón lồi đồng thời là một tập lồi đa diện, ta gọi nó là nón lồi đa diện.
Mệnh đề 1.5 (xem [2], mệnh đề 1.6)
Một tập C là nón lồi khi và chỉ khi nó có các tính chất sau:
(i) C + C ⊆ C Chứng minh Điều kiện cần: Giả sử C là một nón lồi Do C là một nón nên ta có (i).
Do C là một tập lồi nên với mọi
Vậy theo (i) ta có x + y ∈ C x, y ∈ C thì 1 ( x + y ) ∈ C
2 Điều kiện đủ: Giả sử ta có (i) và (ii).
Từ (i) suy ra C là một nón Giả sử x, y ∈ C và ∈ [ 0,1 ]
Từ (ii) suy ra x ∈ C, ( 1 − ) y ∈ C Theo (ii) ta có x + ( 1 − ) y ∈ C
Vậy C là một nón lồi. Định nghĩa 1.11
Bao nón lồi của tập C là giao của tất cả các nón lồi chứa C , ký hiệu là
Cho C là một tập lồi trong R n Một véc tơ y ≠
Hướng lùi xa của tập hợp C được định nghĩa là hướng y khi mọi tia xuất phát từ một điểm bất kỳ trong C theo hướng y đều nằm hoàn toàn trong C Điều này có nghĩa là y là hướng lùi xa khi và chỉ khi với mọi x thuộc C và mọi giá trị không âm λ, thì x + λy cũng thuộc C.
Tập hợp của tất cả các hướng lùi xa của C cùng với điểm gốc là nón lùi xa của C , ký hiệu là re C
Hiển nhiên nếu C là một tập bị chặn thì re C chỉ gồm duy nhất một gốc.
Nhận xét 1.2 Nếu C là tập lồi đóng thì trong định nghĩa trên, thay vì đòi hỏi với mọi x ∈ C , chỉ cần đòi hỏi cho một điểm x ∈ C
Mệnh đề 1.6 (xem [2], mệnh đề 1.7)
Giả sử C là một tập lồi đóng Khi đó y là một hướng lùi xa của
Gi ả sử lồi nên ta có x
C không đóng thì bổ đề trên không đúng.
( 0,1 ) có tính chất là mọi tia xuất phát từ một điểm
C theo hướng này đều nằm trọn trong C nhưng nếu xuất phát từ x
= 0 thì điều này không đúng. Định nghĩa 1.13
Cho C ⊆ R n là tập lồi và x ∈ C
NC ( x ) gọi là nón pháp tuyến ngoài của C tại x
−NC ( x ) gọi là nón pháp tuyến trong của C tại x
Tập C * gọi là nón đối cực.
Ta có thể kiểm tra được r ằ n g
NC ( x ) và C * là hai nón lồi đóng chứa gốc.
C là tập lồi, khác rỗng và x
R n là một hướng chấp nhận đ ư ợ c c ủ a
0 ≤ t ≤ t 0 Tập tất cả các hướng chấp nhận được là một nón lồi chứa gốc và gọi là nón chấp nhận được
FC ( x ) Nón này có thể không đóng, tuy nhiên nếu lấy bao đóng, ta sẽ được một nón khác là nón tiếp xúc với C tại x
Ký hiệu nón này là TC ( x ) , thì đây suy ra
Nón pháp tuyến và nón tiếp xúc là đối cực của nhau.
Ta có thể suy ra trực tiếp từ định nghĩa.
Giả sử tập lồi C được cho bởi C := { x ∈ R n | a j , x
= b j } gọi là tập chỉ số tích cực tại x Khi đó
Trong chương trình Toán phổ thông, chúng ta đã được giới thiệu về khái niệm hàm lồi một cách cơ bản Bài viết này sẽ trình bày khái niệm tổng quát về hàm lồi cùng với một số tính chất quan trọng của nó Định nghĩa 1.14.
R n và f : C → R Ta sẽ ký hiệu dom f := { x ∈ C | f ( x ) < +∞ } , epi f : = { ( x, ) ∈ C × R | f ( x ) ≤ }
Các tập dom f , epi f lần lượt được gọi là miền hữu dụng và trên đồ thị của hàm f
B ằ n g c á c h c h o không gian và f ( x ) = +∞ nếu x ∉ C , ta có thể coi f được xác định trên toàn dom f := { x ∈ R n | f ( x ) < +∞ } , j
R | thì f ( x ) = 0 với mọi x f ( x ) ≤ } Định nghĩa 1.15
R n l ồ i v à f : C → R Ta nói f là hàm lồi trên C nếu epif là một tập lồi tro ng
R n+1 Hàm f được gọi là hàm lõm trên C nếu
Sau đây chủ yếu ta xét hàm tương đương với: f : Rn → R ∪ { +∞ } Dễ thấy định nghĩa trên f ( x +
Hàm f : Rn → R ∪ { +∞ } được gọi là lồi chặt trên C nếu f ( x +
Hà m f : Rn → R ∪ { +∞ } được gọi là lồi mạnh trên C với hệ số > 0 nếu f
Dễ dàng kiểm tra rằng hàm f lồi mạnh trên C với hệ số
> 0 khi và chỉ khi hàm lồi trên C
Bài viết này sẽ giới thiệu một bất đẳng thức quen thuộc trong chương trình phổ thông, liên quan đến các bất đẳng thức về hàm lồi Bất đẳng thức giữa trung bình cộng và trung bình nhân, cùng với bất đẳng thức Holder, đều là những trường hợp đặc biệt của bất đẳng thức tổng quát này.
Nếu f là hàm lồi và nhận giá trị hữu hạn trên tập lồi C thì
∈ C và ∀ j ≥ 0 thỏa mãn ∑ j =1 j = 1 , ta có: f m x j
Mệnh đề 1.8 (xem [2], mệnh đề 8.1)
Một hàm f : C → R là lồi trên C khi và chỉ khi
Chứng minh Điều kiện cần: Giả sử f lồi, chọn x, y, , như đã nêu trong mệnh đề.
) và ' ∈ ( f ( y ) , ) Vậy ( x, ' ) , ( y, ' ) ∈epi f Do epi f lồi nên
⇒ f ( ( 1− ) x + y ) ≤ ( 1− ) '+ ' < ( 1 − ) + Điều kiện đủ: Chọn ( x, ) , ( y, ) ∈epi f và ∈ ( 0,1 ) Với mọi > 0 , ta có f ( x ) < + , f ( y ) < +
Dưới đây là một định nghĩa khác, tương đương về hàm lồi, lồi mạnh dựa vào khái niệm hệ số lồi. Định nghĩa 1.17
R n là một tập lồi khác rỗng và là một số thực Ta nói là hệ số lồi của f trên C , nếu với mọi
Hiển nhiên, nếu = 0 thì f lồi trên C Nếu f có hệ số lồi trên C là > 0 , thì f lồi mạnh trên C vớih hệ số lồi Định nghĩa 1.18
Một hàm f được gọi là chính thường nếu dom f ≠ ∅ và f ( x ) > −∞ với mọi x
Hàm f được gọi là đóng nếu epi f là một tập đóng trong R n +1
Theo định nghĩa của epi f, một hàm lồi hoàn toàn có thể được xác định chỉ từ epi f Nếu f là hàm lồi trên một tập lồi C, ta có thể mở rộng f ra toàn bộ không gian bằng cách định nghĩa f(x) = {f(x)}.
Hiển nhiên fe ( x ) = f ( x ) với mọi x
Hàm f trên R^n được coi là chính thường khi và chỉ khi hàm fe(x) cũng chính thường Tương tự, hàm f được xem là đóng Hàm fe(x) sẽ đóng khi và chỉ khi f là một hàm lồi trên R^n Đặc biệt, miền xác định của f (dom f) là một tập lồi, vì miền xác định này chính là hình chiếu trên R^n của epi f.
Ví dụ 1.4 Một số hàm lồi
= a, x + , trong đó a ∈ R n , ∈ R Dễ dàng kiểm tra được rằng f là hàm vừa lồi vừa lõm trên toàn không gian.
Khi = 0 thì hàm này được gọi là hàm tuyến tính.
Cho C ≠ ∅ là một tập lồi Đặt
Ta nói C là hàm chỉ của C Do C lồi nên
1 } là một mặt cầu và h : S →
R + là một hàm bất kỳ. Định nghĩa hàm f như sau:
Hàm này được gọi là hàm mặt cầu Dễ thấy rằng f là một hàm lồi trên R n
Hàm dưới đây được gọi là hàm tựa của C
Cho C lồi đóng, hàm khoảng cách đến tập C được định nghĩa bởi d x := min y∈C x − y
Hàm lồi
Trong chương trình Toán phổ thông, chúng ta đã được giới thiệu về khái niệm hàm lồi một cách cơ bản Bài viết này sẽ trình bày khái niệm tổng quát về hàm lồi cùng với một số tính chất quan trọng của nó.
R n và f : C → R Ta sẽ ký hiệu dom f := { x ∈ C | f ( x ) < +∞ } , epi f : = { ( x, ) ∈ C × R | f ( x ) ≤ }
Các tập dom f , epi f lần lượt được gọi là miền hữu dụng và trên đồ thị của hàm f
B ằ n g c á c h c h o không gian và f ( x ) = +∞ nếu x ∉ C , ta có thể coi f được xác định trên toàn dom f := { x ∈ R n | f ( x ) < +∞ } , j
R | thì f ( x ) = 0 với mọi x f ( x ) ≤ } Định nghĩa 1.15
R n l ồ i v à f : C → R Ta nói f là hàm lồi trên C nếu epif là một tập lồi tro ng
R n+1 Hàm f được gọi là hàm lõm trên C nếu
Sau đây chủ yếu ta xét hàm tương đương với: f : Rn → R ∪ { +∞ } Dễ thấy định nghĩa trên f ( x +
Hàm f : Rn → R ∪ { +∞ } được gọi là lồi chặt trên C nếu f ( x +
Hà m f : Rn → R ∪ { +∞ } được gọi là lồi mạnh trên C với hệ số > 0 nếu f
Dễ dàng kiểm tra rằng hàm f lồi mạnh trên C với hệ số
> 0 khi và chỉ khi hàm lồi trên C
Bất đẳng thức mà chúng ta sẽ thảo luận là một khái niệm quan trọng trong chương trình phổ thông, đặc biệt liên quan đến các bất đẳng thức về hàm lồi Đây là một dạng tổng quát, trong đó các bất đẳng thức như trung bình cộng, trung bình nhân và bất đẳng thức Holder đều là những trường hợp đặc biệt.
Nếu f là hàm lồi và nhận giá trị hữu hạn trên tập lồi C thì
∈ C và ∀ j ≥ 0 thỏa mãn ∑ j =1 j = 1 , ta có: f m x j
Mệnh đề 1.8 (xem [2], mệnh đề 8.1)
Một hàm f : C → R là lồi trên C khi và chỉ khi
Chứng minh Điều kiện cần: Giả sử f lồi, chọn x, y, , như đã nêu trong mệnh đề.
) và ' ∈ ( f ( y ) , ) Vậy ( x, ' ) , ( y, ' ) ∈epi f Do epi f lồi nên
⇒ f ( ( 1− ) x + y ) ≤ ( 1− ) '+ ' < ( 1 − ) + Điều kiện đủ: Chọn ( x, ) , ( y, ) ∈epi f và ∈ ( 0,1 ) Với mọi > 0 , ta có f ( x ) < + , f ( y ) < +
Dưới đây là một định nghĩa khác, tương đương về hàm lồi, lồi mạnh dựa vào khái niệm hệ số lồi. Định nghĩa 1.17
R n là một tập lồi khác rỗng và là một số thực Ta nói là hệ số lồi của f trên C , nếu với mọi
Hiển nhiên, nếu = 0 thì f lồi trên C Nếu f có hệ số lồi trên C là > 0 , thì f lồi mạnh trên C vớih hệ số lồi Định nghĩa 1.18
Một hàm f được gọi là chính thường nếu dom f ≠ ∅ và f ( x ) > −∞ với mọi x
Hàm f được gọi là đóng nếu epi f là một tập đóng trong R n +1
Dựa vào định nghĩa của epi f, ta nhận thấy rằng một hàm lồi hoàn toàn được xác định khi biết epi f Nếu f là một hàm lồi trên một tập lồi C, ta có thể mở rộng f lên toàn bộ không gian bằng cách định nghĩa f(x) = { f(x) }.
Hiển nhiên fe ( x ) = f ( x ) với mọi x
Hàm f: R^n → R được gọi là chính thường khi và chỉ khi hàm fe(x) cũng chính thường Tương tự, hàm f được coi là đóng Đặc biệt, nếu f là một hàm lồi trên R^n, thì miền xác định của f (dom f) sẽ là một tập lồi, vì dom f chính là hình chiếu trên R^n của epi f.
Ví dụ 1.4 Một số hàm lồi
= a, x + , trong đó a ∈ R n , ∈ R Dễ dàng kiểm tra được rằng f là hàm vừa lồi vừa lõm trên toàn không gian.
Khi = 0 thì hàm này được gọi là hàm tuyến tính.
Cho C ≠ ∅ là một tập lồi Đặt
Ta nói C là hàm chỉ của C Do C lồi nên
1 } là một mặt cầu và h : S →
R + là một hàm bất kỳ. Định nghĩa hàm f như sau:
Hàm này được gọi là hàm mặt cầu Dễ thấy rằng f là một hàm lồi trên R n
Hàm dưới đây được gọi là hàm tựa của C
Cho C lồi đóng, hàm khoảng cách đến tập C được định nghĩa bởi d x := min y∈C x − y
Định lý tách các tập lồi 21 2.1 Định lý tách 1
Định lý tách 2
Bổ đề 2.2 (xem [2], bổ đề 6.2)
Cho C ⊂ R n là một tập lồi đóng khác rỗng sao cho 0 ∉ C
Khi đó tồn tại một véc-tơ t ∈
Do C đóng và 0 ∉ C , nên tồn tại quả cầu B tâm ở gốc, bán kính r >
0 sao cho C ∩ B = ∅ Áp dụng định lý tách 1 cho hai tập C và B , ta có
Bằng chuẩn hóa ta có thể xem nhất là bằng ≥ r Vậy thì t = 1 và do đó khoảng cách từ gốc đến siêu phẳng ít t, x ≥ ≥ r > 0
Theo bổ đề này thì C và điểm gốc tọa độ có thể tách mạnh, ví dụ bởi siêu phẳ ng t, x
Hai tập lồi C và D là hai tập hợp khác rỗng với điều kiện C ∩ D = ∅ Nếu ít nhất một trong hai tập này là tập hợp compact, thì chúng có thể được tách biệt mạnh mẽ bởi một siêu phẳng.
Giả sử C là tập Compact Ta chỉ ra tập C − D đóng.
Thật vậy, giả sử z k ∈ C − D và z k → z Ta có z k = x k − y k với x k ∈ C, y k ∈ D Vì
C compac t, nên có một dãy con x k j
D nên theo bổ đề 2.2, tồn tại t
Chứng tỏ C và D có thể tách mạnh.
Hình 1. Điều kiện một trong hai tập là com-pắc trong định lý là không thể bỏ được
Rõ ràng hai tập này lồi, đóng, không có điểm chung, nhưng chúng không thể tách mạnh được.
Nếu hai tập hợp nằm trong cùng một siêu phẳng, chúng vẫn có thể tách biệt bằng chính siêu phẳng đó Để giải quyết vấn đề này, khái niệm "tách đúng" đã được đưa ra.
Hai tập C và D được gọi là tách đúng bởi siêu phẳng a T x = nếu a T x ≤ ≤ a T y, ∀x ∈ C, ∀y ∈ D và cả hai tập này không cùng nằm trọn trong siêu phẳng tách.
Mệnh đề 2.3 (xem [2], mệnh đề 6.1)
Cho hai tập lồi khác rỗng A và B Điều kiện cần và đủ để hai tập này tách đúng là riA ∩ riB = ∅
Chứng minh Điều kiện cần
Giả sử có siêu phẳng t T x = tách A và B , tức là t ' T x ≤ ≤ t ' T y, ∀x ∈ A, ∀y ∈ B
Giả sử siêu phẳng này không chứa B , khi đó riA ∩ riB = ∅ Điều kiện đủ t T y >
Giả sử riA ∩ riB = ∅ Khi đó, 0 ∉ ( riA − riB ) = ri ( A − B ) Xét hai trường hợp: i) Trường hợp int ( A − B ) ≠ ∅
0 ∉int ( A − B ) Vậy tồn tại t ≠ 0 và t T x < t T y,
Nếu \( \lambda = \inf \{ t_T y | y \in \text{int} B \} \) và \( \lambda = \sup \{ t_T x | x \in \text{int} A \} \), thì có \( \lambda \leq \lambda \) Giả sử \( \lambda \leq \lambda \leq \lambda \), khi đó siêu phẳng \( t_T x = \lambda \) sẽ tách biệt A và B, nhưng không thể chứa đồng thời cả A và B Trong trường hợp \( \text{int} (A - B) = \emptyset \), đặt \( C = A - B \) và \( F \) là không gian con song song với bao a-phin của C.
Khi đó, áp dụng lập luận ở phần trên cho không gian F , sẽ tồn tại một siêu phẳng
H ' (trong F ) tách đúng A và B Gọi t ' là phiếm hàm tuyến tính từ F → R xác định siêu phẳng
H ' Gọi F ⊥ là không gian vuông góc với F Với mỗi x ∈
R n đặt t ( x ) là hàm hợp giữa t ' và p , trong đó p là ánh xạ chiếu xuống không gian con
F Do p là tuyến tính, nên dễ thấy t và t ' cũng là tuyến tính và là siêu phẳng tách đúng hai tập A và B
Nếu A và B là hai tập lồi mà riA ∩ riB ≠ ∅ , thì hai tập này vẫn có thể tách được.
A và B là hai đường chéo của một hình chữ nhật trong mặt phẳng 2-chiều.
Rõ ràng A và B là hai tập lồi mà riA ∩ riB ≠ ∅ , chúng vẫn tách được bằng chính mặt phẳng nhưng chúng không tách đúng được.
Một hệ quả quan trọng của định lý tách là bổ đề chọn của nhà toán học Hungary Farkas, được chứng minh từ năm 1892 dưới dạng định lý hình học Bổ đề này không chỉ trực quan mà còn dễ áp dụng trong nhiều lĩnh vực như tối ưu hóa, điều khiển và lý thuyết toán tử.
Hệ quả 2.1 (Bổ đề Farkas) (xem [2], hệ quả 6.1)
Cho A là một ma trận thực cấp m × n và a ∈ R n Khi đó trong hai hệ dưới đây có một hệ và chỉ duy nhất một hệ có nghiệm:
A T y = a, y ≥ 0 với một y ∈ R m (2.2)Một cách phát biểu tương đương dưới ngôn ngữ hình học là:
0 } chứa nón { x | Ax ≥ 0 } khi và chỉ khi véc tơ a nằm trong nón sinh bởi các hàng của ma trận A tức là
Tính chất hình học của bổ đề này rất rõ.
Nó nói rằng nón lồi, đóng
} nằm trong nửa không gian { x
| a T x ≥ 0 } khi và chỉ khi véc tơ pháp tuyến a ở trong nón sinh bởi các hàng của ma trận A
Giả sử (2.2) có một nghiệm y nào đó Nếu như
A T y = a , nhân tích vô hướng với x , và do có nghiệm
Ax ≥ 0, y ≥ 0 , ta có a T x = y T Ax ≥ 0 Vậy (2.1) không thể
Giả sử hệ (2.2) không có nghiệm Lấy tập
Hiển nhiên C là tập lồi đóng và 0 ∈
Do (2.2) không có nghiệm nên a ∉ C Theo định lý tách 2, tồn tại p ≠
, với y ≥ 0 , ta viết được ≤ p T A T y = y T Ap
x = A T y Vậy các tọa độ của y có thể lớn tùy ý, nên từ bất đẳng thức
Vậy, ta đã chỉ ra sự tồn tại của một véc tơ p cho rằng (2.1) có nghi ệm.
Một số ứng dụng của định lý tách 27 3.1 Điều kiện tối ưu
Hệ bất đẳng thức lồi
Trong phần này chúng ta sử dụng định lý tách để tìm điều kiện cần và đủ để hệ bất đẳng thức lồi có nghiệm.
Cho D ⊆ R n là một tập lồi và f , , f là các hàm lồi trên R n Hệ bất đẳng thức
1 m x ∈ D, fi ( x ) fi ( x ) , ta có ( y0 , , ym ) ∈ C , nên
+∞ còn mọi y i khác cố định, ta thấy vế trái của bất đẳng thức trên tiến đến −∞ Mâu thuẫn vì vế phải bằng 0 Vậy
Cuối cùng giả sử điều kiện Slater thỏa mãn Nếu như 0 = 0 thì theo
Lấy x = x 0 ∈ D , theo điều kiện chính quy Slater thì m
Ta có mâu thuẫn và do đó mệnh đề được chứng minh.
Trong nhiều ứng dụng, trong một hệ bất đẳng thức lồi thường có sự tham gia của các đẳng thức tuyến tính Khi đó ta có mệnh đề sau:
Mệnh đề 3.2 (xem [2], mệnh đề 9.6)
1 , , f m là các hàm lồi hữu hạn trên một tập lồi D ≠ ∅ và A là một ma trận thực cấp k × n Giả sử b ∈ riA ( D ) Khi đó, hệ x ∈ D, Ax = b, fi ( x ) <
0, i = 1, , m không có nghiệm khi và chỉ khi tồn tại t ∈ R k và i ≥ 0, i = 1, , m sao cho ∑ i = 1 và i =1 t, Ax - b
Chứng minh Điều kiện đủ: Hiển nhiên Điều kiện cần:
Do D lồi nên E lồi và theo giả thiết, hệ x ∈ E, fi ( x ) < 0, i = 1, , m không có nghiệm Vậy áp dụng mệnh đề 3.1, sẽ tồn tại i , i = 1, , m thỏa mãn
Bằng cách chia cho ∑ i > 0 , ta có thể coi ∑ i = 1 i =1 i =1
Với mỗi x ∈ D , lấy f ( x ) := ∑ i fi ( x ) Khi đó f lồi và hữu hạn trên D Lấy i=1 m
Do D và f lồi nên C lồi Từ đó cùng với giả thiết ta suy ra 0 ∉ C Theo mệnh đề
2.1, ta có thể tách đúng C và 0 Tức là tồn tại ( t, t ) ∈ R k × R và ( y, y ) ∈
C sao cho t, y + t 0 y 0 ≥ 0 ∀ ( y, y0 ) ∈ C , và t, y + t 0 y 0 > 0 (3.4) Dựa vào định nghĩa của C , lập luận tương tự như mệnh đề 3.2.1 ta có t 0 ≥ 0
Nhưng t 0 không thể bằng 0, vì nếu t 0 = 0 thì t, y ≥ 0 ∀y ∈ A ( D ) − b (3.5)
Thế nhưng theo giả thiết b ∈ riA ( D ) , tức là 0 ∈ ri ( A ( D ) − b ) Từ đây và (3.5) suy ra
Mâu thuẫn với (3.4), vì y ∈ A ( D ) Vậy t0 > 0
Từ định nghĩa của C ta có ( Ax - b, f ( x ) +
∀x ∈ D Điều này đúng với mọi > 0 , nên t, Ax - b
Thay f ( x ) = ∑ i fi ( x ) và chia hai vế cho t0 > 0 , ta có điều cần chứng minh. i=1
Mệnh đề vẫn còn đúng khi thay hệ Ax = b bởi hệ Ax ≤ b
Xấp xỉ tuyến tính của hàm lồi
Một tập lồi có thể được xấp xỉ với độ chính xác tùy ý bằng các tập lồi đa diện, xác định qua các nửa không gian tựa Tương tự, một hàm lồi cũng có thể được xấp xỉ với độ chính xác tùy ý bằng các hàm a-phin non của nó Kết quả này tạo nền tảng cho việc xấp xỉ các bài toán lồi bằng các bài toán tuyến tính Trong phần này, chúng ta sẽ sử dụng định lý tách để chứng minh Bổ đề, làm cơ sở cho định lý về việc xấp xỉ một hàm lồi bằng các hàm non a-phin Trước tiên, chúng ta sẽ xem xét định nghĩa về hàm non a-phin.
Hàm l là hàm non a-phin của một hàm f trên R n nếu l là hàm a-phin trên
Hàm đồng nhất bằng −∞ là hàm non a-phin của mọi hàm.
Nếu f * là hàm liên hợp của f , thì x * , x
Từ đây thấy rằng mỗi x * xác định một hàm a-phin l ( x ) := x x * ,
∀x là hàm non a-phin của f trên toàn không gian.
Bổ đề 3.1 (xem [2], bổ đề 10.1)
Cho f là một hàm lồi đóng, chính thường trên R n Khi đó với mọi điểm
Theo giả thiết, hàm f là hàm lồi đóng chính, dẫn đến epif là một tập lồi, đóng và khác rỗng Vì điểm (x0, t0) không thuộc epi f, ta có thể áp dụng định lý tách mạnh cho hai tập lồi, đóng.
Tr ướ c hết ta thấ y rằn g
0 thì sẽ có mâu thuẫn ở bất đẳng thức đầu của (3.6) khi cho t tiến đến +∞ Lúc đó vế trái tiến đến
+∞ , trong khi đó ở vế phải là một số hữu hạn cố định.
= 0 thì từ bất đẳng thức (3.5), lấy x = x 0
, ta có a T x 0 < < a T x 0 Vô lý Vậy trong trường hợp này, chia hai vế (3.6) cho − > 0 , ta có điều phải chứng minh.
Bây giờ chỉ cần xét trường hợp x 0
∉do m f và = 0 Từ (3.6) có a T x < < a T x 0 ∀x ∈ dom f
Lấy \( x_1 \in \text{dom} f \) và \( t_1 < f(x_1) \) Khi đó, \( (x_1, t_1) \notin \text{epif} \) Áp dụng định lý tách mạnh cho tập gồm duy nhất một điểm \( \{(x_1, t_1)\} \) và tập \(\text{epif}\) Chú ý rằng tồn tại \( (b, \lambda) \neq 0 \) với \( b \in \mathbb{R}^n \).
Từ đây và (3.6), thấy rằng với mọi > 0 và mọi ( x, t ) ∈ epif , ta có
(b + a) T x 0 − t = b T x 0 − t + a T x 0 < + (3.8) với mọi đủ lớn Vậy với đủ lớn, bằng cách lấy
Như vậy trong trường hợp này ta cũng có (3.6).
T ừ b ổ đ ề t r ê n c h úng ta chứng minh được định lý Định lý 3.2 (xấp xỉ tuyến tính hàm lồi) (xem [2], định lý 10.1)
Mọi hàm lồi đóng chính thường f trên a- phin của nó Tức là:
R n đều là bao trên của các hàm non f ( x ) = sup { l v ( x ) | l v ∈ A } v trong đó A là tập hợp tất cả các hàm non a-phin của f
Chứng minh [xem [2], định lý 10.1]
Sự tồn tại dưới vi phân của hàm lồi
Phép tính vi phân là một trong những vấn đề cơ bản của giải tích cổ điển.
Trong giải tích lồi, lý thuyết về tập lồi và hàm lồi rất phong phú Chúng ta mở rộng khái niệm đạo hàm thông qua khái niệm dưới vi phân và các tính chất cơ bản của nó Đặc biệt, định lý tách và siêu phẳng tựa được áp dụng để chứng minh sự tồn tại của dưới vi phân của hàm f trong trường hợp hàm f lồi.
Hàm lồi khả vi tại một điểm có phương trình tiếp tuyến nằm dưới đồ thị, nhưng một hàm lồi có thể không khả vi, chẳng hạn như hàm lồi một biến f(x) = x không khả vi tại x = 0 Để giải quyết vấn đề này, khái niệm đạo hàm được mở rộng bằng dưới đạo hàm, vẫn giữ được tính chất cơ bản của đạo hàm của hàm lồi khả vi.
R n là dưới đạo hàm của f tại x nếu x * , z − x
Tương tự như hàm lồi khả vi thông thường, biểu thức này chỉ ra rằng phương trình tiếp tuyến nằm dưới đồ thị của hàm số Tuy nhiên, khác với trường hợp khả vi, tiếp tuyến trong trường hợp này có thể không tồn tại duy nhất.
Ký hiệu tập hợp tất cả các dưới đạo hàm của f tại x là ∂ f ( x ) Đây là một tập trong R n (có thể bằng rỗng).
Khi ∂f ( x ) ≠ ∅ thì ta nói hàm f khả vi dưới vi phân tại x
Theo định nghĩa, một điểm x* thuộc ∂f(x) nếu và chỉ nếu nó thỏa mãn một hệ vô hạn các bất đẳng thức tuyến tính Do đó, ∂f(x) là giao của các nửa không gian đóng.
∂f ( x ) luôn là một tập lồi đóng (có thể rỗng) Ký hiệu dom ( ∂f ) := { x | ∂f ( x ) ≠ ∅ }
0 hàm này không khả vi, nhưng nó khả dưới vi phân và ∂f ( 0 ) :=
C ⊂ R n là một tập lồi, khác rỗng. f ( x ) =
( x ) = 0 nếu x ∈ C là hàm chỉ của C
Khi đó với x 0 ∈ C , ta có:
C thì C = +∞ nên bất đẳng thức này luôn đúng Vậy
Vậy dưới vi phân của hàm chỉ của một tập lồi C khác rỗng tại một điểm x 0 ∈ C chính là nón pháp tuyến ngoài của C tại
Cho f : Rn → R ∪ { +∞ } lồi, chính thường Khi đó:
(ii) Nế u và Co m- pắc thì x
∂f ( x ) ≠ ∅ và com-pắc Ngược lại, nếu
+∞ và do đó kh ôn g thể tồn tại
) ) nằm trên biên của epi f Do f lồi, chính thường, nên tồn tại siêu phẳng tựa của bao đóng của epi f đi q u a
R không đồng thời bằng 0 thỏa mãn p, x + t f
) nên điều này kéo theo p = 0 Vậy, t ≠ 0 Hơn nữa, t > 0 , v ì n ế u t
Chia hai vế của (x) cho t >
C á c h c h ứ n g m i n h t r ê n c h o t h ấ y d ư ớ i đ ạ o h à m c ủ a f t ạ i x c h í n h l à v é c t ơ pháp tuyến của siêu phẳng tựa của bao đóng của epi f tại ( x, f ( x
3.5 Phép vô hướn g hóa bài toán véc tơ.
T r o n g c u ộ c s ố n g , c á c v ấ n đ ề t h ư ờ n g c ó n h i ề u m ố i r à n g b u ộ c K h i m ô h ì n h h ó a n h ữ n g m ố i l iên hệ đó bằng toán học thì ta được các bài toán nhiề u biến.
Nếu ta coi nhiề u biến đó là véc tơ thì ta được các bài toán véc tơ.
Tron g phần này chún g ta sẽ nghi ên cứu bài toán tối ưu véc tơ.
D : tập xác định (tập ràng buộc).
F : hàm mục tiêu (hàm tiêu chuẩn)
Với hai véc tơ aT = ( a , , a ) và bT = ( b , , b ) trong Rn , ta nói a ≤ b nếu a ≤ b ∀i
D được gọi là nghiệm Pareto lý tưởng của bài toán ( VP ) nếu
Trong trường hợp tổng quát thì nghiệm Pareto lý tưởng nói chung thường không tồn tại. Định nghĩa 3.6
D được gọi là nghiệm Pareto của bài toán VP nếu không tồn tại x ∈ D sao cho F ( x ) ≤ F ( x * ) và
Nếu không tồn tại x ∈ D yếu của bài toán (VP). Định nghĩa 3.7 mà F ( x ) < F ( x * ) thì x * được gọi là nghiệm Pareto
D được gọi là nghiệm Pareto lý tưởng của bài toán max { F ( x ) : x ∈ D ⊆
( VP max ) nếu không tồn tại x ∈ D sao cho F ( x ) ≥ F ( x * ) và F ( x ) ≠ F ( x * )
Nếu không tồn tại x ∈ D mà yếu của bài toán ( VP max ).
F ( x ) > F ( x * ) th ì x * được gọi là nghiệm Pareto
Một điểm được coi là nghiệm Pareto (nghiệm Pareto yếu) của bài toán cực tiểu min { F ( x ) : x ∈ D ⊆ R n } nếu và chỉ nếu nó cũng là nghiệm Pareto (nghiệm Pareto yếu) của bài toán cực đại max { −F ( x ) : x ∈ D ⊆ R n }.
Bài toán véc tơ tuyến tính:
Bài toán ( VP ) hoặc ( VP max ) trong đó
F ( x ) = Cx với C là ma trận thực, x ∈ R n
D là tập lồi đa diện được xác định rõ, ví dụ như
D = { x ≥ 0, Ax ≥ b } với A là ma trận ( m × n ) và b ∈ Rm được gọi là bài toán tối uu véc tơ tuyến tính.
Bài toán tối ưu véc tơ lồi
Bài toán tối ưu véc tơ lồi được định nghĩa khi D là tập lồi và tất cả các hàm mục tiêu đều là hàm lồi trên D.
Giả sử một công ty sản xuất hai loại hàng hóa, ký hiệu là x1 và x2 Chi phí sản xuất cho các hàng hóa này được biểu thị bằng hàm f1(x1, x2), trong khi chi phí xử lý chất thải liên quan đến sản phẩm cũng được mô tả bởi hàm f1(x1, x2).
0 ≤ x 1 ≤ a 1 , 0 ≤ x 2 ≤ a 2 (giới hạn số lượng sản phẩm) b 1 x 1 + b 2 x 2 ≤ b (ngân sách)
Bài toán cần giải quyết là xác định số lượng từng loại hàng hóa cần sản xuất nhằm giảm thiểu chi phí, tức là tìm nghiệm (x1, x2) cho bài toán tối ưu Để giải quyết các bài toán tối ưu theo dạng véc tơ, chúng ta thường áp dụng phương pháp vô hướng hóa.
(i) Cho > 0 ∈ R p Khi đó mọi nghiệm cực tiểu toàn cục của bài toán m
R n đều là nghiệm Pareto của bài toán ( VP )
(ii) Cho 0 ≠ ≥ 0 ∈ R p Khi đó mọi nghiệm cực tiểu toàn cục của bài toán min
R n } đều là nghiệm Pareto yếu của bài toán ( VP )
Giả sử ( VP ) là bài toán lồi ( F và D là các tập lồi) Khi đó, với mọi nghiệm
Ta sẽ chứng minh C ∩ Rp = { 0 }
Giả sử y ∈ C , khi đó, tồn tại y 1 , , y r ∈
Với mọi j , do y j ∈ K nên tồn tại x j ∈
Từ đó, do u là nghiệm Pareto nên
Do đó C ∩ Rp = { 0 } y ≤ 0 kéo theo y = 0
Theo định lý tách thì tồn tại ≠ 0 thỏa mãn
Bằng cách chia cho ∑ j , chúng ta có thể giả thiết ∑ j = 1 j =1 j =1
Từ (3.10) ta thấy ≥ 0 , từ (2) và định nghĩa của K ta suy ra
T ( F ( x ) − F ( u ) ) ≥ 0 ∀x ∈ D Điều đó có nghĩa rằng u là nghiệm nhỏ nhất của ( P ( ) )
− x = ∑ t x j Do F là hàm lồi nên ta có
Như vậy, ta đã vô hướng hóa xong bài toán ( VP )
Bài viết trình bày hai định lý tách cùng với các ứng dụng quan trọng của chúng Cụ thể, nội dung bao gồm hai định lý tách và các hệ quả liên quan Đặc biệt, định lý tách được ứng dụng để chứng minh các điều kiện tối ưu, tìm điều kiện có nghiệm cho hệ bất đẳng thức lồi, xác minh sự tồn tại xấp xỉ tuyến tính của hàm lồi qua các hàm non a-phin, và chứng minh sự tồn tại dưới vi phân của hàm lồi, từ đó vô hướng hóa bài toán tối ưu véc tơ.
Trong luận văn này, tác giả tập trung vào các định lý tách các tập lồi và ứng dụng của chúng trong không gian hữu hạn chiều R^n, mà chưa mở rộng đến trường hợp tổng quát trong không gian vô hạn chiều Một số vấn đề thú vị có thể được khai thác thêm từ đề tài này.
1 Ứng dụng định lý tách trong không gian vô hạn chiều.
2 Xây dựng và giải các bài toán tối ưu về kinh tế dựa trên các định lý tách.
3 Mô hình hóa toán học hoạt động sản xuất của một doanh nghiệp và dự đoán sự thành bại của doanh nghiệp…bằng việc mở rộng các định lý kiểu tách cho các tập rời rạc
Do hạn chế về thời gian và kiến thức, luận văn này không thể tránh khỏi những thiếu sót Tác giả rất mong nhận được sự quan tâm và góp ý từ các thầy cô cũng như đồng nghiệp để hoàn thiện bản luận văn hơn nữa.
Tác giả xin chân thành cảm ơn!
