Chương 1 KIẾN THỨC CHUẨN BỊ Chương này được dành để nhắc lại một số khái niệm và kết quả cơ bản liên quan đến tối ưu DC (Mục 1.1) và tối ưu đơn điệu (Mục 1. Nội dung chính của chương này được tham khảo trong [2, 3, 39, 40, 41, 42, 43].1 Tối ưu DC Mục này sẽ nhắc lại một số khái niệm và kết quả cơ bản liên quan đến bài toán tối ưu DC và thuật toán DCA.1 Một số khái niệm cơ bản Nếu hàm số f xác định trên một tập C ⊂ Rn thì ta luôn có thể mở rộng nó thành một hàm xác định trên toàn không gian Rn bằng cách đặt f (x) = +∞ với mọi x ∈ / C. Vì vậy không giảm tính tổng quát trong những phần tiếp theo của Mục 1.1 chúng ta sẽ xét hàm f : Rn → R ∪ {−∞, +∞} (tức là một hàm xác định trên toàn không gian) và quy ước rằng +∞ − (+∞) = +∞. Kí hiệu: domf = {x ∈ Rn | f (x) < +∞} (miền hữu hiệu của hàmf ), epif = {(x, t) ∈ Rn × R | f (x) ≤ t} (trên đồ thị của hàmf ).
Hàm f được gọi là (i) chính thường nếu domf 6= ∅ và f (x) > −∞ với mọi x ∈ Rn ; (ii) nửa liên tục dưới nếu nó nửa liên tục dưới tại mọi x0 ∈ Rn , tức là lim inf 0 f (x) ≥ f (x0 ) với mọi x0 ∈ Rn ; x→x (iii) lồi nếu với mọi x1 , x2 ∈ Rn , λ ∈ [0, 1] ta có f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ). 6 Ngoài ra f được gọi là lõm nếu −f là hàm lồi; aphin nếu f vừa lồi vừa lõm; f được gọi là lồi chính thường nếu f vừa lồi vừa chính thường. Rõ ràng, từ định nghĩa ta có f lồi nếu và chỉ nếu trên đồ thị của nó là một tập lồi. Xem minh họa ở Hình 1.1: Minh họa trên đồ thị của hàm lồi y = f (x) Kí hiệu Γ0 (Rn ) là tập tất cả các hàm nửa liên tục dưới, lồi chính thường trên Rn ; h.k tương ứng là tích vô hướng và chuẩn Euclide trong Rn.
(i) Hàm chỉ của một tập lồi C khác rỗng nếu x ∈ C ( 0 χC (x) = +∞ nếu trái lại là một hàm lồi chính thường. (ii) Hàm chuẩn của một véc-tơ ||x||p = ( i |xi |p )1/p (p ≥ 1) là hàm lồi chính P thường. Nói riêng chuẩn Euclide ||x|| = hx, xi cũng là một hàm lồi chính 1/2 thường. (iii) Hàm toàn phương f (x) = 1/2 hx, Qxi + hx, ai + α, trong đó Q là ma trận thực đối xứng cấp n × n; a ∈ Rn và α ∈ R.
Nếu Q là ma trận nửa xác định dương thì f (x) là hàm lồi. , m} + χC (x), với ai ∈ Rn , αi ∈ R, i = 1,. , m; C là tập lồi đa diện khác rỗng trong Rn , là hàm lồi và được gọi là hàm lồi đa diện. Hàm f ∗ xác định bởi f ∗ (y) = sup{hx, yi − f (x) | x ∈ Rn }, với y ∈ Rn 7 được gọi là hàm liên hợp của f.
Hàm bao lồi đóng của hàm f , kí hiệu là cof, là một hàm có trên đồ thị là bao lồi đóng của trên đồ thị của f. Hàm được gọi là lồi đóng nếu hàm bao lồi đóng của nó là chính nó. Như vậy nếu f ∈ Γ0 (Rn ) thì f là hàm lồi đóng và từ [40, Hệ quả 10.1, trang 154] ta suy ra mệnh đề sau. 2 Như vậy, hàm liên hợp của một dạng toàn phương đối xứng xác định dương cũng là một dạng toàn phương, đối xứng xác định dương.
Trong trường hợp đặc biệt 1 ta có hàm liên hợp của hàm ||x||2 là chính nó (xem [40, trang 152]). 2 (ii) Hàm liên hợp của hàm chỉ χ∗C (y) = sup{hx, yi − χC (x) | x ∈ Rn } = sup{hx, yi | x ∈ C}. Cho ε > 0, véc-tơ p ∈ Rn được gọi là một ε-dưới gradient của hàm chính thường f tại x0 (x0 ∈ domf ) nếu p, x − x0 ≤ f (x) − f (x0 ) + ε với mọi x ∈ Rn. Tập tất cả các ε-dưới gradient được gọi là ε-dưới vi phân của f tại x0.
Véc-tơ p ∈ Rn được gọi là dưới gradient của hàm chính thường f tại x0 (x0 ∈ domf ) nếu p, x − x0 ≤ f (x) − f (x0 ) với mọi x ∈ Rn. Tập tất cả các dưới gradient được gọi là dưới vi phân của f tại x0. Như vậy ta có ∂f (x0 ) = ∩ε>0 ∂ε f (x0 ). Định lí sau cho ta biết sự tồn tại của ε-dưới vi phân và dưới vi phân của một hàm chính thường.9, trang 19] và [43, Định lí 2.10, trang 20]) (i) Với ε > 0 bất kì, mỗi hàm lồi chính thường f trên Rn đều có ε-dưới vi phân khác rỗng tại mỗi điểm x0 ∈ domf.
Kí hiệu dom∂f = {x ∈ Rn | ∂f (x) 6= ∅}. Như vậy, theo Định lí 1. (ii) Dưới vi phân của hàm chỉ χC (·) của một tập lồi C là ∂χC (x) = {p | hp, z − xi ≤ 0 ∀z ∈ C} = NC (x), trong đó NC (x) là nón pháp tuyến của C tại x0. (iii) Dưới vi phân của hàm f (x) = ||x|| là ( {p ∈ Rn | ||p|| ≤ 1} khi x = 0 ∂f (x) = {p ∈ Rn | ||p|| = 1, hp, xi = ||x||} khi x 6= 0.
Chi tiết chứng minh có thể tham khảo [43, trang 22]. (iv) Xét hàm φ(y) = supx∈C hx, yi , với C là tập lồi trong Rn. Khi đó p ∈ ∂φ(y 0 ) khi và chỉ khi φ(y) − φ(y 0 ) ≥ p, y − y 0 ∀y ∈ Rn ⇔ sup hx, yi − hp, yi ≥ sup x, y 0 − p, y 0 ∀y ∈ Rn x∈C x∈C 0 0 ⇔ p, y = sup x, y. x∈C Trường hợp đặc biệt, dưới vi phân của hàm χ∗C (y) = supx∈C hx, yi , tại y 0 chính là nghiệm tối ưu của bài toán tối ưu lồi sau max x, y 0.
x∈C 9 Bài toán tối ưu DC và đối ngẫu DC Bài toán tối ưu DC (hay còn gọi là bài toán tối ưu hiệu hai hàm lồi) là một trong những lớp bài toán quan trọng của tối ưu không lồi được nghiên cứu mạnh trong hơn nửa thập kỉ gần đây với rất nhiều ứng dụng trong thực tế. Theo [3, 43], hầu hết các bài toán tối ưu không lồi có thể đưa về một bài toán tối ưu DC. Bài toán tối ưu DC tổng quát có dạng α = inf{g1 (x) − h1 (x) | x ∈ C, u1 (x) − u2 (x) ≤ 0}, trong đó g1 , h1 , u1 , u2 là các hàm lồi trên tập lồi C ⊂ Rn. Tuy nhiên, theo [3], bằng cách sử dụng định lí về hàm phạt chính xác và hàm chỉ χC , bài toán này có thể viết lại được dưới dạng α = inf{f (x) = g(x) − h(x) | x ∈ Rn }, (P) với g, h là các hàm lồi trên Rn.
Khi g, h thỏa mãn thêm điều kiện nửa liên tục dưới trên Rn (tức g, h ∈ Γ0 (Rn )) ta sẽ thu được mối liên hệ giữa bài toán (P) và bài toán đối ngẫu của nó cùng kết quả về điều kiện tối ưu. Những nội dung này sẽ được trình bày dưới đây, trích từ các tài liệu [3, 44] và danh mục tài liệu tham khảo kèm theo. Hàm f trong bài toán (P) được gọi là hàm DC còn g, h được gọi là các thành phần DC của f. Bài toán (P) được gọi là một bài toán tối ưu DC.
Nếu g hoặc h là hàm lồi đa diện thì bài toán (P) được gọi là bài toán tối ưu DC đa diện. Nếu g và h có giá trị hữu hạn trên Rn thì ta nói f là hàm DC hữu hạn trên Rn. Theo định nghĩa của hàm liên hợp và Mệnh đề 1.1 ta có α = inf{g(x) − h(x) | x ∈ Rn } = inf{g(x) − h∗∗ (x) | x ∈ Rn } = inf{g(x) − sup {hx, yi − h∗ (y)} | x ∈ Rn } y∈Rn = inf{β(y) | y ∈ Rn } với β(y) = inf{g(x) − (hx, yi − h∗ (y)) | x ∈ Rn } h∗ (y) − g ∗ (y) nếu y ∈ domh∗ ( = +∞ trường hợp còn lại. Như vậy bài toán (P) tương đương với bài toán α = inf{h∗ (y) − g ∗ (y) | y ∈ domh∗ }.
10 Chú ý rằng với quy ước +∞ − (+∞) = +∞ ta có thể viết lại bài toán trên như sau α = inf{h∗ (y) − g ∗ (y) | y ∈ Rn }. Để tránh trường hợp tầm thường khi giá trị của α có thể bằng −∞ ta luôn giả thiết domg ⊂ domh và domh∗ ⊂ domg ∗ trong những phần tiếp theo. Điểm x∗ được gọi là cực tiểu địa phương của g − h trên Rn nếu g(x∗ ) − h(x∗ ) hữu hạn (tức x∗ ∈ domg ∩ domh) và tồn tại một lân cận U của x∗ thỏa mãn g(x∗ ) − h(x∗ ) ≤ g(x) − h(x), ∀x ∈ U.1) Với quy ước +∞ − (+∞) = +∞, bất đẳng thức (1.1) tương đương với g(x∗ ) − h(x∗ ) ≤ g(x) − h(x), ∀x ∈ U ∩ domg. Điểm x∗ được gọi là điểm tới hạn của g − h nếu ∂g(x∗ ) ∩ ∂h(x∗ ) 6= ∅.
Định lí sau cho ta điều kiện cần và đủ của nghiệm tối ưu của bài toán (P) và (D) và mô tả mối quan hệ giữa hai tập nghiệm của cặp bài toán đối ngẫu này. S Theo khẳng định (iii) và (iv) của Định lí 1.2, việc giải bài toán gốc (P) tương đương với việc giải bài toán đối ngẫu (D). Như vậy trong nhiều trường hợp, khi bài toán gốc "khó giải", ta có thể giải bài toán đối ngẫu. Khẳng định (i) và (ii) của Định lí 1.2 cho phép kiểm tra một điểm cho trước có phải là nghiệm tối ưu toàn cục của bài toán gốc (P) hay bài toán đối ngẫu (D) hay không.
Tuy nhiên những điều kiện này rất khó để kiểm tra trong thực tế. Khi đó chúng ta có thể sử dụng kết quả dưới đây liên quan đến tính tối ưu địa phương. Ngược lại nếu h thỏa mãn thêm điều kiện là hàm lồi đa diện thì từ ∂h(x∗ ) ⊂ ∂g(x∗ ) kéo theo x∗ là cực tiểu địa phương của g − h. Gọi U là lân cận của x∗ sao cho U ∩ domg ⊂ dom∂h.