Bài soạn môn tối ưu tuyến tính

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (53.73 KB, 8 trang )

(1)<div class='page_container' data-page=1>

Tối ưu tuyến tính

Câu 1: (Định lý 2.1.1 - Nguyên lý biến phân Ekeland)

Cho (X, d) là không gian mêtric đủ, f :X →R∪ {+∞} là hàm lsc bị chặn dưới. Giả
sử ε >0 và z ∈Z thỏa

f(z)<inf
X f+ε
Khi đó tồn tại y∈X sao cho

(i) d(z, y)≤1.

(ii) f(y) +εd(z, y)≤f(z).

(iii) f(x) +εd(x, y)≥f(y),∀x∈X.

Chứng minh
* Ta định nghĩa dãyzi bằng qui nạp:

+ Đặt z0 :=z.

+ Giả sử ta có zi, đặt Si :={x∈X|f(x) +εd(x, zi)≤f(zi)}
Ta xét hai trường hợp sau

(a) inf
Si

f =f(zi), khi đó ta định nghĩa zi=1 :=zi.
(b) inf

Si

f < f(zi). Ta chọn zi+1 ∈Si sao cho

f(zi+1) < inf
Si

f+

1
2

[

f(zi)−inf
Si

f

]

=
1
2

[

f(zi) + inf
Si

f

]

< f(zi) (1)

Khi đó (zi)là dãy Cauchy.

Thật vậy, nếu (a) xảy ra thì dãy zi dừng khi i đủ lớn hay

εd(zi, zi+1)≤f(zi)−f(zi+1) (2)
và

εd(zi, zj)≤f(zi)−f(j) với j−1> i (3)
Dãy (f(z−i))giảm và bị chặn dưới bởi inf

</div>
(2)<div class='page_container' data-page=2>

* Đặt y:= lim
i→∞zi.

Chọn i= 0, từ (3) ta có:

εd(z, zj) +f(zj)≤f(z) (4)
Cho j → ∞ ta được

f(y) +εd(z, y)≤f(z) (ii)
Do f(z)−f(y)≤f(z)−inf

X f < ε
Kết hợp (ii) ta đượcd(z, y)≤1 (i).
*Ta phải chứng minh y thỏa (iii)

+ Từ (3), cố địnhi và cho j → ∞ ta được y∈Si
Suy ra

y∈

∞
∩

i=1

Si

Mặt khác, nếu x∈

∞
∩

i=1

Si thì ∀i= 1,2, . . .

εd(x, zi+1)≤f(zi+1)−f(x)≤f(zi+1)−inf
Si

f (5)

Do đó lim
i→∞

