Định lý tách và ứng dụng: Luận văn Thạc sĩ Khoa học chi tiết

MỤC LỤC

Mở đầu 2

Chương 1. Các khái niệm cơ bản 4

1.1. Tập lồi…………………………………………………………….. 4

1.1.1 Tổ hợp lồi…………….………………………..…..... ….. 4

1.1.2 Tập a-phin, tập lồi đa diện……………………………..… 6

1.1.3 Nón lồi………………………………………… …….….. 11

1.2. Hàm lồi…………………………………………………….……. . 15

Chương 2. Định lý tách các tập lồi. 21

2.1. Định lý tách 1…………………………………………………..… 21

2.2. Định lý tách 2………………………………………………… ….. 26

Chương 3. Một số ứng dụng của định lý tách. 27

3.1. Điều kiện tối ưu…………………….………………………………32

3.2. Hệ bất đẳng thức lồi…………………………………………...….. 36

3.3. Xấp xỉ tuyến tính của hàm lồi………………..……………………..41

3.4. Sự tồn tại dưới vi phân của hàm lồi……………………………..…43

3.5. Ứng dụng trong phép vô hướng hóa bài toán véctơ…….…………46

Kết luận 51

Tài liệu tham khảo 52

MỞ ĐẦU

Giải tích lồi là một bộ môn cơ bản của giải tích hiện đại, nghiên cứu về tập

lồi và hàm lồi cùng những vấn đề liên quan. Bộ môn này có vai trò quan trọng trong

nhiều lĩnh vực khác nhau của toán học ứng dụng, đặt biệt là trong tối ưu hóa, bất

đẳng thức biến phân, các bài toán cân bằng.

Một trong những vấn đề trung tâm của giải tích lồi là các định lý tách. Về

bản chất, định lý tách trả lời câu hỏi rằng một phần tử có thuộc một tập lồi hay

không, và nếu không thuộc thì nó sẽ mang tính chất gì? Đây là câu hỏi về liên

thuộc, một vấn đề cơ bản của toán học. Ta có thể hình dung tập lồi đó là tập hợp

nghiệm của một hệ phương trình đại số, hay vi, tích phân, tập các điểm bất động của

một ánh xạ, hay là tập nghiệm của một bài toán tối ưu,…Dĩ nhiên nếu câu trả lời là

có, thì vấn đề liên thuộc đã được giải quyết. Trái lại, nếu câu trả lời là không, thì sẽ

xảy ra điều gì? Điều này giải thích vì sao các định lý tách thuộc loại các định lý

chọn và là công cụ rất mạnh, thường được dùng để chứng minh sự tồn tại của một

đối tượng trong nhiều vấn đề thuộc những lĩnh vực khác nhau.

Trong luận văn này, tác giả tập trung vào việc trình bày hai định lý tách và

những ứng dụng quan trọng.

Luận văn được chia làm ba chương:

Chương 1: Trình bày một số kiến thức cơ sở của tập lồi và hàm lồi. Chúng là

những công cụ cơ bản nhất cho những nghiên cứu được trình bày trong luận văn.

Chương 2: Là phần chính của luận văn, trong chương này tác giả trình bày

nội dung hai định lý tách và hệ quả (Bổ đề Farkas).

Chương 3: Trình bày các ứng dụng của hai định lý tách để: Chứng minh các

điều kiện tối ưu, giải hệ bất đẳng thức lồi, xấp xỉ tuyến tính hàm lồi bởi các hàm

non a-phin của nó, chứng minh sự tồn tại dưới vi phân của hàm lồi, vô hướng hóa

bài toán tối ưu véc tơ.

Luận văn được hoàn thành dưới sự hướng dẫn khoa học của GS.TSKH Lê

Dũng Mưu, Viện Toán học, người thầy đã tận tình hướng dẫn, giúp đỡ tác giả trong

suốt quá trình hoàn thành bản luận văn này. Tác giả xin bày tỏ lòng biết ơn chân

thành và kính trọng sâu sắc đối với Giáo sư.

Tác giả xin bày tỏ lòng cảm ơn tới các thầy cô giáo trường Đại học Khoa học

Tự nhiên, Đại học Quốc gia Hà Nội về những ý kiến đóng góp quý báu, sự giúp đỡ

tận tình và sự cổ vũ hết sức to lớn trong suốt thời gian qua.

Tác giả xin chân thành cảm ơn Ban giám hiệu, phòng sau Đại học, khoa

Toán – Cơ – Tin học trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội

đã tạo điều kiện thuận lợi cho tác giả trong suốt quá trình học tập tại trường.

Bản luận văn được hoàn thành trong quá trình con gái của tác giả trào đời,

được sự ủng hộ về mặt tinh thần từ hai mẹ con. Kết quả của luận văn chính là món

quà mà tác giả giành tặng cho hai mẹ con.

Chương 1

CÁC KHÁI NIỆM CƠ BẢN

Trong chương này, chúng tôi trình bày những khái niệm cơ bản trong giải

tích lồi cùng với những tính chất đặc trưng của nó như: tập lồi, tập a-phin, nón nồi,

hàm lồi…

1.1. Tập lồi

Những tập hợp quen thuộc mà chúng ta đã biết như không gian con, siêu

phẳng, … đều là tập lồi. Khái niệm về tập lồi có một vai trò quan trọng trong giải

tích lồi. Trong phần này chúng tôi trình bày định nghĩa, tính chất của tập lồi, tập a-

phin, tập lồi đa diện, nón lồi.

1.1.1 Tổ hợp lồi.

Định nghĩa 1.1

nR là tập hợp tất cả

Một đường thẳng nối hai điểm (véc tơ) a và b trong

x R có dạng



  (1

   

)

các điểm (véc tơ)



  R

nR là tập hợp tất cả các

Một đoạn thẳng nối hai điểm (véc tơ) a và b trong

x R có dạng

n x R x



  (1

   a b

)

, 0

  

điểm (véc tơ)



 1

Định nghĩa 1.2

C R được gọi là một tập lồi nếu C chứa mọi đoạn thẳng đi qua

Một tập



x y C ,

   ,



  (1

   x

)

y C



 0;1

 .

hai điểm bất kỳ của nó. Tức là C lồi khi và chỉ khi

1 x

,..., m x

n R nếu

x R gọi là tổ hợp lồi của các véc tơ

Ta nói véc tơ



   0

1, 2,...,



i   , x i

 i



 1

Mệnh đề 1.1 [xem [2], mệnh đề 1.1)

nR là tập lồi khi và chỉ khi nó chứa mọi tổ hợp lồi của các

Một tập con của

   k N



0 :

1   1, x

,...,

  C



điểm của nó. Tức là C lồi khi và chỉ khi:

  ,..., k

 j



 1

Chứng minh

k  . 2

Điều kiện đủ: Suy ra từ định nghĩa tập lồi ứng với

Điều kiện cần: Ta chứng minh bằng quy nạp theo số điểm.

k  , điều kiện cần chứng minh suy ra ngay từ định nghĩa của tập lồi và

Với

tổ hợp lồi.

1k  điểm, ta cần chứng minh mệnh đề đúng với k điểm.

1,..., x

C . Tức là

Giả sử mệnh đề đúng với



  

1,...,

=1.

 j



 1

 1



Thật vậy, nếu x là tổ hợp lồi của k điểm

1  và

k  , đặt: 0

 j

  . Khi đó, 0

 1

 1

Giả sử









 j

 k

 



 j 

 1

 1



1, 2,...,

 với mọi

 nên theo giả thiết quy nạp, điểm

 j  

j 

 1

 1

Do và

 :





 j 

 1



   y k

Ta có .





 và

   k

 0, k

  j

 1

kx đều thuộc C .

nên x là một tổ hợp lồi của hai điểm y và

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)

, A B là các tập lồi trong

nR , C là lồi trong mR , thì các tập sau là lồi:

A B

 





  , x x A x B ,

   A

 :

x x |



   a

b a A b B



  ,



  , R

 m n

 A C

x R

x |



a c ,

a A c C ,







   :

  .

Nếu

1.1.2 Tập a-phin, tập lồi đa diện.

Trong giải tích cổ điển, ta đã làm quen với các không gian con, các siêu

