Luận văn Cận sai số cho bất đẳng thức lồi

ĐẠI  HỌC THÁI NGUYÊN   TRƯỜNG ĐẠI HỌC SƯ PHẠM   NGUYỄN ĐÌNH LONG CẬN SAI SỐ CHO BẤT ĐẲNG THỨC LỒI LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên, năm 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI  HỌC THÁI NGUYÊN   TRƯỜNG ĐẠI HỌC SƯ PHẠM   NGUYỄN ĐÌNH LONG CẬN SAI SỐ CHO BẤT ĐẲNG THỨC LỒI Chuyên ngành: Toán giải tích Mã số: 60.46.01.02 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: PGS.TS TRƯƠNG XUÂN ĐỨC HÀ Thái Nguyên, năm 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  i  MỤC LỤC Trang  MỤC LỤC.............................................................................................. i  BẢNG KÝ HIỆU ........................................................................................... ii LỜI NÓI ĐẦU .............................................................................................iii Chương 1: MỘT SỐ KIẾN THỨC CHUẨN BỊ ......................................... 1 1.1. Tập lồi ................................................................................................. 1  1.2. Hàm lồi................................................................................................ 4  1.3. Dưới vi phân........................................................................................ 7  Chương 2: CẬN SAI SỐ ĐỐI VỚI BẤT ĐẲNG THỨC LỒI CÓ RÀNG BUỘC VÀ KHÔNG CÓ RÀNG BUỘC.................................................... 11 2.1. Khái niệm cận sai số.......................................................................... 11  2.2. Cận sai số đối với bất đẳng thức lồi không có ràng buộc ................... 14  2.3. Cận sai số đối với bất đẳng thức lồi có ràng buộc .............................. 21  Chương 3: CẬN SAI SỐ VỚI MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆT .... 33 3.1. Tập thử compact (Compact test sets) ................................................. 33  3.2. Nón hình kem (The ice-cream cone).................................................. 34  3.3. Bất đẳng thức khả vi lồi (Convex differentiable inequalities) ............ 36  KẾT LUẬN................................................................................................. 40 TÀI LIỆU THAM KHẢO.......................................................................... 41 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  ii   BẢNG KÝ HIỆU x S                  phần tử  x  thuộc tập  S   y S                  phần tử  y  không thuộc tập  S                           tập rỗng  C S                C  là một tập con của  S   C S                 giao của hai tập C  và  S   C S                 hợp của hai tập C  và  S   \C S                  hiệu của hai tập C  và  S   L                        phần bù trực giao của  L  trong không gian véc tơ  C S                  tích đề các của hai tập  C  và  S   C S                  tổng của hai tập C  và  S  trong không gian véc tơ  C S                 tổng trực tiếp của hai tập  C  và  S  trong không gian véc tơ  C                      vị tự tập C  theo tỉ số   trong không gian véc tơ  x                      với mọi  x   x                       tồn tại  x    sup ( ) x K f x              supremum của tập  ( ) :f x x K    inf ( ) x K f x               infimum của tập  ( ) :f x x K   coA                     bao lồi của tập  A   coA                     bao lồi đóng của tập  A   clA                      bao đóng của tập  A   intA                    phần trong của tập  A   x                       chuẩn của  x  trong không gian định chuẩn  X                            tập số thực  n                       không gian Euclide  n -chiều  B                        quả cầu đơn vị trong  n Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên   0                         điểm gốc trong không gian tuyến tinh  X   ,x y                   tích vô hướng trong không gian Hilbert  ( ; )N x A                nón pháp tuyến của  A  tại  x   ( ; )T x A                nón tiếp xúc với  A  tại  x   dom( )f                miền hữu hiệu của  f   epi( )f                  tập trên đồ thị của  f   dist( , )x y              khoảng cách giữa hai điểm  x  và  y   dist( , )x S             khoảng cách từ điểm  x  tới tập  S   dist( , )C D            khoảng cách giữa hai tập C  và  D   aff( )A                  bao afin của tập  A   riA                       tập hợp các điểm trong tương đối của  A     ( )L f                   tập mức dưới của hàm  f    ( )C f                   tập mức trên của hàm  f   ( ; )f x d                 đạo hàm theo phương  d  của hàm  f  tại  x    ( )f x                   dưới vi phân của hàm  f  tại  x   *f                         hàm liên hợp với hàm  f   X                         không gian lồi địa phương  *X                       không gian liên hợp (tô pô) của không gian  X    S                        nón lùi xa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  iii  LỜI NÓI ĐẦU  Cho      : nf   là một hàm nửa  liên  tục dưới. Bài  toán xác định  cận sai số toàn cục của hàm  f  là đi tìm điều kiện cần và đủ cho sự tồn tại của  hằng số   0  sao cho                                    dist( , ) ( )x S f x  với mọi   nx ,                              (1)  trong đó     : : ( ) 0nS x f x   là  một  tập  lồi đóng, khác  rỗng  trong  n ,  “dist ”  là  khoảng  cách  từ  một  điểm  x   bất  kỳ  tới  một  tập  cố  định  (chuẩn  Euclid), và   ( ) ma ( ( ),0)f x x f x .       Quá trình nghiên cứu cận sai số trong những năm gần đây nhận được nhiều  sự chú ý. Năm 1975 Robinson   16  đã thiết  lập cận sai số toàn cục của một  tập lồi, đóng bất kỳ trong không gian định chuẩn với giả thiết  S  bị chặn và có  phần  trong  khác  rỗng.  Tiếp  đó  Mangasarian   14   nghiên  cứu  tập  lồi,  đóng   nS  xác định bởi  hệ hữu hạn bất đẳng thức lồi khả vi và thiết lập cận sai  số  toàn  cục  với  giả  thiết  Slater  và  tiêu  chuẩn  hạn  chế  tiệm  cận.  Sau  đó  Auslender và Crouzeix  4  mở rộng kết quả của Mangasarian cho những hàm  không khả vi. Năm 1994 Luo và Luo   12  nghiên cứu hệ bất đẳng thức bậc  hai, lồi và thiết lập cận sai số toàn cục chỉ với giả thiết Slater ( không có điều  kiện ràng buộc nào nữa). Tiếp đó Klatte  10  nghiên cứu liên hệ giữa tính liên  tục Haussdorff của nghiệm với hệ bất đẳng thức có “nhiễu” và cận sai số toàn  cục của hệ không nhiễu. Li  13  nhận được một số tính chất thú vị của cận sai  số  trên  tập compact  cho  những bất đẳng  thức  lồi khả vi  theo khía  cạnh  tiêu  chuẩn hạn chế.  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên         Gần đây, Deng   6,7  xây dựng cận sai số của tập  lồi đóng xác định bởi  những  hàm  lồi  thực sự đóng  trong  không  gian  Banach,  với điều kiện Slater  trên những hàm lùi xa tương ứng. Deng và Hu   8  nhận được những kết quả  cận sai số cho quy hoạch nửa xác định.        Khái niệm cận sai số có vai trò quan trọng trong giải tích biến phân và lý  thuyết tối ưu. Nó liên hệ chặt chẽ các bài toán về điều kiện tối ưu, điều khiển  tối ưu, cực tiểu  - xấp xỉ        Gần đây, các  tác  giả của bài báo   11  bằng cách đặc  biệt  hóa  một cách  thích  hợp  đã  thống  nhất  và  mở  rộng  nhiều  kết  quả  đã  biết  đến  nay  cho  hệ  thống bất đẳng thức lồi.        Trong luận văn này, tác giả sẽ trình bày bài toán cận sai số toàn cục cho  bất đẳng thức lồi trong hai trường hợp, bất đẳng thức lồi không có ràng buộc  và bất đẳng thức lồi có ràng buộc. Bài toán được cho như sau:  Cho   : nf      là một hàm nửa liên tục dưới.   1  Cho      : : ( ) 0nS x f x   là một  tập lồi  đóng,  khác rỗng trong   n ,   tìm dều kiện tồn tại số  0   sao cho     dist( , ) ( )x S f x  , với mọi   nx .     2  Cho   nC  là một tập lồi đóng, khác rỗng và    1( , 0]S C f , tìm  điều kiện tồn tại số   0  sao cho                                         dist( , ) ma ( ( ) ,dist( , ))x S x f x x C , với mọi   nx .        Luận văn gồm ba chương  Chương 1: Trình bày các kiến thức cơ sở của giải tích lồi về tập afin, tập lồi,  nón lồi, hàm lồi, cực trị của hàm lồi, đạo hàm theo phương, dưới vi phân.  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  Chương 2: Trình bày một số điều kiện cần và đủ cho sự tồn tại của cận sai số đối  với bất đẳng thức lồi không có ràng buộc và bất đẳng thức lồi có ràng buộc.  Chương 3: Trình bày một số điều kiện cần và đủ cho sự tồn tại của cận sai số  đối với tập compact, nón kem, bất đẳng thức khả vi lồi.        Để hoàn thành luận văn này, tác giả đã nhận được sự giúp đỡ hướng dẫn  tận tình của PGS. TS. Trương Xuân Đức Hà. Tác giả xin bày tỏ lòng biết ơn  sâu sắc tới cô giáo của mình.        Tác giả cũng xin chân thành cảm ơn tới các thầy cô trong Viện Toán Học,   Trường Đại học Sư phạm Thái Nguyên đã giảng dạy và  tạo điều kiện  thuận  lợi trong quá trình học tập và nghiên cứu.        Bản luận văn chắc chắn sẽ không tránh khỏi những khiếm khuyết vì vậy  rất mong nhận được sự đóng góp ý kiến của các thầy cô giáo và các bạn học  viên để luận văn được hoàn chỉnh.  Thái Nguyên, tháng 7, năm 2012                                                                                            Học viên   Nguyễn Đình Long.  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên   1  Chương 1 MỘT SỐ KIẾN THỨC CHUẨN BỊ       Trong chương này chúng tôi trình bày khái quát những kiến thức giải tích  lồi  về  tập  afin,  tập  lồi,  nón  lồi,  hàm  lồi,  cực  trị  của  hàm  lồi,  đạo  hàm  theo  phương, dưới vi phân. Các kết quả chủ yếu được trích dẫn trong  1 ,  2 ,  3 .  Sau đây, ta luôn giả thiết  nA  là một tập con khác rỗng.  1.1. Tập lồi 1.1.1. Tập afin       Tập  A  là tập afin nếu  ,a b A ,      thì      1a b A .  Giao của tất cả các tập afin chứa tập  A  được gọi là bao afin của tập A , và ký  hiệu là aff( )A . Dễ thấy rằng aff( )A  là tập afin nhỏ nhất chứa tập A .  Tập   nL  là không gian con nếu       , ,   , a b L  thì   a b L .  Một tập afin  ( 1)n  chiều trong n được gọi là siêu phẳng.  1.1.2. Mệnh đề. Tập  nL là không gian con nếu và chỉ nếu L là tập afin chứa 0 . 1.1.3. Tập lồi       Tập A  là một tập lồi nếu         , ,   0,1a b A  thì    (1 )a b A .  Bao lồi của một tập   nA  là giao của tất cả các tập lồi chứa  A . Ký hiệu là  coA . Dễ thấy rằng đây là tập lồi nhỏ nhất chứa A .  Giao của tất cả các tập lồi đóng chứa A  được gọi là bao lồi đóng của tập A ,  và ký hiệu là  coA . Dễ thấy rằng  coA  là tập lồi đóng nhỏ nhất chứa A .  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên   2  Một điểm a  của tập lồi A  gọi là điểm trong tương đối nếu với mọi  x A đều  có một số   0  sao cho    ( )x a A .   Tập hợp các điểm trong tương đối của A  ký hiệu là  riA .  Nhận xét:  riA  là tập lồi, mọi tập lồi A  đều có   riA .  Một điểm biên của tập lồi A  là một điểm của bao đóng của A  mà không phải  là điểm trong tương đối của A .  1.1.4. Ví dụ . Các tập cho sau đây là các tập lồi thường gặp.  1  Trong mặt phẳng hay trong không gian 3 chiều, mọi hình quen biết như   đoạn thẳng, hình tam giác, hình chữ nhật, khối lập phương, hình tròn, hình  cầu đều là những tập lồi.          2  Mọi tập afin.   3  Hình cầu       ( , )  :nB a r x a x r .   4  Hình ellipsoit         2: ( )TnE x x a M x a r  (M  là ma trận  xác  định dương).   5  Các nửa không gian đóng      : ,nx a x ;    : ,nx a x ,        hay các nửa không gian mở     : ,nx a x ;    : ,nx a x ,        trong đó     ,   0,  na a .  1.1.5. Mệnh đề . Cho A là tập lồi. Khi đó  i intA , clA là lồi;  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên   3   ii cl cl(int )A A ;   iii int(cl ) intA A .  1.1.6. Nón lồi Tập   nA   được  gọi  là  nón  có  đỉnh  tại  0  nếu     , 0x A   ta  có   x A . A  được gọi là nón có đỉnh tại  0 x  nếu   0 ( )A x là nón có đỉnh tại 0.  Nón A  có đỉnh tại 0 được gọi là nón lồi nếu A  là một tập lồi, có nghĩa là:      , , , 0x y A ta có   x y A .  Véc tơ   * nx  được gọi là véc tơ pháp tuyến của tập lồi A  tại x nếu:   *, 0x x x    x A.  Tập tất cả các véc tơ pháp tuyến của tập lồi A  tại  x A được gọi là nón pháp  tuyến của A  tại x .             * n *( ; ) : : , 0,N x A x x x x x A .  Cho  A   là  một  tập  lồi. Véc  tơ   0y  được gọi  là  một phương  lùi  xa của  A    nếu          : 0 , ,x y A x A .  Tập tất cả các phương lùi xa của một tập lồi A  cùng với véc tơ 0 làm thành  một nón lồi. Nón lồi ấy gọi là nón lùi xa của tập A .  1.1.7. Ví dụ . Các tập sau đây là các nón lồi gốc tại  0 trong  n          i       1,...,( ) : 0, 1,2,...nn i i n  ( Orthant không âm).  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên   4   ii       1,...,( ) : 0, 1,2,...nn i i n  ( Orthant dương).  1.2. Hàm lồi Giả sử X  là không gian lồi địa phương, S  là một tập con của X  và cho  một hàm tùy ý      : ,f X  là hàm số xác định trên X .  Kí hiệu          dom( ) : ( )f x X f x     là miền hữu hiệu của  f .               epi( ) ( , ) : ( )f x t X f x t     là tập trên đồ thị của  f .         ( ) : ( )L f x X f x     là tập mức dưới của hàm  f .        ( ) : ( )  C f x X f x     là tập mức trên của hàm  f .  1.2.1. Định nghĩa. Cho X  là không gian lồi địa phương. Một hàm   : ,f X      được  gọi là hàm lồi, nếu với mọi  ,x y X  và   0,1 , ta có ( (1 ) ) ( ) (1 ) ( ).   f x y f x f y          Hàm  f  được gọi là hàm lõm nếu hàm   ( )f  là hàm lồi.  Hàm  f  gọi là chính thường nếu  dom( )  f    và  ( ) ,f x    với mọi x X .  1.2.2. Ví dụ . Các hàm sau đây là các hàm lồi   1  Xét không gian  n . Lấy  na    cố định và t   . Khi đó hàm afin           : ,nf      , xác định bởi  ( ) ,f x a x t  ,  nx     Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên   5         là hàm lồi, trong đó  ,a x  là tích vô hướng trong  n , được định nghĩa:  1/2 2 1 , n i i a x x          ,   1,..., na a a ,   1,..., nx x x .   2  Hàm chỉ của một tập lồi  C   0 khi   ( )    khi  C x C I x x C              là một hàm lồi.   3  Cho  *X  . Với mọi x X , hàm  ( / )S x   được xác định như sau:   ( / ) sup ( ) :S x x     ,         được gọi là hàm giá và là hàm lồi.   4  Cho X  là không gian định chuẩn và A X  là tập lồi. Hàm khoảng cách   dist( , ) inf :x A x a a A            là hàm lồi.  1.2.3. Định nghĩa. Cho S  là một tập con của không gian lồi địa phương X   và   : ,f S     . Hàm  f  được gọi là nửa liên tục dưới tại một điểm  x S  nếu       lim inf ( ) ( )   y x f y f x   .  1.2.4. Mệnh đề. Cho hàm  : ,f X     , các điều kiện sau là tương đương:              i Epi của f là một tập đóng trong X  . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên   6              ii Với mỗi    , tập mức dưới  ( ) : ( )L f x X f x    là đóng.             iii f là hàm nửa liên tục dưới trên X . 1.2.5. Định nghĩa . Hàm   : ,f X      được gọi là Lipschitz địa  phương tại x  với hằng số Lipschitz K  nếu tồn tại một lân cận U  của x sao  cho:    ( ) ( ) ,f x f y K x y    với mọi  ,x y U .  Hàm  f   được  gọi  là  Lipschitz  địa  phương  trên  S   nếu  nó  Lipschitz  tại  mọi  điểm thuộc S .  1.2.6 Định lí. Cho f là một hàm lồi chính thường trên X . Các khẳng định sau là tương đương:  i f  là liên tục tại mọi điểm;  ii f là bị chặn trên mọi tập mở;                      iii  int epi( )f   ;                      iv  int dom( )f   và f là Lipschitz địa phương trên mọi tập bị chặn chứa trong   int dom( )f   ; ( )v  int dom( )f   và f là liên tục trên  int dom( )f   . 1.2.7. Định nghĩa. Cho một hàm lồi   : ,f X     ,  dom( )C f  là  một tập lồi khác rỗng và  x C . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên   7      i  x C  là  điểm  cực tiểu toàn cục  của  hàm   f   nếu  với  mọi  x C   ta  có            ( ) ( )f x f x  với mọi x C .      ii   x C   là điểm cực tiểu địa phương của hàm  f  nếu có một lân cận W  của            x C  sao cho  ( ) ( )f x f x  với mọi  W Cx   .  1.2.8. Mệnh đề. Mọi cực tiểu địa phương của một hàm lồi : ,f X      trên một tập dom( )C f khác rỗng đều là cực tiểu toàn cục. ký hiệu argmin ( ): f x x C là tập các điểm cực tiểu của ( )f x trên C . 1.2.9. Định lí. Cho một hàm lồi  : ,f X     và cho một tập lồi int(dom( ))C f . Khi đó ta có  argmin ( ):  0 ( ) ( ; )x f x x C f x N x C      . 1.2.10. Hệ quả. Với intx C là điểm cực tiểu khi và chỉ khi 0 ( )f x  .        Cho X  là một không gian lồi địa phương Hausdorff và  f  là hàm xác  định trên không gian X .  1.3. Dưới vi phân 1.3.1. Định nghĩa. Cho  f  là hàm lồi từ X  vào   ,   ,  ,x d X . Đạo  hàm theo phương d  của hàm  f  tại x , ký hiệu là  ( ; )f x d , được định nghĩa là  giới hạn sau:  0 ( ) ( ) ( ; )=lim f x d f x f x d       .  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên   8  Giới hạn này luôn tồn tại, có thể hữu hạn hoặc bằng   ,  .  1.3.2. Định lí. Giả sử f là hàm lồi chính thường trên X . Khi đó, hàm f có đạo hàm theo phương tại mọi điểm dom( )x f và 0 ( ) ( ) ( ; )= inf f x d f x f x d       . 1.3.3. Mệnh đề. Cho x C xác định và nd   , P là một phép chiếu. Khi đó ( )0 ( ) lim ( ) C C T xt P x td x P d t    . 1.3.4. Định nghĩa. Cho hàm lồi chính thường   :f X    , véc tơ  * *x X  được gọi là dưới gradient của  f  tại điểm x  nếu thỏa mãn    *, ( ) ( )x x x f x f x      x X  .    Tập tất cả các dưới gradient của  f  tại x  được gọi là dưới vi phân của hàm  f   tại x  và được ký hiệu là  ( )f x    * * *( ) : , ( ) ( ),   f x x X x x x f x f x x X        .  Hàm  f  được gọi là khả dưới vi phân tại x nếu  ( )f x   .        Dưới đây là một số ví dụ về dưới vi phân của những hàm lồi chúng ta hay gặp.   1.3.5. Ví dụ  1  Dưới vi phân của hàm  ( )f x x  là      * * * * * * * : 1                   khi  0       ( ) : , , 1   khi  0        x X x x f x x X x x x x x            Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên   9   2  Hàm afin  :   nf   , xác định  bởi  ( ) ,f x c x   ,  với  ,   nc x  ,       có dưới vi phân với mọi  nx    và   ( )f x c  .  1.3.6. Định lí. Giả sử hàm f là hàm lồi chính thường trênX và dom( )x f . Khi đó: * *( ) ( ; ) , ,   x f x f x d x d d X      . 1.3.7. Định lí. Mọi hàm lồi chính thường f trên X có dưới vi phân khác rỗng tại mỗi điểm int(dom( ))x f . 1.3.8. Mệnh đề. Cho f là một hàm lồi, đóng, chính thường và dom( )S f là một tập khác rỗng, đóng và bị chặn . Khi đó tập  ( ) ( ) :f S f x x S     là khác rỗng, đóng và bị chặn. Ký hiệu       * *: sup : ( )x x f S , ta có   ( ; )   f x z z    ,  ,  x S z X    .  1.3.9. Mệnh đề. Cho f là một hàm lồi, chính thường. Cho x là một điểm sao cho hàm f khả dưới vi phân nhưng f không đạt cực tiểu tại x , khi đó nón pháp tuyến của  : ( ) ( )C z f z f x  tại x là bao đóng của nón lồi sinh bởi ( )f x . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên   10  1.3.10. Mệnh đề. Cho f là một hàm lồi chính thường và x là một điểm trong tương đối của dom( )f sao cho ( )f x không là cực tiểu của f . Một véc tơ *x là véc tơ pháp tuyến của  : ( ) ( )C z f z f x  tại điểm x nếu và chỉ nếu tồn tại một số  không âm sao cho * ( )x f x  . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên   11  Chương 2 CẬN SAI SỐ ĐỐI VỚI BẤT ĐẲNG THỨC LỒI CÓ RÀNG BUỘC VÀ KHÔNG CÓ RÀNG BUỘC       Bài toán xác định cận sai số toàn cục của một hàm số có liên hệ ch