[

f(zi+1−inf
Si

f

]

= 0.

Từ (5) cho i→ ∞ ta được εd(x, y) = 0. Suy ra

∞
∩

i=1

Si ={y} (6)

+ Xét dãy tập (Si)

∀x∈Si+1 ⇒f(x) +εd(x, zi+1)≤f(zi+1), với zi+1 ∈Si ta được

f(x) +εd(x, zi) ≤ f(x) +εd(x, zi+1) +εd(zi, zi+1)

≤ f(zi+1) +εd(zi, zi+1)≤f(zi)
Suy ra x∈Si. Do đó Si+1 ⊂Si.

Vậy dãy tập(Si) lồng nhau.

</div>
(3)<div class='page_container' data-page=3>

Vớix̸=y, từ (6) suy rax̸∈Si. Do đóf(x) +εd(x, zi)≥f(zi). Cho i→ ∞ta được

f(x) +εd(x, y)≥f(y) (iii).

Câu 2: (Định lý 2.3.2 - Định lý điểm bất động Banach)

Cho (X, d)là không gian mêtric đầy. Giả sử ϕ:X →X là ánh xạ co, khi đó ϕ có duy
nhất điểm bất động.

Chứng minh
+Xét hàm f(x) :=d(x, ϕ(x)).

Áp dụng định lý 2.1.1 (Nguyên lý biến phân Ekeland) với ε ∈ (0,1−k), ∃y ∈X sao
cho:

f(x) +εd(x, y)≥f(y),∀x∈X

Chọn x=ϕ(y), ta có:

d(y, ϕ(y)) ≤ d(ϕ(y), ϕ2(y)) +εd(y, ϕ(y))

≤ (k+ε)d(y, ϕ(y))
Vậy y là điểm bất động.

+Duy nhất

Giả sử y′ cũng là điểm bất động. Suy raϕ(y) =y, ϕ(y′) = y′
⇒d(ϕ(y), ϕ(y′)) =d(y, y′)≤k(d(y, y′))∀k∈(0,1)

⇒d(y, y′) = 0 ⇒y =y′.
Câu 3: (Ánh xạ co có hướng)

(a) Định nghĩa: Cho (X, d) là không gian mêtric đầy.

x, y ∈X, phân đoạn giữa xvà y xác định bởi

[x, y] ={x∈X|d(x, z) +d(z, y) =d(x, y)}
(b) Định nghĩa: Ánh xạ co có hướng

Cho (X, d) là khơng gian mêtric đầy và ϕ là ánh xạ từ X vào X. Khi đó ϕ là ánh xạ
co có hướng nếu:

</div>
(4)<div class='page_container' data-page=4>

(ii) ∃k ∈ (0,1) sao cho ∀x∈ X, ϕ(x)̸= x,∃z ∈ [x, ϕ(x)]\ {x} sao cho d(ϕ(x), ϕ(z))≤

kd(x, z).

(c) Định lý 2.3.3: Cho (X, d) là không gian mêtric đầy. Giả sử ϕ : X → X là ánh xạ
co có hướng. Khi đó ϕ có điểm bất động.

Chứng minh
Xét f(x) =d(x, ϕ(x)).

Hàmf(x)liên tục và bị chặn dưới bởi 0 (do ϕ liên tục).

Áp dụng nguyên lý biến phân Ekeland với ε ∈ (0,1−k),∃y ∈ X sao cho f(y) ≤

f(x) +εd(x, y)∀x∈X(1).

+Nếu ϕ(y) =y thì y là điểm bất động củaϕ.

+Với ϕ(y)̸=y, do ϕ là ánh xạ co có hướng nên ∃z ̸=y với z ∈[y, ϕ(y)], tức là

d(y, z) +d(z, ϕ(y)) =d(y, ϕ(y)) =f(y) (2)
và

d(ϕ(z), ϕ(y))≤kd(z, y) (2)
Chọn x=z, từ (1) và (2) ta có:

d(y, z) +d(z, ϕ(y))≤d(z, ϕ(z)) +εd(z, y)
hay

d(y, z)≤d(z, ϕ(z))−d(z, ϕ(y)) +εd(z, y)
Theo bất đẳng thức tam giác và (3) ta có

d(z, ϕ(z))−d(z, ϕ(y))≤d(ϕ(y), ϕ(z))≤kd(z, y)
Do đó:

d(y, z)≤(k+ε)d(y, z)
Điều này mâu thuẫn.

Vậy ϕ(y) =y hay y là điểm bất động của ϕ.

Câu 4: (Định lý 2.3.5 - Định lý điểm bất động Caristi - Kirk)

</div>
(5)<div class='page_container' data-page=5>

Giả sử F :X →2X là hàm đa trị có đồ thị đóng thỏa f(y)≤f(x)−d(x, y),∀(x, y)∈
graphF. Khi đó F có điểm cố định.

Chứng minh
Xét mêtric ρ trên X×X xác định bởi:

ρ((x1, y1),(x2, y2)) :=d(x1, x2) +d(y1, y2)∀(x1, y1),(x2, y2)∈X×X
Khi đó (X×X, ρ) là mêtric đầy.

Cho ε∈(0,12 và g :X×X →R∪ {+∞}xác định bởi

g(x, y) = f(x)−(1−ε)d(x, y) +ıgraphF(x, y)
Khi đó g là hàm lsc và bị chặn dưới (CM ra).

Theo nguyên lý biến phân Ekeland ta thấy ∃(x∗, y∗) ∈ graphF sao cho g(x∗, y∗) ≤

g(x, y) +ερ((x, y),(x∗, y∗)),∀(x, y)∈X×X

Do đó: ∀x, y ∈ graphF, f(x∗)−(1−ε)d(x∗, y∗) ≤f(x)−(1−ε)d(x, y) +ε(d(x, x∗) +

d(y, y∗))(1).

Giử sử z∗ ∈F(y∗).

Từ (1) cho (x, y) = (y∗, z∗)ta có

f(x∗)−(1−ε)d(x∗, y∗)≤f(y∗)−(1−ε)d(y∗, z∗) +ε(d(y∗, x∗) +d(z∗, y∗))
Suy ra 0≤f(x∗)−f(y∗)−d(x∗, y∗)≤ −(1−2ε)d(y∗, z∗).

Do đóy∗ =z∗.

Vậy y∗ là một điểm bất động của F.

Câu 5: (Nguyên lý biến phân Borwein - Preiss)

(a) Định nghĩa 2.5.1: Cho(X, d)là khơng gian mêtric. Hàm liên tụcρ:X×X →[0,∞]
được gọi là hàm cỡ trên không gian mêtric đầy (X, d)nếu:

(i) ρ(x, x) = 0,∀x∈X.

(ii) ∀ε >0,∃δ >0 sao cho ∀y, z ∈X, ρ(y, z)≤δ suy ra d(y, z)< ε.
(b) Định lý 2.5.2: (Nguyên lý biến phân Borwein - Preiss)

</div>
(6)<div class='page_container' data-page=6>

Giả sử ρ là hàm cỡ và (δi)∞i=0 là một dãy số dương và giả sử ε >0, z∈X thỏa

f(z)≤inff +ε

Khi đó ∃y và dãy {xi} ⊂X sao cho:
(i) ρ(z, y)≤

ε
δ0

, ρ(xi, y)≤

ϵ

2iδ.
(ii) f(y) +

∞
∑

i=0

δiρ(y, xi)≤f(z).

(iii) f(x) +

∞
∑

i=0

δiρ(x, xi)> f(y) +

∞
∑

i=0

δiρ(y, xi),∀x∈X\ {y}
Chứng minh

+ Tổng quát từ x0 =z,

S0 ={x∈X :f(x) +δ0ρ(x, x0)≤f(x0)
Xây dựng dãy {xi}∞i=0;{Si}∞i=0 theo phương pháp qui nạp.
Giả sử xj, Sj với j = 0, i−1 thỏa

f(xj) +
j−1

∑

k=0

δkρ(xj, xk)≤ inf
x∈Sj−1

[

f(x) +
j−1

∑

k=0

δkρ(x, xk)

]

εδj
2jδ
0

(1)

và

Sj =

{

x∈Sj−1|f(x) +
j

∑

k=0

δkρ(x, xk)≤f(xj) +
j−1

∑

k=0

δkρ(xj, xk)

}

(2)

+ Chọn xi ∈Si−1 sao cho

f(xi) +
i−1

∑

k=0

δkρ(xi, xk)≤ inf
x∈Si−1

[

f(x) +
i−1

∑

k=0

δkρ(x, xk)

]

εδi
2iδ
0

(3)

+ Ta định nghĩa:

Si =

{

x∈Si−1 :f(x) +
i

∑

k=0

δkρ(x, xk)≤f(xi) +
i−1

∑

k=0

δkρ(xi, xk)

}

(4)

</div>
(7)<div class='page_container' data-page=7>

∀x∈Si, từ (3) và (4) ta suy ra

δiρ(x, xi) ≤

[

f(xi) +
i−1

∑

k=0

δkρ(xi, xk)

]

−

[

f(x) +
i−1

∑

k=0

δkρ(x, xk)

]

≤

[

f(xi) +
i−1

∑

k=0

δkρ(xi, xk)

]

− inf
x∈Si−1

[

f(x) +
i−1

∑

k=0

δkρ(x, xk)

]

≤ εδi

2iδ
0

Vậy ρ(x, xi)≤

ε

2iδ
0

,∀x∈Si (5)

ρ(x, xi)→0⇒d(x, xi)→0



x, x′ ∈Si :d(x, x′)≤d(x, xi) +d(x′, xi)≤

ε

2iδ
0

ε

2iδ
0 →




Suy ra diam(Si)→0.

Do X đầy, theo định lý Cantor ta có{y}=

∞
∩

i=0

Si ⇒y ∈Si,∀i= 0,1,2, . . ..
Suy ra (i) đúng với (5).

+Mặt khác: xi →y,∀x̸=y⇒x̸∈

∞
∩

i=0

Si.

Thật vậy, dox̸=y nên ∃j0 sao cho x∈Sj0 ⊇Sj0+1 ⊇. . .⊇Sj0+p ⇒x̸∈Sj,∀j ≥j0.

Vì vậy với j0 ta có:

f(x) +

∞
∑

k=0

δkρ(x, xk) ≥ f(x) +
j

∑

k=0

δkρ(x, xk)

> f(xj) +
j−1

∑

k=0

δkρ(xj, xk)( dox∈Sj)

⇒f(x) +
j

∑

k=0

δkρ(x, xk)> f(xj) +
j−1

∑

k=0

δkρ(xj, xk)
Cho j → ∞ ta được:

f(x) +

∞
∑

k=0

δkρ(x, xk) > lim
j→∞

[

f(xj) +
j−1

∑

k=0

δkρ(xj, xk)

]

≥ f(y) +

∞
∑

k=0

δkρ(y, xk) ( dof, ρ lsc )

</div>
(8)<div class='page_container' data-page=8>

Với xj ∈Sj ⊆Sj−1 ⊆. . .⊆S0 ⇒xj ∈S0

⇒f(x0)≥f(xj) +
j−1

∑

k=0

δkρ(xj, xk)

Cho j → ∞, do ρ lsc nên f(z) = f(x0)≥f(y) +

∞
∑

k=0

</div>

Bài soạn môn tối ưu tuyến tính

<b>Tối ưu tuyến tính</b>

Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về