Luận án Phương pháp giải một số lớp bài toán tối ưu đa mục tiêu và ứng dụng

y∗ ∈ {yL,yR} và ϕ(y∗) là giá trị tối ưu của (SP(yL,yR)). Trường hợp 2 (vL và vR độc lập tuyến tính): Ký hiệu đường thẳng HL là siêu phẳng tựa của Y+ tại yL và đường thẳng HR là siêu phẳng tựa của Y+ tại yR. Giao điểm yO của hai đường thẳng này là nghiệm duy nhất yO của hệ 〈 vL,y 〉 = 〈 vL,yL 〉〈 vR,y 〉 = 〈 vR,yR 〉 . (4.5) Ký hiệu S(yL,yR) = conv{yL,yO,yR}, trong đó conv{yL, yO,yR} là bao lồi của ba điểm yL, yO,yR. Ta có S(yL,yR) là một 2-đơn hình chứa đoạn cong hữu hiệu Γ(yL,yR) (xem Hình 4.3). Vì vậy, giá trị tối ưu của bài toán nới lỏng min ϕ(y) v.đ.k. y ∈ S(yL,yR) (RP(yL,yR)) là một cận dưới của bài toán con (SP(yL,yR)). Vì hàm mục tiêu ϕ(y) là hàm tựa lõm nên bài toán (SP(yL,yR)) có một nghiệm tối ưu là y∗ thuộc tập đỉnh 88 {yL,yO,yR}. Nếu y∗ ∈ {yL,yR} thì y∗ cũng là một nghiệm tối ưu của bài toán (SP(yL,yR)) và giá trị tối ưu của (SP(yL,yR)) là ϕ(y∗). Ngược lại, y∗ ≡ yO và β (Γ(yL,yR)) = ϕ(y∗) là một cận dưới của giá trị tối ưu của bài toán con (SP(yL,yR)), tức β (Γ(yL,yR))≤min{ϕ(y) | y ∈ Γ(yL,yR)}. Hình 4.3: Đơn hình S(yL,yR) Ký hiệu yopt là nghiệm tối ưu của bài toán con (SP(yL,yR)). Thủ tục giải bài toán con này được mô tả chi tiết như sau. Thủ tục Solve(SP(yL,yR)) Bước 1. (1.1) If vL = tvR với t > 0 Then Đặt Vopt :=min{ϕ(yL),ϕ(yR)} Else Chuyển sang Bước 2; (1.2) If ϕ(yL) =Vopt Then yopt = yL Else yopt = yR. 89 Bước 2. (2.1) Giải hệ (4.5) để tìm điểm yO; (2.2) Đặt Vopt :=min{ϕ(yL),ϕ(yR),ϕ(yO)}. Bước 3. If ϕ(yL) =Vopt Then yopt = yL Else If ϕ(yR) =Vopt Then yopt = yR Else yopt = yO. 4.1.2 Thuật toán nhánh cận trên không gian ảnh Thuật toán đề xuất để giải bài toán (QPY+) được xây dựng dựa trên kỹ thuật nhánh cận. Việc phân hoạch, rẽ nhánh và tính cận dưới đã được trình bày ở Mục 4.1.1. Để cập nhật cận trên của bài toán (QPY+), ta sử dụng ngay điểm hữu hiệu mới ynew ∈MinY+ thu được từ việc giải bài toán (BP0). Dạng tường minh của bài toán (BP0) là min 〈vnew,y〉 v.đ.k. f (x)− y≤ 0 x ∈ X . (BP1) Gọi (xnew,ynew) là nghiệm tối ưu của bài toán (BP1). Vì ynew ∈ MinY+ và ynew ≥ f (xnew) nên xnew ∈ XE . Để thuận tiện, ta gọi xnew là nghiệm hữu hiệu tương ứng với ynew ∈MinY+. Ký hiệu ϕopt là giá trị tối ưu của bài toán (QPY+). Cho ε là một số dương đủ nhỏ. Nếu y∗ ∈MinY+ thì ϕ(y∗) là một cận trên của bài toán (QPY+). Điểm y∗ ∈MinY+ được gọi là một nghiệm tối ưu ε-xấp xỉ của bài toán (QPY+) nếu có một cận dưới β ∗ của bài toán (QPY+) thỏa mãn |ϕ(y∗)−β ∗| ≤ ε(|ϕ(y∗)|+ 1). Khi đó điểm y∗ là một nghiệm tối ưu ε-xấp xỉ của bài toán (QPY+) và bất kỳ điểm x∗ ∈ XE tương ứng với y∗ là một nghiệm tối ưu xấp xỉ của bài toán (QP). Sau đây là thuật toán chi tiết giải bài toán (QPY+). 90 Thuật toán Solve(QPY+). Bước 0. (Khởi tạo) (0.1) Chọn sai số ε > 0; Với mỗi i = 1,2, tìm nghiệm yˆi ∈MinY+ của bài toán (SPi) và xˆi ∈ XE tương ứng với yˆi; (0.2) If yˆ1≡ yˆ2 Then Thuật toán dừng. (yˆ1 ∈Argmin(QPY+) và xˆ1 ∈Argmin(QP)) (0.3) If ϕ(yˆ1)< ϕ(yˆ2) Then α0 = ϕ(yˆ1), ybest0 = yˆ 1, xbest0 = xˆ 1 Else α0 = ϕ(yˆ2) và ybest0 = yˆ 2, xbest0 = xˆ 2 (α0 - cận trên tốt nhất hiện tại, ybest0 - nghiệm chấp nhận được tốt nhất hiện tại, xbest0 ∈ XE tương ứng với ybest0 ); (0.4) Giải bài toán (SP(yL,yR)) với yL = yˆ1 và yR = yˆ2 để tìm nghiệm tối ưu yopt; (0.5) Đặt Γ0 = Γ(yˆ1, yˆ2); (0.6) If ϕ(yO) = ϕ(yopt) Then Đặt G = {Γ0}, β (Γ0) = ϕ(yopt) và k := 0 Else Thuật toán dừng (ybest0 ∈ Argmin(QPY+) và xbest0 ∈ Argmin(QP)). Bước 1. (Điều kiện dừng) (1.1) If G = /0 Then Thuật toán dừng. (ybestk là nghiệm tối ưu ε-xấp xỉ của bài toán (QPY+) và xbestk là nghiệm tối ưu xấp xỉ của bài toán (QP)) Bước 2. (Cập nhật cận dưới) (2.1) Tìm Γk ∈ G , trong đó Γk = Γ(yL,yR), thỏa mãn β (Γk) =min{β (Γ) | Γ ∈ G }; (2.2) Đặt βk := β (Γk). (cận dưới tốt nhất hiện tại) Bước 3. (Rẽ nhánh và cập nhật cận trên) (3.1) Giải bài toán (BP1) để xác định ynewk ∈MinY+và xnewk ∈ XE tương ứng; (3.2) If ynewk ∈ {yL,yR} Then G := G \{Γk} và chuyển sang Bước 1; 91 (3.3) If αk > ϕ(ynewk ) Then αk+1 = ϕ(y new k ) (cận trên tốt nhất hiện tại) ybestk = y new k (nghiệm chấp nhận được tốt nhất hiện tại) xbestk = x new k (x best k ∈ XE tương ứng với ybestk ) Else Đặt αk+1 := αk; (3.4) If (αk+1−βk)≤ ε(|αk+1|+1) Then Đặt G = /0, chuyển sang Bước 1 Else Đặt G := ( G \{Γk})∪{Γk1,Γk2}, trong đó Γk1 = Γ(yL,ynewk ) và Γk2 = Γ(ynewk ,y R). Bước 4. (Loại bỏ) (4.1) Xác định nghiệm tối ưu yopt của bài toán (SP(yL,yR)) với yR = ynewk ; (4.2) If ϕ(yO) = ϕ(yopt) Then Đặt β (Γk1) = ϕ(yopt) Else G := G \{Γk1}; (4.3) Xác định nghiệm tối ưu yopt của bài toán (SP(yL,yR)) với yL = ynewk ; (4.4) If ϕ(yO) = ϕ(yopt) Then Đặt β (Γk2) = ϕ(yopt) Else G := G \{Γk2}; (4.5) If G = /0Then Thuật toán dừng (ybestk ∈Argmin(QPY+) và xbestk ∈Argmin(QP)) Else Đặt G = {Γ ∈ G | (αk+1−β (Γ))> ε(|αk+1|+1)}; (4.6) Đặt k := k+1 và quay lại Bước 1. Giả sử thuật toán dừng ở Bước lặp k nào đó. Nếu nó dừng ở Bước 0 hoặc dừng ở Bước 4, ta nhận được một nghiệm tối ưu ybestk của bài toán (QPY+), và một nghiệm tối ưu xbestk của bài toán (QP). Nếu nó dừng ở Bước 1 thì y ∗ = ybestk là một nghiệm tối ưu ε−xấp xỉ của bài toán (QPY+), và x∗ = xbestk là một nghiệm ε−xấp xỉ của bài toán (QP). Nếu thuật toán không dừng thì nó hội tụ như khẳng định trong kết quả sau. Định lý 4.1. Nếu thuật toán không dừng thì dãy {ϕ(ybestk )} hội tụ tới giá trị tối ưu của bài toán (QPY+) và dãy {ybestk } ∈MinY+ có một điểm tụ là nghiệm toàn cục của bài toán (QPY+). 92 Chứng minh. Nếu thuật toán không dừng thì nó sinh ra một dãy {ybestk } ∈MinY+. Bên cạnh đó, thuật toán cũng sinh ra một dãy các đa diện {Sk} thỏa mãn S0 ⊃ S1 ⊃ S2 ⊃ ·· · ⊃MinY+, trong đó S0 = S(yˆ1, yˆ2) và Sk+1 = {y ∈ Sk|〈vnewk ,y〉 ≥ 〈vnewk ,ynewk 〉},k = 0,1,2, . . . với ynewk là điểm chia đôi được xác định ở Bước 3 và v new k là véc tơ pháp tuyến trong tương ứng với ynewk (xem Hình 4.4). Phần còn lại của định lý được suy ra trực tiếp từ Định lý 3.1 [46]. Hình 4.4: Minh họa cách sinh dãy các đa diện {Sk} Nhận xét 4.1. Thuật toán đề xuất ở đây có thể được dùng để giải bài toán cực tiểu tích hai hàm lồi trên tập lồi (CBMP) tương ứng với bài toán (CBOP), tức là min f1(x) f2(x) v.đ.k. x ∈ X , (CBMP) trong đó các hàm f j, j= 1,2 và tập chấp nhận được X được cho như trong bài toán (CBOP). Dạng trên không gian ảnh của bài toán (CBMP) được viết như sau minϕ(y) = y1y2 v.đ.k. y ∈ Y. (CBMPY ) Như đã biết, nếu y∗ là nghiệm tối ưu của bài toán (CBMPY ) thì bất kỳ x∗ ∈ X thỏa 93 mãn f (x∗) ≤ y∗ là nghiệm tối ưu của bài toán (CBMP). Từ định nghĩa, dễ dàng chứng minh được rằng nghiệm tối của bài toán (CBMPY ) phải thuộc tập ảnh hữu hiệuMinY . Khi đó, bài toán (CBMPY ) tương đương với bài toán minϕ(y) = y1y2 v.đ.k. y ∈MinY. Vì ϕ(y) = y1y2 là hàm tựa lồi trên intR2+ nên đây là trường hợp riêng của bài toán (QPY ). Nói cách khác, bài toán (CBMP) có thể được giải thông qua việc giải bài toán (QP) với ϕ(y) = y1y2. 4.1.3 Tính toán thử nghiệm Tất cả các ví dụ trong mục này được thử nghiệm với thuật toán cài đặt bằng ngôn ngữ Matlab trên máy laptop Pavilon 1.8Ghz, RAM 2GB. Ví dụ 4.1. Xét bài toán (QP) được cho bởi Benson H.P. và Boger G.M. trong [18], trong đó f1(x) = x1+ 1 9 x3, f2(x) = x2+ 1 9 x3, ϕ(y1,y2) = y1y2 và X = {x ∈ R11|Ax= b,x≥ 0} với A=  9 9 2 1 0 0 0 0 0 0 0 8 1 8 0 1 0 0 0 0 0 0 1 8 8 0 0 1 0 0 0 0 0 7 1 1 0 0 0 −1 0 0 0 0 1 7 1 0 0 0 0 −1 0 0 0 1 1 7 0 0 0 0 0 −1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1  , b=  81 72 72 9 9 9 8 8  . Cho ε = 0.00001. Thuật toán dừng ngay trong bước lặp đầu tiên. Nghiệm tối ưu ε−xấp xỉ của bài toán (QPY+) là ybest = (0.1111,8.1111), và nghiệm tối ưu xấp xỉ tương ứng của bài toán (QP) là xbest = (0,8,1,7,56,0,0,48,6,8,0)T và giá trị tối ưu ε−xấp xỉ của bài toán (QP) là h(xbest) = 0.9012. Kết quả tính toán này giống với kết quả trong thuật toán [18], trong đó thuật toán dừng sau 2 bước lặp. 94 Ví dụ 4.2. Xét bài toán (QP) với f1(x) = (x1− 2)2+ 1, f2(x) = (x2− 4)2+ 1, X = {x∈R2 | 25x21+4x22−100≤ 0, x1+2x2−4≤ 0} và ϕ(y1,y2) ở một trong các dạng sau (xem [90]) với các tham số α1,α2, α1 j,α2 j,k j > 0 với mọi j = 1,2, ...,s, ϕ0(y1,y2) = y1y2 ϕ1(y1,y2) = yα11 y α2 2 ϕ2(y1,y2) = ∑sj=1 k jy α1 j 1 y α2 j 2 ϕ3(y1,y2) = α1ey1+α2ey2 ϕ4(y1,y2) = yα11 /(K− yα22 ) với K >maxy∈Y yα22 ϕ5(y1,y2) = α1 logy1+α2 logy2. Đầu tiên, ta xét trường hợp h(x) = ϕ0( f (x)), Theo Nhận xét 4.1, việc giải bài toán (QP) trong trường hợp này tương đương với việc giải bài toán quy hoạch tích hai hàm lồi (CMP). Chọn ε = 0.01. Bảng 4.1 liệt kê các nghiệm chấp nhận được tốt nhất hiện tại ybestk , điểm chia đôi y new k , cận trên tốt nhất hiện tại αk, cận dưới tốt nhất hiện tại βk và Gapk = (αk−βk)/(|αk+1|+1) tại mỗi bước. Sau 4 bước lặp, vìGap3= 0.0094< ε và G = /0 nên thuật thoán dừng . Nghiệm tối ưu ε-xấp xỉ của bài toán (QPY+) là ybest = (1.0178,9.6040) và nghiệm tối ưu xấp xỉ của bài toán (QP) là xbest = (1.8665,1.0667)T . Giá trị tối ưu ε-xấp xỉ của bài toán (QP) là h(xbest) = 9.7751. Kết quả tính toán này giống với kết quả trong [12], [30] và [46]. Kết quả tính toán trong các trường hợp còn lại của hàm ϕ được nêu trong Bảng 4.2, trong đó #Iter là số bước lặp, yε là nghiệm tối ưu ε-xấp xỉ của bài toán (QPY+), ϕopt là giá trị tối ưu ε-xấp xỉ của bài toán (QP) và Time là thời gian tính toán theo đơn vị giây. Kết quả này chỉ ra rằng thuật toán làm việc hiệu quả với nhiều dạng khác nhau của hàm mục tiêu. 95 Bước lặp ybestk y new k αk βk Gapk k = 0 (2.4131,6.7871) (2.4131,6.7871) 16.3778 2.3804 0.8055 k = 1 (1.0505,9.3381) (1.0505,9.3381) 9.8102 8.2168 0.1474 k = 2 (1.0505,9.3381) (1.0018,9.8740) 10.0999 9.6628 0.0394 k = 3 (1.0178,9.6040) (1.0178,9.6040) 9.7751 9.6743 0.0094 Bảng 4.1: Kết quả tính toán của Ví dụ 4.2 trong trường hợp ϕ = ϕ0 ϕ(y) #Iter yε ϕopt Time y0.51 y 3 2 6 (21.3477,1.5544) 17.3524 0.6240 0.4y0.51 y 3 2+0.9y 2 1y 0.25 2 3 (6.0127,4.5365) 139.0545 0.9516 2.5ey1+0.75ey2 5 (3.7922,5.6851) 331.7185 0.7176 y0.251 /(10− y0.52 ) 4 (1.0000,10.0999) 0.1466 0.8424 0.3logy1+1.5logy2 5 (21.3477,1.5544) 1.5799 0.6708 Bảng 4.2: Kết quả tính toán của Ví dụ 4.2 trong các trường hợp của ϕ Ví dụ 4.3. Để so sánh thuật toán đề xuất với thuật toán của N.V. Thoại [87], ta xét một dạng khác của ví dụ trong [87, tr. 65], được cho dưới dạng bài toán (QP), trong đó f (x) = ( f1(x), f2(x)) , X = {x ∈ R2 | Ax≤ b,x≥ 0,g(x)≤ 0} với A=  1.0 −2.0 −1.0 1.0 2.0 1.0 2.0 5.0 −1.0 −1.0  ,b=  1.0 1.0 4.0 10.0 −1.5 , 96 g(x) = 0.5(x1−1)2+1.4(x2−0.5)2−1.1, f1(x) = x21+ x 2 2+0.4x1−4x2, f2(x) =max{−(0.5x1+0.25x2+0.2);−2x1+4.6x2−5.8} , và ϕ(y) =min{0.1(y1−7);0.9(y2−1)}}. Chọn ε = 0.00001. Thuật toán dừng ngay bước khởi tạo. Ta thu được nghiệm tối ưu ε-xấp xỉ ybest = (−1.3365,−1.2000) của bài toán (QPY+), nghiệm tối ưu xấp xỉ xbest = (1.3170,1.3659)T của bài toán (QP), và giá trị tối ưu ε−xấp xỉ của bài toán (QP) là h(xbest) =−1.9800 . Trong [87], thuật toán giải bài toán này dừng sau 6 bước lặp với nghiệm tối ưu xấp xỉ x∗ = (1.3170,1.3659)T . Ví dụ 4.4. Xét bài toán (QP) trong đó ϕ(y) = (y1−β1)α1(y2−β2)α2 và fi(x) = xTci+ xTDix, i= 1,2, X = x ∈ Rn ∣∣∣∣∣ ( −2+ n ∑ j=1 x j j )2 ≤ 100,Ax≤ b,x≥ 0  . Các tham số được cho như sau (xem [41]): ci ∈ Rn, với mọi i = 1,2, là các véc tơ với các thành phần được sinh ngẫu nhiên trong [0,1]. Di = (di j) ∈Rn×n là các ma trận đường chéo với phần tử đường chéo dii được sinh ngẫu nhiên trong [0,1]. A = (ai j) ∈ Rm×n là ma trận với các phần tử được sinh ngẫu nhiên trong [−1,1]. b= (b1,b2, ...,bm)T là véc tơ có các thành phần bi = n ∑ j=1 ai j+2b0, i= 1,2, ...,m, với b0 là một số ngẫu nhiên trong [0,1]. 97 αi, với mọi i= 1,2, là các số ngẫu nhiên trong [0,1]. βi =min{ fi(x) | x ∈ X}, với mỗi i= 1,2. Với ε = 0.005, đối với mỗi bộ tham số n,m, ta giải 10 bài toán. Kết quả tính toán thu được trong Bảng 4.3, trong đó #Iter là số bước lặp trung bình, UB = αK và LB = βK lần lượt là cận trên và cận dưới ở Bước lặp K cuối cùng, Gap cho bởi UB−LB |UB|+1 và Time là thời gian tính trung bình theo giây. n m #Iter UB LB Gap Time 60 40 5.2 4.8458 4.8312 0.0025 0.88 70 50 6.4 6.1537 6.1458 0.0011 1.31 80 80 5.8 2.3188 2.3135 0.0016 1.77 100 60 4.4 5.3968 5.3917 0.0008 2.45 100 80 5.1 1.5828 1.5707 0.0047 3.94 120 120 4.7 3.8471 3.8331 0.0029 6.12 150 100 4.9 6.6608 6.6340 0.0035 7.34 150 120 6.2 8.7834 8.7580 0.0026 9.21 Bảng 4.3: Kết quả tính toán với bài toán sinh ngẫu nhiên trong Ví dụ 4.4 4.2 Thuật toán giải bài toán (DP) với ϕ là hàm đơn điệu tăng Xét bài toán maxϕ(y) v.đ.k. y ∈MinY+, (DPY+) trong đó ϕ : Y → R là hàm đơn điệu tăng trên Y . Mục này đề xuất thuật toán giải bài toán (DPY+) theo lược đồ nhánh cận kết hợp kỹ thuật xấp xỉ ngoài. 98 Nhắc lại rằng, hàm k được gọi là đơn điệu tăng trên S nếu k(y1)> k(y2) với bất kỳ y1,y2 ∈ S sao cho y1 ≥ y2,y1 6= y2. 4.2.1 Đơn hình xấp xỉ ngoài và lược đồ rẽ nhánh Xét hai điểm bất kỳ yL,yR ∈MinY+ thỏa mãn (4.3). Ta vẫn ký hiệu Γ(yL,yR) là đường cong duy nhất nằm trênMinY+ nối hai điểm yL và yR. Đặt yO = (yO1 ,y O 2 ) trong đó yO1 = y L 1 > 0, y O 2 = y R 2 > 0. (4.6) Hiển nhiên là yL,yO,yR không thẳng hàng nên conv{yL,yO,yR} là một 2-đơn hình. Ký hiệu S(yL,yR) := conv{yL,yO,yR}. Dễ thấy, đơn hình S(yL,yR) nằm trong nón lồi (yO+R2+). Hơn nữa, S(yL,yR) chứa đường cong hữu hiệu nối yL và yR (xem Hình 4.5) hay Γ(yL,yR)⊂ S(yL,yR). Để thuận tiện, ta gọi đơn hình S(yL,yR) là đơn hình sinh ra bởi yL và yR. Đồng thời, yO được gọi là gốc của đơn hình này. Hình 4.5: Đơn hình S(yL,yR) Theo định nghĩa, dễ thấy rằng tia xuất phát từ gốc O của không gian ảnh R2 qua đỉnh yO của đơn hình S(yL,yR) giao với biên ∂Y+ của tập Y+ tại một điểm duy nhất yω ∈ Γ(yL,yR) ⊆MinY+ (xem minh họa trong Hình 4.6). Kết quả này đóng vai trò then chốt trong thuật toán giải bài toán (DPY+). 99 Hình 4.6: Đường cong Γ(yL,yR) Mệnh đề 4.1. Cho hai điểm yL,yR ∈MinY+ thỏa mãn (4.3) và cho 2−đơn hình S(yL,yR) = conv{yL,yO,yR}, trong đó yO thỏa mãn (4.6). Khi đó tia nối gốc O của không gian ảnh R2 và gốc yO của đơn hình S(yL,yR) cắt ∂Y+ tại một điểm duy nhất yω ∈MinY+. Hơn nữa, yL1 < y ω 1 < y R 1 và y R 2 < y ω 2 < y L 2. (4.7) Chứng minh. Vì yL,yR ∈MinY+ và yO thỏa mãn (4.6) nên yO 6∈ Y+. Do đó, theo Mệnh đề 1.9, tia nối gốc O với yO cắt ∂Y+ tại một điểm duy nhất yω ∈ Y . Vì MinY+ = ∂Y+∩Y (Mệnh đề 1.7) nên yω ∈MinY+. Hơn nữa, do yL,yR ∈MinY+ và thỏa mãn (4.3) nên yω phải thỏa mãn (4.7). Gọi (x∗,λ ∗) là nghiệm tối ưu của bài toán quy hoạch lồi với hàm mục tiêu tuyến tính min λ (T (yO)) v.đ.k. f (x)−λyO ≤ 0, gi(x)≤ 0, i= 1, · · · ,m. Khi đó x∗ là nghiệm hữu hiệu tương ứng với yω = λ ∗yO (Xem Mệnh đề 1.9). Nhận xét 4.2. Giả sử yL,yR ∈ MinY+ thỏa mãn (4.3) và Γ(yL,yR) ⊆ MinY+ là đường cong hữu hiệu nối yL và yR. Xét 2−đơn hình S(yL,yR) sinh bởi yL và yR. 100 Ký hiệu yω là điểm xác định như mô tả trong Mệnh đề 4.1. Theo (4.7), ký hiệu S(yL,yω) là đơn hình sinh bởi yL và yω , và S(yω ,yR) là đơn hình sinh bởi yω và yR (xem Hình 4.7). Khi đó, ta có Γ(yL,yR)⊂ (S(yL,yω)∪S(yω ,yR))⊂ S(yL,yR). Điểm yω được xem như một điểm chia đôi đơn hình S(yL,yR). Việc chia đơn hình S(yL,yR) như vậy được gọi là lược đồ rẽ nhánh áp dụng cho đơn hình S(yL,yR). Tính chất này sẽ được sử dụng để xây dựng thuật toán giải bài toán (DPY+). Hình 4.7: Lược đồ rẽ nhánh áp dụng cho đơn hình S(yL,yR) Hiển nhiên là (4.3) thỏa mãn với hai điểm yL = yˆ1,yR = yˆ2, trong đó yˆ1 và yˆ2 được xác định bởi (4.2). Đặt S(yˆ1, yˆ2) là đơn hình sinh bởi hai điểm yˆ1 và yˆ2. Ta có MinY+ ⊂ S(yˆ1, yˆ2), và S(yˆ1, yˆ2) được chọn làm đơn hình xuất phát của thuật toán xấp xỉ ngoài giải bài toán (DPY+). 4.2.2 Thuật toán nhánh cận - xấp xỉ ngoài Đặt T 0 = {S0,1}, trong đó S0,1 = S(yˆ1, yˆ2) và U0 = ⋃ S∈T 0 S= S0,1 ⊃MinY+. Xuất phát từ hai tập T 0 và U0, thuật toán là một quá trình lặp sinh ra hai dãy 101 { T k = {Sk,1,Sk,2, . . . ,Sk,ηk}} gồm các 2−đơn hình, trong đó ηk là số phần tử của T k, và { Uk = ⋃ S∈T k S } thỏa mãn U0 ⊃U1 ⊃ ...Uk ⊃Uk+1 ⊃ ...⊃MinY+. Tại Bước lặp k = 0, ta đã có yˆ1, yˆ2 ∈MinY+. Đặt β0 =max{ϕ(yˆ1),ϕ(yˆ2)}. Rõ ràng β0 là cận dưới tốt nhất hiện tại của bài toán (DPY+). Điểm ybest ∈ {yˆ1, yˆ2} thỏa mãn ϕ(ybest) = β0 được gọi là nghiệm chấp nhận được tốt nhất hiện tại. Gọi xbest là điểm hữu hiệu tương ứng với ybest . Cho số thực ε > 0 đủ nhỏ. Điểm chấp nhận được y∗ ∈ MinY+ được gọi là nghiệm tối ưu ε−xấp xỉ của bài toán (DPY+) nếu tồn tại một cận trên α∗ của bài toán này thỏa mãn α∗−ϕ(y∗)< ε(|ϕ(y∗)|+1). Khi đó, nghiệm hữu hiệu x∗ tương ứng với y∗ là một nghiệm tối ưu xấp xỉ của bài toán (DP). Ở bước lặp k điển hình, k ≥ 0, ta có nghiệm chấp nhận được tốt nhất hiện tại ybest , nghiệm hữu hiệu xbest tương ứng với ybest , cận dưới βk = ϕ(ybest), tập các đơn hình T k, và tập Uk thỏa mãn MinY+ ⊂Uk. Với mỗi η ∈ {1,2, . . . ,ηk}, đơn hình Sk,η được sinh bởi hai điểm đã biết. Tại đây thuật toán thực hiện những việc sau: i) Tìm giá trị tối ưu αk của bài toán max{ϕ(y)|y ∈Uk}. Vì MinY+ ⊂Uk nên giá trị tối ưu αk là một cận trên của bài toán (DPY+). ii) Nếu αk−ϕ(ybest)≤ ε( ∣∣ϕ(ybest)∣∣+1) thì thuật toán dừng. Khi đó, ta thu được ybest là nghiệm tối ưu ε−xấp xỉ của bài toán (DPY+) và xbest là nghiệm xấp xỉ của bài toán (DP). Ngược lại, thuật toán sinh một tập mới T k+1, trong đó Uk+1 = ⋃ S∈T k+1 S thỏa mãn Uk ⊃Uk+1 ⊃MinY+. Với mỗi S ∈ T k, ký hiệu α(S) là giá trị tối ưu của bài toánmax{ϕ(y)|y ∈ S}. Vì Uk = ⋃ S∈T k S nên ta có αk =max{α(S)|S ∈ T k}. Tại Bước lặp k, nếu thuật toán chưa dừng, ta chọn đơn hình S(yL,yR)= Sk,η¯ ∈ T k sao cho αk = α(Sk,η¯). Gọi yω và điểm x∗ tương ứng với nó là các điểm xác định như mô tả trong Mệnh đề 4.1. Khi đó, áp dụng lược đồ nhánh cận cho đơn hình 102 S(yL,yR) với điểm chia đôi yω ta được hai đơn hình S(yL,yω) và S(yω ,yR) như trong Nhận xét 4.2. Đặt T k+1 = ( T k \{S(yL,yR)})∪{S(yL,yω),S(yω ,yR)} vàUk+1 = ⋃ S∈T k+1 S. Từ Nhận xét 4.2, ta cóMinY+ ⊂Uk+1 ⊂Uk. Bây giờ, ta xét bài toán max{ϕ(y)|y ∈ S(yL,yR)}, (DP(S(yL,yR))) trong đó ϕ là hàm đơn điệu tăng trên R2+ và S(yL,yR) là 2−đơn hình được sinh bởi hai điểm yL,yR nào đó. Vì ϕ là hàm đơn điệu tăng trên S(yL,yR)⊂R2+ nên nghiệm tối ưu của bài toán (DP(S(yL,yR))) đạt tại cạnh [ yL,yR ] của đơn hình S(yL,yR). Theo định nghĩa, mỗi điểm y ∈ [yL,yR] có thể cho bởi y= tyL+(1− t)yR, 0≤ t ≤ 1. Do đó, bài toán (DP(S(yL,yR))) có thể đưa về một bài toán cực đại hàm một biến trên một khoảng đóng trong R max{θ(t)|0≤ t ≤ 1}, (DP1(S(yL,yR))) trong đó θ(t) = ϕ ( tyL+(1− t)yR). Nhận xét 4.3. Theo lý luận trên, thay vì giải bài toán (DP(S(yL,yR))), ta giải bài toán cực đại hàm một biến (DP1(S(yL,yR))). Nếu t¯ là nghiệm tối ưu của (DP1(S(yL,yR))) thì yopt = t¯yL+(1− t¯)yR là nghiệm tối ưu của (DP(S(yL,yR))). Thuật toán nhánh cận kết hợp xấp xỉ ngoài giải bài toán (DPY+) được mô tả chi tiết như sau. Thuật toán Solve(DPY+) Bước khởi tạo. Thực hiện các bước dưới đây: (0.1) Chọn sai số ε > 0; Giải bài toán (SPi) với i= 1,2 để xác định hai điểm hữu hiệu đầu tiên yˆ1, yˆ2 ∈ MinY+ và hai nghiệm hữu hiệu xˆ1, xˆ2 tương ứng với yˆ1, yˆ2; 103 (0.2) If yˆ1 ≡ yˆ2 Then Thuật toán dừng, yˆ1 là nghiệm tối ưu của bài toán (DPY+) và xˆ1 là nghiệm tối ưu của bài toán (DP); (0.3) If ϕ(yˆ1)> ϕ(yˆ2) Then β0 = ϕ(yˆ1) và ybest = yˆ1, xbest = xˆ1 Else β0 = ϕ(yˆ2) và ybest = yˆ2, xbest = xˆ2; (β0 là cận dưới tốt nhất hiện tại, ybest là điểm chấp nhận được tốt nhất hiện tại, xbest là nghiệm hữu hiệu tương ứng với ybest) (0.4) Đặt S0,1 = S(yˆ1, yˆ2). Đặt T 0 := {S0,1} vàU0 := S0,1; (0.5) Tìm giá trị tối ưu α(S) của bài toán (DP(S(yL,yR))) với S= S(yˆ1, yˆ2); (0.6) Đặt k := 0; Chuyển sang Bước lặp k. Bước lặp k,(k = 0,1,2, ...) Thực hiện từ Bước 1 đến Bước 3 như dưới đây. Bước 1. (Chọn đơn hình và tính cận trên) (1.1) Tìm Sk,η¯ ∈ T k, trong đó Sk,η¯ là đơn hình sinh ra bởi hai điểm yL và yR đã biết, thỏa mãn α(Sk,η¯) :=max{α(S′) | S′ ∈ T k}; (1.2) Đặt αk := α(Sk,η¯) (cận trên tốt nhất hiện tại); (1.3) If αk−βk ≤ ε(|βk|+1) Then Thuật toán dừng (ybest là nghiệm tối ưu ε−xấp xỉ của bài toán (DPY+), xbest là nghiệm tối ưu xấp xỉ của bài toán (DP)) Else Đặt Sk = Sk,η¯ . Bước 2. (Tìm điểm chia và cập nhật cận dưới) (2.1) Xác định gốc yO của đơn hình Sk bởi (4.6), trong đó yL và yR là hai điểm sinh ra đơn hình Sk; (2.2) Giải bài toán (T (yO)) để tìm nghiệm tối ưu (λ ∗,x∗); (2.3) Đặt yωk = λ ∗yO ∈MinY+ (điểm chia đơn hình Sk) và x∗ là nghiệm hữu hiệu tương ứng với yωk; 104 (2.4) If ϕ(yωk)> βk Then βk+1 = ϕ(yωk) (cận dưới tốt nhất hiện tại) ybest = yωk (nghiệm chấp nhận được tốt nhất hiện tại) xbest = x∗; (nghiệm hữu hiệu tương ứng với ybest) Bước 3. (Áp dụng lược đồ rẽ nhánh cho Sk với điểm chia yωk) (3.1) Đặt Sk1 là 2−đơn hình sinh ra bởi hai điểm yL và yR= yωk và Sk2 là 2−đơn hình sinh ra bởi hai điểm yL = yωk và yR; (3.2) Với mỗi i = 1,2, tìm giá trị tối ưu α(Ski ) của bài toán (DP(S(yL,yR))) với S= Ski ; (3.3) Đặt T k+1 = ( T k \{Sk})∪{Sk1,Sk2}; (3.4) Đặt k := k+1 và Chuyển sang Bước lặp k. Bổ đề sau đây có thể coi như một trường hợp đặc biệt của Bổ đề 4.2 [15]. Bổ đề 4.1. Giả sử thuật toán Solve(DPY+) lặp vô hạn và {Sk} là một dãy các 2−đơn hình sinh ra bởi thuật toán, trong đó với mỗi k ∈ {0,1,2 . . .} lược đồ rẽ nhánh rút gọn được áp dụng cho Sk. Khi đó {Sk}có một dãy con {Skq} thỏa mãn lim q Skq = y∗ ∈MinY+. Định lý 4.2. Nếu thuật toán Solve(DPY+) lặp vô hạn thì dãy {yωk} có một điểm tụ là nghiệm tối ưu toàn cục của bài toán (DPY+). Chứng minh. Ký hiệu f∗ là giá trị tối ưu của bài toán (DPY+). Nếu thuật toán không dừng thì nó sinh ra một dãy vô hạn các đơn hình {Sk}, và {yoptk ∈ Sk} là nghiệm tối ưu của bài toán (DP(S(yL,yR))) với S = Sk, trong đó lược đồ rẽ nhánh được áp dụng cho Sk trong mỗi bước lặp k. Hơn nữa, theo Bổ đề 4.1, bằng cách lấy dãy con 105 nếu cần, ta có thể giả thiết limk Sk = y∗ ∈MinY+. Từ đó suy ra yoptk → y∗. Vì dãy cận trên {αk} là đơn điệu và αk = α(Sk) = ϕ(yoptk) nên ta có lim k αk = lim k ϕ(yoptk) = ϕ(y∗)≥ f∗. Vì y∗ ∈MinY+ là nghiệm chấp nhận được của bài toán (DPY+) nên suy ra y∗ là nghiệm tối ưu toàn cục của bài toán (DPY+). 4.2.3 Tính toán thử nghiệm Ví dụ 4.5. Xét bài toán (DP) với h(x) = (x1+ x2−0.4)(x1+4x2+0.2), và XE là tập nghiệm hữu hiệu của bài toán (CBOP), trong đó X = {x ∈ R2 | gi(x)≤ 0, i= 1,2} và f1(x) = x1+ x2, f2(x) = x1+4x2+1, g1(x) = (x1−1)2+4x22−0.2, g2(x) = 3x1−8x2−6. Dễ thấy, hàm h(x) = ϕ( f (x)) trong đó ϕ(y) = (y1−0.4)(y2−0.8) và ϕ đơn điệu tăng trên Y . Bây giờ, ta áp dụng thuật toán Solve(DPY+) để giải bài toán (DPY+). Bước khởi tạo. (0.1) Chọn sai số ε = 0.0001. Giải các bài toán (SP1) và (SP2), ta thu được xˆ1 = (0.599782,−0.099782)T , xˆ2 = (0.799562,0.199890)T , là các nghiệm hữu hiệu tương ứng với các điểm hữu hiệu yˆ1 = (0.500000,1.998910), yˆ2 = (0.999452,1.000000); (0.3) Vì ϕ(yˆ1) = 0.119891 > ϕ(yˆ2) = 0.119890, ta chọn β0 = ϕ(yˆ1) = 0.119891 và ybest = yˆ1,xbest = xˆ1; (0.4) Đặt S0,1 = S(yˆ1, yˆ2). Đặt T 0 := {S0,1} vàU0 := S0,1; 106 (0.5) Giải bài toán (DP(S0,1)), ta được α(S0,1) = 0.244618. Bước lặp k = 0. Bước 1. (1.2) Vì T 0 = {S0,1} nên α0 := α(S0,1) = 0.244618; (1.3) Vì α0−β0 > ε(|β0|+1) nên đặt S0 = S0,1. Bước 2. (2.1) Từ (4.6), ta có yO = (yL1,y R 2 ) = (0.500000,1.000000); (2.2) Giải bài toán (T (yO)), ta thu được nghiệm tối ưu (λ ∗,x∗) = (1.292892,0.575735,0.070711)T ; (2.3) Đặt yω0 = λ ∗yO = (0.646446,1.292892); (2.4) Vì ϕ(yω0) = 0.121471> β0 = 0.119891 nên β1 = 0.121471 và ybest = yω0 = (0.646446,1.292892), xbest = x∗ = (0.575735,0.070711)T . Bước 3. (3.1) Gọi S01 là 2-đơn hình sinh bởi hai điểm y L và yR = yω0, và S02 là 2-đơn hình sinh bởi hai điểm yL = yω0 và yR; (3.2) Giải (DP(S01)) và (DP(S 0 2)), ta nhận được các giá trị tối ưu tương ứng là α(S01) = 0.146536 và α(S 0 2) = 0.146536; (3.3) Ta có T 1 = {S1,1,S1,2}, trong đó S1,1 = S01 và S1,2 = S02; (3.4) Đặt k = 1; Chuyển sang Bước lặp k. Bước lặp k = 1. Bước 1. 107 (1.2) Vì α(S1,1) =max{α(S′) | S′ ∈ T 1}, nên đặt α1 = α(S1,1) = 0.146536, trong đó S1,1 được sinh bởi hai điểm yL = (0.500000,1.998910) và yR = (0.646446,1.292892); (1.3) Vì α1−β1 > ε(|β1|+1), nên đặt S1 = S1,1. Bước 2. (2.1) Từ (4.6), ta có yO = (yL1,y R 2 ) = (0.500000,1.292892); (2.2) Giải bài toán (T (yO)), ta thu được nghiệm tối ưu (λ ∗,x∗) = (1.145344,0.554299,0.018373)T ; (2.3) Đặt yω1 = λ ∗yO = (0.572672,1.480806); (2.4) Vì ϕ(yω1) = 0.117556< β1 = 0.121471 nên không cập nhật cận dưới. Bước 3. (3.1) Gọi S11 là 2-đơn hình sinh bởi hai điểm y L and yR = yω1, và S12 à 2-đơn hình sinh bởi hai điểm yL = yω1 và yR; (3.2) Giải (DP(S11)) và (DP(S 1 2)), ta nhận được các giá trị tối ưu tương ứng là α(S11) = 0.128172 và α(S 1 2) = 0.123256; (3.3) Ta có T 2 = {S2,1,S2,2,S2,3}, trong đó S2,1 = S1,2,S2,2 = S11 và S2,3 = S12; (3.4) Đặt k = 2. Chuyển sang Bước lặp k = 2. Sau 7 bước lặp, ta có β7 = 0.121471,α7 = 0.121560 và α7− β7 < ε(|β7|+ 1). Thuật toán dừng sau 7 bước lặp với nghiệm tối ưu ε−xấp xỉ của bài toán (DPY+) là ybest = (0.646446,1.292892). Đồng thời ta có nghiệm tối ưu của bài toán (DP) tương ứng là xbest =(0.575735,0.070711)T và giá trị tối ưu là ϕ(ybest)= 0.1214710. 108 Ví dụ 4.6. Xét bài toán (DP) được cho dưới dạng sau max ϕ( f (x)) = ( f1(x)−m1)( f2(x)−m2) v.đ.k. x ∈ XE , với mi = min{ fi(x) | x ∈ X}, i = 1,2 và XE là tập nghiệm hữu hiệu của bài toán (CBOP), trong đó fi(x) = xT γ i+ xTDix, i= 1,2, X = {x ∈ Rn | ( −2+ n ∑ j=1 x j j )2 ≤ 100,Ax≤ b,x≥ 0} và các tham số được xác định như sau γ1,γ2 ∈ Rn là các véctơ với các thành phần ngẫu nhiên thuộc đoạn [0,1]. A = (ai j) ∈ Rm×n là một ma trận ngẫu nhiên với các thành phần thuộc đoạn [-1,1]. b= (b1,b2, ...,bm)T là vectơ ngẫu nhiên thỏa mãn bi = n ∑ j=1 ai j+2b0, với b0 là một số thực ngẫu nhiên trong đoạn [0,1]. Di ∈ Rn×n là ma trận đường chéo với các phần tử trên đường chéo nhận giá trị ngẫu nhiên trong đoạn [0,1]. Áp dụng thuật toán Solve(DPY+) cho lớp bài toán này với từng trường hợp của n và m nhằm tìm nghiệm tối ưu ε− xấp xỉ với ε = 0.005 và xác định Gap=UB−LB|LB|+1 vớiUB,LB lần lượt là cận trên và cận dưới ở Bước lặp K cuối cùng, tứcUB= αK và LB= βK , ta thu được Bảng 4.4. Từ bảng kết quả này ta thấy thuật toán thực hiện tốt, thậm chí trong trường hợp bài toán có kích thước lớn. Số bước tính toán khá nhỏ và thời gian chạy từng bước cũng tương đối nhỏ do trong mỗi bước chỉ phải giải một bài toán quy hoạch lồi với hàm mục tiêu tuyến tính và hai bài toán tìm cực đại của đa thức bậc 2. Hơn nữa, nghiệm đạt được cuối cùng là chấp nhận được với độ xấp xỉ nhỏ hơn ε = 0.005. 109 n m ]Inter UB LB Gap 60 40 7 4.103116 4.096561 0.001598 70 50 8 1.865636 1.860822 0.002580 80 80 8 1.137924 1.136717 0.001061 100 60 8 5.153709 5.138920 0.002870 100 80 7 4.169557 4.166498 0.000731 120 120 5 15.94133 15.94088 0.000029 150 100 8 55.40159 55.29604 0.001905 150 120 6 7.587685 7.559456 0.003720 Bảng 4.4: Kết quả tính toán của Ví dụ 4.6 Kết luận Nội dung của Mục 4.1 dựa trên kết quả của các bài báo [2], còn nội dung của Mục 4.2 dựa trên kết quả của bài báo [1] thuộc Danh mục các công trình đã công bố của tác giả có liên quan đến luận án. Chương này đã thực hiện các công việc chính sau: - Phân tích và khai thác tính chất tập giá trị hữu hiệu của bài toán quy hoạch lồi hai mục tiêu (CBOP). - Nghiên cứu và đề xuất một thuật toán nhánh cận Solve(QPY+) giải bài toán (QP) với ϕ là hàm tựa lõm và một thuật toán nhánh cận kết hợp với lược đồ xấp xỉ ngoài Solve(DPY+) giải bài toán (DP) với ϕ là hàm đơn điệu, từ cơ sở lý thuyết đến tính toán thử nghiệm. Bằng việc tận dụng tính chất của tập ảnh hữu hiệu trong không gian hai chiều, hướng tiếp cận này nhiều khả năng cho phép giảm đáng kể chi phí tính toán. 110 Kết luận chung Các đóng góp chính của luận án là: 1. Nghiên cứu bài toán quy hoạch đa mục tiêu lồi suy rộng (GMOP) và đề xuất thuật toán hướng pháp tuyến Solve(GMOP) dựa trên kỹ thuật xấp xỉ ngoài theo tiếp cận trên không gian ảnh để giải bài toán này. • Đề xuất khái niệm hàm véc tơ giả lồi vô hướng, khai thác tính chất hữu dụng của lớp hàm này (Định lý 1.4) cũng như mối liên hệ giữa tập ảnh Y và tập tương đương hữu hiệu Y+ (Mệnh đề 1.7) để thiết lập siêu phẳng cắt tại mỗi bước lặp k của thuật toán. Cụ thể, siêu phẳng này có véc tơ pháp tuyến là hướng pháp tuyến không âm của một điểm giá trị hữu hiệu được sinh ra tại bước lặp k (Định lý 2.1 và Mệnh đề 1.9). • Với một sai số ε ≥ 0 cho trước, thuật toán cho phép xác định tập tất cả các điểm giá trị hữu hiệu yếu θ - xấp xỉ và tập nghiệm hữu hiệu yếu θ - xấp xỉ của bài toán (GMOP), trong đó θ = εe với e ∈ Rp là véc tơ có tất cả các thành phần đều bằng 1. Đặc biệt, khi sử dụng thuật toán này giải bài toán quy hoạch đa mục tiêu tuyến tính, ta nhận được tập giá trị hữu hiệu yếu YWE và tập nghiệm hữu hiệu yếu XWE sau hữu hạn bước lặp với sai số ε = 0. Các tính toán thử nghiệm đã chứng tỏ tính hữu hiệu và ưu việt của thuật toán. • Thuật toán được chứng minh là hội tụ (Định lý 2.2, Định lý 2.3 và Hệ quả 2.1). Đây có thể coi là một đóng góp của luận án về mặt lý thuyết vì vấn đề "sự hội tụ của thuật toán" vẫn là câu hỏi mở cho một số thuật toán xấp xỉ ngoài trên không gian ảnh giải bài toán quy hoạch đa mục tiêu lồi mới đề xuất trong khoảng vài năm gần đây. 2. Xây dựng thuật toán xấp xỉ ngoài Solve(GMPY ) trên không gian ảnh giải bài toán quy hoạch tích lồi suy rộng (GMP) dựa trên mối quan hệ của bài toán này với bài toán quy hoạch đa mục tiêu lồi suy rộng tương ứng. Đây là một ứng dụng trực tiếp của thuật toán hướng pháp tuyến giải bài toán quy hoạch 111 đa mục tiêu lồi suy rộng (GMOP). Tính hội tụ của thuật toán được chỉ ra ở Định lý 3.1. 3. Nghiên cứu bài toán (GIMP) cực đại một hàm mục tiêu là tổng của một hàm lõm với tích p≥ 2 hàm lõm trên tập chấp nhận được là tập lồi compact khác rỗng, đưa việc giải bài toán này về giải bài toán (EPY−) cực đại một hàm liên tục, đơn điệu tăng trên tập điểm hữu hiệu yếu của một tập lồi có thứ nguyên đầy đủ trong R2. Thuật toán nhánh cận Solve(EPY−) giải bài toán (EPY−) được xây dựng dựa trên cấu trúc đặc biệt của tập điểm hữu hiệu và được chứng minh là hội tụ (Định lý 3.2). Các kết quả tính toán thử nghiệm cho thấy thuật toán có thể giải các bài toán có số biến lớn. 4. Đề xuất hai thuật toán trên không gian ảnh để giải hai bài toán tối ưu hàmmục tiêu có dạng h(x) = ϕ( f (x)) trên tập nghiệm hữu hiệu XE của bài toán quy hoạch hai mục tiêu lồi (CBOP), trong đó hàm véc tơ lồi f (x) = ( f1(x), f2(x)) là hàm mục tiêu của bài toán (CBOP), dựa trên cấu trúc đặc biệt của tập giá trị hữu hiệu YE = f (XE) và tính đặc thù của hàm ϕ: • Thuật toán nhánh cận giải bài toán cực tiểu hàm h(x) = ϕ( f (x)) trên XE , trong đó ϕ : R2→ R là hàm tựa lõm (Thuật toán Solve(QPY+)); • Thuật toán nhánh cận kết hợp xấp xỉ ngoài giải bài toán cực đại hàm h(x) = ϕ( f (x)) trên XE , trong đó ϕ : R2→ R là đơn điệu tăng (Thuật toán Solve(DPY+)). Cả hai thuật toán này đều được chứng minh là hội tụ (Định lý 4.1 và Định lý 4.2). Tính toán thử nghiệm với nhiều bài toán khác nhau cho thấy thuật toán xây dựng theo hướng tiếp cận trên không gian ảnh cho phép giảm đáng kể chi phí tính toán. Một số vấn đề có thể tiếp tục nghiên cứu: 1. Sử dụng phương pháp hướng pháp tuyến trên không gian ảnh để giải các lớp bài toán tối ưu khác như bài toán quy hoạch lõm, bài toán tối ưu trên tập nghiệm hữu hiệu, bài toán quy hoạch toàn phương, bài toán tối ưu với ràng buộc không lồi,... 112 2. Đề xuất thuật toán giải các lớp bài toán quy hoạch tích mở rộng khác nảy sinh từ các vấn đề thực tế trong lĩnh vực kinh tế, viễn thông, công nghiệp,... 3. Mở rộng các thuật toán giải hai bài toán tối ưu trên tập nghiệm hữu hiệu được trình bày ở Chương 4 cho trường hợp bài toán quy hoạch đa mục tiêu có số mục tiêu lớn hơn 2. 4. Nghiên cứu và đề xuất thuật toán hiệu quả giải các lớp bài toán quy hoạch đa mục tiêu lồi suy rộng khác, trong đó các hàm mục tiêu có thể là hàm tựa lồi, hàm phân thức hoặc hàm đa thức,... 5. Nghiên cứu và xây dựng thuật toán giải bài toán tối ưu đa mục tiêu rời rạc với các biến là số nguyên. 6. Ứng dụng các thuật toán đã đề xuất vào việc giải các bài toán nảy sinh trong thực tế, chẳng hạn bài toán tối ưu danh mục đầu tư, bài toán tối ưu hóa sản xuất, bài toán luồng cực đại trong mạng, bài toán xử lý ảnh,... 113 Danh mục các công trình đã công bố của luận án 1. Nguyen Thi Bach Kim, Tran Ngoc Thang (2013), Optimization over the ef- ficient set of a bicriteria convex programming problem, Pac. J. Optim., 9(1), 103-115. (ISI) 2. Tran Ngoc Thang (2015), Outcome-based branch and bound algorithm for optimization over the efficient set and its application, Adv. Int. Syst. Comput., Springer Publishing Switzerland, 341, 31-47 (SCOPUS). 3. Tran Ngoc Thang, Nguyen Thi Bach Kim (2016), Outcome space algorithm for generalized multiplicative problems and optimization over the efficient set1, J. Ind. Manag. Optim., 12(4), 1417 - 1433. (ISI) 4. Tran Ngoc Thang, Dinh The Luc, Nguyen Thi Bach Kim (2016), Solving gen- eralized convex multiobjective programming problems by a normal direction method, Optimization, 65(12), 2269-2292. (ISI) 1Thuộc danh sách các công trình được thưởng năm 2016 của Chương trình Trọng điểm Quốc gia phát triển Toán học giai đoạn 2010 - 2020. 114 Danh mục tài liệu tham khảo Tiếng Việt 1. Lê Dũng Mưu, Nguyễn Văn Hiền (2009), Nhập môn giải tích lồi ứng dụng, NXB Khoa học tự nhiên và Công nghệ, Hà Nội. 2. Nguyễn Thị Bạch Kim (2014), Giáo trình các phương pháp tối ưu: Lý thuyết và thuật toán, NXB Bách Khoa, Hà Nội. 3. Trần Vũ Thiệu, Nguyễn Thị Thu Thủy (2011), Giáo trình tối ưu phi tuyến, NXB Đại học Quốc gia, Hà Nội. Tiếng Anh 4. An L.T.H., Tao P.D., Muu L.D. (1996), Numerical solution for optimization over the efficient set by d.c. optimization algorithm,Oper. Res. Lett., 19, 117- 128. 5. An L.T.H., Tao P.D., Nam N.C., Muu L.D. (2010), Method for optimizing over efficient and weakly efficient the sets of an affine fractional vector opti- mization program, Optimization, 59(1), 77-93. 6. Ashtiani A.M.M., Ferreira P.A.V. (2011), On the solution of generalized mul- tiplicative extremum problems, J. Optim. Theory Appl., 149, 411-419. 7. Armand P., Malivert C. (1991), Determination of the efficient set in multiob- jective linear programming, J. Optim. Theory Appl., 70, 467 - 489. 8. Avriel M., Diewert W.E., Schaible S., Zang I. (1988), Generalized concavity, Plenum Press, New York. 9. Benoist J. (2001), Contractibility of the efficient set in strictly quasiconcave vector maximization, J. Optim. Theory Appl., 110, 325-336. 10. Benson H.P. (1991), An all-linear programming relaxation algorithm for op- timization over the efficient set, J. Global Optim., 1, 83 - 104. 115 11. Benson H.P. (1998), An outer approximation algorithm for generating all ef- ficient extreme points in the outcome set of a multiple objective linear pro- gramming problem, J. Global Optim., 13, 1-24. 12. Benson H.P. (1999), An outcome space branch and bound-outer approxima- tion algorithm for convex multiplicative programming, J. Global Optim., 15, 315-342. 13. Benson H.P. (2004), On the global optimization of sums of linear fractional functions over a convex set, J. Optim. Theory Appl., 121(1), 19–39. 14. Benson H.P. (2008), Global maximization of a generalized concave multi- plicative function, J. Optim. Theory Appl., 137, 105-120. 15. Benson H.P. (2010), Simplicial branch-and-reduce algorithm for convex pro- grams with a multiplicative constraint, J. Optim. Theory Appl., 145, 213-233. 16. Benson H.P. (2012), An outcome space algorithm for optimization over the weakly efficient set of a multiple objective nonlinear programming problem, J. Global Optim., 52, 553-574. 17. Benson H.P., Boger G.M. (1997), Multiplicative programming problems: Anal- ysis and efficient point search heuristic, J. Optim. Theory Appl., 94, 487-510. 18. Benson H.P., Boger G.M. (2000), Outcome-space cutting-plane algorithm for linear multiplicative programming, J. Optim. Theory Appl., 104, 301-322. 19. Benson H.P., Sayin S. (1994), Optimization over the efficient set: four special case, J. Optim. Theory Appl., 80, 3-18. 20. Ben-Tal A. (1980), Characterization of Pareto and lexicographic optimal so- lutions, Lecture Notes in Eco. and Math. Sys., Springer-Verlag, Berlin, Hei- delberg, 177, 1-11. 21. Cantor G. (1897), Contributions to the foundation of transfinite set theory, Math. Ann., 49, 207–246. 116 22. Chen P.C., Hansen P., Jaumard B. (1991), On-line and off-line vertex enu- meration by adjacency lists, Oper. Res. Lett., 10, 403-409. 23. Cohon J.L. (1978), Multiobjective programming and planning, New York, Academic Press. 24. Dan N.D., Muu L.D. (1996), Parametric simplex method for optimizing a linear function over the efficient set of a bicriteria linear problem, Acta Math. Vietnam., 21, 59-67. 25. Das I., Dennis J.E. (1998), Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization prob- lems, SIAM J. Optim., 8, 631-657. 26. Dauer J.P., Fosnaugh T.A. (1995), Optimization over the eficient set, J. Global Optim., 7, 261-277. 27. Dauer J.P., Liu Y.H. (1990), Solving multiple objective linear programs in objective space, Eur. J. Oper. Res., 46, 350–357. 28. Dauer J.P., Gallagher R.J. (1996), A combined constraint-space, objective- space approach for determining high-dimensional maximal efficient faces of multiple objective linear programs, Eur. J. Oper. Res., 88, 368-381. 29. Ehrgott M., Lo¨hne A., Shao L. (2012), A dual variant of Benson’s “outer ap- proximation algorithm” for multiple objective linear programming, J. Global Optim., 52(4), 757–778. 30. Ehrgott M., Shao L., Schobel A. (2011), An approximation algorithm for convex multi-objective programming problems, J. Global Optim., 50, 397- 416. 31. Fulop J., Muu L.D. (2000), Branch-and-bound variant of an outcome-based algorithm for optimizing over the efficient set of a bicriteria linear program- ming problem, J. Optim. Theory Appl., 105, 37-54. 117 32. Gao Y., Wu G., Ma W. (2010), A new global optimization approach for con- vex multiplicative programming, Appl. Math. Comput., 216, 1206-1218. 33. Gourion D., Luc D.T. (2008), Generating the weakly efficient set of noncon- vex multiobjective problems, J. Global Optim., 41, 517-538. 34. Gourion D., Luc D.T. (2010), Finding efficient solutions by free disposal outer approximation, SIAM J. Optim., 20, 2939-2958. 35. Greenberg H.J., Pierskalla W.P. (1971), A review of quasi-convex functions, Oper. Res., 19, 1553–1570. 36. Haimes Y.Y., Lasdon L.S., Wismer D.A. (1971), On a bicriterion formulation of the problems of integrated system identification and system optimization, IEEE Trans. Syst. Man Cyber., 1 ,296-297. 37. Hausdorff F. (1906), Investigations concerning order types, Math. Physic. Class., 58, 106-169. 38. Horst R., Thoai N.V. (1997), Utility function programs and optimization over the efficient set in multiple-objective decision making, J. Optim. The- ory Appl., 92 , 605-631. 39. Horst R., Thoai N.V., Yamamoto Y., Zenke D. (2007), On optimization over the efficient set in linear multicriteria programming, J. Optim. Theory Appl., 134, 433-443. 40. Huy N.Q. (2003), Topology of the efficient sets of convex sets inR2, Vietnam J. Math., 31(1), 45-55. 41. Jaumard B., Meyer C., Tuy H. (1997), Generalized convex multiplicative pro- gramming via quasiconcave minimization, J. Global Optim., 10, 229-256. 42. Kim N.T.B. (2000), An algorithm for optimizing over the efficient set, Viet- nam J. Math., 28, 329-340. 43. Kim N.T.B. (2007), Finite algorithm for minimizing the product of two linear functions over a polyhedron, J. Ind. Manag. Optim., 3(3), 481-487. 118 44. Kim N.T.B., Luc D.T. (2000), Normal cone to a polyhedral convex set and generating efficient faces in linear multi-objective programming, Acta Math. Vietnam., 25(1), 101-124. 45. Kim N.T.B., Luc D.T. (2002), Normal cone method in solving linear multi- objective problem, J. Stat. Manag. Sys., 5, 341 - 358. 46. Kim N.T.B., Nam N.C., Thuy L.Q. (2013), An outcome space algorithm for minimizing the product of two convex functions over a convex set, J. Ind. Manag. Optim., 9(1), 243-253. 47. Kim N.T.B., Muu L.D. (2002), On the projection of the efficient set and po- tential application, Optimization, 51, 401-421. 48. Kim N.T.B., Trang N.T.L., Yen T.T.H. (2007), Outcome-space outer approxi- mation algorithm for linear multiplicative programming, East West J. Math., 9, 81-98. 49. Kim N.T.B., Thuy L.Q. (2010), An algorithm for generating efficient out- come points for convex multiobjective programming problem, Lecture Notes in Comp. Sci., 5991, 390-399. 50. Klamroth K., Tind J., Wiecek M.M. (2002), Unbiased approximation in mul- ticriteria optimization, Math. Meth. Oper. Res., 56, 413-457. 51. Konno H. and Kuno T. (1990), Generalized linear multiplicative and frac- tional programming, Ann. Oper. Res., 25, 147-162. 52. Konno H., Kuno T. (1992), Linear multiplicative programming, Math. Pro- gram., 56, 51-64. 53. Kuno T. (2001), A finite branch-and-bound algorithm for linear multiplica- tive programming, Comput. Optim. Appl., 20, 119-135. 54. Kuno T., Yajima Y., Konno H. (1993), An outer approximation method for minimizing the product of several convex functions on a convex set, J. Global Optim., 3, 325-335. 119 55. Lohne A., Rudloff B., Ulus F. (2014), Primal and dual approximation algo- rithms for convex vector optimization problems, J. Global Optim., 60, 713- 736. 56. Luc D.T. (1987), Connectedness of the efficient point sets in quasiconcave vector maximization, J. Optim. Theory Appl., 122, 346-354. 57. Luc D.T. (1989), Theory of vector optimization, Lecture Notes in Econom. and Math. Systems, 319, Springer-Verlag, Germany. 58. Luc D.T. (2005), Generalized convexity in vector optimization, Handbook of Generalized Convexity and Generalized Monotonicity, Springer, New York, 195–236. 59. Luc D.T. (2016),Multiobjective Linear Programming, Springer, Switzerland. 60. Luc L.T., Muu L.D. (1997), Global optimization approach to optimization over the efficient set, Lecture Notes in Econom. and Math. Systems, 452, Springer-Verlag, Berlin, Germany, 213-221. 61. Luc D.T., Phong T.Q., Volle M. (2005), Scalarizing functions for generating the weakly efficient solution set in convex multiobjective problems, SIAM J. Optim., 15, 987-1001. 62. Luc D.T., Phong T.Q., Volle M. (2006), A new duality approach to solving concave vector maximization problems, J. Global Optim., 36, 401-423. 63. Matsui T. (1996), NP-hardness of linear multiplicative programming and re- lated problems, J. Global Optim., 9, 113-119. 64. Marler R., Arora J. (2004), Survey of multi-objective optimization methods for engineering, Struct. Multi. Optim., 26(6), 369–395. 65. Miettinen K. (1999), Nonlinear Multiobjective Optimization, Kluwer Aca- demic Publishers, Boston. 66. Mangasarian O.L. (1969),Nonlinear Programming, McGraw-Hill, NewYork. 120 67. Muu L.D. (2000), A convex-concave programming method for optimizing over the efficient set, Acta Math. Vietnam., 25, 67-85. 68. Muu L.D., Tam B.T. (1992), Minimizing the sum of a convex function and the product of two affine functions over a convex set, Optimization, 24, 57-62. 69. Muu L.D., Thuy L.Q. (2011), Smooth optimization algorithms for optimizing over the Pareto efficient set and their application to minmax flow problems, Vietnam J. Math., 39(1), 31-48. 70. Muu L.D., Tuyen H.Q. (2002), Bilinear programming approach to optimiza- tion over the efficient set of a vector affine fractional problem, Acta Math. Vietnam., 27, 119 - 139. 71. Oliveira R.M., Ferreira P.A.V. (2008), A convex analysis approach for convex multiplicative programming, J. Global Optim., 41, 579-592. 72. Payne A.N., Polak E., Collins D.C., Meisel W.S. (1975), An algorithm for bicriteria optimization based on the sensitivity function, IEEE Trans. Autom. Control, 20, 546 - 548. 73. Philip J. (1972), Algorithms for the vector maximization problem,Math. Pro- gram., 2, 207-229. 74. Phu H.X. (2005), On Efficient Sets in R2, Vietnam J. Math., 33(4), 463–468. 75. Polak E. (1976), On the approximation of solutions to multiple-criteria de- cision making problems, Lecture Notes in Econom. and Math. Systems, 123, Springer, 271- 282 76. Rockafellar R.T. (1970), Convex analysis, Princeton University Press, Prince- ton, New Jersey. 77. Rockafellar R.T., Wets R.B. (2010), Variational Analysis, Springer-Verlag, Berlin, Germany. 78. Ruzika S., Wiecek M.M. (2005), Approximation methods in multiobjective programming, J. Optim. Theory Appl., 126, 473-501. 121 79. Sach P.H. (1999), Characterization of scalar quasiconvexity and convexity of locally lipschitz vector-valued maps, Optimization, 46, 283-310. 80. Schaible S., Sodini C. (1995), Finite algorithm for generalized linear multi- plicative programming, J. Optim. Theory Appl., 87, 441-455. 81. Shao L., Ehrgott M. (2014), An objective space cut and bound algorithm for convex multiplicative programmes, J. Global Optim., 58, 711-728. 82. Shao L., Ehrgott M. (2016), Primal and dual multi-objective linear program- ming algorithms for linear multiplicative programmes, Optimization, 65(2), 415-431. 83. Steuer R.E. (1986) Multiple criteria optimization: Theory, computation and application, Wiley, New York. 84. Thang T.N., Kim N.T.B., Hung D.X. (2017), An outcome-space normal cone method for generalized concave multiplicative problems, Pac. J. Optim., (đã nhận đăng). 85. Thieu T.V., Tam B.T., Ban V.T. (1983), An outer approximation method for globally minimizing a concave function over a compact convex set, Acta Math. Vietnam., 8, 21-40. 86. Thoai N.V. (1991), A global optimization approach for solving the convex multiplicative programming problem, J. Optim. Theory Appl., 1, 341-357. 87. Thoai N.V. (2000) , A class of optimization problems over the efficient set of a multiple criteria nonlinear programming problem, Eur. J. Oper. Res., 122, 58-68. 88. Thoai N.V. (2010), Reverse convex programming approach in the space of extreme criteria for optimization over efficient sets, J. Optim. Theory and Appl., 147, 263-277. 89. Tuy H. (1998), Convex analysis and global optimization, Kluwer Academic Publishers. 122 90. Tuy H., Nghia N.D. (2003), Reverse polyblock approximation for generalized multiplicative/fractional programming, Vietnam J. Math., 31(4), 391-402. 91. Yamamoto Y. (2002), Optimization over the efficient set: overview, J. Global Optim., 22, 285-317. 92. Wiecek M.M., Ehrgott M., Engau A. (2016), Continuous multiobjective pro- gramming,Multiple criteria decision analysis: State of the art surveys, Oper. Res. Manag. Sci., Springer, New York, 233, 739-815 93. Yu P.L. (1985),Multiple-criteria decision making: Concepts, techniques and extensions, Plenum Press, New York. 94. Zeleny M. (1982), Multiple criteria decision making, New York, McGraw Hill. 123 Danh mục thuật ngữ 2-đơn hình, 70, 88 bài toán (CBMP), 93 (CBOP), 83, 93 (CMOP), 17 (CMP), 56, 57 (DP), 85 (DPY+), 85, 98 (GIMP), 55 (GMOP), 17 (GMP), 55, 57 (LMOP), 17 (LMP), 56 (P(v)), 16 (QP), 85 (QPY+), 85 (SPi), 84 (P(vk)), 24 (PM(i)), 15 (Pm(i)), 15 (IPi), 68 (DP(S(yL,yR))), 103 (EPY−), 66 (GIMPY ), 65 (GIMP), 64 (P1sub), 69 (P2sub), 72 (Pro(z∗)), 68 (RP(E )), 71 (SP(E )), 69 (T (yO)), 100 nới lỏng, 71, 88 tối ưu một biến, 72 trên tập nghiệm hữu hiệu, x, 83 cấu trúc tập điểm hữu hiệu, 67 tập ảnh hữu hiệu, 18 cận dưới tốt nhất hiện tại, 58 trên tốt nhất hiện tại, 59 đồng phôi, 13, 84 đơn hình, 32 đường cong hữu hiệu, 84 liên thông, 67 điều kiện Slater, 8, 21, 26, 55 tối ưu, 11 điểm 124 ảnh hữu hiệu, 18 hữu hiệu yếu, 18 chia đôi, 74, 87, 101 dừng, 4, 5 giá trị hữu hiệu, 18 hữu hiệu yếu, 18, 27 hữu hiệu yếu θ− xấp xỉ, 22 hữu hiệu, 9 θ -xấp xỉ, 10 hữu hiệu yếu, 9 θ− xấp xỉ ngoài, 28 KKT, 4 lý tưởng, 15, 83 tụ, 77, 92 đoạn cong hữu hiệu, 86 hình chiếu, 33, 68 hàm đơn điệu tăng, 99 afin, 3 giả lồi, 4 giả lõm, 4 lồi, 2 lồi suy rộng, 2 lõm, 2 phân thức, 3 tựa lồi, 2 tựa lõm, 2 hàm véc tơ giả lồi, 6 giả lồi vô hướng, 6, 21, 55 lồi, 6 tựa lồi, 6, 21 tuyến tính, 6 hướng pháp tuyến, 10 dương, 11, 86 không âm, 11 không gian ảnh, ix giá trị, ix quyết định, viii khoảng cách Hausdorff, 33 lược đồ rẽ nhánh, 101 liên thông, 17, 18 đường, 17, 18 đường gấp khúc, 13 nón pháp tuyến, 11, 27 nửa không gian tựa, 11 nghiệm chấp nhận được tốt nhất hiện tại, 59 hữu hiệu, 18 θ− xấp xỉ, 19 hữu hiệu yếu, 18 θ− xấp xỉ, 19 tối ưu địa phương, 4 toàn cục, 4, 57, 77 xấp xỉ, 90, 102 ε- xấp xỉ, 58 125 phân hoạch, 73 phân phối của các điểm ảnh hữu hiệu, 48 phương pháp hướng pháp tuyến, 23 liệt kê các đỉnh, 33 xấp xỉ ngoài, ix, 57 quy hoạch đa mục tiêu, viii lồi, viii, 1, 17, 21 lồi suy rộng, 1, 17, 21 tuyến tính, viii, 17, 21 hai mục tiêu lồi, 83 lồi, 68, 100 tích lồi, xi, 56 lồi suy rộng, 55 lõm mở rộng, 64 tuyến tính, xi, 56 tối ưu đa mục tiêu, viii véc tơ, viii, 1 tập ảnh, 18 hữu hiệu, 18 hữu hiệu yếu, 18 chỉ số của các ràng buộc thỏa mãn chặt, 8, 25 giá trị, 18 hữu hiệu, 22 mức dưới, 2 trên, 2 nghiệm hữu hiệu, 18, 19 hữu hiệu xấp xỉ, 19 hữu hiệu yếu, 18, 19, 22 hữu hiệu yếu xấp xỉ, 19 tương đương hữu hiệu, 14 thứ tự từng phần, 9 thủ tục Solve(SP(yL,yR)), 89 Solve(SP(E )), 72 thuật toán hướng pháp tuyến, 22, 23, 27 nhánh cận, 74, 90 nhánh cận - xấp xỉ ngoài, 101 Solve(DPY+), 103 Solve(EPY−), 74 Solve(QPY+), 90 Solve(GMPY ), 59 Solve(GMOP), 29 tiếp cận xấp xỉ, 19 tiêu chí dừng, 48 véc tơ pháp tuyến, 11, 86 126