phẳng. Đó là các trường hợp riêng của tập a-phin (đa tạp a-phin) được định nghĩa

như sau:

Định nghĩa 1.3

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



x y C ,

    



   x

)

y C

 .

điểm bất kỳ của nó, tức là

nR ) đều là tập lồi.

Nhận xét 1.1

a) Mọi tập affin (bao gồm cả tập  và

nR đều là tập a-phin.

b) Mọi siêu phẳng trong

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)

  với L là một

Tập M   là tập a-phin khi và chỉ khi nó có dạng M L a

không gian con và a M . Không gian con này được xác định duy nhất.

Chứng minh



Điều kiện cần: Giả sử M là tập a-phin và a M .

 chứa 0 và là tập a-phin. Do đó, L là một không gian con.

  Vậy M L a

Khi đó L M a

  với a M , L là một không gian con thì



 x y M ,

R

 , ta có:

Điều kiện đủ: Nếu M L a





 y



 x a



 y a

 1

 

    1





 



x a y a L



  và L là một không gian con nên





 x a



y a

 1





 

   .





y M

 .

   1

 

M L a

 '



Vậy M là tập a-phin.

  và

Không gian con L là duy nhất. Thật vậy, nếu M L a , trong

'L L là những không gian con và

a a M thì ,

L M a L a a

   



 '

