Luận văn Về cực trị hàm lồi

sao cho chi phí thấp nhất, với x là phương án sản xuất mà mỗi tọa độ jx của nó là số lượng sản phẩm loại j cần sản xuất, còn  f x là chi phí ứng với phương án x . Bài toán  P trong mô hình này có nghĩa là tìm một phương án sản xuất trong tập hợp các phương án chấp nhận được D sao cho chi phí sản xuất ứng với phương án này là thấp nhất. Định nghĩa 2.1. Điểm *x D mà    * ,   f x f x x D Chương 2. Cực tiểu hàm lồi trên tập lồi 20 được gọi là nghiệm tối ưu, hoặc nghiệm tối ưu toàn cục, hoặc nghiệm cực tiểu toàn cục, hoặc đơn giản là nghiệm của bài toán  P . Định nghĩa 2.2. Điểm *x D được gọi là nghiệm cực tiểu toàn cục chặt của bài toán  P nếu    * ,   f x f x x D và *x x . Giá trị tối ưu (hay giá trị cực tiểu) của bài toán  P được kí hiệu là  min x D f x . Nếu bài toán  P có nghiệm là *x thì    * min   x D f x f x . Ta ký hiệu   Argmin f x x D là tập nghiệm tối ưu của bài toán  P . Nếu bài toán chỉ có một nghiệm tối ưu thì có thể viết   * argmin x f x x D . Định nghĩa 2.3. Điểm *x D được gọi là nghiệm tối ưu địa phương hoặc nghiệm cực tiểu địa phương của bài toán  P nếu tồn tại một lân cận U của điểm *x sao cho    * ,    f x f x x U D . Định nghĩa 2.4. Điểm *x D được gọi là nghiệm tối ưu địa phương chặt hoặc nghiệm cực tiểu địa phương chặt của bài toán  P nếu tồn tại một lân cận U của điểm *x sao cho    * ,    f x f x x U D và *x x . Chú ý 2.1. (i) Nếu  nD thì ta nói  P là bài toán tối ưu không ràng buộc. Ngược lại, nếu  nD thì ta nói  P là bài toán tối ưu có ràng buộc. Chương 2. Cực tiểu hàm lồi trên tập lồi 21 (ii) Nghiệm tối ưu toàn cục cũng là nghiệm tối ưu địa phương nhưng điều ngược lại chưa chắc đúng. Tuy nhiên, nếu D là tập lồi và  f x là hàm lồi thì nghiệm tối ưu địa phương của bài toán  P cũng là nghiệm tối ưu toàn cục. Cụ thể : Mệnh đề 2.1. Cho hàm lồi :  nf và tập lồi khác rỗng  nD . Xét bài toán   min f x x D . Khi đó: a) Nếu *x là một nghiệm tối ưu địa phương của bài toán này thì *x cũng là nghiệm tối ưu toàn cục. b) Nếu *x là nghiệm tối ưu địa phương chặt hoặc f là hàm lồi chặt thì *x là nghiệm tối ưu toàn cục duy nhất của bài toán. Chứng minh. a) Giả sử *x D là một nghiệm tối ưu địa phương của bài toán   min f x x D . Theo định nghĩa, tồn tại một lân cận U của điểm *x sao cho    * ,    f x f x x U D . Với bất kỳ x D , ta có    * * *1       λx λx λ x x λ x x U D khi 0 1λ  và λ đủ nhỏ. Do *x là nghiệm cực tiểu địa phương và f là hàm lồi nên          * *1   λf x f x λf x λ f x    * f x f x . Điều đó chứng tỏ *x là nghiệm tối ưu toàn cục của bài toán đang xét. b) Giả sử *x là nghiệm tối ưu địa phương chặt. Theo (i), *x cũng là nghiệm tối ưu toàn cục. Bây giờ, ta giả thiết phản chứng rằng *x không phải là nghiệm tối ưu toàn cục duy nhất của bài toán, tức là tồn tại x D , *x x và    *f x f x . Kí hiệu   *1  λx λx λ x với 0 1λ  . Vì D là tập lồi và f là hàm lồi trên D nên Chương 2. Cực tiểu hàm lồi trên tập lồi 22 λx D và          * *1   λf x λf x λ f x f x ,  0,1λ  . (2.1) Cho 0λ , ta có thể chọn được λx U , với U là một lân cận của *x . Điều này và (2.1) mâu thuẫn với giả thiết *x là nghiệm tối ưu địa phương chặt. Vì vậy *x phải là nghiệm tối ưu toàn cục duy nhất. Cuối cùng, giả sử *x là nghiệm tối ưu địa phương và hàm mục tiêu f là lồi chặt. Vì hàm lồi chặt là hàm lồi nên theo (i), *x là nghiệm tối ưu toàn cục. Ta cũng giả thiết phản chứng rằng *x không phải là nghiệm tối ưu toàn cục duy nhất, tức là tồn tại x D , *x x và    *f x f x . Do f là hàm lồi chặt nên      * * *1 1 1 1 2 2 2 2          f x x f x f x f x . Do D là tập lồi nên * 1 1 2 2        x x D và bất đẳng thức trên mâu thuẫn với giả thiết *x là nghiệm tối ưu toàn cục của bài toán, chứng tỏ *x là nghiệm tối ưu toàn cục duy nhất. (iii) Nếu bài toán  P không có nghiệm tối ưu thì giá trị tối ưu của bài toán này, kí hiệu là  inf f D , là cận dưới lớn nhất (hay giá trị infimum) của hàm f trên D . Giả sử  0 inft f D với  0   t . Khi đó   0,   f x t x D và   nx D sao cho   0lim  n n f x t . Ví dụ 2.1. (i) Cho   cosf x x , D   . Khi đó, bài toán  P tương ứng có vô số nghiệm tối ưu toàn cục,     *Argmin cos 2 1 ,      x x x k π k và giá trị tối ưu là min cos 1    x x . (ii) Cho    2 khi 1 2 1 khi 1,        x x f x x x D   . Chương 2. Cực tiểu hàm lồi trên tập lồi 23 Dễ thấy 2x  là nghiệm cực tiểu toàn cục duy nhất. Điểm 0x  là nghiệm cực tiểu địa phương của f trên D . Giá trị tối ưu là    min 2 1     x f x f . (iii) Cho   arctanf x x và D   . Dễ thấy, trên  hàm f không có một nghiệm cực tiểu địa phương, cực tiểu toàn cục nào. Ta có  inf 2 π f D   . (iv) Cho   1f x x và  2 2 2 21 2 14, 1    D x x x x . Hàm f có một nghiệm cực tiểu toàn cục trên D là  2,0  Tx và vô số nghiệm cực tiểu địa phương, đó là cả đoạn thẳng nối  1, 3 T và  1, 3 T . Giá trị tối ưu của bài toán  P tương ứng là  min 2    x D f x . (v) Cho   1f x x và  2 1 2 0  D x x x . Khi đó bài toán  P tương ứng có vô số nghiệm cực tiểu địa phương, đó là tập các điểm  2 1 20, 0  x x x ; không có nghiệm cực tiểu toàn cục và  inf f D   . 2.2. Sự tồn tại nghiệm tối ưu Xét bài toán  P . Khi đó, có một trong bốn khả năng sau có thể xảy ra: (i) Bài toán  P không có phương án chấp nhận được, tức là D   . (ii) Bài toán  P có nghiệm tối ưu, tức là tồn tại *x D sao cho    * ,   f x f x x D và giá trị tối ưu của bài toán là    * min   x D f x f x . (iii) Bài toán không có nghiệm tối ưu và giá trị hàm mục tiêu  f x giảm vô hạn trên tập chấp nhận được D , tức là giá trị tối ưu  inf    x D f x . Chương 2. Cực tiểu hàm lồi trên tập lồi 24 (iv) Bài toán không có nghiệm tối ưu và giá trị tối ưu  inf x D f x là hữu hạn. Định lý 2.1. Điều kiện cần và đủ để bài toán  P có nghiệm tối ưu là tập     : ,     F D t t f x x D đóng và có một cận dưới hữu hạn. Chứng minh.  Giả sử *x là nghiệm tối ưu của bài toán  P . Khi đó, ta có    * min   x D f x f x và     * ,  F D f x . Hiển nhiên  F D là tập đóng và nhận  *f x là một cận dưới  Ngược lại, nếu tập  F D có một cận dưới hữu hạn thì cận dưới lớn nhất (hay infimum) của tập này là hữu hạn và ta kí hiệu nó là 0t . Theo định nghĩa của infimum thì  0 ,   t t t F D và tồn tại dãy    nt F D hội tụ đến 0t . Vì  F D là tập đóng nên  0 t F D . Theo định nghĩa của tập  F D , tồn tại *x D sao cho  *0 t f x . Hiển nhiên  *f x cũng thuộc  F D và vì 0t là cận dưới lớn nhất của tập  F D nên ta có  * 0f x t . Suy ra  *0 t f x . Điều đó chứng tỏ *x là nghiệm tối ưu của bài toán  P . Định lý 2.2. (Định lý Weierstrass) Nếu D là tập compact và hàm f nửa liên tục dưới trên D thì bài toán  P có nghiệm tối ưu. Chứng minh. Giả sử giá trị tối ưu của bài toán  P là  0 inft f D . Theo định nghĩa, ta có   0,   f x t x D (2.2) và   nx D sao cho   0lim  n n f x t . Chương 2. Cực tiểu hàm lồi trên tập lồi 25 Do D là tập compact nên có một dãy con  knx của dãy  nx hội tụ đến một điểm *x D , tức là *lim   kn k x x D . Do f nửa liên tục dưới tại *x D nên    * 0lim   kn k f x f x t . Kết hợp với (2.2) ta có    *0 inf t f D f x , chứng tỏ *x là nghiệm tối ưu của bài toán  P . Hệ quả 2.1. Nếu hàm f là nửa liên tục dưới trên D và thỏa mãn điều kiện bức trên D ,  f x  khi x D và x  thì bài toán  P có nghiệm tối ưu. Chứng minh. Lấy một điểm bất kỳ 0 x D . Trước hết, ta chứng minh rằng tập       0 0:  D x x D f x f x là tập compact. Thật vậy, do f là nửa liên tục dưới trên D nên với mỗi dãy    0nx D x , nx x mà dãy   nf x hội tụ, ta có      0lim   n n f x f x f x . Suy ra  0x D x , chứng tỏ  0D x là tập đóng. Hơn nữa, nếu  0D x không bị chặn thì phải tồn tại một dãy    0kx D x , tức là    0kf x f x sao cho kx . Do điều kiện bức nên    kf x , mâu thuẫn với    0kx D x . Vậy  0D x là tập compact. Theo Định lý Weierstrass, hàm f đạt cực tiểu trên  0D x , tức là tồn tại  * 0x D x sao cho      * 0,   f x f x x D x . Dễ thấy, *x cũng chính là nghiệm cực tiểu của bài toán  P . Chương 2. Cực tiểu hàm lồi trên tập lồi 26 2.3. Điều kiện tối ưu Định lý 2.3. Giả sử D là tập lồi và f là hàm lồi, khả dưới vi phân trên D . Khi đó *x D là nghiệm tối ưu của bài toán ( )P khi và chỉ khi    * *0  Df x N x trong đó    * *, 0,     DN x w w x x x D là nón pháp tuyến ngoài của D tại *x . Chứng minh. Gọi Dδ là hàm chỉ của tập D , tức là   0 khi , khi .      D x D δ x x D Khi đó bài toán ( )P có thể viết dưới dạng     min  nDf x δ x x . 1( )P *x là nghiệm của bài toán 1( )P khi và chỉ khi        * * ,     nD Df x δ x f x δ x x        * * *0, ,        nD Dx x f x δ x f x δ x x     * *0   Df x δ x    * *0    Df x δ x . Vì *x D nên    * * D Dδ x N x . Vậy    * *0  Df x N x . Hệ quả 2.2. Với các giả thiết như Định lý 2.3, nếu * intx D là nghiệm tối ưu của bài toán ( )P thì  *0f x . Hơn nữa, nếu f khả vi và  nD thì  *0  f x . Chương 2. Cực tiểu hàm lồi trên tập lồi 27 2.3.1. Bài toán với ràng buộc đẳng thức 1. Xét bài toán   min f x x C ,  2P trong đó C là tập affine và C M a  với M là một không gian con của n và a C , f là một hàm lồi trên n . Định lý 2.4. a) Giả sử f liên tục tại một điểm của C , *x là một nghiệm của bài toán  2P . Khi đó  *    f x M (2.3) với  , 0,      nM z z x x M . b) Giả sử (2.3) đúng tại *x C . Khi đó *x là nghiệm của bài toán  2P . Chứng minh. a) Ta có    * *0  Cf x N x ,    * *C MN x N x vì C M a  với M là một không gian con của n và a C . Mặt khác vì M là một không gian con của n nên  * MN x M . Do đó  *0  f x M . Suy ra  *    f x M . b) Giả sử  *    f x M với *x C . Khi đó tồn tại  *  x f x M . Vì * x x M với x C nên    * *0 , ,      x x x f x f x x C . Do đó *x là nghiệm của bài toán  2P . 2. Xét bài toán   min f x x C ,  3P Chương 2. Cực tiểu hàm lồi trên tập lồi 28 trong đó  , , 1,2,...,   n i iC x a x α i m với i na và iα , 1,2,...,i m và f là hàm lồi trên n , liên tục tại một điểm của C . Định lý 2.5. *x là nghiệm của bài toán  3P khi và chỉ khi tồn tại các số iλ với 1,2,...,i m sao cho  1 2 *1 2 ...   mmλ a λ a λ a f x . Chứng minh. Để chứng minh định lý, chúng ta cần bổ đề sau: Bổ đề 2.1. Đặt  , 0, 1,2,...,   n iM x a x i m . Khi đó  1 2, ,...,  mM a a a . Chứng minh. Không mất tính tổng quát, ta có thể xem 1 2, ,..., ma a a là độc lập tuyến tính. Xét toán tử tuyến tính    1 : , ,..., , .      n m m φ x φ x a x a x Khi đó Im  mφ và   *Ker Im φ φ Ta lại có  Ker  φ M và  * 1 2Im , ,..., mφ a a a . Do đó  1 2, ,...,  mM a a a Bây giờ ta chứng minh định lý. Vì C là tập affine nên C M a  với M là một không gian con của n và a C , trong đó  , 0, 1,2,...,   n iM x a x i m . Từ Định lý 2.4 suy ra *x là của bài toán  3P khi và chỉ khi tồn tại  *  x f x M . Theo Bổ đề 2.1, ta có Chương 2. Cực tiểu hàm lồi trên tập lồi 29  1 2, ,...,  mx M a a a . Do đó tồn tại các số 1 2, ,..., mλ λ λ sao cho  1 2 *1 2 ...   mmλ a λ a λ a f x . 2.3.2. Bài toán với ràng buộc bất đẳng thức Xét bài toán   min f x x D ,  OP trong đó   0, 1,...,   iD x X g x i m với    nX là một tập lồi đóng và các hàm  , 1,...,if g i m là các hàm lồi hữu hạn trên X . Chúng ta xây dựng hàm sau, được gọi là hàm Lagrange      0 1 0 1 , , ,..., :    m m i i i L x λ λ λ λ f x λ g x . Định lý 2.6. (Định lý Karush-Kuhn-Tucker) a) Nếu *x là nghiệm của bài toán  OP , thì tồn tại 0iλ  0,1,...,i m không đồng thời bằng 0 sao cho    * 0 0, ,..., min , ,...,  m m x X L x λ λ L x λ λ , (2.4)  * 0i iλ g x  1,...,i m . (2.5) Hơn nữa nếu int X   và điều kiện Slater sau thỏa mãn  0 0: 0, 1,...,   ix D g x i m thì 0 0λ . b) Nếu (2.4) và (2.5) thỏa mãn với 0 0λ thì điểm chấp nhận được *x là nghiệm của bài toán  OP . Chứng minh. a) Giả sử *x là nghiệm của bài toán  OP . Đặt         1 *0 1 0: , ,..., : , , 1,...,       T mm i iC μ μ μ x X f x f x μ g x μ i m . Chương 2. Cực tiểu hàm lồi trên tập lồi 30 Ta có 1int   m C . Thật vậy: Lấy   10 1, ,..., int    T m mμ μ μ . Khi đó 0, 1,..., iμ i m . Với *x x , ta có    * * 00  f x f x μ ,  * 0 i ig x μ , 1,...,i m . Suy ra  0 1, ,...,  T mμ μ μ C , do đó 1int   m C . Vậy C   trong 1m . Do 1, ,..., mf g g là hàm lồi, nên C là một tập lồi. Hơn nữa, 0 C . Thật vậy: Nếu 0 C thì    *: 0   x X f x f x ,   0, 1,..., ig x i m . Do đó *x không phải là nghiệm của bài toán  OP . Điều này mâu thuẫn với giả thiết. Vậy 0 C . Theo định lý tách 1, có thể tách tập C và  0 , tức là tồn tại các số iλ , 1,...,i m không đồng thời bằng 0 sao cho 0 0   m i i i λ μ ,  0 1, ,...,  T mμ μ μ C . (2.6) Do 1int   m C , suy ra 0iλ , 0,1,...,i m . Với mọi 0ε  và x X , lấy       * 0 , , 1,..., .     i i μ f x f x ε μ g x i m thay vào (2.6) ta có      *0 1 0,            m i i i λ f x f x ε λ g x x X . Cho 0ε  ta được Chương 2. Cực tiểu hàm lồi trên tập lồi 31      *0 0 1 ,      m i i i λ f x λ g x λ f x x X . (2.7) Do *x là điểm chấp nhận được nên ta có  * 0, 1,..., ig x i m . Vậy      * * *0 0 1   m i i i λ f x λ f x λ g x . (2.8) Từ (2.7) và (2.8) ta có        * *0 0 1 1 ,         m m i i i i i i λ f x λ g x λ f x λ g x x X    *0 1 0 1, , ,..., , , ,..., ,    m mL x λ λ λ L x λ λ λ x X . Vậy ta có    * 0 0, ,..., min , ,...,  m m x X L x λ λ L x λ λ . Do *x là điểm chấp nhận được nên  * 0ig x , 1,...,i m . Nếu tồn tại  1,...,i m sao cho  * 0 ig x ξ thì 0ε  ta có       * * * 0 , 0 , 1,..., 1, 1,..., .        j f x f x ε g x ε j i i m Do đó  ,..., , , ,..., Tε ε ξ ε ε C (ξ ở vị trí thứ i). Thay  ,..., , , ,..., Tε ε ξ ε ε vào (2.6) và cho 0ε  , suy ra 0iλ ξ . Từ đó ta có 0iλ . Mặt khác, do 0iλ nên 0iλ . Như vậy, nếu  * 0ig x thì 0iλ . Do đó  * 0, 1,..., i iλ g x i m . Giả sử điều kiện Slater được thỏa mãn, tức là  0 0: 0, 1,...,   ix D g x i m . Khi đó, giả sử 0 0λ  , ta có Chương 2. Cực tiểu hàm lồi trên tập lồi 32        * *0 0 1 1 0 ,          m m i i i i i i λ f x λ g x λ f x λ g x x X . Do 0 0λ  nên phải có ít nhất một 0iλ  . Thay 0x vào bất đẳng thức trên, ta được        * * 0 00 0 1 1 0 0         m m i i i i i i λ f x λ g x λ f x λ g x . Mâu thuẫn. Vậy 0 0λ  , tức là 0 0λ  . b) Giả sử *x là điểm chấp nhận được, thỏa mãn hai điều kiện (2.4) và (2.5) với 0 0, 0, 1,...,iλ λ i m   . Do 0 0λ  , nên bằng cách chia cho 0λ , ta có thể coi hàm Lagrange là      1 1 , ,...,     m m i i i L x λ λ f x λ g x . Từ điều kiện (3.1) và (3.2), ta có        * * 1 1 ,         m m i i i i i i f x λ g x f x λ g x x X ,  * 0, 1,..., i iλ g x i m . Suy ra      * 1 ,      m i i i f x f x λ g x x X . Do đó    * , f x f x x D   . Chứng tỏ *x là nghiệm của bài toán  OP . 2.4. Đối ngẫu Lagrange Đối ngẫu là một phần quan trọng của bài toán tối ưu. Có rất nhiều kiểu đối ngẫu, nhưng đối ngẫu Lagrange được sử dụng rộng rãi hơn cả. Đối ngẫu Lagrange dựa trên cơ sở hàm Lagrange. Ta xét bài toán     min , 0, 1,...,  if x x X g x i m ,  P Chương 2. Cực tiểu hàm lồi trên tập lồi 33 trong đó  nX là tập lồi khác rỗng. Từ bài toán tối ưu trên, ta định nghĩa bài toán tối ưu khác có dạng   max d y y Y ,  D Đúng hơn, viết là   sup d y y Y ,  D trong đó  mY . Định nghĩa 2.7. Bài toán  D được gọi là đối ngẫu của bài toán  P nếu với mọi điểm chấp nhận được x của  P và mọi điểm chấp nhận được y của  D , ta có    f x d y . Bài toán  D được gọi là đối ngẫu chính xác của bài toán  P nếu  D là bài toán đối ngẫu của  P và tồn tại nghiệm *x của  P và *y của  D sao cho    * *f x d y . Từ Định nghĩa 2.7 ta thấy rằng, nếu bài toán  D là đối ngẫu chính xác của bài toán  P thì    * *f x d y và hiển nhiên  P cũng là đối ngẫu chính xác của  D . Xét bài toán  P , ta định nghĩa hàm Lagrange       1 , :    m i i i L x y f x y g x . Lấy hàm mục tiêu của bài toán đối ngẫu là    : inf ,   x X d y L x y .  LD với miền ràng buộc của  LD bằng  m . Khi đó bài toán đối ngẫu trở thành     0 0 sup : sup inf ,    x Xy y d y L x y . Định lý 2.7. Bài toán  LD là đối ngẫu của bài toán  P . Chứng minh. Ta có Chương 2. Cực tiểu hàm lồi trên tập lồi 34           1 inf , , ,           m i i x X i d y L x y f x y g x f x x X y Y . Chứng tỏ  LD là đối ngẫu của bài toán  P . Nhận xét 2.1. Nhìn chung, một cặp đối ngẫu chưa chắc đã là cặp đối ngẫu chính xác, chẳng hạn ta xét ví dụ sau: Ví dụ 2.2. Xét bài toán     2min 0,2 , 1 0     f x x x X x . Ta thấy  1 min 1f f   . Hàm Lagrange của bài toán là      2, 1 , 0, 0,2      L x y x y x y x X . Ta thấy   0 max 0   y d y . Vậy cặp đối ngẫu là không chính xác. Vậy cần thêm điều kiện gì để hai bài toán  P và  LD là cặp đối ngẫu chính xác. Ta có định lý sau: Định lý 2.8. (Định lý đối ngẫu chính xác) Giả sử (i)  P có một lời giải tối ưu. (ii) Các hàm f và , 1,...,ig i m lồi và liên tục trên X . (iii) Điều kiện Slater thỏa mãn, nghĩa là có 0x sao cho  0 0, 1,..., ig x i m . Khi đó,  P và  LD là cặp đối ngẫu chính xác. Chứng minh. Giả sử         1 2: , ,..., T mg x g x g x g x . Lấy       : , , , nA t z t f x z g x x X        . Chương 2. Cực tiểu hàm lồi trên tập lồi 35 Do f và , 1,...,ig i m là lồi nên tập A là lồi. Giả sử *x là nghiệm tối ưu của bài toán  P thì   * ,0 f x A . Theo định lý tách tồn tại  , 0α y  thuộc  n sao cho    * , ,   Tαt y z αf x t z A . (2.9) Do các hàm f và , 1,...,ig i m liên tục, bất đẳng thức trên đúng với mọi  ,t z A A là bao đóng của tập A . Mà     ,f x g x A ,      * ,    Tαf x y g x αf x x X . (2.10) Ta chỉ ra rằng  , 0α y  . Thật vậy, giả sử có chỉ số i thỏa mãn 0iy . Lấy  00, t z A . Điểm    00 0, ,  it z t z ξe A với mọi 0ξ   ie là vectơ đơn vị thứ i . Thay    0, ,t z t z vào (2.9) và cho ξ  . Ta có vế trái bằng  mà vế phải hữu hạn. Mâu thuẫn này chứng tỏ 0y  . Chứng minh tương tự ta chỉ ra được 0α  . Hơn nữa, 0α  vì nếu 0α  thì 0y  . Trong trường hợp này, từ (2.10) ta có   0,   Ty g x x X . Mâu thuẫn với điều kiện Slater. Chia cả hai vế của (2.10) cho α và theo định nghĩa của d ta có  *      y d f x α . Do đó  P và  LD là cặp đối ngẫu chính xác. 2.5. Các phương pháp giải cơ bản 2.5.1. Phương pháp chiếu dưới đạo hàm Chúng ta xét bài toán   min f x x D ,  P Chương 2. Cực tiểu hàm lồi trên tập lồi 36 trong đó :  nf là hàm lồi, khả dưới vi phân và  nD là tập lồi đóng. Thuật toán. Chọn điểm 0 x D , và  kβ là dãy các số dương thỏa mãn 2   jβ . Tại mỗi Bước lặp k  0,1,...k  ta có kx D . Lấy  k kg f x và tính  1 :  k k kD kx P x α g , trong đó : kk k β α γ với  : max 1, kkγ g . a) Nếu 1 k kx x thì kx là nghiệm của bài toán  P . b) Ngược lại, thay kx bằng 1kx và tiếp tục Bước lặp k với : 1k k  . Định lý 2.9. Giả sử bài toán  P có nghiệm tối ưu và f là khả dưới vi phân trong D . Khi đó dãy  kx được tạo ra bởi thuật toán hội tụ tới nghiệm của bài toán  P . Chứng minh. Để chứng minh định lý, chúng ta cần bổ đề sau: Bổ đề 2.2. Chúng ta có: (i) ,  kk kα g β k ; (ii) 1 ,    k k kx x β k . Chứng minh. (i) Từ  kk k β α γ và k kg γ ta có ,    k kk k k k β g α g β k γ . (ii) Từ  1  k k kD kx P x α g , ta có 1 1, 0,       k k k kkx α g x x x x D . Thay  kx x , theo bất đẳng thức Cauchy-Schwarz, ta có Chương 2. Cực tiểu hàm lồi trên tập lồi 37 21 1 1 1 , . .            k k k k k k k k k k k k k x x α g x x α g x x β x x Bây giờ ta chứng minh định lý. Giả sử *x là nghiệm của bài toán  P , khi đó với mọi k , ta có 2 2 21 * * 1 1 * 12 ,          k k k k k k kx x x x x x x x x x 2* 1 * 12 , .     k k k kx x x x x x (2.11) Từ  1  k k kD kx P x α g , ta có 1 * 1, 0    k k k kkx α g x x x . Vì vậy 1 * 1 * 1, ,     k k k k kkx x x x α g x x . Khi đó, từ (2.11) suy ra 2 21 * * * 12 ,     k k k kkx x x x α g x x . Bằng cách viết * 1 * 1, ,     k k k k k kg x x g x x x x , ta có 2 21 * * * 1 2* * 1 2* * 1 2 , 2 , 2 , 2 . 2 , 2                        k k k k k k k k k k k k k k k k k k k k k k k k x x x x α g x x α g x x x x α g x x α g x x x x α g x x β x x 2* * 22 , 2    k k kk kx x α g x x β . (2.12) Chú ý rằng, từ  *kg f x , chúng ta có Chương 2. Cực tiểu hàm lồi trên tập lồi 38    * *, 0   k k kg x x f x f x . (2.13) Khi đó từ (2.12) suy ra 2 21 * * 22 ,      k k kx x x x β k . (2.14) Do giả thiết 2   jβ , từ (2.14) ta suy ra rằng  *kx x hội tụ. Từ (2.12) và (2.13) chúng ta suy ra    1 * * * 22 2 ,           k k k k kx x x x α f x f x β k , hay     2 2* * 1 * 2 2* 2 0 2 2 2 , .               k k k k k k k α f x f x x x x x β x x β k Tổng k từ 0 tới m , chúng ta có được     2* 0 * 2 0 0 2 2             m j j k j α f x f x x x β . Điều này đúng với mọi m . Do đó    * 0         j j j α f x f x , nghĩa là    * 0    j jα f x f x . Do lim 0jα , suy ra    *lim 0    jf x f x . Nhưng, từ    * 0 jf x f x , chúng ta có    *liminf 0    jf x f x . Do đó    *lim 0    jf x f x . Chú ý rằng  *kx x hội tụ với mọi nghiệm *x . Vì vậy dãy  kx là bị chặn, và do đó nó có một dãy con có giới hạn hữu hạn, chẳng hạn *s , là nghiệm của bài toán. Khi đó dãy  kx hội tụ đến *s . 2.5.2. Thuật toán Frank-Wolfe Xét bài toán quy hoạch lồi với ràng buộc tuyến tính Chương 2. Cực tiểu hàm lồi trên tập lồi 39   min f x x D , trong đó f là hàm lồi khả vi trên n và  nD là đa diện xác định bởi    nD x Ax b , với A là ma trận cấp m n và vectơ mb . Một thuật toán cơ bản để giải bài toán quy hoạch lồi với ràng buộc tuyến tính là thuật toán Frank-Wolfe. Ý tưởng cơ bản của phương pháp là xấp xỉ tuyến tính hàm mục tiêu ở mỗi bước lặp. Thuật toán. Tìm 0 x D . Tại mỗi Bước lặp k  0,1,2,...k  ta có kx . Bước 1. Tính   kf x . Nếu   0 kf x thì dừng thuật toán và kx là nghiệm tối ưu. Trái lại, sử dụng phương pháp đơn hình để giải bài toán quy hoạch tuyến tính   min , kf x x x D ,  kLP thu được nghiệm tối ưu ku . Ta xét hai trường hợp: (i) Nếu   , 0  k k kf x u x , thì kết thúc: kx là nghiệm tối ưu. (ii) Nếu   , 0  k k kf x u x , lấy : k k kd u x là một hướng giảm. Tìm độ dài bước lặp kt theo công thức   argmin 0 1   k kkt f x td t . Bước 2. Tính 1 :  k k kkx x t d . Thay : 1k k  và quay lại Bước lặp k . Định lý 2.10. (i)    1 ,   k kf x f x k . (ii) Nếu thuật toán kết thúc ở bước lặp k , thì kx là nghiệm tối ưu. Nếu thuật toán không kết thúc, thì mọi điểm tụ của dãy  kx là nghiệm tối ưu. Chương 2. Cực tiểu hàm lồi trên tập lồi 40 (iii) Hơn nữa, dãy   kf x hội tụ giảm về giá trị tối ưu *f và ta có    *0 , ,      k k k kf x f f x x u k . Chứng minh. (i) Vì theo thuật toán, kd là hướng giảm. (ii) Ta có, nếu thuật t