Kián thực cỡ sð
Mởt số kián thực cỡ bÊn cừa xĂc suĐt
• GiÊ sỷ Ω l mởt têp tuý ỵ khĂc rộng Kỵ hiằu P(Ω) l têp hủp gỗm tĐt cÊ cĂc têp con cừa Ω.
Lợp A ⊂ P(Ω) ữủc gồi l mởt Ôi số náu:
• Lợp F ⊂ P(Ω) ữủc gồi l σ- Ôi số náu nõ l Ôi số v ngo i ra A4) Náu A n ∈ F, ∀n = 1,2, thẳ ∞
C°p (Ω,F) ữủc gồi l mởt khổng gian o, trong õ: Ω 6= ∅ bĐt ký, F l mởt σ- Ôi số cĂc têp con cừa Ω.
H m thỹc X = X(ω) xĂc ành trảnΩ lĐy giĂ trà trản R gồi l h m F-o ữủc ho°c bián ngău nhiản suy rởng náu
(vợi B(R) l σ- Ôi số cĂc têp Borel cừa trửc thỹc R).
X : Ω → R = (−∞; +∞) thẳ X ữủc gồi l bián ngău nhiản.
H m ϕ : (R n ,B(R n )) → (R,B(R)) ữủc gồi l h m Borel, náu nõ l B(R n ) - o ữủc, nghắa l ϕ −1 (B) ∈ B(R n ), vợi mội B ∈ B(R).
1.1.1.5 H m phƠn phối xĂc suĐt cừa bián ngău nhiản
GiÊ sỷ X l bián ngău nhiản xĂc ành trản (Ω,F,P) nhên giĂ trà trản R.
H m số F X (x) = P[X < x], (x ∈ R) ữủc gồi l h m phƠn phối cừa bián ngău nhiản X.
1.1.1.6 Ký vồng cừa bián ngău nhiản
⊕ Náu X l bián ngău nhiản ỡn giÊn xĂc ành trản (Ω,F,P), cõ nghắa l
X k=1 x k I A k, vợi x k ∈ R, A k ∈ F,(k = 1,2, , n) v A k A l = ∅(k 6= l) thẳ ký vồng cừa
X, kỵ hiằu l EX ữủc ành nghắa nhữ sau
⊕ Náu bián ngău nhiản X l giợi hÔn cừa dÂy tông cĂc bián ngău nhiản ỡn giÊn, khổng Ơm {X n } : 0 ≤ X n ↑ X thẳ
⊕ GiÊ sỷ X l bián ngău nhiản bĐt ký, khi õ X cõ thº biºu diạn dữợi dÔng X = X + −X − , vợi X + , X − l cĂc bián ngău nhiản khổng Ơm.
(X + = max{X,0}, X − = max{−X,0}) Náu min (EX + ,EX − ) < ∞ thẳ
EX := EX + −EX − Trong trữớng hủp EX + v EX − ãu hỳu hÔn thẳ X cõ ký vồng hỳu h¤n.
1.1.2 Tẵnh chĐt cừa bián ngău nhiản
1.1.2.1 ành lỵ GiÊ sỷ X : Ω →R Khi õ cĂc mằnh ã sau l tữỡng ÷ìng a) X l bián ngău nhiản. b) {ω : X(ω) < x} ∈ F vợi mội x ∈ R. c) {ω : X(ω) ≤ x} ∈ F vợi mội x ∈ R. d) {ω : a ≤ X(ω) < b} ∈ F vợi a < b bĐt ký.
1.1.2.2 ành lỵ GiÊ sỷ X 1 , , X n l cĂc bián ngău nhiản cũng xĂc ành trản (Ω,F) v ϕ(t 1 , , t n ) l h m Borel giĂ trà thỹc Khi õ
Y = ϕ(X1, , Xn) cụng l bián ngău nhiản.
1.1.2.3 Hằ quÊ GiÊ sỷ X, Y l cĂc bián ngău nhiản Khi õ
X + = X ∨ 0, X − = (−X)∨0, |X| = X + +X − cụng l cĂc bián ngău nhiản °c biằt, náu Y khổng triằt tiảu thẳ X/Y l bián ngău nhiản.
1.1.2.4 ành lỵ GiÊ sỷ {X n , n ≥ 1} l dÂy bián ngău nhiản v sup n
Xn, inf n Xn hỳu hÔn trản Ω Khi õ sup n
Xn, inf n Xn, lim sup n
Xn, lim inf n Xn l cĂc bián ngău nhiản °c biằt náu tỗn tÔi limX n = X thẳ X cụng l bián ngău nhiản.
Mởt số khĂi niằm v kỵ hiằu cừa GiÊi tẵch lỗi
Trong mửc n y, chúng tổi trẳnh b y mởt số khĂi niằm cừa GiÊi tẵch v Ôi số cõ liản quan trong trẳnh b y cừa luên vôn.
+ Cho ma trên vuổng A(x) cĐp nìn, vợi x ∈ R n Ma trên A(x) ữủc gồi l xĂc ành dữỡng náu ành thực kA(x)k > 0, vợi mồi x.
+ Cho têp K ⊂ R n Têp K ữủc gồi l nõn ối xựng tÔi x ∗ náu x ∗ + λ(x−x ∗ ) ∈ K, vợi mồi λ ∈ R.
Kỵ hiằu K + v l nõn sinh ra bði nhỳng ma trên xĂc ành dữỡng.
Náu nõn K l têp lỗi thẳ ta cõ nõn lỗi.
+ BĐt ¯ng thực suy rởng Cho nõn lỗi K ⊂ R n v x, y ∈ K Trản K, ta cho cÊm sinh thự tỹ bở phên, kỵ hiằu l K , nhữ sau x K y ⇔ y −x ∈ K.
Ta cụng cõ thº viát x K y thay cho y K x.
Náu nõn lỗi K õng, nhồn, cõ iºm trong Khi Đy hằ thực x K y gồi l bĐt ¯ng thực suy rởng cÊm sinh trản K.
+ Cho nõn K + v , trản õ Â xĂc ành thự tỹ bở phên K Khi õ mội
A ∈ K + v thoÊ mÂn A K 0 thẳ ta nõi A l ma trên nỷa xĂc ành dữỡng. + Kỵ hiằu vec(M) l vectỡ cừa ma trên M.
+ Tẵch A⊗B ữủc gồi l tẵch Kronecker cừa 2 ma trên A v B, nghắa l
[A⊗B][C ⊗D] = [AC ⊗BD], vợi giÊ thiát rơng số h ng cừa ma trên A v B bơng số cởt cừa C v D 1.2.2 Kỵ hiằu
X := diag(x 1 , , x n ) l ma trên ữớng ch²o gỗm cĂc phƯn tỷ x 1 , , x n
5f l vectỡ Ôo h m riảng bêc 1 cừa h m f.
5 2 f l vectỡ Ôo h m riảng bêc 2 cừa h m f.
5 3 f l vectỡ Ôo h m riảng bêc 3 cừa h m f. x 0 l ¤o h m cõa x.
S := mat(s) l ma trên tữỡng ựng cừa vectỡ s. vec(M) l vectỡ cừa ma trên M.
1.2.3.1 K l nõn lỗi ¿nh O khi v ch¿ khi vợi x, y ∈ K;λ ≥ 0 thẳ λx ∈ K;x+y ∈ K.
1.2.3.2 Cho M ∈ R vìv v giÊ thiát rơng M l ma trên ối xựng nỷa x¡c ành d÷ìng Khi â
K p là tập hợp các vectơ M, được xác định trên không gian và có tính chất đặc biệt Tập hợp này bao gồm những vectơ thu được từ các vectơ khác trong không gian, đảm bảo tính chính xác và đồng nhất trong việc xác định dữ liệu.
1.2.3.3 Thự tỹ bở phên K cõ tẵnh chĐt bưc cƯu, phÊn xÔ, kh²p kẵn vợi ph²p toĂn cởng v nhƠn vợi số khổng Ơm.
1.2.3.4 Thự tỹ bở phên K cõ tẵnh chĐt
C°p b i toĂn quy hoÔch tuyán tẵnh ối ngău
1.3.1 C°p b i toĂn ối ngău khổng ối xựng
Cho b i toĂn quy hoÔch tuyán tẵnh min n f(x) n
B i toĂn quy hoÔch tuyán tẵnh  cho gồi l b i toĂn gốc.
Khi õ b i toĂn sau Ơy ữủc gồi l b i toĂn quy hoÔch tuyán tẵnh ối ngău khổng ối xựng maxn g(y) m
Bián y i , i= 1, , m cỏn gồi l nhƠn tỷ Lagrông hay nhƠn tỷ ối ngău.
1.3.2 Tẵnh chĐt cừa c°p b i toĂn ối ngău
1.3.2.1 Vợi mồi phữỡng Ăn x, y cừa c°p b i toĂn ối ngău thẳ f(x) ≤ g(y) B i to¡n gèc câ ph÷ìng ¡n tèi ÷u x ∗ khi v ch¿ khi b i to¡n èi ng¨u cõ phữỡng Ăn tối ữu y ∗ , ỗng thới f(x ∗ ) = g(y ∗ ).
1.3.2.2 Ph÷ìng ¡n x ∗ = (x ∗ j ) cõa b i to¡n gèc l tèi ÷u khi v ch¿ khi tỗn tÔi phữỡng Ăn y ∗ = (y i ∗ ) cừa b i toĂn ối ngău sao cho tÔi ch¿ số j cõ x ∗ j > 0 thẳ iãu kiằn thự j cừa b i toĂn ối ngău cõ P m i=1
B i toĂn quy hoÔch ngău nhiản hai giai oÔn
X²t b i to¡n quy ho¤ch min{f(x), x ∈ M ⊂ R n }.
• Trong trữớng hủp cĂc dỳ liằu cừa b i toĂn ờn ành, ta cõ b i toĂn quy ho¤ch d¤ng ên ành.
• Trong trữớng hủp cĂc dỳ liằu phử thuởc cĂc bián cố ngău nhiản, ta cõ b i toĂn quy hoÔch ngău nhiản.
Quy hoạch ngẫu nhiên hai giai đoạn trong sản xuất giúp tối ưu hóa việc sử dụng nguồn lực và đáp ứng nhu cầu của thị trường Trong giai đoạn 1, ưu tiên tập trung vào việc thu thập và phân tích thông tin để xác định khối lượng sản xuất cần thiết Sang giai đoạn 2, điều chỉnh theo nhu cầu cụ thể nhằm đảm bảo tính linh hoạt và hiệu quả trong quá trình sản xuất.
Chú ỵ rơng nghiằm sỡ bở khổng l m mĐt khÊ nông cừa nghiằm iãu ch¿nh v phÊi cũng phối hủp vợi nghiằm iãu ch¿nh sao cho chi phẵ trung bẳnh phÊi tối thiºu cho cÊ hai giai oÔn Việc phối hợp giữa các yếu tố này là rất quan trọng để đảm bảo hiệu quả trong sản xuất nông nghiệp, đồng thời giảm thiểu chi phí trung bình cho cả hai giai đoạn.
B i toĂn quy hoÔch ngău nhiản tuyán tẵnh hai giai oÔn, kỵ hiằu l 2SSLP (Two-Stage Stochastic linear Programming).
Chúng ta tiáp cên vợi b i toĂn cõ iãu kiằn r ng buởc phử thuởc v o bián ngău nhiản Cử thº ta x²t b i toĂn
(SLP) min{c T x : Ax= b, T x= h, x≥ 0}, trong õ c l ma trên cĐp nì1, x l ma trên cĐp nì1, b l ma trên hằ số cĐp mì1, A l ma trên hằ số cĐp mìn, h l ma trên cĐp pì1 v
T l ma trên cĐp pìn, cĂc phƯn tỷ cừa cĂc ma trên h v T l cĂc bián ngău nhiản cõ phƠn phối xĂc suĐt  biát.
Ta giÊ sỷ h ho n to n chữa biát, những biát h m phƠn phối cừa nõ, vợi ký vồng hỳu hÔn Eh Ró r ng khổng thº xĂc ành x tứ cĂc phữỡng trẳnh
T x = h Sỹ khĂc nhau giỳa T x v h cụng chẵnh l mởt bián ngău nhiản cõ h m phƠn phối phử thuởc v o x Ta phÊi "trÊ giĂ" cho sỹ phử thuởc n y.
Do vêy, b i toĂn cừa ta l quyát ành l m cỹc tiºu h m c T x v cƯn cõ mực ph¤t cho sü kh¡c nhau ph£i tr£ gi¡ â.
Kÿ thuêt 2 bữợc nhơm chuyºn b i toĂn (SLP) vã mởt b i toĂn tĐt ành theo giĂ trà ký vồng tữỡng ựng QuĂ trẳnh giÊi b i toĂn (SLP) gỗm hai bữợc.
Bữợc thự nhĐt: Chồn vectỡ x khổng Ơm n o õ thọa mÂn nhỳng iãu kiằn nhĐt ành  biát n o õ.
Bữợc thự hai: Chúng ta bờ sung ở lằch giỳa T x v h bði mởt ma trên bờ sung W v mởt bián phÔt y thọa mÂn
Do thổng tin khổng Ưy ừ, ta °t d l vectỡ phÔt v i tẳm giĂ trà nhọ nhĐt cừa d T y vợi iãu kiằn bờ sung ở lằch W y = h−T x, y ≥ 0 v x ≥ 0. GiÊ sỷ ð bữợc 1 ta biát x ∗ , ta tẳm y tứ b i toĂn
(PLP) mind T y vợi iãu kiằn
T x ∗ +W y = h y ≥ 0. Ơy l giai oÔn hai cừa b i toĂn quy hoÔch ngău nhiản Ta kỵ hiằu α(x ∗ , h, T) l giĂ trà tối ữu h m mửc tiảu cừa b i toĂn (P LP)
Khi õ b i toĂn (SLP) cõ thº viát th nh b i toĂn
(P) min x (c T x+Emin y d T y) vợi iãu kiằn
Lúc n y b i toĂn (SLP) cụng cõ thº viát l
BƠy giớ ta x²t mởt lợp b i toĂn quy hoÔch ngău nhiản hai giai oÔn
(2SSLP) min{g(x) = c T x+ Q(x)} vợi iãu kiằn
W(ξ)y = h(ξ)−T(ξ)x với y ≥ 0, trong đó ξ là biến ngẫu nhiên trong không gian xác suất (Ω, F, P) với Ω ⊆ R^k Hàm h(ξ) và T(ξ) lần lượt là hàm trên các cấp độ khác nhau, trong khi y là hàm trên cấp độ q Đặc biệt, d(ξ) được hiểu như một vector phụ thuộc vào biến ngẫu nhiên ξ, với E[Q(x, ξ)] là kỳ vọng của hàm Q(x, ξ) theo biến ngẫu nhiên ξ ∈ Ω Các tham số A, B, T(ξ), h(ξ), và W(ξ) đều là hàm trên các cấp độ khác nhau, thể hiện sự phụ thuộc vào biến ngẫu nhiên ξ.
Náu ξ l bián ngău nhiản rới rÔc nhên giĂ trà trong têp hỳu hÔn Ω (ξ 1 , ξ 2 , , ξ k ) vợi xĂc suĐt P(ξ = ξ i ) = p i thẳ
Trong thời gian gần đây, nhiều nhà toán học đã phát triển những thuật toán giải bài toán quy hoạch ngẫu nhiên hai giai đoạn, và thực tế đã chứng minh nhiều thuật toán khá tin cậy Trong chương 2, chúng ta sẽ tập trung hiểu sâu hơn và vận dụng những kiến thức này.
Trong mức này, chúng tôi trình bày một số tính chất chung nhất cho lớp bài toán quy hoạch tuyến tính ngẫu nhiên 2 giai đoạn Trạng mối mô hình cụ thể sẽ cung cấp cho ta các lớp bài toán khác nhau, sẽ có tính chất riêng biệt khác nhau.
1.4.2.1 H m α(x ∗ , h, T) l lỗi theo x vợi mội h v T cố ành Do õ E(c T x+α(x, h, T)) l h m lỗi theo x v (P) l b i toĂn quy hoÔch lỗi. Chựng minh Cho h 0 , T 0 lƯn lữủt l giĂ trà cố ành cừa h v T;x 1 , x 2 l vectỡ khổng Ơm cố ành GiÊ sỷ y 1 , y 2 lƯn lữủt l phữỡng Ăn tối ữu cừa (P LP) t÷ìng ùng gi¡ trà cè ành(x 1 , h 0 , T 0 ) v (x 2 , h 0 , T 0 ) º chùng minh α(x, h, T) l h m lỗi, vợi bĐt ký λ ∈ [0,1], ta cƯn chựng minh rơng α(λx 1 + (1−λ)x 2 , h 0 , T 0 ) ≤λα(x 1 , h 0 , T 0 ) + (1−λ)α(x 2 , h 0 , T 0 ).
Thêt vêy, tứ y 1 , y 2 ≥ 0 v 0≤ λ ≤ 1, ta cõ y 0 = λy 1 + (1−λ)y 2 ≥0. Ngo i ra
= h0 −T0(λx 1 + (1−λ)x 2 ). iãu õ ch¿ ra rơng y 0 l mởt phữỡng Ăn cừa (P LP) tữỡng ựng vợi (λx 1 +
Tính lỗi của E(cTx + α(x, h, T)) liên quan đến các phép toán tối ưu trong không gian tuyến tính Để giải bài toán (2SSLP), ta thiết lập các điều kiện sau: i) Ma trận T có hạng m và các phần tử của T không phụ thuộc vào biến ngẫu nhiên ξ ii) Biến ngẫu nhiên ξ được xác định trong tập hợp Ω = {w1, w2, , wk} với xác suất P(ξ = wi) = pi Khi đó, E[Q(x, ξ)] được tính là ∑(pi * Q(x, wi)) iii) Tập M = {x ∈ R^n : Tx = h(ξ), x ≥ 0} không rỗng và được chọn (lưu ý rằng h phụ thuộc vào biến ngẫu nhiên ξ, do đó x cũng phụ thuộc vào ξ) iv) −∞ < Q(x, ξ) < ∞, với mọi x ∈ M và mọi giá trị của ξ Cuối cùng, ta đưa ra bài toán quy hoạch tham số z.
Bián z ∈ R m ð Ơy ữủc hiºu nhữ l "bián nhÔy cÊm" (tender variable) trong quy hoÔch ngău nhiản, nõ nhơm tÔo nản mối liản hằ giỳa giai oÔn
1 v giai oÔn 2 Khi õ theo lỵ thuyát quy hoÔch tham số ta cõ φ(z) l h m lỗi, liản tửc, tuyán tẵnh tứng khúc.
Gồi x 0 l nghiằm cừa b i toĂn (A) tữỡng ựng vợi tham số z Kỵ hiằu
Kỵ hiằu M s ,(s = 1,2, ), l cĂc miãn giĂ trà cừa z ữủc xĂc ành trong φ(z) tứ b i toĂn quy hoÔch tuyán tẵnh tham số (A) Khi õ ta cõ
Trong quy hoÔch tuyán tẵnh tham số, ngữới ta  ch¿ ra rơng giĂ trà s l húu h¤n B¥y gií ta x²t b i to¡n
Kỵ hiằu z ∗ l phữỡng Ăn tối ữu cừa b i toĂn (P), x ∗ l phữỡng Ăn tối ữu cõa b i to¡n min{c T x : x ∈ M, T x = z ∗ }.
Ta cõ cĂc ành lỵ sau Ơy l m cỡ sð cho viằc xƠy dỹng thuêt toĂn giÊi b i to¡n (2SSLP).
1.4.2.2 Vợi z ∗ , x ∗ ữủc xĂc ành nhữ trản thẳ giĂ trà tối ữu cừa h m mửc tiảu b i toĂn (P) v b i toĂn (2SSLP) l bơng nhau ỗng thới x ∗ công s³ l ph÷ìng ¡n tèi ÷u cõa b i to¡n (2SSLP).
Chựng minh Tứ giÊ thiát i), tực l T(ξ) = T v tứ cổng thực xĂc ành Q(x, w i ), ψ(z, w i ), ta câ ψ(z, w i ) = min{q(w i )y : W(w i )y = z−h(w i );y ≥0}= Q(x, w i ).
Tứ viằc xĂc ành x ∗ v cĂc h m φ(z), ψ(z, w i ) ta ữủc f(z ∗ ) =c T x ∗ + k
B¥y gií ta cán ph£i chùng minh x ∗ l ph÷ìng ¡n tèi ÷u cõa b i to¡n (2SSLP).
Thêt vêy, giÊ sỷ ngữủc lÔi, x ∗ khổng l phữỡng Ăn tối ữu cừa b i toĂn (2SSLP), khi õ tỗn tÔi x 1 ∈ M sao cho c T x 1 + k
Do x 1 ∈ {x : x ∈ M, T x = z 1 } v tứ (*), (**) ta suy ra f(z 1 ) = c T x 1 + k
X i=1 p i Q(x ∗ , w i ) = f(z ∗ ).iãu n y mƠu thuân vợi z ∗ l phữỡng Ăn tối ữu cừa b i toĂn (P) Vêy x ∗ l ph÷ìng ¡n tèi ÷u cõa b i to¡n(2SSLP).
B i toĂn quy hoÔch ngău nhiản hai giai oÔn vợi r ng buởc nỷa xĂc ành
B i to¡n
2.1.1 B i toĂn quy hoÔch ngău nhiản hai giai oÔn nỷa xĂc ành (Two-Stage Stochastic Semidefinite Programming)
Cho ξel bián ngău nhiản rới rÔc thuởc hồ hỳu hÔn Θ = {ξ 1 , ξ 2 , , ξ K } vợi xĂc suĐt {p 1 , p 2 , , p K } v º thuên tiằn, ta °t ρ i (x) := ρ(x, ξ i ), T i :T(ξ i ), W i := W(ξ i ), h i := h(ξ i ), y i := y(ξ i ) v d i := p i d(ξ i ).
Khi õ, ta cõ b i toĂn quy hoÔch tuyán tẵnh ngău nhiản hai giai oÔn nûa x¡c ành max η(x) := c T x+ρ(x), vợi iãu kiằn
X i=1 ρi(x) (2.2) ỗng thới, vợi mội i = 1,2, , K ρ i (x) := maxd T i y i , vợi iãu kiằn
Gồi γ v λ i l cĂc nhƠn tỷ ối ngău cừa b i toĂn giai oÔn thự nhĐt v thù hai Ta câ b i to¡n èi ng¨u cõa b i to¡n (2.3) l min{(h i −T i x) T λ i } vợi iãu kiằn
2.1.2 CĂc kỵ hiằu, khĂi niằm v giÊ thiát
2.1.2.2 Phữỡng phĂp iºm trong v h m chưn lổgarit
Mởt phữỡng phĂp giÊi b i toĂn quy hoÔch bơng viằc sỷ dửng phữỡng Ăn xuĐt phĂt l mởt iºm trong cừa têp phữỡng Ăn, v men theo mởt ữớng
Phương pháp "tửt" là một giải pháp tối ưu trong việc giảm thiểu rủi ro Quá trình "tửt" không chỉ đơn thuần là áp dụng phương pháp ăn kiêng, mà còn liên quan đến việc thiết lập các mục tiêu cụ thể Thay vì chỉ tập trung vào các điều kiện hạn chế, người ta cần xác định rõ ràng các tiêu chí thành công, nhằm đạt được hiệu quả cao hơn trong việc kiểm soát cân nặng và sức khỏe.
GiÊ sỷ têp phữỡng Ăn cõ dÔng
M := {x ∈ R n : g i (x) ≤0}, vợi giÊ thiát M bà ch°n v tỗn tÔi iºm trong º xỷ lỵ cĂc r ng buởc g i (x) ≤ 0, i = 1, , m, ta dòng h m ch n log nh÷ sau: φ(x)
H m chưn φ(x) cõ cĂc tẵnh chĐt °c biằt sau Ơy: l h m lỗi, trỡn; φ(x) →+∞ khi x tián tợi giợi hÔn biản cừa M; lỗi ch°t trản têp int(M).
Tứ các tính chất của hàm φ(x) có 1 điểm cực tiểu duy nhất trên miền int(M) Đối với tham số t > 0, ta định nghĩa F(x, t) = f(x) + 1/t φ(x), trong đó f(x) là hàm mục tiêu của bài toán quy hoạch Hàm F(x, t) cũng là hàm lỗi chất trên miền int(M), với điểm cực tiểu duy nhất x*(t), được xác định bởi điều kiện.
GiÊ thiát A1) cho thĐy b i toĂn (2.1)-(2.3) cõ têp phữỡng Ăn cừa b i toĂn  cho v b i toĂn ối ngău cõ têp iºm trong khĂc rộng.
A2) CĂc ma trên A v W i cõ hÔng bơng số cởt cừa chúng.
Tứ õ, ngữới ta dăn án b i toĂn, vợi h m chưn log, sau Ơy: max{η(à, x) := c T x+ρ(à, x) +àln(detS)} vợi iãu kiằn
X i=1 ρi(à, x) (2.6) v vợi mội i := 1, , K ρ i (à, x) := max{d T i y i +àln(detS i )} vợi iãu kiằn
W i y i + s i = h i −T i x, (2.7) s i ∈ K r Lóc n y b i to¡n èi ng¨u (2.4) trð th nh min{(h i −T i x) T λ i −àln(detΛ i )} vợi iãu kiằn
Chú ỵ rơng à > 0 v h m ρ(à, x) < ∞, vợi ∀x ∈ F 1 M°t khĂc, tứ giÊ thiát A1) ta suy ra b i toĂn (2.5), (2.7)-(2.8) cõ nghiằm duy nhĐt.
Do cĂc b i toĂn (2.7), (2.8) l cĂc b i toĂn lóm v lỗi nản(y i , s i ) v λ i l phữỡng Ăn tối ữu cừa (2.7) v (2.8) náu v ch¿ náu chúng thoÊ mÂn
Kỵ hiằu Λ i = vec(λ); x(à) l phữỡng Ăn tối ữu giai oÔn thự nhĐt cừa b i toĂn (2.5) v (y i (à, x), s i (à, x), λ i (à, x)) l nghiằm cừa hằ iãu kiằn tối ÷u (2.9),∀x ∈ F 1 ,.
Phữỡng Ăn tối ữu cừa b i toĂn (2.5)-(2.7) ữủc mð rởng tợi b i toĂn min{c T x+
X i=1 d T i y i +àln(detS) +àe T ln(detS i )} vợi iãu kiằn
Tứ õ, ngữới ta  chựng minh ữủc Mằnh ã sau Ơy.
(x(à), s(à);y 1 (à), s 1 (à), , y K (à), s K (à)) l phữỡng Ăn tối ữu cừa (2.10) vêy thẳ (x(à), s(à)) l phữỡng Ăn tối ữu cừa (2.5), (y 1 (à), s 1 (à), , y K (à), s K (à)) l phữỡng Ăn tối ữu cừa (2.7), vợi à Â cho v x = x(à).
Ngữủc lÔi, náu vợi à Â cho (x(à), s(à)) l phữỡng Ăn tối ữu cừa b i toĂn (2.5),(y 1 (à), s 1 (à), , y K (à), s K (à)) l phữỡng Ăn tối ữu cừa b i toĂn (2.7), vợi x = x(à) thẳ (x(à), s(à), y 1 (à), s 1 (à), , y K (à), s K (à)) l phữỡng ¡n tèi ÷u cõa b i to¡n (2.10).
CĂc tẵnh chĐt cừa b i toĂn
2.2.1 Tẵnh Ôo h m cừa h m mửc tiảu
Tứ (2.9) chúng ta cõ thº ch¿ ra rơng giĂ trà h m mửc tiảu tối ữu cừa b i toĂn (2.7)-(2.8) ữủc tẵnh l ρ i (à, x) = (h i −T i x)λ i (à, x)−àln(detΛ i (à, x))−rà+àln(rà) (2.11)
BƠy giớ, chúng ta tẵnh ∇η(à, x) v ∇ 2 η(à, x) LĐy Ôo h m hai vá (2.9), ta ữủc
GiÊi hằ trản, ta ữủc
P i := P i (à, x) = I −Q i W i R i −1 W i T Q i (2.15) LĐy Ôo h m hai vá (2.11) v sỷ dửng iãu kiằn (2.9) v (2.13) ta ữủc
T i T ∇λ i (à, x)−àA T (S −1 ⊗S −1 )A (2.18) Sau â, thay ∇λ i trong (2.18), ta câ
Cho Q ⊂ R n l mởt têp con lỗi, mð, khĂc rộng; h m sốf : Q → R, α > 0.
Ta gồi f l α - tỹ phũ hủp trản Q vợi giĂ trà tham số α náu f ∈ C 3 l mởt h m lỗi trản Q v vợi mồi x ∈ Q, h ∈ R n thẳ bĐt ¯ng thực sau thọa mÂn
Hàm số f(x) là một thành phần quan trọng trong việc xác định giá trị của hàm trong tập hợp Q Việc nghiên cứu hàm số này giúp chúng ta hiểu rõ hơn về các đặc tính và ứng dụng của nó trong toán học Các giá trị x i thuộc Q sẽ được sử dụng để phân tích và đánh giá hàm f(x), từ đó đưa ra những kết luận chính xác và có cơ sở.
BƠy giớ chúng ta ch¿ ra rơng h m ρ(à, x) l h m tỹ phũ hủp trản F 1 2.2.2.2 Bờ ã Vợi mội à > 0, h m ρ i (à, ) l à-tỹ phũ hủp mÔnh trản
Chựng minh Vợi mội à > 0, d ∈ R n v x ∈ {x|ρ i (x) = maxd T i y i < ∞}, ta °t Φ i (t) := ∇ 2 ρ i (à, x+td)[d, d].
Chú ỵ rơng Φ 0 i (0) = ∇ 3 ρ i (à, x)[d, d, d] GiÊ sỷ x j ∈ F i 1 l mởt dÂy hởi tử án mởt iºm giợi hÔn trong F i 1 Khi õ ρ i (à, x) → ∞.
Để chứng minh một hàm \( F_{i1} \) là một hàm lỗi liên tục, cần phải xác định rằng \( F_{i1} \) là hàm số thực với tham số Cụ thể, hàm này được định nghĩa trên không gian \( R \) và phải thỏa mãn điều kiện liên tục cho mọi \( x \in F_{i1} \) và \( d \in R^n \).
√à(∇ 2 ρi(à, x)[d, d]) 3 2 Nhữ vêy ta ch¿ cƯn chựng minh
(câ ¯ng thùc cuèi còng l do (I −W i R −1 i W i Q 2 i )T i d = Q −1 i u i ).
Chú ỵ rơng u T i Q i W i = 0, tứ (2.20) ta thĐy
= |u T i (Q 0 i Q −1 i +Q −1 i Q 0 i )u i |vẳQ i , Q 0 i l ma trên ối xựng
= |u T i Q −1 i (Q 2 i ) 0 Q −1 i u i | (2.21) °t ∇λ i := ∇λ i (à, x) v λ 0 i := δλ i (à,x+td) δt | t=0 = ∇λ i d Tứ (2.14) chúng ta câ
Vêy Bờ ã Â ữủc chựng minh.
Chúng ta cõ hằ quÊ sau Ơy.
2.2.2.3 Hằ quÊ H m r ng buởc ρ(à, x) l mởt à- tỹ phũ hủp trản F 1 v h m mửc tiảu giai oÔn mởt η(à, x) := c T x+ ρ(x) +àln(detS) l mởt à-tỹ phũ hủp mÔnh trản F 0
Tứ Bờ ã 2.2.2.2 ta suy ra ρ(à, x) l mởt à- tỹ phũ hủp trản F 1 ỗng thới, ta thĐy rơng àln(detS) l mởt à- tỹ phũ hủp trản
Tứ kát quÊ ρ(à, x) tỹ phũ hủp trản F 1 , suy ra ρ(x) K
P i=1 ρ i (à, x) l mởt à- tỹ phũ hủp trản F 0 (do F 0 ⊂ F 1 ).
M°t khĂc, tứ Mằnh ã 2.1.1(ii) trong [6] ta suy raη(à, x)l à- tỹ phũ hủp mÔnh trản F 0
2.2.2.4 ành nghắa Hồ cĂc h m {η(à, ) : à > 0} ữủc gồi l tỹ phũ hủp mÔnh trản F 0 vợi cĂc h m tham số α(à), γ(à), ν(à), ξ(à) v σ(à) náu thọa mÂn cĂc iãu kiằn sau Ơy:
1) η(à, x) l h m lóm v liản tửc trản (à, x) ∈ R + ì F 0 v cõ Ôo h m cĐp 3 ối vợi bián x l h m liản tửc trản (à, x) ∈ R + ì F 0
2) ∇η(à, x) v ∇ 2 η(à, x) khÊ vi, liản tửc ối vợi bián à.
3) Vợi mội à ∈ R + , η(à, x) l α(à)- tỹ phũ hủp mÔnh trản F 0
4) H m tham số α(à), γ(à), ν(à), ξ(à) v σ(à) l cĂc h m vổ hữợng dữỡng, liản tửc theo bián à ∈ R +
|{h T ∇ 2 η(à, x)h} 0 − {lnγ(à)} 0 h T ∇ 2 η(à, x)h| ≤ −2σ(à)h T ∇ 2 η(à, x)h. º tiáp tửc nghiản cựu tẵnh tỹ phũ hủp cừa cĂc h m, ta tẵnh Ôo h m cừa (y i (à, x), λ i (à, x), s i (à, x))
LĐy Ôo h m hai vá (2.9) theo à, ta ữủc
|{∇η(à, x) T h}| 0 ≤ [−(p+Kr) à h T ∇ 2 η(à, x) T h] 1 2 Chựng minh LĐy Ôo h m hai vá (2.17) theo à v Ăp dửng (2.25), ta ữủc
T i T Q i P i vec(I)−A T (S − 1 2 ⊗S − 1 2 )vec(I). °t B := [ √ 1 à T 1 T Q 1 P 1 , , √ 1 à T K T Q K P K , A T (S − 1 2 ⊗S − 1 2 )] v z := [vec(I r ), ,vec(I r ),vec(I p )] l vectỡ cõ ở d i l (p 2 +Kr 2 ).
≤ 1 àz T z = 1 à(p+ Kr) (2.26) BƠy giớ sỷ dửng bĐt ¯ng thực chuân v (2.26) ta cõ
Chùng minh Chóng ta cè ành h ∈ R n v °t
Tứ chựng minh cừa bờ ã 2.2.2.2 (xem (2.21)), ta suy ra
M°t khĂc, do S i Λ i = àI v tứ (2.25) nản u T i Q −1 i (Q 2 i ) 0 Q −1 i u i
Tứ (2.27) v (2.28), vợi mội h ∈ R n , ta ữủc
Tứ cĂc Bờ ã 2.2.2.5 v 2.2.2.6 ta cõ tẵnh chĐt sau l cỡ sð º xƠy dỹng thuêt toĂn º giÊi b i toĂn  nảu.
2.2.2.7 ành lỵ Hồ cĂc h m η : R ++ ì F 7→ R l hồ tỹ phũ hủp vợi tham số α(à) = à, γ(à) =ν(à) = 1, ξ(à) √ p+Kr à v σ(à) √ r 2à. Chựng minh º chựng minh ành lỵ, ta ch¿ cƯn thỷ lÔi cĂc iãu kiằn cừa ành nghắa 2.2.2.4 Ró r ng cĂc iãu kiằn 1), 2) 4) ãu ữủc thọa mÂn, iãu kiằn 3) ữủc suy ra tứ Hằ quÊ CĂc iãu kiằn 5) v 6) ữủc thọa mÂn nhớ cĂc Bờ ã 2.2.2.5 v 2.2.2.6.
Tứ cĂc tẵnh chĐt cừa b i toĂn (2.5)-(2.7), ngữới ta  xƠy dỹng thuêt toĂn º giÊi nõ, thuêt toĂn n y dỹa trản phữỡng phĂp iºm trong trản cỡ sð sü ph¥n r¢ cõa Bender.
Thuêt toĂn giÊi
Giá sỉ có thể tắm ủc nghiằm chẵn xác của dải kiền (2.12), trong thực hành, người ta tắm nghiằm xác dải kiền (2.12) để xây dựng theo hướng Newton Dựa vào bài toán giải ôn 1 (2.8), ta cho
TÔi mởt iºm cho ph²p x theo hữợng Newton ta °t
Cho β > 0, γ ∈ (0,1) v θ >0 Vợi ở chẵnh xĂc mong muốn ε ữủc gồi l tiảu chuân dứng, ta giÊ sỷ x 0 ∈ F 0
Tứ õ ta cõ thuêt toĂn nhữ sau
1.2 Tẵnh theo hữợng Newton 4x tứ (2.30).
1.3 °t δ(à, x) q− à 1 4x T ∇ 2 η(à, x)4x. + Náu δ ≤β thẳ chuyºn sang bữợc 2.
Cự sau mội bữợc l°p k thẳ x k c ng chẵnh xĂc v δ(à k , x k ) ≤ β.
Sau mội lƯn ta °t à := γà ð bữợc 2, tực l giÊm à k xuống à k+1 = γà k thẳ δ(à k+1 , x k ) ≤2β.
Nhữ vêy, cự sau mội bữợc l°p Newton vợi θ = 1 thẳ ta cõ mởt iºm mợi x k+1 vợi δ(à k+1 , x k+1 ) ≤β.
VĐn ã ữủc °t ra l thuêt toĂn n y cõ hởi tử hay khổng? iãu õ ữủc trẳnh b y ð mửc sau Ơy.
2.3.2 Sỹ hởi tử cừa thuêt toĂn 2.3.1
Trữợc khi x²t sỹ hởi tử cừa thuêt toĂn, ta º ỵ tợi cĂc kát quÊ sau: 2.3.2.1 Mằnh ã Cho à > 0, x ∈ F 0 v 4x Ta °t δ :r
−1 à4x T ∇ 2 η(à, x)4x v cho δ < 1, τ ∈ [0,1], vợi mội h, h1, h2 ∈ R n , ta cõ
−h T 2 ∇ 2 η(à, x)h 2 2.3.2.2 Bờ ã Cho à > 0 v x ∈ F 0 GiÊ sỷ 4x l hữợng Newton ữủc tẵnh theo cổng thực (2.30) v °t δ(à, x) r
Khi õ, cĂc hằ thực sau ữủc thọa mÂn
√ p+Kr κ ) lnγ −1 vợi κ > 0. GiÊ sỷ δ(à, x) < κ v à + := γà sao cho ϕ κ (η;à, à + ) ≤1− δ(à, x) κ Khi õ δ(à + , x) < κ.
Chúng ta i án cĂc kát quÊ sau:
1−δe+ ln(1−eδ)], (2.32) (ii) |φ 0 (à, x)| ≤ −p p+Krln(1−eδ) (2.33) 2.3.2.6 Bờ ã Cho à > 0, x ∈ F 0 ,eδ < 1 Vợi γ ∈ (0,1), ta °t à + = γà Khi õ η(à + , x(à + ))−η(à + , x) ≤ O(p+ Kr)à +
Cuối cũng, chúng ta cõ thº Ănh giĂ eδ dỹa v o δ trong Bờ ã sau Ơy: 2.3.2.7 Bờ ã Cho à > 0, x ∈ F 0 v Γ ∈ S p GiÊ sỷ (4x,4S,4Γ) l hữợng Newton ữủc cho bði cổng thực (2.30) v 4xe := x−x(à). °t δ(à, x) := q
Tại Tứ Bờ ã 2.3.2.2 và Bờ ã 2.3.2.4, chúng ta thực hiện giảm và bồi hồi với số γ = 1 − σ/√(p + Kr), trong đó σ < 0,1 cho mỗi bước lặp Như vậy, cứ sau mỗi bước lặp, thẩm phán sẽ đánh giá chính xác hơn Chúng ta cần cân nhắc kỹ lưỡng để đảm bảo rằng các quyết định và số liệu được thu thập là chính xác và đáng tin cậy.
2.3.2.8 ành lỵ GiÊ sỷ à 0 l tham số chưn ban Ưu v cho ε > 0 l tiảu chuân dứng, β = (2−√
3)/2 Náu iºm xuĐt phĂt ban Ưu x 0 thọa mÂn δ(à 0 , x 0 ) ≤ β thẳ số bữợc cừa thuêt toĂn s³ kát thúc sợm nhĐt l O(√ p+Krlnà 0 /ε).
Cuối cũng, tứ Bờ ã 2.3.2.2(ii), Bờ ã 2.3.2.6 v Bờ ã 2.3.2.7 ta suy ra ành lþ sau ¥y.
2.3.2.9 ành lỵ GiÊ sỷ à 0 l tham số chưn ban Ưu v cho ε > 0 l tiảu chuân dứng, β = 1/6 Náu iºm xuĐt phĂt ban Ưu x 0 thọa mÂn δ(à 0 , x 0 ) ≤ β thẳ số bữợc cừa thuêt toĂn s³ kát thúc chêm nhĐt l O(√ p+Krlnà 0 /ε).ành lỵ 2.3.2.8 v ành lỵ 2.3.2.9 cho thĐy bơng phữỡng phĂp iºm trong theo hữợng tửt  xĂc ành s³ cho ta thuêt toĂn hởi tử.
I) Nhỳng õng gõp cừa luên vôn
Kát quÊ cừa Luên vôn bao gỗm:
1 Hằ thống ữủc nhỳng kián thực cỡ bÊn cừa lỵ thuyát xĂc suĐt (bián ngău nhiản v cĂc tẵnh chĐt cừa bián ngău nhiản); cừa lỵ thuyát quy hoÔch (mởt số khĂi niằm v kỵ hiằu cừa GiÊi tẵch lỗi, c°p b i toĂn ối ngău, quy hoÔch ngău nhiản) cõ liản quan vợi viằc nghiản cựu cừa ã t i.
2 Giợi thiằu chi tiát mổ hẳnh b i toĂn quy hoÔch ngău nhiản tuyán tẵnh hai giai oÔn v cĂc vĐn ã liản quan.
3 Giợi thiằu b i toĂn quy hoÔch ngău nhiản hai giai oÔn nỷa xĂc ành ð dÔng tờng quĂt, tứ õ xem x²t mởt b i toĂn cử thº (b i toĂn (2.5)-(2.7)), trẳnh b y cĂc tẵnh chĐt (Bờ ã 2.2.2.2, Hằ quÊ 2.2.2.3, ành lỵ 2.2.2.7).
4 ữa ra ữủc mởt thuêt toĂn khĂ tin cêy (thuêt toĂn 2.3.1) º giÊi b i toĂn v chựng minh sỹ hởi tử cừa thuêt toĂn õ. °c biằt, thuêt toĂn 2.3.1  phĂt triºn phữỡng phĂp iºm trong, vợi h m chưn phũ hủp, dỹa trản phữỡng phĂp phƠn r cừa Bender.
Trong quá trình nghiện cựu và hồi phục, tôi thấy bài toán đặt ra văn cảnh đang dần mờ nhạt, chữa các nghĩa thực tiễn Trong thời gian tới, nếu có điều kiện tôi sẽ nghiên cứu bài toán đặt ra một cách sâu hơn nữa.