(

 a a

đó

'a M a L

   , nên

  . a L

   '

(

 a a

 . L

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 .

a R là tập a-phin có số chiều bằng 0 bởi vì không gian con song

L 

Điểm

  M a

 0

song với là .

Mệnh đề 1.4 (xem [2], mệnh đề 1.4)

M R có số chiều r đều có dạng



Bất kỳ một tập a-phin

 M x R Ax b

  

m n b R ,



, (1.1)

 , và rankA n r

  .

Trong đó: A là ma trận cấp

  đều là tập a-phin có số chiều

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

  với



a M . Vậy L M a

 là không gian con có số chiều là r .

Điều kiện cần: Giả sử M là tập a-phin có số chiều là r và M L a



x Ax |





 0

  .

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

  suy ra

M x A x a |







 x Ax Aa

x Ax |



Từ M L a





  

 b



   0

b , do đó

M x A x a |







  , a L







 0



x Ax |



Điều kiện đủ: Nếu M được cho bởi (1.1) với a M , ta có Aa



 0

với

  nên L là không gian con có số chiều r .

Do rankA n r

Vậy dim M r

Định nghĩa 1.5

nR là tập hợp các điểm có dạng

Siêu phẳng trong không gian

 x R



  a x 

 a R

R

 .

  \ 0 ,

trong đó:

Véc tơ a ở trên được gọi là véc tơ pháp tuyến của siêu phẳng.

a x ,



a x ,



Nửa không gian đóng là tập hợp có dạng



   ,

 

 a R



 . R

  \ 0 ,

trong đó:

a x ,



a x ,



Nửa không gian mở là tập hợp có dạng



   ,

 

 a R



 . R

  \ 0 ,

trong đó:

Như vậy, một siêu phẳng chia không gian ra làm hai nửa không gian, mỗi

nửa không gian ở về một phía của siêu phẳng. Nếu hai nửa không gian này đóng thì

phần chung của chúng chính là siêu phẳng.

Định nghĩa 1.6.

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

,a x  là siêu phẳng tựa tại

C , ta nói siêu phẳng

0x nếu

a x ,





a x ,





  . x C

Cho



x a x





0x .

Ta nói là nửa không gian tựa của C tại



 0

Định nghĩa 1.8

R cho trước được gọi là bao lồi

Giao của tất cả các tập lồi chứa tập

của S , ký hiệu coS , đó là tập lồi nhỏ nhất chứa S .

C R , 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 ,

Tập

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 .



1 x

  ...

(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

 1

 k



  ...

(1.2)

 và k  Ν .

i x C  1

 k

sao cho

Chứng minh.

(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 .

C 

coC

M 

coC

M 

coC

M là tập lồi .

Vì . Vì thế để chỉ ra , ta chỉ cần chứng tỏ và coC lồi nên

,x y M . Theo định nghĩa của M , các điểm này có dạng

  , x i

 1

Thật vậy, lấy

i x y ,





  và , i j



 i

 j

 i

 j

  , với y i



 1

.Khi đó, nếu





0,1

thì

 :

 x







   1

 

 1

 i

   j



 1







 1

 i

   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 đó

coM

C

(ii) Cho M là tập hợp các điểm có dạng (1.2).

,x y M , theo định nghĩa của M ta có:

Giả sử

  . y i

  , x i

 1



i x y ,

   C i ,

1,..,

  j

1,...,

 i

 j



 1

 :

 x







Trong đó và . Với  bất kỳ, ta có

   1

 

 1

 i

   j



 1







 1

 i

   j



 1



aff

nên z M và do đó M là tập a-phin. Suy ra .

aff

1 x

,...,

1,...,

Định nghĩa 1.9.

k x được gọi là độc lập a-phin nếu





 1

Các điểm có số chiều



,...,



là độc lập tuyến tính. là k , tức là, nếu các véc tơ

1,..., x

Hệ quả 1.1

nR là tập



trong Bao lồi a-phin M của tập k điểm độc lập a-phin 

k  - chiều.

a-phin (

  , x i

  i

 1

Mọi điểm x M có thể biểu diễn duy nhất dưới dạng:

1.1.3. Nón lồi

Định nghĩa 1.10

x C



      . 0

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.

Ví dụ 1.1

x R x



  

 0

là một nón nhưng không lồi.

Một nón được gọi là nón nhọn nếu nó không chứa đường thẳng, khi đó, ta

nói 0 là đỉnh của nón. Một nón được gọi là nón lồi nếu nó đồng thời là một tập lồi.

Nếu nón lồi này lại là một tập lồi đa diện thì ta nói nó là nón lồi đa diện.

Mệnh đề 1.5. (xem [2], mệnh đề 1.6)



C C

Một tập C là nón lồi khi và chỉ khi nó có các tính chất sau:

   , 

(i)

  .

(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).

,x y C thì



   .

1 2

Do C là một tập lồi nên với mọi

  . y C

Vậy theo (i) ta có x

,x y C và

Điều kiện đủ: Giả sử ta có (i) và (ii).





0,1



 x C



y C

 x

. Từ (i) suy ra C là một nón. Giả sử

 . Theo (ii) ta có

 y C

 , 1

 

   1

 

Từ (ii) suy ra

Vậy C là một nón lồi.

Định nghĩa 1.11

Cone C .

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à

Định nghĩa 1.12

nR . Một véc tơ

y  được gọi là hướng lùi xa

Cho C là một tập lồi trong

của C nếu mọi tia xuất phát từ một điểm bất kỳ của C theo hướng y đều nằm trọn





 y C

 

x C



  .

trong C . Tức là: y là hướng lùi xa khi và chỉ khi

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 C khi và



 y C



  .

chỉ khi

với một điểm x nào đó thuộc C .



y C



Chứng minh

   với x C .Thế thì với mọi u C , mọi

0 , do C

Giả sử

lồi nên ta có

 :



 y





 u C





x 

   

  

  

y C

0 .

 ,với mọi u C và

Cho   , do C đóng, ta thấy u

Nhận xét 1.3. Trong trường hợp C không đóng thì bổ đề trên không đúng.

2R lấy

 :





Ví dụ 1.2. Trong





x x , 1 2

x 1

x 2



     0 0

y 



0,1

  theo hướng này đều nằm trọn trong C nhưng nếu xuất phát từ

x C

x  thì 0

Hiển nhiên, véc tơ có tính chất là mọi tia xuất phát từ một điểm

điều này không đúng.

Định nghĩa 1.13

C R là tập lồi và x C .

Cho

 :



y C

  CN x

   , |

    ,

Ký hiệu

 

CN x gọi là nón pháp tuyến ngoài của C tại x .



 :



y C

  CN x

   , |

    ,

Tập



  CN x

* : 

x C

   , |

    ,

Tập gọi là nón pháp tuyến trong của C tại x .

*C gọi là nón đối cực.

Tập

*C là hai nón lồi đóng chứa gốc.

  CN x và

Ta có thể kiểm tra được rằng

d R là một hướng chấp nhận

0 t

  . Tập tất cả các hướng

Cho C là tập lồi, khác rỗng và x C . Ta nói

t  sao cho x

  với mọi

td C

được của C nếu

 

CF 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



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. Ký hiệu là

  CT x , thì

  F x C

  T x C

khác là nón tiếp xúc với C tại x . Ký hiệu nón này là . Từ

d R

d t ,

x t d

0 :

 T x C

     k

   

   . C k

đây suy ra

Mệnh đề 1.7 (xem [2], mệnh đề 1.8)

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.

x R

j a x ,





1,...,

Ví dụ 1.3

b j , j

Giả sử tập lồi C được cho bởi

   :

 m

với x C , đặt

 :

,j a x



  J x





gọi là tập chỉ số tích cực tại x .

Khi đó

x R

j a x ,







 CT x

  

   J x



cone







 J x



  N x C

j a  j





    j J x

    

    

1.2 Hàm lồi

Trong chương trình Toán phổ thông, chúng ta đã làm quen với khái niệm hàm lồi

một cách cơ bản. Mục này, chúng tôi trình bày khái niệm tổng quát về hàm lồi và

một số tính chất của nó.

:f C

Định nghĩa 1.14.

n C R và

R . Ta sẽ ký hiệu

dom

 x C f x |



   :

   ,

Cho tập

f epi

 :

 



 

  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 .

  f x   nếu x C , ta có thể coi f được xác định trên toàn

Bằng cách cho

dom

n R |

  f x

   : x

   ,

không gian và

f epi

 :

x ,

n   R



 

  R f x |

 

 

f x

0  thì

 với mọi x .

  0

Quy ước nếu

Định nghĩa 1.15

n    lồi và

C R

:f C

R . Ta nói f là hàm lồi trên C nếu epif là

Cho

1nR  . Hàm f được gọi là hàm lõm trên C nếu

f là hàm lồi trên

C .

một tập lồi trong

f R :

R   . Dễ thấy định nghĩa trên





Sau đây chủ yếu ta xét hàm







x y C ,

   ,



   1

 

  f x

   1

 

 f y





 0;1

  x



tương đương với:

f R :

Định nghĩa 1.16

R   được gọi là lồi chặt trên C nếu











x y C ,

   ,



   1

 

  f x

   1

 

 f y





 0;1

  x



f R :

Hàm

R   được gọi là lồi mạnh trên C với hệ số

0 nếu











x y -



x y C ,

   ,



   1

 

  f x

   1

 

 f y



    1



 0;1

  x



1 2

Hàm

Nhận xét 1.4

0 khi và chỉ khi

Dễ dàng kiểm tra rằng hàm f lồi mạnh trên C với hệ số





  . :

  .

 2

hàm

lồi trên C .

Sau đây ta sẽ đề cập đến một bất đẳng thức quen thuộc trong chương trình

phổ thông. Đây là bất đẳng thức tương đối tổng quát trong các bất đẳng thức về hàm

lồi. Các bất đẳng thức giữa trung bình cộng và trung bình nhân, Holder… là những

trường hợp riêng của bất đẳng thức này.

Bất đẳng thức Jensen

f là hàm lồi và nhận giá trị hữu hạn trên tập lồi C thì

Nếu

 

m N



1 x x ,

,..., m x

 và C

j  thỏa mãn

  j

 1

, ta có:



 j

 f x





 1

  

  

Mệnh đề 1.8 (xem [2], mệnh đề 8.1)

:f C

R là lồi trên C khi và chỉ khi



x y C ,

   ,



  

  







  f x

 f y



   1

 

   1

  



 0;1

  x



Một hàm

Chứng minh

x y   như đã nêu trong mệnh đề. ,

Điều kiện cần: Giả sử f lồi, chọn









 ,

epi

 f x



 f y



  ' ,

   '



  ,



 





 y



 '   



epi

Chọn và . Do epi f lồi nên . Vậy 

 1

 

 , 1













 y

 '   





   

 1

 

   1

 1









epi



0  , ta có

  ,

   ,



0,1

 

  ,

  .  

  f x

 f y



và .Với mọi Điều kiện đủ: Chọn 



 '   



    



Do đó nên

 1



   1

        





   1



 

 



epi

   1

      





Vậy hàm f lồi.

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.

f R :

Định nghĩa 1.17

R   (không nhất thiết lồi),

C R là một tập lồi khác





Hàm

f trên C , nếu với mọi



rỗng và  là một số thực. Ta nói  là hệ số lồi của

,x y thuộc C , ta có



0,1





 y







, mọi

 1

 

   1

 

  f x

 f y



    1

 

 

1 2

0 thì f lồi trên C . Nếu f có hệ số lồi trên C là

0 ,

Hiển nhiên, nếu

thì f lồi mạnh trên C vớih hệ số lồi .

Định nghĩa 1.18

  f x   với mọi

x .

Một hàm f được gọi là chính thường nếu dom f   và

1nR  .

Hàm f được gọi là đóng nếu epi f là một tập đóng trong

Nhận xét 1.5

a) Từ định nghĩa của epi f , ta thấy rằng một hàm lồi hoàn toàn được xác

định nếu biết epi f .

b) Nếu f là một hàm lồi trên một tập lồi C thì có thể thác triển f lên toàn

  x

 x C ,  x C .

   : 

  nếu f x  nếu

không gian bằng cách đặt

nR . Hơn nữa



  x

  f x



 x lồi trên

  x là

Hiển nhiên với mọi x C và



 x đóng khi và chỉ khi

f đóng.

chính thường khi và chỉ khi f chính thường. Tương tự,

nR thì dom f là một tập lồi, vì dom f chính là

c) Nếu f là một hàm lồi trên

nR của epi f , tức là:

hình chiếu trên

dom



  



f epi

 R x :

 







a x 

a R

,n R

Ví dụ 1.4 Một số hàm lồi

 , trong đó

 . Dễ dàng kiểm tra

  f x

1. Hàm a-phin:

được rằng f là hàm vừa lồi vừa lõm trên toàn không gian.

0  thì hàm này được gọi là hàm tuyến tính.

Khi

2. Hàm chỉ:

  x

 C

 x C ,  x C .

Cho C   là một tập lồi. Đặt

nếu 0    :  nếu 

Ta nói C là hàm chỉ của C . Do C lồi nên C là một hàm lồi.

x R

| x



3. Hàm mặt cầu.

:h S

R là một hàm bất kỳ.

   :

 1

Cho là một mặt cầu và



 :



  f x



0  nếu    h x nếu    + nếu 

Định nghĩa hàm f như sau:

nR .

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

4. Hàm tựa.

Hàm dưới đây được gọi là hàm tựa của C

y x ,

s C

 ( ) : sup y  x C

5. Hàm khoảng cách.



  : min  x

 y C

Cho C lồi đóng, hàm khoảng cách đến tập C được định nghĩa bởi



1,..., x

6. Hàm chuẩn.





 :

  f x

 : max i x

Giả sử .

 :

  ...

Hoặc

  f x

2 x 1

1 2 2 n





Chương 2

ĐỊNH LÝ TÁCH CÁC TẬP LỒI

Trong giải tích lồi và nhiều lĩnh vực khác như giải tích hàm, giải tích không

trơn và giải tích phi tuyến…, các định lý tách hai tập lồi có một vai trò trung tâm.

Về bản chất, định lý tách trả lời câu hỏi rằng một phần tử có thuộc một tập lồi

không, và nếu không thuộc thì nó sẽ có tính chất gì? Ví dụ tập lồi là nghiệm của hệ

phương trình đại số, hay vi tích phân, tập các điểm bất động của một ánh xạ, hay là

tập nghiệm của một bài toán tối ưu… Nếu điểm thuộc tập lồi đó thì vấn đề được

giải quyết, trái lại, nếu không thì sẽ xảy ra điều gì? Điều này giải thích vì sao các

định lý tách thuộc loại các định lý chọn và là công cụ rất mạnh, thường được dùng

để chứng minh sự tồn tại của một đối tượng trong nhiều vấn đề thuộc những lĩnh

vực khác nhau. Một mệnh đề thường được dùng làm nền tảng lý thuyết tối ưu hiện

đại là định lý tách các tập lồi, mà một dạng tương đương của nó trong giải tích hàm

là định lý Hahn – Banach rất quen thuộc trong giải tích hàm.

2.1. Định lý tách 1

Định nghĩa 2.1

   (không nhất thiết lồi) và y là véc tơ bất kỳ, đặt

C R





 : 

inf  x C

Cho

C sao cho



 y là khoảng cách từ y đến C . Nếu tồn tại

y



Ta nói





 

, thì ta nói  là hình chiếu (vuông góc) của y trên C . Ký hiệu





nR . Khi đó:

Mệnh đề 2.1 (xem [2], mệnh đề 5.1)

 y R

, n

C

Cho C là một tập lồi đóng khác rỗng trong

 hai tính chất sau là tương đương:

(i) Với mọi

 





a) ,

 

N

 ( )

b) .

