Chương 1 Bài toán quy hoạch đa mục tiêu lỗi suy rộng Tất cả các bài toán được nghiên cứu trong luận án này đều liên quan gần gũi đến bài toán quy hoạch đa mục tiêu lồi suy rộng (GMOP) và trường hợp riêng của nó là bài toán quy hoạch đa mục tiêu lỗi (CM#ÓP). Để tiện theo dõi, chương này giới thiệu mô hình toán học của bài toán quy hoạch đa mục tiêu lồi suy rộng (GMOP) cùng một số khái niệm và kết quả cơ bản liên quan. Các khái niệm và kết quả được trình bày ở đây là sự chuẩn bị để thiết lập cơ sở lý thuyết cho các thuật toán được để xuất trong các chương sau của luận án. Một số hàm lỗi suy rộng như hàm tựa lỗi, hàm giả lồi, hàm véc tơ giả lồi vô hướng cùng các tính chất hữu dụng của chúng được giới thiệu ở Mục 1.
Mục này cũng trình bày về định lý KKT về điều kiện tối ưu cho bài toán quy hoạch lỗi suy rộng một mục tiêu. Định lý này được dùng làm công cụ lý thuyết để xác định siêu phẳng cắt trong thuật toán xấp xỉ ngoài được đề xuất trong Chương 2 để giải bài toán (GMOP). Như đã biết, khái niệm nền tảng của tối ưu véc tơ là điểm hữu hiệu và điểm hữu yếu của một tập, nhờ đó, người ta mới có thể hiểu được thế nào là nghiệm của bài toán quy hoạch đa mục tiêu. Các khái niệm điểm hữu hiệu, điểm hữu hiệu yếu của một tập, điều kiện nhận biết thông qua khái niệm hướng pháp tuyến và các kết quả về cấu trúc của các tập điểm này sẽ được trình bày ở Mục 1.
1 Cuối cùng, Mục 1.3 giới thiệu bài toán quy hoạch đa mục tiêu lồi suy rộng (GMOP), cùng các khái niệm cơ bản như nghiệm hữu hiệu, nghiệm hữu hiệu yếu, nghiệm hữu hiệu 6-xấp xỉ, nghiệm hữu hiệu yếu 6-xấp xỉ cũng như cấu trúc của tập giá trị hữu hiệu và của tập giá trị hữu hiệu yếu của bài toán (GMOP).1 Hàm lồi suy rộng Cho tập lỗi khác rỗng Š C IR" và hàm số ? : IR" —› IR. Ta nói h là hàm lôi xác định trên $ nếu h(Ax! + (1 —A)x*) < Ah(x!) + (1—A)h(x?) với mọi xÌ,x” € S, và0< Â < 1. Hàm g được gọi là hàm lõm nêu h := —g là hàm lồi. Hàm lỗi có nhiều tính chất đặc sắc, xuất hiện trong nhiều lĩnh vực của toán học và trong thực tế.
Trong toán học còn có một lớp hàm có tính chất tương tự hàm lỗi hoặc liên quan gần gũi với hàm lỗi và có nhiều ứng dụng. Đó là lớp các hàm lỗi suy rộng. Hai dạng hàm lỗi suy rộng được sử dụng trong luận án này là hàm tựa lồi và hàm giả lồi. Theo định nghĩa [66Ï tr.
132], hàm được gọi là hàm /a lôi xác định trên tập lồi S nếu h(x!) — h(x?) <0 => h(Ax! + (1—A)x”) < h(x’), tức h(Ax! + (1—A)x?) < max {h(x!), h(x?) } , véi moi x!,x7 € S va0 <A < 1. Nếu ở là hàm tựa lỗi thì g := —h là hàm tựa lõm. Trong trường hợp h kha vi, néu h tựa lồi trên Š thì h(x!) — A(x”) <0 > (VA(x’), x! — x”) <0 v6i moi x!,x? € S, trong dé VA(x7) 1a véc to gradient ctia ham h tai diém x? (xem Dinh ly 9. Nhu đã biết, tính lồi của tập mức dưới (t., tập mức trên) chỉ là điều kiện cần của hàm lỗi (t., hàm lõm), nhưng nó là điều kiện cần và đủ để nhận biết hàm tựa lỗi (t., hàm tựa lõm) (Định ly 9.
Mọi hàm lồi (t., hàm lõm) đều 2 là hàm tựa lỗi (t., hàm tựa lõm), nhưng điều ngược lại chưa chắc đúng. Chẳng hạn, hàm A(x) = tanx là hàm tựa lồi trên tập lồi S = (—$, $), nhưng không phải là hàm lồi trên S. Sau đây là một số tính chất hữu ích của hàm lỗi, hàm lõm, hàm tựa lồi, hàm tựa lõm cùng mối liên hệ giữa chúng. 154]) Cho ham @ xác định và nhận giá trị dương trên tập loi khác rỗng S C 1TR".
Nếu @ là hàm lõm thì 1/Q là hàm lôi trên S. Ngược lại, nếu @ là hàm lôi thì 1/@ chưa chắc là hàm lõm trên S. Dé thay, ham @(x) = e* véi x € R 1a hàm lồi trên IR nhưng hàm 1/0(x) = e* không phải làm hàm lõm trên ïR. Khẳng định sau chỉ ra điều kiện đủ để một hàm phân thức là tựa lồi (xem Bảng 5.
165] và Bài tập 9. Cho hai hàm số @\, 0› xác định trên tập lôi khác rỗng S CR". )_ Nếu @\ là hàm lôi, @ là hàm lõm trên S thỏa mãn @\(x) > 0 và @(x) > 0 với mọi x € S thi hàm phân thức h = @\ /@ là hàm tựa li trên S: ii) Nếu @\, @ là hai hàm afin và @(x) # 0 với mọi x € Š thì hàm phân thúc h = 0\/@ là hàm vừa tựa lỗi, vừa tựa lõm trên S.,zm, trong đó m > 2, nhận giá trị dương trên tập lỗi S C ]R" và các số thực œ; > 0, i= 1,. Khi do, h(x) = Ie" (x) là hàm tựa lõm trên Š (Định lý 5.
Đặc biệt, Mệnh đề [I.3Ìsau đây khẳng định rằng, nếu œ; = 1 với mọi ¿ = I,.,im, thì trung bình nhân của ở lại là hàm lõm. Tính chất này sẽ được sử dụng trong Chương 3 của luận án để phân tích và giải bài toán quy hoạch tích mở rộng (GIMP).,m, là các hàm lõm nhận giá trị dương trên tập lôi S C IR" thì hàm m 1/m h(x) = Tle là một hàm lõm trên S. Xét bài toán min A(x) v. x€ S, (Ps) trong dé S C R” va h 1a ham sé xac dinh trén mét tap mé chita S.
Nhu đã biết, nếu h là hàm lồi va S 1a tập lỗi thì là một bài toán quy hoạch lồi. Khi đó, bài toán có tính chất đặc biệt là mọi điểm dừng hay điểm KKT của bài toán này đều là nghiệm tối ưu địa phương và cũng chính là nghiệm tối ưu toàn cục của bài toán (xem [3]]). Bai todn vẫn giữ được tính chất quan trọng này khi Š là tập lỗi và hàm mục tiêu ở là giả lồi (Định lý [L I}. Dựa trên tính chất đặc biệt trên, ta có thể giải bài toán khi S là tập lồi và hàm mục tiêu ở là giả lồi bằng việc sử dụng các thuật toán giải bài toán quy hoạch lồi thông thường (xem Nhận xét 2.
Theo định nghĩa (xem [66] tr. 141]), hàm số J xác định trên tập mở chứa tập lồi Š được gọi là hàm giả lôi trên S nêu h khả vi trên S va (Vh(x"),x! —x°) > 0 => h(x!) — h(x?) > 0, véi moi x!, x? € S. Néu / 1a gia lỗi thi ham g := —/ 1A gid lom. Ta đã biết, hàm A(x) = tanx là hàm tựa lỗi khả vi, đơn điệu tăng trên tập mở $ = (—5, 5).
nhưng không phải là hàm lồi. Lập luận sau đây chứng tỏ h là hàm giả lồi trên S. Thật vậy, lấy tùy ý hai điểm bất kỳ x,x; € Š thỏa mãn h' (x2)(x1 — x2) >0. Vì h (xạ) = 1+ tan?x¿ > 0 nên xị > xạ.
Do h don điệu tăng trên Š nên h(x¡) — h(x›) > 0. Theo định nghĩa, h là hàm giả lỗi trên S. 165]) Cho hai hàm số @\, 0a xác định trên tập lôi khác rỗng S C IR". Nếu @\ là hàm lôi khả vi và 0 là hàm afin nhận giá trị dương trên S thì hàm phân thức h = Ọ@\ /@ là hàm giả lôi trên S.
(Xem Dinh ly 9. 142]) Cho h là hàm giả lôi trên tập lôi S và x* là một điểm dừng của bài toán (P$), tức (Vh(x*),x— x*) > 0 với mọi x € S. Khi đó, x* là nghiệm tôi tu toàn cục của bài toán (Ps). Các định lý sau chỉ ra rằng lớp các hàm lồi được chứa trong lớp các hàm giả lồi, và lớp các hàm giả lồi được chứa trong lớp các hàm tựa lỗi.
144]) Cho S là tập lỗi trong IR" và hàm h xác định, khả vi trên một tập mỏ chứa S. Nếu h là hàm lôi (t., lõm) trên S thì h là giả lôi (t. Điều ngược lại chưa chắc đúng. 143]) Cho S là tập lôi trong R" va ham h xdc định trên một tập mỏ chứa S.
Nêu h là hàm giả lôi trên S thì h là tựa lôi trên S. Điêu ngược lại chưa chắc đúng. Xét hàm h(x) = 1 — xỶ xác định trên ÏR. Theo định nghĩa, / 1a ham tua lỗi trên IR.
Tuy nhiên, điểm x = 0 là điểm dừng nhưng nó không phải nghiệm tối ưu của bài toán min{h(x) | x € R}. Vì vậy, theo Định lý [I.I| không phải là hàm giả lỗi trên S. Khác với lớp các hàm lỗi, tính giả lồi và tựa lỗi của hàm số không được bảo toàn qua phép cộng, tức tổng của hai hàm giả lồi chưa chắc đã là hàm giả lồi. Cho hai hàm ¡(x) = tanx và ha(x) = —x xác định trên § = (—', ').2| hy là hàm giả lỗi trên ,$.
Vì ha là hàm tuyến tính trên Š nên h; cũng là hàm giả lồi trên Š. Tuy nhiên, hàm h(x) = hị(x) + ha(x) = tanx — x không phải là hàm giả lồi trên S. Thật vậy, điểm x = 0 là điểm dừng của hàm # do # (0) = 0. Mặt khác, x = 0 không phải là nghiệm tối ưu của bài toán min{h(x) | x € S} vì h(0) > h(—z/4).1| không phải là hàm giả lồi trên S.
Mệnh đề sau khẳng định lớp các hàm giả lỗi và tựa lồi vẫn đóng đối với phép lấy cực đại. i) Néu ø\ và @ là hai hàm tựa lôi thì max{@\, @} cũng là hàm tựa lôi trên S; 1) Nếu ø\ và @ là hai hàm giả lôi thì max{@\, 0y} cũng là hàm giả lôi trên S. Cho tập lồi khác rỗng ,$ C IR" và hàm véc tơ ƒ:R'>R xr— f(x) = (fi); +--+ fo), trong đó ƒ¡,., ƒ› là các hàm xác định trên S. Để thuận tiện (xem [9| |56li58]), hàm véc tơ ƒ được gọi là hàm véc tơ tuyến tính (tư., lôi, tựa lôi, giả lôi) nêu các hàm fi;-., „ đều là các hàm tuyến tính (t., lồi, tựa lồi, giả lồi).
Chương 2 của luận án nghiên cứu bài toán quy hoạch đa mục tiêu lỗi suy rộng với giả thiết tập chấp nhận được là tập lồi và hàm véc tơ mục tiêu là hàm giả lôi vô hướng (scalarly pseudoconvex). Khái niệm hàm giả lồi vô hướng dưới đây được định nghĩa tương tự khái niệm hàm tựa lồi vô hướng (scalarly quasiconvex) đã được sử dụng trong [9| f79].