Một số khái niệm và tính chất cơ bản
Trong bài viết này, R[x] được định nghĩa là vành của các đa thức thực với n biến, trong đó x = (x1, , xn) thuộc R^n Tập hợp N* đại diện cho các số tự nhiên dương, trong khi R+ là tập hợp các số thực không âm Đối với mỗi đa thức f thuộc R[x], chúng ta ký hiệu bậc của f là deg f Đối với ma trận vuông A, chúng ta sẽ sử dụng ký hiệu thích hợp để diễn đạt các khái niệm liên quan.
A 0 và A 0 tương ứng để chỉ A là ma trận xác định dương và A là ma trận nửa xác định dương Với Ω ⊂R n , đặt coneΩ :( k X i=1 t i x i |t i ≥ 0, x i ∈ Ω, i = 1, , k, k ∈ N
(i) Ta nói đa thức f ∈ R[x] là tổng các bình phương (SOS) nếu tồn tại m ∈ N ∗ và f i ∈ R[x], i = 1, , m, sao cho f = f 1 2 + +f m 2 Tập tất cả các SOS đa thức trong R[x] được ký hiệu là Σ 2 [x].
M(g 1 , , g r ) := {σ 0 +σ 1 g 1 + +σ r g r |σ j ∈ Σ 2 [x], j = 0,1, , r}, cùng với phép toán trên R[x], là mô-đun toàn phương sinh bởi g1, , gr. (iii) M(g1, , gr) là Archimedean nếu tồn tại h ∈ M(g1, , gr) sao cho tập hợp {x ∈ R n |h(x) ≥0} là compact.
1.1.2 Mệnh đề (xem [1]) Cho g j ∈ R[x], j = 1, , r, thỏa mãn
M(g 1 , , g r ) là Archimedean Khi đó, tập
Tập K := {x ∈ R n |g j (x) ≥ 0, j = 1, , r} được gọi là một tập nửa đại số cơ bản, trong đó g 1, , g r ∈ R[x] Việc biểu diễn đa thức dương trên tập nửa đại số cơ bản là một bài toán quan trọng trong hình học nửa đại số thực, với nhiều ứng dụng trong tối ưu đa thức.
Trong phần sau, chúng ta cần định lý biểu diễn đa thức dương sau:
1.1.4 Bổ đề (Định lý biểu diễn dương Putinar [10]) Cho f, gj ∈ R[x], j = 1, , r, thỏa mãn M(g 1 , , g r ) là Archimedean Đặt
Khi đó, nếu f(x) > 0 với mọi x ∈ K, thì f ∈ M(g 1 , , g r ).
Tiếp theo là một số khái niệm liên quan đến bài toán tối ưu đa thức hai cấp không chắc chắn Xét bài toán tối ưu:
, (1.1) ở đây f : R m ×R n → R là một đa thức và Y(x,ˆa1,ˆb1, ,ˆaq,ˆbq) là tập nghiệm của bài toán tối ưu: z∈minR n n c T 0 x+d T 0 z|c T j x+ ˆa T j z ≤ˆb j , j = 1, , q o
Tại thời điểm giải (P), giả sử rằng các thông số f, c 0, d 0, c j (với j = 1, , q) được biết chính xác, trong khi các biến (˜a i, ˜b i, c˜ i) (với i = 1, , l) và (ˆa j, ˆb j) (với j = 1, , q) lại có sự không chắc chắn và chỉ có thể biến thiên trong những tập hợp đã được xác định trước: (˜ai, ˜bi, ˜ci) thuộc U˜i, với U˜i nằm trong R m × R n × R, cho i = 1, , l, và (ˆaj, ˆbj) thuộc Uˆj, với Uˆj nằm trong R n × R, cho j = 1, , q.
1.1.5 Định nghĩa (i) Các tập U˜ i và Uˆ j , i = 1, , l, j = 1, , q, được gọi là các tập không chắc chắn (uncertain set).
(ii) Bài toán (1.1) và (1.2) tương ứng được gọi là bài toán cấp cao (cấp trên) và bài toán cấp thấp (cấp dưới).
(iii) Hàm f và hàm z 7→ g x (z) := c T 0 x +d T 0 z tương ứng được gọi là hàm mục tiêu của bài toán cấp cao và hàm mục tiêu của bài toán cấp thấp.
(iv) Ta gọi x là biến quyết định của bài toán cấp cao, trong khi z là biến quyết định của bài toán cấp thấp.
(v) Bài toán (P) được gọi là một bài toán tối ưu đa thức hai cấp với ràng buộc tuyến tính không chắc chắn.
Trong quá trình ra quyết định, người ra quyết định cấp cao thường đưa ra quyết định trước, sau đó cấp thấp sẽ dựa vào đó để đưa ra quyết định của mình Cụ thể, người cấp cao quyết định x, và từ đó, cấp dưới giải bài toán tối ưu để trả lại kết quả y = y(x) Nếu cấp dưới không hợp tác, họ có thể chọn phương án làm tăng hàm mục tiêu của cấp trên, tạo ra tình huống không mong đợi Ngược lại, nếu cấp dưới hợp tác, họ sẽ chọn phương án tối ưu nhất cho cấp trên Từ góc nhìn của cấp trên, nếu họ lạc quan, họ sẽ tin rằng cấp dưới sẽ hợp tác, trong khi nếu bi quan, họ sẽ nghĩ ngược lại Do đó, bài toán (P) được xem là bài toán tối ưu hai cấp lạc quan.
Trong luận văn này, các tập không chắc chắn được giả định là các tập lồi compact, và những cấu trúc đặc biệt của chúng sẽ được trình bày trong các phần tiếp theo.
Phiên bản vững của bài toán tối ưu không chắc chắn (P) được ký hiệu là (1.3) Nghiệm tối ưu toàn cục của phiên bản này, ký hiệu là (RP), được gọi là nghiệm tối ưu vững (toàn cục) của bài toán (P).
(iii) Nếu (¯x,y)¯ là một nghiệm tối ưu vững của (P) thì f(¯x,y)¯ được gọi là giá trị tối ưu vững (toàn cục) của (P).
được gọi là miền chấp nhận được vững của (P) Mỗi (x, y) ∈ F R được gọi là một nghiệm chấp nhận được vững của (P).
1.1.9 Chú ý Trong phần sau, chúng ta giả thiết miền chấp nhận được vững F R của bài toán (P) là khác rỗng.
Bổ để Farkas suy rộng
Mục này trình bày bổ đề Farkas suy rộng và đặc trưng nghiệm vững của một lớp quy hoạch tuyến tính với ràng buộc không chắc chắn.
1.2.1 Định nghĩa Cho s1, s2, , sm là các phần tử trong R n Ta nói rằng{s j |j = 1, , m}là một hệ phụ thuộc tuyến tính dương nếu tồn tại α = (α1, , αm) ∈ R m + \{0} sao cho m
P j=1 αjsj = 0 Nếu {s j |j = 1, , m} là không phụ thuộc tuyến tính dương, thì ta nói {s j |j = 1, , m} là độc lập tuyến tính dương.
P i=1 α i v i ở đây v i ∈ R n với mọi i, {v i } m i=1 là độc lập tuyến tính và α i 6= 0 với mọi i = m + 1, , m + p. Khi đó, tồn tại J ⊂ {m+ 1, , m+p} và α¯ i ∈ R với i ∈ {1, , m} ∪J, sao cho x = P i∈{1, ,m}∪J ¯ α i v i , α i α¯ i > 0 với mọi i ∈ J, và {v i }i∈{1, ,m}∪J là độc lập tuyến tính.
1.2.3 Bổ đề ([7, Theorem 4.3.3, p 130]) Cho s 1 , s 2 , , s m là các phần tử trong R n Khi đó, nón lồi
Chứng minh Lấy {x k } ⊂ K thỏa mãn x k → x¯ ∈ R n Ta cần chứng minh x¯∈ K Vì x k ∈ K nên tồn tại α k j ≥ 0, j = 1, , m, sao cho x k m
X j=1 α k j s j (1.4) Đặt α k := (α k 1 , , α k m ) Xét hai trường hợp sau:
Trong trường hợp 1, tập hợp {s j |j = 1, , m} có tính độc lập tuyến tính dương, dẫn đến dãy {α k } là bị chặn Nếu giả định này không đúng, chúng ta có thể chọn một dãy con sao cho kα k k tiến tới vô cùng và kα k k −1 α k hội tụ về một vector α = (α 1 , , α m ) thuộc R m + \{0} Bằng cách chia hai vế của phương trình (1.4) cho kα k k và lấy giới hạn khi k tiến tới vô cùng, ta có được kết quả cần thiết.
X j=1 α j s j = 0 và (α 1 , , α m ) ∈ R m + \{0}. Điều này mâu thuẫn với hệ {s j |j = 1, , m} độc lập tuyến tính dương.
Do đó, dãy {α k} là bị chặn, và bằng cách sử dụng một dãy con, chúng ta có thể giả định rằng α k tiến tới α¯ = ( ¯α 1 , , α¯ m ) thuộc R m + Khi lấy giới hạn của hai vế trong (1.4) khi k tiến tới vô cực, ta thu được x¯ m.
Trong trường hợp 2, các vectơ {s j | j = 1, , m} phụ thuộc tuyến tính dương Theo Bổ đề 1.2.2, với mỗi k ∈ N ∗, tồn tại một tập con Jk ⊂ {1, , m} và các hệ số α˜ k ∈ R + sao cho x k = P j∈J k ˜ α k j sj, và tập {s j} j∈J k là độc lập tuyến tính dương Vì tập {1, , m} chỉ có hữu hạn tập con, ta có thể giả sử J k = J ⊂ {1, , m} với mọi k ∈ N ∗ bằng cách lấy dãy con nếu cần thiết.
Như vậy, x k = P j∈J ˜ α k j s j → x¯ và {s j } j∈J là độc lập tuyến tính dương. Theo Trường hợp 1, ta có x¯∈ cone{s j |j ∈ J} ⊂ K.
Kết quả tiếp theo là một dạng suy rộng của bổ đề Farkas.
1.2.4 Định lý ([7, Theorem 4.3.4, p 131]) Cho J là một tập chỉ số bất kỳ, (b, r) ∈ R n ×R và (sj, pj) ∈ R n ×R với mọi j ∈ J Giả sử hệ (1.5) (ẩn x ∈ R n ) có nghiệm: s T j x ≤ pj, j ∈ J (1.5)
Khi đó, hai mệnh đề sau là tương đương:
Chứng minh [(ii) ⇒ (i)]: Trước hết, lấy bất kỳ (b, r) ∈ K := coneS. Khi đó, tồn tại tập hữu hạn I ⊂ J và α 0 , α i ∈ R + , i ∈ I, sao cho
= 0 Do đó, với mỗi x thỏa mãn (1.5), ta có b T x = P i∈I αis T i x ≤ P i∈I αipi
Như vậy, với mỗi (b, r) ∈ K và mỗi x thỏa mãn (1.5), ta có b T x ≤r (1.6)
Giả sử (b, r) ∈ clK, tồn tại (bk, rk) ∈ K sao cho (bk, rk) → (b, r) Với bất kỳ x thỏa mãn (1.5), theo 1.6, ta có b T k x ≤ rk Khi k → ∞, ta suy ra b T x ≤ r, chứng minh rằng điều kiện (i) được thỏa mãn Nếu (i) đúng nhưng (b, r) ∉ clK, theo định lý tách các tập lồi, tồn tại (d,−t) ∈ R n × R sao cho κ := sup.
[hs, di −pt] < hb, di −rt (1.7)
Vì K là một nón chứa 0 nên từ (1.7) ta suy ra κ = 0 Do đó, t ≥ 0, hb, di −rt > 0 và hs j , di −p j t ≤ 0 với mọi j ∈ J (1.8)
Trường hợp 1: t >0.Đặtx = d/t.Từ (1.8) ta suy raxthỏa mãn (1.5) và b T x > r Điều này mâu thuẫn với giả thiết (i) đúng.
Trong trường hợp t = 0, chọn x0 thỏa mãn điều kiện (1.5) Theo (1.8), ta có x(α) = x0 + αd cũng thỏa mãn (1.5) với bất kỳ α > 0 Do bT x(α) = hb, x0i + αhb, di tiến tới +∞ khi α tăng, nên bT x(α) > r với α đủ lớn Điều này tạo ra mâu thuẫn với điều kiện (i) đã được chứng minh là đúng.
X i=1 u i j A i j 0 , j = 1, , q, (1.9) và gọi a j : R s → R n và b j : R s → R, j = 1, , q, tương ứng là các ánh xạ được cho bởi a j (u j ) := a 0 j + s
X i=1 u i j b i j , (1.10) ở đây A i j , i = 0,1, , s, j = 1, , q là các (p× p)-ma trận đối xứng, a i j ∈ R n và b i j ∈ R, i = 0,1, , s, j = 1, , q.
1.2.5 Định lý ([5, Theorem 2.2]) Cho (℘, r) ∈ R n ×R Giả sử nón
C := cone a j (u j ), b j (u j ) |u j ∈ U j , j = 1, , q (1.11) là một tập đóng, và tồn tại x¯∈ R n sao cho a j (u j ) T x¯ ≤ b j (u j ) với mọi u j ∈ U j , j = 1, , q Tập U j và các ánh xạ a j (u j ), b j (u j ) được xác định bởi (1.9) và (1.10) Các mệnh đề sau đây là tương đương.
(i) Nếu x ∈ R n và a j (u j ) T x ≤ b j (u j ) với mọi u j ∈ U j , j = 1, , q, thì ℘ T x−r ≥ 0;
(ii) Tồn tại λ 0 j ≥ 0 và λ i j ∈ R, j = 1, , q, i = 1, , m, sao cho
Chứng minh [(i) ⇒ (ii)] : Giả sử mệnh đề (i) đúng Ta cần chứng minh mệnh đề (ii) đúng Đặt
Trước hết, chúng ta sẽ chứng minh C˜ là một tập đóng Lấyx ∗ k ∈ C˜ thỏa mãn x ∗ k →x ∗ Khi đó, ta có x ∗ k := λ k 0 (0 R n ,1) + q
X j=1 λ k j aj(u k j ), bj(u k j ) với λ k j ≥ 0, j = 0,1, , q và u k j ∈ U j, j = 1, , q Dãy {λ k 0} k∈ N là một dãy bị chặn Nếu giả sử {λ k 0} k∈ N là không bị chặn, ta có thể lấy dãy con để giả định rằng λ k 0 > 0 và λ k 0 → +∞ Đặt ˜ z ∗ k: q.
Ta thấy rằng z˜ k ∗ ∈ C với mọi k ∈ N và z˜ k ∗ = x λ ∗ k k
−(0 R n ,1) →0−(0 R n ,1). Kết hợp với tính đóng của tập C, ta có −(0 R n ,1) ∈ C Tức là, tồn tại à j ≥ 0 và u j ∈ U j , j = 1, , p, sao cho
Mặt khác, aj(uj) T x¯ ≤bj(uj)với mọiuj ∈ Uj, j = 1, , q.
Dựa vào điều (1.13), ta có mâu thuẫn 0 ≤ −1, dẫn đến dãy {λ k 0} k∈ N là một dãy bị chặn Bằng cách điều chỉnh dãy con nếu cần thiết, ta có thể giả định rằng λ k 0 hội tụ về λ 0 ≥ 0 Đặt z˜ k ∗:
P j=1 λ k j a j (u k j ), b j (u k j ) Ta thấy rằng z˜ k ∗ ∈ C với mọi k ∈ N và z˜ k ∗ →x ∗ −λ 0 (0 n ,1) khi k → ∞ Kết hợp với tớnh đúng của C, ta cú x ∗ −λ 0 (0 R n ,1) ∈ C Do đú, tồn tại à≥ 0 và u j ∈ U j , j = 1, , p, sao cho x ∗ −λ0(0 R n ,1) q
X j=1 àj aj(uj), bj(uj)
Vì vậy x ∗ ∈ C.˜ Điều này chứng tỏ C˜ là một tập đóng Vì (i) đúng nên, theo Định lý 1.2.4, ta có (−℘,−r) ∈ cl ˜C = ˜C Do đó, tồn tại λ 0 ≥ 0, à j ≥ 0, và u j := (u 1 j , , u s j ) ∈ U j , j = 1, , q, sao cho
X i=1 u i j b i j ). Đặt λ 0 j := àj ≥ 0 và λ i j := àju i j ∈ R, j = 1, , q, i = 1, , s Ta cú
X i=1 λ i j b i j ) = 0. Đẳng thức sau cùng kéo theo −r − q
P i=1 u i j A i j 0 Tiếp theo chúng ta chứng minh λ 0 j A 0 j + s
Thật vậy, nếu λ 0 j = 0 thì λ i j = λ 0 j u i j = 0 với mọi i = 1, , s Vì vậy, (1.14) đúng Nếu λ 0 j 6= 0 thì λ 0 j A 0 j + s
Tức là, (1.14) cũng đúng Do đó, mệnh đề (ii) được chứng minh.
[(ii) ⇒ (i)] : Giả sử rằng mệnh đề (ii) đúng Tức là, tồn tại λ 0 j ≥ 0, λ i j ∈ R, j = 1, , q, i = 1, , s, sao cho
Lấyj ∈ {1, , q}tùy ý Khi đó, nếuλ 0 j = 0thìλ i j = 0với mọii = 1, , s. Thật vậy, giả sử λ 0 j = 0 nhưng tồn tạii 0 ∈ {1, , s} mà λ i j 0 6= 0 Trường hợp này, (1.16) trở thành s
Xét biểu thức X i=1 λ i j A i j 0 với mọi t > 0, ta có u j + t(λ 1 j , , λ s j ) ∈ U j, điều này dẫn đến mâu thuẫn với giả thiết U j là tập compact Do đó, nếu λ 0 j = 0, thì λ i j = 0 với mọi i = 1, , s Đặt ubj := (ub 1 j , , bu s j ) ∈ Uj và uej := (ue 1 j , , ue s j ), trong đó ue i j được xác định như sau: ( bu i j nếu λ 0 j = 0, λ i j / λ 0 j nếu λ 0 j ≠ 0), với j = 1, , q và i = 1, , s.
P i=1ue i j A i j 0 Vì vậy, ue j ∈ U j với j = 1, , q Từ (1.15) ta suy ra
X j=1 λ 0 j a j (ue j ), b j (eu j ) Điều này cho thấy rằng
Trong bài viết này, chúng ta xem xét mệnh đề (i) với điều kiện (−℘,−r) ∈ C,˜ được định nghĩa theo (1.12) Để chứng minh, ta chọn x ∈ R n sao cho a j (u j ) T x ≤ b j (u j ) với mọi u j ∈ U j, j = 1, , q Theo Định lý 1.2.4, từ (1.17) suy ra −℘ T x ≤ −r, dẫn đến ℘ T x−r ≥ 0 Kết quả này chứng minh được định lý đã đề ra.
1.2.6 Nhận xét Từ phép chứng minh ở trên chúng ta thấy rằng chiều (ii) ⇒(i) luôn đúng mà không cần giả thiết C là đóng.
Ví dụ sau đây cho thấy rằng nếu C không phải là một tập đóng thì chiều (i) ⇒ (ii) có thể sai.
X i=1 u i A i 0} và các ánh xạ a : R 2 →R 2 và b : R 2 → R tương ứng được xác định bởi a(u) := a 0 +
Ma trận vuông đối xứng có ba giá trị riêng là 1±p(u₁)² + (u₂)² và 1 Một ma trận dương đối xứng được coi là nửa xác định dương khi tất cả các giá trị riêng của nó đều không âm Điều này dẫn đến một số kết luận quan trọng về tính chất của ma trận.
U = u := (u 1 , u 2 ) ∈ R 2 |(u 1 ) 2 + (u 2 ) 2 ≤ 1 Với x := (x 1 , x 2 ) ∈ R 2 , ta có a(u) T x ≤ b(u), ∀u = (u 1 , u 2 ) ∈ U nếu và chỉ nếu u 1 x 1 + (u 2 + 1)x 2 ≤ 0, ∀u = (u 1 , u 2 ) ∈ U (1.18)
Dễ thấy (1.18) tương đương với q (x 1 ) 2 + (x 2 ) 2 ≤ −x 2
Do đó, tập chấp nhận vững là
Ta có x¯ := (0,−1) ∈ Ω và đặt ℘ := (1,0) với r := 0 Điều này dẫn đến ℘ T x ≥ r cho mọi x ∈ Ω, chứng minh mệnh đề (i) ở Định lý 1.2.5 là đúng Tiếp theo, chúng ta sẽ chứng minh rằng mệnh đề (ii) ở Định lý 1.2.5 không đúng Giả sử ngược lại, tồn tại λ ≥ 0 và λ 1, λ 2 ∈ R.
Khi λ 1 = −1 và λ 2 = −λ 0, với điều kiện (λ 0) 2 ≥ (λ 1) 2 + (λ 2) 2, ta nhận thấy sự mâu thuẫn này chứng tỏ mệnh đề (ii) trong Định lý 1.2.5 không đúng Do đó, trong trường hợp này, ta có (i) không dẫn đến (ii), nguyên nhân là do nón.
= cone (u 1 , u 2 + 1,0)|(u 1 ) 2 + (u 2 ) 2 ≤ 1 không đóng Thật vậy, lấy z k := (1, k 1 ,0) = k( k 1 , k 1 2,0) ∈ C với k ∈ N.
Ta thấy rằng z k → z 0 := (1,0,0) và z 0 ∈/ C Do vậy, C không phải là một tập đóng.
Kết quả sau cung cấp điều kiện đủ để tập C cho bởi (1.11)là đóng.
1.2.8 Mệnh đề ([5, Proposition 2.4]) Giả sử một trong hai điều kiện sau được thỏa mãn:
(i) Mỗi U j , j = 1, , q, là một đa diện bị chặn;
(ii) Mỗi U j , j = 1, , q, là một tập compact và thỏa mãn điều kiện Slater: tồn tại xˆ ∈ R n sao cho a j (u j ) T x < bˆ j (u j ), ∀u j ∈ U j , j = 1, , q (1.19) Khi đó, nón C := cone a j (u j ), b j (u j ) |u j ∈ U j , j = 1, , q là đóng.
Chứng minh Với mỗi j ∈ {1, , q}, xét ánh xạ affine F j : R s →R n ×R được cho bởi
(i) Giả sử mỗi Uj, j = 1, , q, là một đa diện bị chặn Khi đó, do
Fj là ánh xạ affine liên tục, và tập Fj(Uj) tạo thành một đa diện bị chặn, điều này cho thấy Fj(Uj) là một bao lồi của một tập hữu hạn Do đó, với mỗi j từ 1 đến q, tồn tại một số nguyên kj và các cặp (a i j , b i j ) thuộc R n × R, với i từ 1 đến kj.
Từ đó suy ra tập conv q
F j (U j ) = conv (a i j , b i j )|i = 1, , k j , j = 1, , q là một đa diện Do đó,
F j (U j ) = conehconv (a i j , b i j )|i = 1, , k j i là một nón đa diện Vì vậy, C là một tập đóng.
(ii) Giả sử mỗi Uj, j = 1, , q, là một tập compact và tồn tại xˆ ∈ R n thỏa mãn (1.19) Khi đó, do Uj là compact và Fj là liên tục, các tập
F j (U j ) là compact với mọi j ∈ {1, , q} Từ đó suy ra tập q
F j (U j ) cũng là compact Lưu ý rằng F j (U j ) là một tập lồi với mỗi j ∈ 1, , q (do U j lồi và F j affine) Tiếp theo, chúng ta sẽ chứng minh
Nếu (1.20) khụng được thỏa món, thỡ tồn tạiu¯j ∈ Uj, à¯j ≥ 0, j = 1, , q, sao cho q
Mặt khác, từ (1.19) ta có q
Do đó, cùng với (1.21) ta suy ra điều mâu thuẫn Vì vậy, (1.20) đúng. Theo [7, Proposition 1.4.7], nón C = cone q
Cố định x ∈ R m và xét bài toán tối ưu cấp thấp với ràng buộc không chắc chắn: minz∈ R n
{c T 0 x+d T 0 z|c T j +a j (u j ) T z ≤ b j (u j ), j = 1, , q}, (LP) u j ∈ U j , j = 1, , q, ở đây U j , a j (u j ) và b j (u j ) được cho (1.9) và (1.10), trong khi c 0 ∈ R m , d 0 ∈ R n , c j ∈ R m , j = 1, , q.
Phiên bản vững của (LN P) là bài toán (RLP) sau đây: z∈minR n
{c T 0 x+ d T 0 z|c T j +aj(uj) T z ≤bj(uj),∀u j ∈ Uj, j = 1, , q} (1.22)
1.2.9 Định nghĩa Ta nói y ∈ R n là một nghiệm tối ưu vững của (LP) nếu y là nghiệm tối ưu của (1.22), tức là, y ∈ Y(x) := argmin z∈ R n c T 0 x+d T 0 z| c T j x+ a j (u j ) T z ≤ b j (u j ),
Kết quả tiếp theo thiết lập đặc trưng nghiệm tối ưu vững của bài toán tối ưu với ràng buộc không chắc chắn (LP).
1.2.10 Định lý ([5, Theorem 2.5]) Cho x ∈ R m , y ∈ R n và giả sử nón
C(x) := cone a j (u j ), b j (u j )−c T j x |u j ∈ U j , , j = 1, , q là đóng Khi đó, y ∈ Y(x) khi và chỉ khi tồn tại λ 0 j ∈ R + và λ i j ∈ R, j = 1, , q, i = 1, , s, sao cho
Chứng minh Giả sử y ∈ Y(x) Ta có c T j x+a j (u j ) T y ≤ b j (u j ) với mọi u j ∈ U j , j = 1, , q, (1.24) và d T 0 y ≤ d T 0 z khi c T j x+a j (u j ) T z ≤ b j (u j ), ∀u j ∈ U j , j = 1, , q (1.25) Đặt r := d T 0 y.Rõ ràng chúng ta thấy rằng (1.25) tương đương với khẳng định: d T 0 z ≥r với mỗi z ∈ R n thỏa mãn a 0 j + s
X i=1 u i j b i j , với mọi u j = (u 1 j , , u s j ) ∈ U j , j = 1, , q Mặt khác, theo giả thiết,
C(x) là một nón đóng Do đó, nhờ Định lý 1.2.5, tồn tại λ 0 j ∈ R + và λ i j ∈ R, j = 1, , q, i = 1, , s, sao cho
Kết hợp (1.24) ta suy ra (2.10) đúng.
Ngược lại, giả sử tồn tại λ 0 j ∈ R + và λ i j ∈ R, j = 1, , q, i = 1, , s, sao cho (2.10) đúng Ta có c T j x+a j (u j ) T y ≤ b j (u j ), ∀u j ∈ U j , j = 1, , q. Điều này có nghĩa y ∈ R n là một điểm chấp nhận được của (RLN P). Lấy z ∈ R n bất kỳ thỏa mãn c T j x+a j (u j ) T z ≤ b j (u j ), ∀u j ∈ U j , j = 1, , q.
Từ định nghĩa của a j (u j ) và b j (u j ) ta suy ra
X i=1 u i j b i j , với mọi uj = (u 1 j , , u s j ) ∈ Uj, j = 1, , q Do đó, nhờ (2.10), tồn tại λ 0 j ∈ R + và λ i j ∈ R, j = 1, , q, i = 1, , s, sao cho
Vì vậy, nhờ tính đóng của C(x), theo Định lý 1.2.5, ta có d T 0 z ≥ d T 0 y.
Từ đó suy ra y ∈ Y(x) Định lý được chứng minh.
Chương 2 Đặc trưng nghiệm toàn cục vững và ứng dụng
Chương này sẽ trình bày kết quả về đặc trưng nghiệm toàn cục vững và lược đồ giải xấp xỷ giá trị tối ưu vững của bài toán (P).
Đặc trưng nghiệm toàn cục vững
Xét bài toán tối ưu đa thức hai cấp sau:
, (2.1) ở đây f : R m ×R n → R là một đa thức và Y(x,ˆa1,ˆb1, ,ˆaq,ˆbq) là tập nghiệm của bài toán tối ưu: z∈minR n n c T 0 x+d T 0 z|c T j x+ ˆa T j z ≤ˆb j , j = 1, , qo, (2.2) c 0 ∈ R m , d 0 ∈ R n , c j ∈ R m , j = 1, , q, (˜a i ,˜b i ,˜c i ) ∈ U˜ i ⊂ R m ×R n ×R, và (ˆa j ,ˆb j ) ∈ Uˆ j ⊂R n ×R, i = 1, , l, j = 1, , q.
Trong phần sau, chúng ta giả thiết các tập không chắc chắn U˜ i và Uˆ j tương ứng được cho bởi:
Uˆj := aj(uj), bj(uj) |uj ∈ Uj , j = 1, , q, ở đây a i := (a 1 i , ,a m i ), ¯a i := (¯a 1 i , ,¯a m i ) ∈ R m , a k i ≤ ¯a k i , k = 1, , m, b i := (b 1 i , ,b n i ), ¯b i := (¯b 1 i , ,¯b n i ) ∈ R n , b k i ≤ ¯b k i , k = 1, , n, c i ¯c i ∈ R, c i ≤ ¯c i , i = 1, , l; U j := Π s i=h [−γ h , γ h ], γ h > 0, h = 1, , s, a i j ∈ R n , b i j ∈ R, i = 0,1, , s, j = 1, , q; a j : R s → R n và b j : R s → R, j = 1, , q, tương ứng được cho bởi a j (u j ) := a 0 j + s
Khi đó, bài toán cấp thấp trong (P) có thể viết lại một cách tương đương như sau: minz∈ R n
{c T 0 x+d T 0 z|c T j x+aj(uj) T z ≤ bj(uj), j = 1, , q}, (LP) ở đây uj ∈ Uj, j = 1, , q Với mỗi x ∈ R m , phiên bản vững của bài toán (LP) được cho bởi: z∈minR n c T 0 x+d T 0 z| c T j x+aj(uj) T j z ≤bj(uj),
Bài toán (P) được xem là thỏa mãn điều kiện Slater cấp thấp (LSC) nếu với mỗi x ∈ R m, tồn tại z ∈ R n sao cho c T j x + aj(uj) T z < bj(uj) cho mọi uj ∈ Uj, với j = 1, , q Hàm f được coi là thỏa mãn điều kiện bức trên R m × R n nếu khi lim k(x,y)k → +∞, f(x, y) sẽ tiến tới +∞.
Trong bài viết này, E₀ được định nghĩa là ma trận đường chéo kích thước (s×s) với các phần tử dương γₕ trên đường chéo chính, trong đó h chạy từ 1 đến s Đồng thời, Eᵢ là ma trận (s×s) có phần tử tại vị trí (i, i) bằng 1 và tất cả các phần tử khác bằng 0.
Trong phần tiếp theo, đặt d 0 := (d 1 0 , , d n 0 ),, a i j := (a i1 j , , a in j ) ∈ R n và ký hiệu
(ˇa k i ,ˇb k i ,ˇc k i ) ∈ R m ×R n ×R|k = 1, ,2 m+n+1 là tập tất cả các điểm cực biên của U˜ i , i = 1, , l.
2.1.2 Bổ đề ([5, Corollary 3.2]) Cho x ∈ R m và y ∈ R n Khi đó, y ∈ Y(x) nếu và chỉ nếu
Chứng minh Vì mỗi Uj, j = 1, , q là một đa diện bị chặn nên, theo Mệnh đề 1.2.8, nón
C(x) := cone n aj(uj), bj(uj)−c T j x |uj ∈ Uj, j = 1, , q o là đóng Do đó, theo Định lý 1.2.10, ta có: y ∈ Y(x) nếu và chỉ nếu tồn tại λ 0 j ≥ 0, λ i j ∈ R, j = 1, , q, i = 1, , s, sao cho
Bài toán tuyến tính nếu có nghiệm tối ưu thì nghiệm tối ưu sẽ nằm ở điểm cực biên của miền ràng buộc Đối với mỗi j ∈ {1, , q}, điều kiện c T j x + aj(uj) T y ≤ bj(uj) với ∀uj ∈ Uj chỉ xảy ra khi ˇu T k (a 1 j) T y − b 1 j, , (a s j) T j − ab s j + (a 0 j) T y + c T j x − b 0 j ≤ 0, với k = 1, , 2 s Tại đây, ˇuk := (ˇu 1 k, , ˇu s k) ∈ R s cho k = 1, , 2 s là tập hợp các điểm cực biên của Uj Thêm vào đó, ta có λ 0 j A 0 j + s.
X i=1 λ i j A i j 0, j = 1, , q, nếu và chỉ nếu (λ 0 j γi) 2 −(λ i j ) 2 ≥ 0, i = 1, , s, j = 1, , q Do đó, điều kiện cần và đủ để y ∈ Y(x) là
Rõ ràng, từ (2.6) ta suy ra (2.4) đúng với
Ngược lại, giả sử (2.4) đỳng Khi đú, ta cú (2.6) đỳng với λ 0 j := à à j
0, λ i j := à i j à 0, j = 1, , q, i = 1, , s Như vậy, định lý được chứng minh. Kết quả sau cung cấp một đặc trưng của nghiệm tối ưu vững của (P).
Theo định lý 2.1.3, nếu bài toán (P) thỏa mãn điều kiện Slater cấp thấp (LSC) và hàm mục tiêu f đáp ứng điều kiện bức ở trên R m × R n, thì với nghiệm chấp nhận được vững (˜x,y)˜ ∈ R m × R n và một số thực κ sao cho κ ≥ f(˜x,y), hai mệnh đề sau sẽ là tương đương.
(i) (¯x,y)¯ là nghiệm toàn cục vững của bài toán (P);
(ii) Với mỗi > 0 tồn tại ζ, σ0, σi ∈ Σ 2 [x, y, à], i = 1, , L, và ξj ∈ R[x, y, à], j = 1, , n+ 1, sao cho f −
X j=1 ˇ u j i−(k−1)2 s −l2 m+n+1 b j k nếu i = l2 m+n+1 + (k−1)2 s + 1, , l2 m+n+1 +k2 s và k = 1, , q; g i (x, y, à) := à 0 nếu i = l2 m+n+1 +q2 s + 1; gi(x, y, à) := à i−l2 m+n+1 −q2 s −1 nếu i = l2 m+n+1 +q2 s + 2, , l2 m+n+1 +q2 s +q + 1; g i (x, y, à) := −à 0 d T 0 y − q
Vì một bài toán quy hoạch tuyến tính nếu có nghiệm tối ưu thì sẽ có nghiệm tối ưu tại phương án cực biên nên
(ˇa k i ,ˇb k i ,cˇ k i ) ∈ R m × R n × R|k = 1, ,2 m+n+1 là những điểm cực biên của U˜i, i = 1, , l Từ đó ta suy ra tập nghiệm chấp nhận được vững của (P) là
, ở đây Y(x)là tập nghiệm tối ưu vững của (LP) Do đó, nhờ Bổ đề 2.1.2, ta có (x, y) ∈ F R nếu và chỉ nếu
Lưu ý cỏc ký hiệu à, g i (x, y, à), i = 1, , Lvà h j (x, y, à), j = 1, , n+ 1 như trong phát biểu định lý, ta có (x, y) ∈ F R khi và chỉ khi tồn tại à ∈ R q(s+1)+1 sao cho
(2.11) Để sử dụng định lý biểu diễn dương Putinar, tiếp theo, chúng ta sẽ chứng minh mô-đun toàn phương
M(g1, , gL, h1, , hn+1,−h 1 , ,−h n+1 , κ−f) là archimedean Ta có ˆh := κ−f + h n+1 = 1.(κ−f) + 1.h n+1
Vì (˜x,y)˜ là nghiệm chấp nhận được vững của bài toán (P), nên tồn tại à˜ ∈ R q(s+1)+1 sao cho (2.11) đỳng tại (˜x,y,˜ à)˜ Điều này dẫn đến hn+1(˜x,y,˜ à) = 0˜ và h(˜ˆ x,y,˜ à) =˜ κ−f(˜x,y)˜ ≥ 0 Do đú,
H := (x, y, à) ∈ R m ìR n ìR q(s+1)+1 |h(x, y, à)ˆ ≥0 6= ∅, bởi vỡ (˜x,y,˜ à)˜ ∈ H Lấy bất kỳ (x, y, à) ∈ H Ta cú ˆh(x, y, à) := κ−f(x, y) + 1− q
Mặt khác, vì f thỏa mãn điều kiện bức ở trên R m ×R n nên inf
Do đó, từ (2.12) ta suy ra H là tập compact Điều này chứng tỏ
(i) ⇒ (ii): Giả sử (¯x,y)¯ là nghiệm toàn cục vững của (P) Với mỗi > 0, đặt fˆ(x, y, à) := f(x, y) −f(¯x,y) +¯ Tiếp theo, chỳng ta sẽ chứng minh rằng f >ˆ 0 trờn K Lấy bất kỳ (x, y, à) ∈ K Ta cú gi(x, y, à) ≥0, i = 1, , L, hj(x, y, à) ≥0,−h j (x, y, à) ≥ 0, j = 1, , n+ 1.
Lưu ý rằng hệ này tương đương với hệ sau:
Do (LSC) được thỏa món, ta cú à 0 6= 0 Thật vậy, giả sử ngược lại rằng à 0 = 0 Khi đú, từ (2.13) ta suy ra q
Nhờ (2.16), mỗi j ∈ {1, , q}, nếu àj = 0 thỡ à i j = 0 với mọi i = 1, , s.
Do đú, từ (2.14) ta suy ra tồn tại j ∈ {1, , q} sao cho àj 6= 0, nghĩa là q
P j=1 à j 6= 0 Với mỗi j ∈ {1, , q}, đặt u¯ j := (¯u 1 j , ,u¯ s j ) ∈ R s , ở đõy ¯ u i j :(0 nếu à j = 0, à i j à j nếu à j 6= 0, i = 1, , s.
Ta có |¯u i j | ≤ γi với mọi i = 1, , s, j = 1, , q Do đó, u¯j ∈ Uj với mọi j = 1, , q Một mặt, theo (LSC), tồn tại z ∈ R n sao cho c T j x+ aj(¯uj) T z < bj(¯uj), j = 1, , q.
P j=1 à j 6= 0 và à j ≥ 0 với mọi j = 1, , q, ta suy ra q
X j=1 àjbj(¯uj). Điều này tương đương với q
(2.17) Mặt khác, từ (2.15) ta suy ra q
X i=1 à i j b i j ≥ 0. Điều này mõu thuẫn với (2.17) Vỡ vậy, ta cú à 0 > 0 Do đú, (x, y, à) thỏa mãn (2.11) và (x, y) ∈ F R Kết hợp (¯x,y)¯ là nghiệm toàn cục vững của bài toán (P), ta có f(x, y) ≥f(¯x,y).¯ Vì vậy, fˆ(x, y, à) := f(x, y)−f(¯x,y) +¯ > 0.
Theo Bổ đề 1.1.4, tồn tại σ i , ξ j 1 , ξ j 2 , ζ ∈ Σ 2 [x, y, à], i = 0,1, , L, j = 1, , n+ 1, sao cho fˆ= σ0 +
X j=1 ξ j 2 (−h j ) +ζ(κ−f) (2.18) Đặt ξ j := ξ j 1 −ξ j 2 , j = 1, , n+ 1 Từ (2.18) ta suy ra f −
X j=1 ξ j 1 hj −ζ(κ−f)−f(¯x,y) +¯ = σ0.Điều này chứng tỏ mệnh đề (ii) đúng.
(ii) ⇒ (i): Giả sử rằng với mỗi > 0 tồn tại σi, ζ ∈ Σ 2 [x, y, à] và ξj ∈ R[x, y, à], i = 0,1, , L, j = 1, , n+ 1, sao cho f −
(2.19) Lấy bất kỳ (x, y) ∈ F R Khi đú, tồn tại à ∈ R q(s+1)+1 sao cho (2.11) đỳng tại (x, y, à) Do đú, nhờ tớnh chất khụng õm của SOS-đa thức, từ (2.19) ta suy ra
Cho → 0, ta có f(x, y) ≥ f(¯x,y)¯ với mọi (x, y) ∈ F R Vì vậy, (¯x,y)¯ là một nghiệm vững toàn cục của bài toán (P).
2.1.4 Nhận xét Phép chứng minh trên cho thấy không cần điều kiện Slater cấp thấp chúng ta vẫn có (ii) ⇒ (i) đúng.
Ví dụ sau đây cho thấy nếu điều kiện Slater cấp thấp không được thỏa mãn thì chiều (i) ⇒ (ii) ở Định lý 2.1.3 có thể sai.
2.1.5 Ví dụ ([5, Example 3.6]) Xét bài toán tối ưu hóa đa thức hai cấp với ràng buộc tuyến tính không chắc chắn sau: min
Bài toán (EP1) được định nghĩa bởi hàm f(x, y) := x² + y² + 2y − 2 với điều kiện y thuộc tập Y(x, u), trong đó u nằm trong khoảng [-1, 1] Bài toán này có thể chuyển đổi sang dạng tương đương (P) với Ũ = [a, ā] × [b, b̄] × [c, c̄], trong đó a, b, c đều bằng 0 Các ánh xạ a(u) và b(u) được xác định bởi a(u) := a₀ + ua₁ và b(u) := b₀ + ub₁, với a₀ = a₁ = b₀ = b₁ = 1 Tập Y(x) chứa duy nhất phần tử 0 cho mọi x ∈ R, dẫn đến nghiệm vững toàn cục (¯x, y) = (0, ¯0) cho bài toán (EP1) Hơn nữa, hàm f thỏa mãn điều kiện bức ở trên R² Để thuận tiện, chúng ta loại bỏ các hàm đồng nhất bằng 0 và đánh lại chỉ số cho các hàm gi(x, y, à) và hj(x, y, à) như trong phát biểu Định lý 2.1.3.
Lấy κ ≥ −2 = f(¯x,y)¯ và 0< < 1 Khi đó, biểu diễn tổng bình phương các đa thức (2.7) không đúng Thật vậy, giả sử ngược lại rằng tồn tại ζ, σ 0 , σ i ∈ Σ 2 [x, y, à] và ξ j ∈ R[x, y, à], i = 1, ,5, j = 1,2, sao cho f −
Trong bài viết này, chúng ta thấy rằng điều kiện 0 ≤ σ0(ˆx,y,ˆ à)ˆ ≤ −1 < 0 dẫn đến một mâu thuẫn, chứng minh rằng khẳng định (ii) không đúng, trong khi khẳng định (i) vẫn đúng Đặc biệt, mặc dù điều kiện Slater cấp thấp bị vi phạm, tất cả các giả thiết còn lại của Định lý 2.1.3 đều được thỏa mãn.
Giải xấp xỷ giá trị tối ưu toàn cục vững
Mục này trình bày lược đồ giải xấp xỷ giá trị tối ưu vững cho bài toán (P), với việc chứng minh dựa vào đặc trưng của nghiệm tối ưu toàn cục vững được nêu trong Định lý 2.1.3.
Với mỗi k ∈ N, ký hiệu (Pk) là bài toán tối ưu sau: sup
, ở đây f, g i , h j , κ được xác định như trong Định lý 2.1.3.
Bài toán (P k) có thể được chuyển đổi thành một quy hoạch nửa xác định (SDP) và có thể giải quyết bằng một số phần mềm trong MATLAB (tham khảo [1], [8]) Ngoài ra, bài toán (P k) còn đóng vai trò là một bài toán xấp xỉ cho bài toán (P).
Kết quả sau cho thấy rằng, dưới một số giả thiết, giá trị tối ưu của(P k ) hội tụ về giá trị tối ưu vững của (P).
Giả sử bài toán (P) thỏa mãn điều kiện Slater cấp thấp (LSC) và hàm mục tiêu f đáp ứng điều kiện bức ở trên R m ×R n Nếu (˜x,y)˜ ∈ R m ×R n là một nghiệm chấp nhận được vững của bài toán (P) với κ là một số thực bất kỳ sao cho κ ≥ f(˜x,y), thì bài toán (P) sẽ có nghiệm tối ưu vững (x 0 , y 0 ) thỏa mãn val(Pk) ≤ val(P) = f(x0, y0) với mọi k ∈ N.
Hơn thế, ta có k→∞lim val(P k ) = val(P) (2.22) Ở đây val(P k ) và val(P) tương ứng là giá trị tối ưu của (P k ) và giá trị tối ưu vững của (P).
Chứng minh Dưới các giả thiết đã cho, từ phép chứng minh Định lý 2.1.3 ta cú (x, y) ∈ F R nếu và chỉ nếu tồn tại à∈ R q(s+1)+1 sao cho
Trong bài toán (P), với k ∈ N, nghiệm chấp nhận được vững được ký hiệu là (˜x,y)˜ ∈ R m ×R n, thỏa mãn điều kiện κ ≥ f(˜x,y)˜ Định lý 2.1.3 định nghĩa các biến hj, với j = 1, , n+1 Tồn tại một biến à˜ ∈ R q(s+1)+1 sao cho tại điểm (x, y, à) = (˜x,y,˜ à)˜, ta có fˆ(x, y, à) = f(x, y)−f(˜x,y) +˜, với mỗi > 0 cố định.
Từ điều kiện bức của f, như trong phép chứng minh của Định lý 2.1.3, ta suy ra tập
H := (x, y, à) ∈ R m ìR n ìR q(s+1)+1 |ˆh(x, y, à) ≥ 0 , ở đây ˆh := (κ−f) + h n+1 , là compact Hơn nữa, ta có
) 6= ∅, bởi vỡ (˜x,y,˜ à)˜ ∈ K Mặt khỏc, K ⊂ H Do đú, K cũng là một tập compact khác rỗng Lưu ý rằng fˆlà một hàm số liên tục Vì thế, tồn tại (x 0 , y 0 , à 0 ) ∈ K sao cho fˆ(x 0 , y 0 , à 0 ) ≤ fˆ(x, y, à) với mọi(x, y, à) ∈ K (2.24)
Tiếp theo, chúng ta chứng minh (x 0 , y 0 ) là một nghiệm tối ưu vững của bài toỏn (P) Thật vậy, vỡ (x 0 , y 0 , à 0 ) ∈ K nờn g i (x 0 , y 0 , à 0 ) ≥ 0, i= 1, , L, h j (x 0 , y 0 , à 0 ) ≥ 0,−h j (x 0 , y 0 , à 0 ) ≥ 0, κ−f(x 0 , y 0 ) ≥ 0, j = 1, , n+ 1.
Dưới điều kiện Slater cấp thấp (LSC), tương tự như chứng minh của Định lý 2.1.3, từ (2.25) ta suy ra (2.23) đỳng tại (x, y, à) = (x 0 , y 0 , à 0 ).
Do đó, (x₀, y₀) là nghiệm chấp nhận được vững của bài toán (P) Nếu (x, y) ∈ Rᵐ × Rⁿ là nghiệm chấp nhận được vững của bài toán (P), thì tồn tại a ∈ Rᵖ(s+1)+1 sao cho (2.23) đúng Nếu κ−f(x, y) ≥ 0, thì (x, y, a) ∈ K, và từ (2.24) suy ra f(x₀, y₀) ≤ f(x, y) Ngược lại, nếu κ−f(x, y) < 0, kết hợp với (2.25) cho thấy f(x, y) > κ ≥ f(x₀, y₀) Do đó, (x₀, y₀) là nghiệm tối ưu vững của (P) và val(P) = f(x₀, y₀).
Bây giờ chúng ta chứng minh bất đẳng thức trong (2.21) đúng Nếu bài toán (P k ) không có nghiệm chấp nhận được thì val(P k ) = −∞ ≤ val(P).
Trường hợp ngược lại, lấy (t, σ 0 , σ i , ξ j , ζ), i = 1, , L, j = 1, , n + 1 là một nghiệm chấp nhận được bất kỳ của bài toán (P k ) Ta có ζ, σ 0 , σ i ∈ Σ 2 [x, y, à], ξ j ∈ R[x, y, à], t ∈ R, deg(σ 0 ) ≤ k,deg(ζf) ≤ k, deg(σ i g i ) ≤ k, deg(ξ j h j ) ≤ k, i = 1, , L, j = 1, , n+ 1 và f −
(2.27) ở đây (x0, y0) là nghiệm vững tối toàn cục của bài toán (P) nói ở trên. Nhờ (2.25) và tính không âm của các SOS-đa thức, từ (2.27) ta suy ra
Do đó, f(x₀, y₀) ≥ t chứng tỏ val(Pₖ) ≤ f(x₀, y₀) Kết hợp với (2.26), ta có (2.21) là đúng Cuối cùng, chúng ta sẽ chứng minh (2.22) đúng Lấy > 0 bất kỳ, ta có κ ≥ f(˜x, y˜) ≥ f(x₀, y₀) Theo Định lý 2.1.3, tồn tại σᵢ, ξⱼ¹, ξⱼ², ζ ∈ Σ²[x, y, à], với i = 1, , L và j = 1, , n+1, sao cho f −.
X j=1 ξ j h j −ζ(κ−f)−f(x 0 , y 0 ) + = σ 0 , ở đây ξj := ξ j 1 −ξ j 2 Từ đó suy ra f −
X j=1 ξ j h j −ζ(κ−f)−t 0 = σ 0 , ở đây t 0 := f(x 0 , y 0 )− ∈ R Vì thế, tồn tại k ∈ N sao cho
deg(σ0) ≤ k , deg(ζf) ≤ k , deg(σigi) ≤ k , deg(ξjhj) ≤ k , i = 1, , L, j = 1, , n+ 1.
Do đó, f(x 0 , y 0 ) ≥ val(P k ) ≥ f(x 0 , y 0 )− với mọi k ≥ k Lưu ý rằng {val(P k )} là dãy tăng theo k Cho k → ∞, ta có f(x 0 , y 0 ) ≥ lim k→∞val(D k ) ≥ f(x 0 , y 0 )− (2.28)
Vì > 0được lấy tùy ý nên từ (2.28) ta suy ra điều phải chứng minh.
Sau đây là hai ví dụ minh họa việc sử dụng lược đồ xấp xỷ trong Định lý 2.2.2 để tìm giá trị tối ưu vững của bài toán (P).
2.2.3 Ví dụ ([5, Example 4.2]) Xét bài toán tối ưu đa thức hai cấp với ràng buộc tuyến tính không chắc chắn sau:
(x,y)∈minR 2 f(x, y) := x 4 +y 2 +y+ 1|y ∈ Y(x, u), x ≤ 0, y ≤ 0 , (EP2) ở đâyu ∈ U := [−1,1] vàY(x, u) := argmin z∈ R {2x−z|(1 + 1 2 u)z ≤ 0}. Bài toán (EP2) là một trường hợp đặc biệt của bài toán (P), ở đó
U˜ := [a, ¯a] × [b, ¯b] × [c, ¯c] với a := b := c = 0 ∈ R, ¯a := ¯b := ¯c := 1, c₀ := 2, d₀ := −1, c := 0 ∈ R Các ánh xạ a : R → R và b : R → R được định nghĩa bởi a(u) := a₀ + ua₁ và b(u) := b₀ + ub₁ với a₀ := 1, a₁ := 1/2, b₀ := b₁ := 0 ∈ R và u ∈ R Kiểm tra cho thấy (x₀, y₀) := (0, 0) là nghiệm tối ưu vững của bài toán (EP2) với giá trị tối ưu vững là val(EP2) = 1 Sử dụng lược đồ xấp xỉ trong Định lý 2.2.2, chúng ta tìm giá trị tối ưu toàn cục vững Hàm f thỏa mãn điều kiện bức trên R² và bài toán (EP2) thỏa mãn điều kiện Slater cấp thấp Đặt à := (à₀, à₁, à₁₁) ∈ R³ và gi(x, y, à), hj(x, y, à) là các hàm theo định nghĩa trong Định lý 2.1.3 Để thuận tiện, chúng ta loại bỏ các hàm đồng nhất bằng 0 và đánh lại chỉ số.
Rõ ràng (˜x,y) := (−1,˜ 0) là nghiệm chấp nhận được vững của (EP2).
Do đó, ta có thể chọn κ := 2 ≥ 2 =f(˜x,y).˜ Khi đó, bài toán (P k ) được viết lại là: sup
P j=1 ξjhj −ζ(2−f)−t= σ0 t∈ R, ζ, σ 0 , σ i ∈ Σ 2 [x, y, à], ξ j ∈ R[x, y, à], deg(σ 0 ) ≤ k,deg(ζf) ≤ k,deg(σ i g i ) ≤ k, deg(ξ j h j ) ≤ k, i = 1, ,11, j = 1,2
Sử dụng lệnh "solvemoment" trong Matlab toolbox YALMIP giải các bài toán xấp xỷ (P k ), chúng ta thu được kết quả sau:
Bài toán xấp xỷ Giá trị tối ưu của bài toán xấp xỷ
Kết quả cho thấy sự khác biệt giữa giá trị tối ưu vững val(EP2) = 1 và giá trị tối ưu của bài toán xấp xỉ (Pk), với k = 2, 3, , 6, là khá nhỏ Hơn nữa, giá trị tối ưu val(Pk) tăng dần theo k và không vượt quá giá trị tối ưu vững val(EP2) = 1, điều này phù hợp với kết luận của Định lý 2.2.2.
2.2.4 Ví dụ ([5, Example 4.3]) Xét bài toán tối ưu đa thức hai cấp với ràng buộc tuyến tính không chắc chắn sau: min
(x,y)∈ R 2 f(x, y) := x 4 −4xy +y 4 −2|y ∈ Y(x, u) , (EP3) ở đây u ∈ U := [ −1 2 , 1 2 ] và Y(x, u) := argmin z∈ R x−z|(1 + u)z ≤ 0 Bài toán (EP3) là một trường hợp đặc biệt của bài toán (P), ở đó
U˜ := [a,¯a]×[b,¯b]×[c,¯c] với a := ¯a := b := ¯b := c := ¯c := 0 ∈ R và c 0 := 1, d 0 := −1, c := 0 ∈ R Các ánh xạ a : R → R và b : R → R được xác định bởi a(u) := a 0 + ua 1 và b(u) := b 0 + ub 1 với a 0 := a 1 := 1, b 0 := b 1 := 0 ∈ R Qua kiểm tra, (x0, y0) := (0,0) là nghiệm tối ưu vững của bài toán (EP3) với giá trị tối ưu vững là val(EP3) = −2 Chúng ta áp dụng lược đồ xấp xỉ từ Định lý 2.2.2 để tìm giá trị tối ưu vững của (EP3), thỏa mãn điều kiện Slater cấp thấp trên R² Đặt à := (à 0, à 1, à 1 1) ∈ R³ và g i (x, y, à), h j (x, y, à) là các hàm theo Định lý 2.1.3 Bằng cách loại bỏ các hàm đồng nhất bằng 0 và đánh lại chỉ số, ta có kết quả cần thiết.
Vì (˜x,y˜) := (1,0) là một nghiệm chấp nhận được vững của (EP3), nên ta có thể lấy κ := −1≥ −1 =f(˜x,y)˜ Khi đó, (P k ) được viết lại là: sup
Tương tự Ví dụ 2.2.3, chúng ta có kết quả số như sau:
Bài toán xấp xỷ Giá trị tối ưu của bài toán xấp xỷ
Kết quả cho thấy sự khác biệt giữa giá trị tối ưu vững val(EP3) = −2 và giá trị tối ưu của bài toán xấp xỉ (P k ), k = 2,3, ,6 là khá nhỏ, với giá trị tối ưu val(P k ) tăng dần theo k Tuy nhiên, giá trị tối ưu của (P k ), k = 4,5,6 lại vượt quá giá trị tối ưu vững val(EP3) = −2, điều này không phù hợp với kết luận của Định lý 2.2.2 Nguyên nhân có thể là do sai số tính toán và làm tròn trong quá trình giải số.
Dựa trên việc tổng hợp và phân tích các tài liệu tham khảo, luận văn này thu được các kết quả chính như sau:
Bài toán tối ưu hai đa thức hai cấp với ràng buộc tuyến tính không chắc chắn là một lĩnh vực quan trọng trong tối ưu hóa, liên quan đến việc tìm kiếm nghiệm chấp nhận được vững và nghiệm toàn cục vững Phiên bản vững của bài toán này giúp đảm bảo tính ổn định và độ tin cậy của các giải pháp trong bối cảnh có sự không chắc chắn Những khái niệm liên quan đến bài toán này rất cần thiết để hiểu rõ hơn về cách thức tối ưu hóa trong các điều kiện phức tạp.
Cung cấp chứng minh chi tiết cho các kết quả bổ trợ quan trọng, bao gồm bổ đề Farkas suy rộng và các kết quả liên quan đến đặc trưng nghiệm vững trong bài toán tối ưu tuyến tính không chắc chắn.
3 Trình bày kết quả về đặc trưng nghiệm toàn cục vững của bài toán tối ưu đa thức hai cấp với ràng buộc tuyến tính không chắc chắn.
Bài viết trình bày lược đồ xấp xỉ tìm giá trị tối ưu cho bài toán tối ưu đa thức hai cấp với ràng buộc tuyến tính không chắc chắn Nội dung được minh họa thông qua hai ví dụ cụ thể, trong đó kết quả giải số được phân tích chi tiết.
Kết quả từ luận văn này mở ra những bước đầu tiên trong việc tiếp cận lý thuyết tối ưu đa thức hai cấp vững Để làm rõ hơn mối liên hệ giữa các vấn đề đã trình bày với các bài toán thực tiễn, chúng tôi đề xuất bước tiếp theo là nghiên cứu các vấn đề kinh tế và kỹ thuật có thể được mô hình hóa bằng các bài toán tối ưu đa thức hai cấp.