y R , hình chiếu

y của y trên C luôn tồn tại và duy nhất. ( )



y x ,



(ii) Với mọi

 là siêu pẳng tựa của C tại









p C

Cp y ( )

(iii) Nếu y C , thì



y x ,



x C

   ,









p C

và tách hẳn y khỏi C , tức là



y y ,



 . 0









p C

và



Chứng minh



0,1

(i) Giả sử có a). Lấy x C và . Đặt

   1

  

 :   x x

C và C lồi, nên x

C  . Hơn nữa do  là hình chiếu của y , nên

 





x

. Hay









 

    

 2

0 , ta có

   x

2 2 



  ,



 . 0



Khai triển vế phải, ước lược và chia hai vế cho



0,1





y x ,





   .

x C

Điều này đúng với mọi x C và . Do đó khi cho  tiến đến 0 ta được

 

N

  

Vậy .

Bây giờ giả sử có b). Với mọi x C , có

















  



 





 











  

 























Từ đây và b), dùng bất đẳng thức Cauchy – Scharz ta có:



 



 

( )p y







  , và do đó

x C

y ( )



inf



Suy ra .

 x C

ii) Do , nên theo định nghĩa của cận dưới đúng (infimum), tồn

C sao cho





y ( )

  .

lim k

tại một dãy

kjx

hội tụ đến một điểm  nào Vậy dãy  kx bị chặn, do đó nó có một dãy con 

C . Vậy

đó. Do C đóng nên

 















lim j

lim k

Chứng tỏ  là hình chiếu của y trên C .

1 đều là hình chiếu của y trên C , thì

  

y ,

1   

Bây giờ ta chỉ ra tính duy nhất của hình chiếu. Thật vậy, nếu tồn tại hai điểm  và

  

 1 



 y

1   

 0

Tức là

1  y

1   

 0

1  

1 

và

 , và do đó

Cộng hai bất đẳng thức này ta suy ra .

 

N

  

iii) Do , nên





y x ,





x C

   .





y x ,







 ,

Vậy là một siêu phẳng tựa của C tại . Siêu phẳng này





y y ,





 





 . 0

tách y khỏi C vì y  , nên

riC

Mệnh đề 2.2 (xem [2], mệnh đề 5.4)

Cho C là một tập lồi khác rỗng và . Khi đó tồn tại siêu phẳng tựa

0x trên C .

của C tại hình chiếu của

Chứng minh

0( p x

)

0x trên C là

C int

Gọi hình chiếu của

Trước hết xét trường hợp int C   . Vậy . Phân biệt trường hợp:

C . Do C lồi, đóng, nên theo (iii) của mệnh đề 2.1, siêu phẳng

p x (

)



0 x x ,



p x (

)



0 x p x ,

(

)

0( p x

)

0x .

là siêu phẳng tựa của C tại tách hẳn C và



\n R C

C . Khi đó do

C int

0 x

b) , nên . Vậy tồn tại dãy

C với mọi k . Do C lồi, đóng, nên lại áp dụng (iii) của Mệnh đề 2.1, tồn tại

)kp x (

với

k  , thỏa mãn:

k 

k 

p x (

)

  . x C

k

siêu phẳng tựa của C tại . Tức là tồn tại

k , ta có thể coi

k  , và do đó có thể giả sử

 .

Bằng cách chuẩn hóa

Do ánh xạ chiếu liên tục, nên từ bất đẳng thức trên, qua giới hạn và chú ý là

p x (

)

x

C ), ta có:

0 



0 

p x (

) =

0 

  . x C

0 

x C

(Vì

  là siêu phẳng tựa của C tại

0x .

Vậy

Định nghĩa 2.2

Ta x 

T a x





T a y

 

x C

  . y D

Cho hai tập C và D khác rỗng, ta nói siêu phẳng tách C và D nếu

Ta x 

T a x





T a y

 

x C

  . y D

Ta nói siêu phẳng tách chật C và D nếu

Ta x 

T a x







T a y

 

x C

  . y D

inf  y D

sup  x C

Ta nói siêu phẳng tách mạnh C và D nếu

Bổ đề 2.1

C R là một tập lồi khác rỗng. Giả sử

C . Khi đó tồn tại

n  t R t ,

 thỏa mãn

t x ,



t x ,

Cho

Chứng minh

riC

Do , nên sự tồn tại siêu phẳng tách trong bổ đề được suy ra từ mệnh đề 2.2.

Định lý 2.1 (Định lý tách 1) (xem [2], định lý 6.1)

nR sao cho C D   . Khi đó

Cho C và D là hai tập lồi khác rỗng trong

có một siêu phẳng tách C và D .

C D

Chứng minh

  



n  t R t ,

Do C và D là lồi, nên C D cũng lồi. Hơn nữa, , vì C D   .

0 x  , tồn tại véc tơ

 sao cho

t z  với , 0

x C y D ,



  , với y

 , nên ta có

Theo bổ đề 2.1 áp dụng với

  . Vì z

t x ,



t y ,

 

x C y D ,

 .



t y

mọi z C D

 : sup ,  y D

Lấy

,t x  tách C và D .

khi đó siêu phẳng

2.2 Định lý tách 2

Bổ đề 2.2 (xem [2], bổ đề 6.2)

C R là một tập lồi đóng khác rỗng sao cho 0 C . Khi đó tồn tại một

Cho

n  t R t ,

 và 0

0  sao cho

t x ,





  . x C

véc-tơ

Chứng minh

r  sao 0

Do C đóng và 0 C , nên tồn tại quả cầu B tâm ở gốc, bán kính

t R

  \ 0

R , sao cho

t x ,





t y ,

 

x C

  . y B

và cho C B   . Áp dụng định lý tách 1 cho hai tập C và B , ta có

t  và do đó khoảng cách từ gốc đến siêu phẳng ít

Bằng chuẩn hóa ta có thể xem

r  . Vậy thì

t x ,

r

  .

nhất là bằng

Nhận xét 2.1

t x ,



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

 2

phẳng .

Định lý 2.2 (Định lý tách 2) (xem [2], định lý 6.2)

Cho C và D là hai tập lồi đóng khác rỗng sao cho C D   . Giả sử có ít

nhất một tập là com-pắc. Khi đó hai tập này có thể tách mạnh được bởi một siêu

phẳng.

Chứng minh

đóng. Giả sử C là tập Compact. Ta chỉ ra tập C D

 

C D







C y ,

z . Ta có

 . Vì

j   . Vậy

C compact, nên có một dãy con

jkx

x khi

   

y C D

Thật vậy, giả sử và với



    . Vậy z

z D

là tập đóng. . Chứng tỏ C D

 

t  sao cho

t x ,



 y 

 với mọi

x C y D ,



 . Vậy

t x ,





t y



nên theo bổ đề 2.2, tồn tại Do 0 C D

inf  x C

sup ,  y D

 2

Chứng tỏ C và D có thể tách mạnh.

Nhận xét 2.2

Điều kiện một trong hai tập là com-pắc trong định lý là không thể bỏ được

Ví dụ 2.1

 :

x t ,



2 R x |







 0 ,

Cho hai tập hợp:

 :

x t ,



2 R t |







1 x

  

     

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

mạnh được.

Hình 1.

Từ định nghĩa ta thấy rằng, nếu hai tập nằm trong cùng một siêu phẳng, thì

chúng vẫn tách được, ví dụ chính bằng siêu phẳng đó. Để tránh trường hợp này

người ta đưa ra khái niệm tách đúng sau:

Định nghĩa 2.3

Ta x  nếu

T a x





T a y

 

x C

  y D

Hai tập C và D được gọi là tách đúng bởi siêu phẳng

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

B ri

  .

đúng là ri

Chứng minh

Điều kiện cần

T '

 

T '

x A

y B

    . ,

Tt y



  y

Giả sử có siêu phẳng Tt x  tách A và B , tức là

B ri

  .

Giả sử siêu phẳng này không chứa B , khi đó . Suy ra

Điều kiện đủ







 A B

B ri

  . Khi đó,









. Xét hai trường hợp: Giả sử ri

  .

 int A B







T t x



T t y

  x

int

  y

int

i) Trường hợp

t  và 0

 0 int A B







inf



int

 ,



sup



int

Khi đó . Vậy tồn tại . Đặt

  . Khi đó siêu

 T t y y |

 B

 T t x x |

 A

, thì   . Lấy   

phẳng Tt x  sẽ tách A và B , nhưng không thể đồng thời chứa cả A và B .

  .

 int A B



ii) Trường hợp

  và F là không gian con song song với bao a-phin của C .

Đặt C A B

'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

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 . Gọi F  là không gian vuông góc với F . Với mỗi

n x R đặt

't và p , trong đó p là ánh xạ chiếu xuống không gian con

  t x là hàm hợp giữa

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

định siêu phẳng

đúng hai tập A và B .

Nhận xét 2.3

B ri

  , thì hai tập này vẫn có thể tách

Nếu A và B là hai tập lồi mà ri

đượ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.

Ví dụ 2.2

B ri

  , chúng vẫn tách được bằng chính

Rõ ràng A và B là hai tập lồi mà ri

mặt phẳng nhưng chúng không tách đúng được.

Một hệ quả rất quan trọng của định lý tách là bổ đề chọn mang tên nhà toán

học Hungary Farkas, được chứng minh từ năm 1892 dưới dạng một định lý hình

học. Bổ đề này rất trực quan, dễ áp dụng trong nhiều lĩnh vực như tối ưu, điều

khiển, lý thuyết toán tử…

Hệ quả 2.1 (Bổ đề Farkas) (xem [2], hệ quả 6.1)

a R . Khi đó trong hai hệ dưới

Cho A là một ma trận thực cấp m n và

đây có một hệ và chỉ duy nhất một hệ có nghiệm:



T a x

 với một

x R ,

(2.1)

TA y



a y ,

 với một

y R

. (2.2)

Một cách phát biểu tương đương dưới ngôn ngữ hình học là:

T x a x 

x Ax 

 0

khi và chỉ khi véc tơ a chứa nón  Nửa không gian 

TA y



a y ,

 0

T A x

   khi và chỉ khi

T a x

nằm trong nón sinh bởi các hàng của ma trận A tức là

T x a x 

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

x Ax 

 0



 0

a ở trong nón sinh bởi các hàng của ma trận A .

Ax  0

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a . . . . . . . . . . . .

khi và chỉ khi véc tơ pháp tuyến nằm trong nửa không gian 

Hình 2

TA y

Chứng minh

Ax  , thì từ

a , nhân



T a x



T y Ax

Giả sử (2.2) có một nghiệm y nào đó. Nếu như

 , ta có

 . Vậy (2.1) không thể

tích vô hướng với x , và do

có nghiệm.



  y

0 :

T A y





 x

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 C .

p  và một số

Do (2.2) không có nghiệm nên a C . Theo định lý tách 2, tồn tại

R sao cho

0  .Thay

T p a





T p x

x A y



0y  , ta viết được

, với với mọi x C . Do 0 C nên

 

T p A y



T y Ap

x C  với mọi

0  . Vì từ

x A y





T  x A y

, có Bên cạnh đó, nếu x C thì

. Vậy các tọa độ của y có thể lớn tùy ý, nên từ bất đẳng thức

Ap  .

 

T p A y



T y Ap

, suy ra

Ap  và 0

Ta p  . Chứng tỏ

Vậy, ta đã chỉ ra sự tồn tại của một véc tơ p sao cho

rằng (2.1) có nghiệm.

CHƯƠNG 3

ỨNG DỤNG CỦA ĐỊNH LÝ TÁCH

3.1. Điều kiện tối ưu.

Định nghĩa 3.1.

C R khác rỗng và

f R :

R .

Cho

*x C được gọi là điểm cực tiểu địa phương của f trên C nếu

Một điểm

*x sao cho



   . x U C

  f x

 f x



tồn tại một lân cận U của

*x C được gọi là điểm cực đại địa phương nếu nếu tồn tại một lân

Điểm

*x sao cho



   . x U C

  f x

 f x

*

cận U của



  x C

  f x

 f x

*

Nếu

*x được gọi là cực tiểu toàn cục hay cực tiểu tuyệt đối của f trên C , và nếu



  x C

  f x

 f x

*

thì

*x được gọi là cực đại toàn cục hay cực đại tuyệt đối của f trên C.

thì

f x với các điều kiện

Bài toán OP: Tìm cực tiểu của một hàm lồi trên một tập lồi có dạng sau

min  



1,...,

  0, 

ig x



1,...,

  0, 

jh x

x X

f g ,



1,...,

R là một tập lồi đóng khác rỗng và







1,...,

Trong đó là các hàm lồi







1,...,

X . Ta sẽ luôn giả sử rằng X có điểm trong và các hàm aphin

hữu hạn trên X , còn là các hàm a-phin hữu hạn trên tập a-phin của





độc



j  với 0

  h x j



 1

lập tuyến tính trên X , theo nghĩa, nếu với mọi x X , thì

mọi j .

Bài toán (OP) này được gọi là một quy hoạch lồi. Hàm f được gọi là hàm mục







1,...,



1,...,

  x X g x ,









  jh x

tiêu. Các điều kiện , được gọi là



i 0



1,...,



1,...,

ràng buộc. Tập

 x X g x |



  m h x j

   :



được gọi là miền chấp nhận được. Một điểm x D được gọi là điểm chấp nhận



1,...,



 ig i

 1,...,

 k aphin, nên D là một tập lồi. Điểm cực tiểu của f trên D cũng được gọi

được của bài toán (OP). Do X là tập lồi, các hàm lồi trên X và

là nghiệm tối ưu của bài toán (OP). Ta xây dựng hàm sau, được gọi là hàm



Lagrange, cho bài toán (OP):

 L x

  f x

  :    0

 i

  g x i

 j

  h x j



 1

Dựa vào hàm Lagrange, ta có kết quả sau:

Định lý 3.1 (Karush – Kuhn - Tucker) (xem [2], Định lý 9.1)

*x là nghiệm của bài toán quy hoạch lồi (OP) thì tồn tại

Nếu



0,1,...,



1,...,









*   i

*  j

* *   ,



* *   ,

và không đồng thời bằng 0 sao cho

 L x



 L x



min  x X



1,..,

(điều kiện đạo hàm triệt tiêu)





*  i

 ig x



(điều kiện độ lệch bù)

Hơn nữa nếu int X   và điều kiện Slater sau thỏa mãn





1,...,







 0   x D g x : 0

0  và hai điều kiện đạo hàm triệt tiêu và độ lệch bù ở trên cũng là điều kiện

* 0

thì

*x là nghiệm tối ưu của bài toán (OP).

đủ để điểm chấp nhận được

Chứng minh

*x là nghiệm của (OP).

Giả sử

 :

,...,

 

x X









1,...,



1,...,

  |



  f x

 0

  g x i

 i

  m h x j

 J

 f x



Đặt

       m k



0 Do X   lồi,

f g lồi và jh a-phin hữu hạn trên X nên C là một tập lồi ,



khác trống trong

  f x

m kR   . Hơn nữa 0 C . Thật vậy, vì nếu trái lại 0 C , thì tồn tại *  f x

*x là nghiệm tối ưu của (OP).

một điểm chấp nhận được x thỏa mãn . Điều này mâu thuẫn với việc



0,1,...,



1,...,









*  i

*  j

Khi đó theo định lý tách 1, tồn tại không đồng



  0

,...,



thời bằng 0 sao cho





*  i i

*   i i

     m k





 1

. (3.1)

     , vì theo định nghĩa của

,...,



   , thì  0,...,

Chú ý rằng với mọi

    . Hơn nữa, 0

,...,

C ta chỉ lấy

x

* 0

* 1

* m

. Từ chú ý này, ta suy ra ngay tất cả

0 

x X ,









1,...,



1,...,

với và ta lấy

 f x



  g x i



  



 0

  , i

 j

h x j

, 0,..., 0

 . Thay vào (3.1) và cho

0  , sẽ được

, mọi   f x



  0,..., m







 

x X

thì 

 f x



*  0

*  i

  g x i

*  i

  h x i

*  0

*  i

*  i

 f x



 g x i



 h x i





 1

* *   ,



* *   ,

  . x X

 L x



 L x



Hay

Đây chính là điều kiện đạo hàm triệt tiêu.

*x chấp nhận được, nên

 , thì với mọi

  . Nếu như tồn tại một i nào đó mà

0  , ta có

 * ig x

,...,

 ( ở vị trí thứ

1i  )

     ,

 , 0,..., 0 C

Để chứng minh độ lệch bù, ta chú ý rằng do

0  , nên

0  , ta thấy

i  . Nhưng

i  . Suy ra

i  .

Thay vào (*) và cho

Điều kiện độ lệch bù do đó cũng được thỏa mãn.

0  . Thật vậy, vì nếu

0  , thì do điều kiện đạo hàm triệt tiêu và điều kiện độ

* 0

Để chứng minh điều kiện đủ, ta giả sử điều kiện Staler thỏa mãn. Ta có









 

x X

lệch bù, ta có

*  i

*  j

*  i

  g x i

*  j

  h x j

 g x i



 h x j





 1

0  , nên phải có hoặc *

i  với một i nào đó, hoặc nếu

i  với 0

* 0

Thế nhưng do

j  với một j nào đó.

mọi i , thì sẽ có

0x vào bất đẳng thức trên sẽ được

Trong trường hợp đầu, thay









*  i

*  j

*  i

*  j

 g x i



 h x j



 g x i



 h x j





 1

Mâu thuẫn.





 

x X

*  j

  h x j

 h x j





 1

  

x X

Trong trường hợp sau, ta có:



jh aphin với mọi j , nên từ đây suy ra

 h x j





Do int X   và . Từ đây

   . Điều này mâu thuẫn

jh độc lập tuyến tính trên X , ta có

* j

và do các hàm

0  .

j không đồng thời bằng 0. Vậy

i và

* 0

với việc tất cả các nhân tử

0  , nên bằng cách chia cho

0  , ta có thể coi hàm Lagrange là

* 0





 L x

   ,

  f x

 i

  g x i

 j

  h x j



 1











Từ điều kiện đạo hàm triệt tiêu và độ lệch bù, nên với mọi x chấp nhận được, ta có:

  f x

 i

 j

 i

  g x i

 j

  h x j

 f x







 g x i



 h x j





 1

*x là lời giải tối ưu của (OP).

Chứng tỏ

Nhận xét 3.1

Khi X là tập mở (nói riêng là toàn không gian) và mọi hàm đều khả vi, thì

điều kiện đạo hàm triệt tiêu sẽ là



 g



*    0

*  j

*   i









 h x i





 1

Như vậy, bài toán trên cho ta thấy một cách định lượng khi xét một bài toán

tìm cực tiểu của một hàm lồi trên một tập lồi. Người ta cũng đã chứng minh một

cách định tính được rằng mọi điểm cực tiểu địa phương của một hàm lồi trên một

tập lồi cũng chính là điểm cực tiểu tuyệt đối (xem [2] chương 9,mệnh đề 9.1).

Tính chất trên không thể áp dụng cho cực đại của hàm lồi: Cực đại địa

phương của một hàm lồi không nhất thiết là cực đại tuyệt đối.

Ví dụ 3.1

f x ( )

x

1, 2

f x ( )

x

Xét hàm số . trên đoạn 

x   , nhưng

1, 2

Hàm số là đạt cực đại địa phương trên đoạn 

x  . 2

điểm cực đại tuyệt đối lại là

3.2. 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.

Định nghĩa 3.2

D R là một tập lồi và

nR . Hệ bất đẳng thức

f 1,..., m f





 I

  x D f x ,

Cho là các hàm lồi trên

Được gọi là hệ bất đẳng thức lồi, trong đó I là tập chỉ số và ký hiệu  có thể hiểu

là  hoặc  .

Hệ bất đẳng thức lồi xuất hiện trong nhiều ứng dụng. Do tính chất của hàm

lồi, tập nghiệm của một hệ bất đẳng thức lồi luôn là một tập lồi. Dựa vào các định lý

tách, ta có thể đưa ra những điều kiện cần và đủ về sự tồn tại nghiệm của một hệ bất

đẳng thức lồi.

Mệnh đề 3.1 (xem [2], mệnh đề 9.5)

f 1

f ,..., m

Giả sử là các hàm lồi hữu hạn trên tập lồi D   . Khi đó, hệ







0,1,...,

  x D f x ,

(3.2)



0,1,...,





  i

không có nghiệm, khi và chỉ khi tồn tại các số không đồng thời

  

x D

bằng 0 sao cho

  x

 i





0  x D f

 với mọi







1,...,

Ngoài ra, nếu có điều kiện chính quy Slater: tồn tại

0  .

thì

Chứng minh

Điều kiện đủ là hiển nhiên, nên ta chỉ cần chứng minh điều kiện cần.

 1

 :



,...,



 





0,...,

Giả sử hệ (3.2) không có nghiệm. Đặt





  x D f x ,

y y , 0 1

y i , i



 m



0,...,



if lồi 

,...,



0 C . Áp dụng định lý tách, tồn tại

 sao cho





    , 0 m

Do D và nên C lồi. Theo giả thiết hệ (9.4) không có nghiệm nên

  

y C

 i

y i





0  , ta có





  x

f ,..., m



   . 

Chú ý rằng theo định nghĩa của C , với mọi x D và



  

x D

Vậy

 i

  f x i



 





0  , nên suy ra

  

x D

Điều này đúng với mọi

  x

 i





. (3.3)

   . Thật vậy, nếu trái lại có

j  với một j nào đó, thì do

Ta sẽ chứng tỏ



C , nên



y i

  f x i

y 0,..., m

với mọi x D , mọi , ta có 

 y i i



iy khác cố định, ta thấy vế trái của bất đẳng thức trên tiến

jy   còn mọi

Cho

i  với mọi i .

đến  . Mâu thuẫn vì vế phải bằng 0. Vậy

0  thì theo (3.3), có

  

x D

Cuối cùng giả sử điều kiện Slater thỏa mãn. Nếu như

 i

  f x i





  , theo điều kiện chính quy Slater thì

0 x D



Lấy

 f x i

0



 1

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)

f 1,..., m f

Cho 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



 A D



x D Ax ,









1,...,

  b f x , i



1,...,

. Khi đó, hệ trận thực cấp k n . Giả sử

k t R và

  i

  i

 1

t Ax b ,



  

x D

không có nghiệm khi và chỉ khi tồn tại sao cho và

 i

  f x i



 1

Chứng minh

Điều kiện đủ: Hiển nhiên

Điều kiện cần:

Lấy tập



   :

 x D Ax b |





i 0,



1,...,

  x E f x ,

1,...,

Do D lồi nên E lồi và theo giả thiết, hệ

  , i i

  

x E

không có nghiệm. Vậy áp dụng mệnh đề 3.1, sẽ tồn tại thỏa mãn

 i

  f x i

  i



 1

và .

  i

  i

 1

Bằng cách chia cho , ta có thể coi

  f x

  f x i

  :

 1

 :

k   R

R x D Ax b

 

 



. Khi đó f lồi và hữu hạn trên D . Lấy Với mỗi x D , lấy



  y f x ,

y y , 0

 



,y y

C sao cho

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 đề

0, t t

  và  R

0

t y ,



  0

 , C





t y 0 0

y y , 0

2.1, ta có thể tách đúng C và 0. Tức là tồn tại 

và

t y ,

 0

t y 0

t  . 0

(3.4)

t  thì 0

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ó 0

Nhưng 0t không thể bằng 0, vì nếu 0

t y ,

  

 .

 y A D b



(3.5)





 A D



 0 ri A D b







t y ,

  

y A D

Thế nhưng theo giả thiết , tức là . Từ đây và (3.5) suy ra





t  , nên

t y ,



  0

y y ,

 . C





t y 0 0

y A D

Do 0

t  0





    . Vậy x D



Mâu thuẫn với (3.4), vì . Vậy 0

  Ax b f x - ,



   

t Ax b ,



   .

x D

  f x



 

Từ định nghĩa của C ta có

0  , nên

t Ax b ,



   .

x D

  t f x 0

Điều này đúng với mọi

t  , ta có điều cần chứng minh.

  f x



 f x i

 

 1

Thay và chia hai vế cho 0

Nhận xét 3.2

b bởi hệ Ax b .

Mệnh đề vẫn còn đúng khi thay hệ Ax

3.3. Xấp xỉ tuyến tính của hàm lồi

Một tập lồi, với những giả thiết cho trước có thể xấp xỉ với độ chính xác tùy

ý bởi các tập lồi đa diện, được xác định bằng các nửa không gian tựa của tập lồi.

Một cách tương ứng, dưới đây ta sẽ chỉ ra rằng một hàm lồi, với các giả thiết thông

thường đều có thể 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 là cơ sở cho việc xấp xỉ các bài toán có cấu trúc lồi bởi các bài toán

tuyến tính. Trong mục này chúng ta sẽ dùng định lý tách để chứng minh Bổ đề làm

cơ sở cho định lý về sự xấp xỉ một hàm lồi bởi các hàm non a-phin. Trước hết ta xét

định nghĩa về hàm non a-phin:

Định nghĩa 3.3

nR nếu l là hàm a-phin trên



Hàm l là hàm non a-phin của một hàm f trên

x R .

nR và   l x

  f x

với mọi

Ví dụ 3.2

Hàm đồng nhất bằng  là hàm non a-phin của mọi hàm.

Ví dụ 3.3

* x x ,





 . x

  f x





Nếu là hàm liên hợp của f , thì

*x xác định một hàm a-phin

 :

* x x ,





 . x

  l x

 f x







Từ đây thấy rằng mỗi

là hàm non a-phin của f trên toàn không gian.

Bổ đề 3.1 (xem [2], bổ đề 10.1)

f là một hàm lồi đóng, chính thường trên

nR . Khi đó với mọi điểm

0,x t 0

epif

Cho



,nR 

 sao cho





, đều tồn tại

T 





T   



  x

dom

  f x

Chứng minh

0, 0 x t



epi

Theo giả thiết f là hàm lồi đóng chính thường nên epif là một tập lồi, đóng



 : epi

, nên áp dụng định lý tách mạnh cho hai tập và khác rỗng. Do điểm 



 a R



 và một số

 :

0 x t ,

 

lồi, đóng và , sẽ tồn tại 

 

 

R sao cho

T a x



  



T a x



 t



x t ,



epi





. (3.6)

0 , vì nếu

0 thì sẽ có mâu thuẫn ở bất đẳng

Trước hết ta thấy rằng

thức đầu của (3.6) khi cho t tiến đến  . Lúc đó vế trái tiến đến  , trong khi đó



dom

ở vế phải  là một số hữu hạn cố định.

0 , vì nếu

0 thì từ bất đẳng thức (3.5),

x 0

Hơn nữa nếu thì

x

T a x





T a x

lấy , ta có . Vô lý. Vậy trong trường hợp này, chia hai vế (3.6)

0  , ta có điều phải chứng minh.



f dom

cho

0 . Từ (3.6) có

T a x





T a x

  x

f dom

Bây giờ chỉ cần xét trường hợp và



1,x t 1

epif



domf

 1 f x





domf

và Lấy . Lại áp dụng định lý tách mạnh

1,x t 1

, và tập epif . Khi đó, chú ý rằng 1x . Khi đó   cho tập gồm duy nhất một điểm 

 

b ,



 b R



 sao cho

 

tương tự như trên, tồn tại 

T b x t

 



1 T a x

1   t

x t ,



f epi





epif

0 và mọi 

,x t

(





)T a x t

 

b x t

 



T a x

 

 

Từ đây và (3.6), thấy rằng với mọi , ta có

. (3.7)

Ta x  nên

Chú ý rằng, do

(





)T a x

  t

T b x

  t



T a x



  

. (3.8)



  b

   

 

với mọi  đủ lớn. Vậy với  đủ lớn, bằng cách lấy thì từ

(3.7) và (3.8) suy ra

T 

x t

 

T    '





x t ,



epi







  f x

T 





T    '



  x

f dom

Nói riêng lấy , ta có

  f x

Như vậy trong trường hợp này ta cũng có (3.6).

Từ bổ đề trên chú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)

nR đều là bao trên của các hàm non

Mọi hàm lồi đóng chính thường f trên



  f x





l v

 l

  A

sup v

a-phin của nó. Tức là:

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]

3.4. 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 này rất phong phú nhờ những tính chất của tập lồi và

hàm lồi. Trong phần này, chúng ta mở rộng khái niệm đạo hàm bằng khái niệm

dưới vi phân và một số tính chất cơ bản của nó. Đặc biệt áp dụng định lý tách và

siêu phẳng tựa để 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 f lồi.

Như ta đã biết, hàm lồi khả vi tại một điểm nào đó, thì phương trình tiếp

tuyến tại điểm đó nằm dưới đồ thị. Tuy nhiên, một hàm lồi có thể không khả vi, ví

x

x  . Trong trường hợp này, người

  f x

dụ hàm lồi một biến không khả vi tại

ta mở rộng khái niệm đạo hàm bằng dưới đạo hàm, sao cho vẫn có được tính chất

cơ bản trên của đạo hàm của hàm lồi khả vi.

f R :

Định nghĩa 3.4

R là dưới đạo hàm của f tại x nếu

 R   . Ta nói



*, x z







 . z

 f x



  z

Cho

Tương tự như đối với hàm lồi khả vi thông thường, biểu thức này có nghĩa là

phương trình tiếp tuyến nằm dưới đồ thị hàm số. Tuy nhiên khác với trường hợp

khả vi, tiếp tuyến ở đây có thể không tồn tại duy nhất.

   f x

. Đây là mộ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à

nR (có thể bằng rỗng).

tập trong

  thì ta nói hàm f khả vi dưới vi phân tại x .

   f x

 

Khi

  f x

Theo định nghĩa, một điểm khi và chỉ khi nó thỏa mãn một hệ vô hạn các

   f x

bất đẳng thức tuyến tính. Như vậy, là giao của các nửa không gian đóng. Vậy

   f x

dom

 f

 :





   f x



   .

luôn là một tập lồi đóng (có thể rỗng). Ký hiệu

Ví dụ 3.4



x x R

 . Tại điểm

x  hàm này không khả vi, nhưng nó khả

  f x

Hàm

 f



* x x ,



  0 :

dưới vi phân và



  . x

C R là một tập lồi, khác rỗng.



Ví dụ 3.5

  f x

  x

 C



x C   x C

0 nếu + nếu

   

là hàm chỉ của C

C , ta có:



* x x ,





  x

  C

 C





Khi đó với



  . x

Với x C thì C   nên bất đẳng thức này luôn đúng. Vậy

* x x ,



  

x C



 C



 N x C



  



C

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

0x .

chính là nón pháp tuyến ngoài của C tại

Mệnh đề 3.3 (xem [2], mệnh đề 11.3)

f R :

R   lồi, chính thường. Khi đó:







Cho

  .

   f x

(i) Nếu x domf , thì



int

domf

  và com-pắc. Ngược lại, nếu

 





   f x



ri domf

(ii) Nếu thì





và Com-pắc thì .



domf



Chứng minh

  z   . Vậy nếu x domf

  f x   và do đó

(i) Cho z , thì , thì

*x thỏa mãn

*,x z







  .

  f x

  f z

không thể tồn tại

  .

   f x



Vậy

 int dom



  ,x f x





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

,n p R t R



(ii) Trước hết giả sử . Ta có điểm nằm trên biên của

 không đồng thời bằng 0 thỏa mãn

  ,x f x





qua , tức là tồn tại

p x ,





p y ,









epi

  tf x



 

(3.9)

t  , vì nếu

t  thì 0

p x ,



p y ,

  y

dom

Ta có



p  . Vậy,

t  . Hơn nữa,

t  , 0

 int dom



Nhưng do nên điều này kéo theo

t  thì trong bất đẳng thức (3.9), khi cho   ta suy ra mâu thuẫn vì vế

vì nếu

 

trái cố định.



t  , đồng thời thay

 f y



p t

* x x ,





* x y ,



  y

f dom

Chia hai vế của (x) cho và đặt , ta

  f x

 f y



được

*, x y







  y

f dom

Hay là

  f x

 f y



 f y   , do đó



*, x y







 . y

  f x

 f y



 

Nếu y domf  thì

  f x

Chứng tỏ .

Nhận xét 3.3

Cách chứng minh trên cho thấy dưới đạo hàm của f tại x chính là véc tơ

  ,x f x





pháp tuyến của siêu phẳng tựa của bao đóng của epi f tại .

3.5. Phép vô hướng hóa bài toán véc tơ.

Trong cuộc sống, các vấn đề thường có nhiều mối ràng buộc. Khi mô hình

hóa những mối liê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ơ.

Trong phần này chúng ta sẽ nghiên cứu bài toán tối ưu véc tơ.

min

  x D R

Bài toán

  F x







(VP )

p  R

f 1,...,





Trong đó,

x : biến.

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)



 i



T b



nR , ta nói a b nếu









a i

b i

a 1,...,

a n

b 1,...,

b n

  

Với hai véc tơ và trong

b nếu

 . i

a i

b i

và a

Định nghĩa 3.5

*x D được gọi là nghiệm Pareto lý tưởng của bài toán (VP ) nếu



  . x D

 F x



 F x



Véc tơ

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

*x 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





Véc tơ

  F x

 F x

*

 F x

*



sao cho và .

*x được gọi là nghiệm Pareto

  F x

 F x

*

thì Nếu không tồn tại x D mà

yếu của bài toán (VP).

Định nghĩa 3.7

*x D được gọi là nghiệm Pareto lý tưởng của bài toán

max

  x D R

Véc tơ

  F x









) ( max VP

  F x

 F x

*

 F x

*



và . nếu không tồn tại x D sao cho

*x được gọi là nghiệm Pareto

  F x

 F x

*

Nếu không tồn tại x D mà thì

yếu của bài toán ( max ).

Nhận xét 3.4

Một điểm là nghiệm Pareto (nghiệm Pareto yếu) của bài toán cực tiểu

min

  x D R

  F x





max

  x D R

khi và chỉ khi nó là nghiệm Pareto (nghiệm Pareto yếu) của bài toán cực đại

  F x

 



Bài toán véc tơ tuyến tính:

Bài toán (VP ) hoặc ( max ) trong đó

Cx

n x R

 F x

D là tập lồi đa diện được xác định rõ, ví dụ như

với C là ma trận thực,





b R



  Ax b

m n

và . với A là ma trận 

đượ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 (VP ) hoặc ( max ) trong đó 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 được gọi là bài toán tối ưu véc tơ lồi.

Ví dụ 3.6

Giả thiết rằng một công ty sản xuất hai loại hàng hóa. Đặt:

j 

1, 2





jx là số lượng của loại hàng hóa



x x là chi phí sản suất của 



f 1

,x x 1 2



x x là chi phí xử lý chất thải của các sản phẩm 



f 1

,x x 1 2





f 1

x x , 1

x 1

x 3 , 2





 

 

x x , 1

x 1

Chẳng hạn:



, 0



Tập ràng buộc là

x 1

a 1

a 2

(giới hạn số lượng sản phẩm)



 b

b x 1 1

b x 2 2

(ngân sách)

Bài toán đặt ra là xác định số lượng của từng hàng hóa cần sản xuất để giảm



,x x 1 2

của bài toán (VP ) tối đa chi phí tức là tìm nghiệm 

Để giải các bài toán tối ưu véc tơ ta thường sử dụng cách vô hướng hóa bài

toán véc tơ.

Mệnh đề 3.4

  . Khi đó mọi nghiệm cực tiểu toàn cục của bài toán

min

  x D R

  F x



   P 

 T 



(i) Cho

VP .

đều là nghiệm Pareto của bài toán 

   . Khi đó mọi nghiệm cực tiểu toàn cục của bài toán

min

  x D R

  F x



   P 

 T 



(ii) Cho 0

VP .

đều là nghiệm Pareto yếu của bài toán 

Chứng minh

Hiển nhiên

Mệnh đề 3.5.2

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

0  sao cho

Giả sử 

VP luôn tồn tại 0



arg min

  F x

 T 

  x D

Pareto u của 

Chứng minh







 y R y F x :



 

   :

 F u x D ,

Đặt

Đặt C coK



 0

C R

Ta sẽ chứng minh

Do 0 K nên C   .

1,...,

K thỏa mãn

Giả sử y C , khi đó, tồn tại



t ,

  0 j



t y j



 1





K nên tồn tại

jx D thỏa mãn

  F u

 F x



Với mọi j , do .

t x j

  . Do F là hàm lồi nên ta có

 1







  F x

  F u

 t F x j





 1







  F u





 . t y j

Đặt

  t F x j



 1

0y  kéo theo

y  . 0

Từ đó, do u là nghiệm Pareto nên



 0

C R

Do đó .

0 thỏa mãn

T 

Theo định lý tách thì tồn tại

p    y R 

T y

    y K

(3.10)

(3.11)

 j

 , chúng ta có thể giả thiết

  j

 1

Bằng cách chia cho

0 , từ (2) và định nghĩa của K ta suy ra





x D



  F u

  T F x

 0    .

Từ (3.10) ta thấy



  P  .

Điều đó có nghĩa rằng u là nghiệm nhỏ nhất của

VP .

Như vậy, ta đã vô hướng hóa xong bài toán 

Kết luận

Luận văn đã trình bày về hai định lý tách và một số ứng dụng của nó, cụ thể:

Nội dung hai định lý tách và hệ quả.

Ứng dụng định lý tách để: Chứng minh các điều kiện tối ưu, tìm điều kiện có

nghiệm của một hệ bất đẳng thức lồi, chứng minh sự tồn tại xấp xỉ tuyến tính của

hàm lồi bởi các hàm non a-phin, chứng minh sự tồn tại dưới vi phân của hàm lồi và

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ả chỉ đề cập đến các định lý tách các tập lồi và ứng

nR , chưa xét trường hợp tổng quát khi xét

dụng trong không gian hữu hạn chiều

trên không gian vô hạn chiều. Một số vấn đề lý thú có thể tiếp tục từ đề tài này là:

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....

Vì thời gian và kiến thức còn hạn chế nên luận văn chắc chắn không tránh

khỏi những thiếu sót. Tác giả rất mong nhận được sự quan tâm, đóng góp ý kiến của

các thầy cô và các bạn đồng nghiệp để bản luận văn được hoàn thiện hơn.

Tác giả xin chân thành cảm ơn!

Tài liệu tham khảo

1. Đỗ Văn Lưu, Phan Huy Khải (2000), Giải tích lồi, Nhà xuất bản Khoa học

và kỹ thuật.

2. Lê Dũng Mưu và Nguyễn Văn Hiền (2009), Nhập môn giải tích lồi ứng

dụng, Nhà xuất bản Khoa học tự nhiên và công nghệ Hà Nội.

3. Hoàng Tụy (2006), Lý thuyết tối ưu, Viên toán học Hà Nội.

4. Hoàng Tụy (1998), Convex Analysis and Global Optimization, Kluwer

academic Publishers.

5. R.Tyrrell Rockafellar (1997), Convex Analysis, Princeton, New Jersey

Princeton University press.

Luận văn Thạc sĩ Khoa học: Định lý tách và một số ứng dụng

MỤC LỤC

MỞ ĐẦU

CÁC KHÁI NIỆM CƠ BẢN



 0

   :

 m





  

   J x

ĐỊNH LÝ TÁCH CÁC TẬP LỒI

ỨNG DỤNG CỦA ĐỊNH LÝ TÁCH

       m k



 

 

 



  . x



  . x



  t F x j



Tài liệu liên quan

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi