BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
——————

——————

NGUYỄN THỊ THANH HOA

TÍNH ỔN ĐỊNH CỦA BÀI TOÁN
ĐIỀU KHIỂN TỐI ƯU MÔ TẢ BỞI
HỆ TUYẾN TÍNH RỜI RẠC
Chuyên ngành: Toán giải tích
Mã số: 60 46 01 02

LUẬN VĂN THẠC SỸ TOÁN HỌC

Người hướng dẫn khoa học: PGS.TS.Nguyễn Quang Huy

Hà Nội-2015


LỜI CẢM ƠN

Trước khi trình bày nội dung chính của khóa luận, tôi xin bày tỏ
lòng biết ơn sâu sắc tới PGS. TS. Nguyễn Quang Huy người đã định
hướng chọn đề tài và tận tình hướng dẫn để tôi có thể hoàn thành khóa
luận này.
Tôi cũng xin bày tỏ lòng biết ơn chân thành tới phòng sau đại học,
các thầy cô giáo giảng dạy chuyên ngành Toán giải tích trường Đại học
Sư phạm Hà Nội 2 đã giúp đỡ tôi trong suốt quá trình học tập và làm
luận văn.

tập số thực suy rộng

F :X⇒Y

ánh xạ đa trị từ X vào Y

domF

tập xác định của F

gphF

đồ thị của F

x

chuẩn của véc tơ x

BX

hình cầu đơn vị đóng trong không gian X

Bρ (x)

hình cầu đóng tâm x, bán kính ρ

X∗

không gian đối ngẫu của không gian Banach X


N (¯
x; Ω)

nón pháp tuyến Fréchet của Ω tại x¯

∂f (x)

dưới vi phân giới hạn
(dưới vi phân Mordukhovich) của f tại x

∂ ∞ f (x)
ˆ (x)
∂f

dưới vi phân Fréchet của f tại x

D∗ F (¯
x, y¯)

đối đạo hàm Mordukhovich của F tại (¯
x, y¯)

D∗ F (¯
x, y¯)

đối đạo hàm Fréchet của F tại (¯
x, y¯)

dưới vi phân suy biến của f tại x



Mục lục

Mở đầu

1

1 Kiến thức chuẩn bị

4

1.1. Nón pháp tuyến . . . . . . . . . . . . . . . . . . . . . . .

4

1.2. Đối đạo hàm của ánh xạ đa trị

. . . . . . . . . . . . . .

8

1.3. Dưới vi phân . . . . . . . . . . . . . . . . . . . . . . . .

10

1.4. Một số phép toán dưới vi phân . . . . . . . . . . . . . .

12

2 Dưới vi phân Fréchet và dưới vi phân Mordukhovich

Xét bài toán điều khiển tối ưu mô tả bởi hệ tuyến tính rời rạc (Pw ):
N −1

Min

hk (xk , uk , wk ) + hN (xN ),

(0.1)

k=0
N −1

trên véctơ điều khiển u = (u0 , u1 , . . . uN −1 ) ∈ U :=

Uk và các qũy
k=0

N

đạo x = (x0 , x1 , . . . , xN ) ∈ X :=

Xk , thỏa mãn phương trình động
k=0

lực
xk+1 = Ak xk + Bk uk + Tk wk với mọi k = 0, 1, . . . , N − 1,

(0.2)

với ràng buộc

Wk .
k=0

Trong trường hợp C là tập một phần tử, tác giả B. T. Kien và đồng
nghiệp [5] đã thu được một vài công thức cho việc tính toán dưới vi phân
Fréchet của hàm giá trị tối ưu V với giả thiết rằng Tk là toàn ánh với
mọi k.
Bằng cách thiết lập một kết quả mới dựa trên dưới vi phân Fréchet
của hàm giá trị tối ưu của bài toán quy hoạch có tham số, tác giả N.
H. Chieu và Jen-Chih Yao [3] đã thu được công thức tính toán dưới vi
phân Fréchet của V dưới một giả thiết yếu hơn trong [5].
Gần đây, tác giả N. T. Toan, B. T. Kien và Jen-Chih Yao [16, 17]
thiết lập đã được công thức tính dưới vi phân Mordukhovich của hàm
giá trị tối ưu của V và các điều kiện đủ cho tính Aubin của ánh xạ
nghiệm S.
Luận văn thạc sĩ với đề tài “Tính ổn định của bài toán điều khiển
tối ưu mô tả bởi hệ tuyến tính rời rạc” nhằm trình bày công thức tính
dưới vi phân Mordukhovich của hàm giá trị tối ưu của V và điều kiện
đủ cho tính chất Aubin (tính giả Lipschitz) của ánh xạ nghiệm S.


3

2. Mục đích nghiên cứu
Tìm hiểu về lý thuyết quy hoạch toán học, điều khiển tối ưu tuyến
tính rời rạc, tính ổn định của tập nghiệm và hàm giá trị tối ưu.

3. Nhiệm vụ nghiên cứu
Nghiên cứu về dưới vi phân Fréchet và dưới vi phân Mordukhovich;
lý thuyết quy hoạch toán học, điều khiển tối ưu tuyến tính rời rạc; trình

· . Với một không gian Banach bất kì X, ta xét không gian đối ngẫu
của nó X ∗ với tôpô yếu∗ được kí hiệu bởi w∗ . BX và BX ∗ kí hiệu tương
ứng là hình cầu đơn vị đóng trong không gian Banach X và không gian
đối ngẫu của nó. Kí hiệu A∗ toán tử liên hợp của toán tử tuyến tính liên
tục A. Hình cầu đóng tâm x bán kính ρ được kí hiệu bởi Bρ (x).
Với mỗi tập Ω ⊂ X, cl Ω, int Ω, co Ω và cone Ω kí hiệu tương ứng
là bao đóng, phần trong, bao lồi và nón lồi sinh của Ω. Ta nhắc lại rằng
Ω ∈ X là đóng địa phương tại x¯ ∈ Ω nếu có một lân cận U của x¯ sao
cho Ω ∩ clU là tập đóng.
Cho F : X ⇒ X ∗ ánh xạ đa trị từ một không gian Banach X vào
không gian đối ngẫu X ∗ của X. Giới hạn trên theo dãy theo nghĩa
Painlevé - Kuratowski đối với tôpô chuẩn của X và tôpô yếu* của X ∗


5

tại x¯ được xác định bởi
w∗

Lim sup F (x) := {x∗ ∈ X ∗ : ∃ xk → x¯, x∗k −→ x∗ , x∗k ∈ F (xk ), ∀k ∈ N}.
x→¯
x

(1.1)
Định nghĩa 1.1. (Nón pháp tuyến) Cho Ω là tập con khác rỗng trong
không gian Banach X, x¯ ∈ Ω và ε

0.

(i) Tập các ε - véctơ pháp tuyến Fréchet của Ω tại x¯ được xác định bởi


Ω

x→¯
x
ε↓0

hay
Ω

w∗

N (¯
x; Ω) := x∗ ∈ X ∗ : ∃εk → 0, xk → x¯, x∗k → x∗ , x∗k ∈ Nεk (xk ; Ω) ∀k ,
ở đó có thể đặt ε = 0 khi Ω là tập đóng trong lân cận của x¯ và X là
không gian Asplund.

Bổ đề 1.1. (Tích Đề các) [6, Proposition 1.2] Lấy tùy ý điểm x¯ =
(¯
x1 , x¯2 ) ∈ Ω1 × Ω2 ⊂ X1 × X2 . Khi đó
N (¯
x; Ω1 × Ω2 ) = N (¯
x1 ; Ω1 ) × N (¯
x2 ; Ω2 ),

(1.4)

N (¯
x; Ω1 × Ω2 ) = N (¯
x1 ; Ω1 ) × N (¯

x; Ω).

(1.8)

Định lý 1.1. (Tính chính quy của tập lồi địa phương) [6, Proposition 1.5] Cho U là một lân cận của x¯ ∈ Ω ⊂ X sao cho tập Ω ∩ U là
lồi. Khi đó Ω chính quy tại x¯ với
N (¯
x; Ω) = {x∗ ∈ X ∗ | x∗ , x − x¯

0, ∀x ∈ Ω ∩ U }.

(1.9)

Tiếp theo chúng ta sẽ trình bày hai dạng biểu diễn tương đương
của nón pháp tuyến Mordukhovich trong không gian hữu hạn chiều Rn
(trong trường hợp này X ∗ = X = Rn ). Do tất cả các chuẩn trong không
gian hữu hạn chiều là tương đương nên ta có thể chọn chuẩn Euclid
x =

x21 + ... + x2n ,

x ∈ Rn .

Cho một tập không rỗng Ω ⊂ Rn . Khoảng cách từ x đến Ω được xác
định bởi
dist(x, Ω) := inf x − u , x ∈ Rn
u∈Ω

và hình chiếu Euclid của x trên Ω
Π(x; Ω) := {¯

Ω

(u1 ,u2 )→(0,0)

u21 + u22

≤ 0.

(1.12)

Lấy (uk1 , uk2 ) = (1/k, 0) ∈ Ω, k ∈ N, ta có (uk1 , uk2 ) → (0, 0) khi k → ∞.
Từ (1.12) ta có
0 ≥ lim sup
k→∞

x∗1 uk1 + x∗2 uk2
(uk1 )2

+

(uk2 )

= x∗1 .

Do đó x∗1 ≤ 0. Lấy (uk1 , uk2 ) = (−1/k, 0) ∈ Ω, k ∈ N, ta có (uk1 , uk2 ) → 0,
khi k → ∞. Từ (1.12), ta có
0 ≥ lim sup
k→∞

x∗1 uk1 + x∗2 uk2


1.2.

Đối đạo hàm của ánh xạ đa trị

Cho F : X ⇒ Y ánh xạ đa trị giữa các không gian Banach X và Y.
Tập xác định và đồ thị của F được kí hiệu bởi
domF := {x ∈ X | F (x) = ∅},

gphF := {(x, y) ∈ X × Y | y ∈ F (x)}.

Định nghĩa 1.3. Cho F : X ⇒ Y với domF = ∅.
(i) Lấy (¯
x, y¯) ∈ X × Y và ε ≥ 0. ε−đối đạo hàm của F tại (¯
x, y¯) được
định nghĩa là ánh xạ đa trị Dε∗ F (¯
x, y¯) : Y ∗ ⇒ X ∗ với các giá trị
Dε∗ F (¯
x, y¯)(y ∗ ) := x∗ ∈ X ∗ : (x∗ , −y ∗ ) ∈ Nε ((¯
x, y¯); gphF )

(1.13)

là ε - đối đạo hàm của của F tại (¯
x, y¯). Nếu (¯
x, y¯) ∈
/ gphF , ta đặt
x, y¯)(y ∗ ) = ∅ với mọi ε
Dε∗ F (¯



Lưu ý rằng đối đạo hàm Mordukhovich cũng có thể được biểu diễn
qua nón pháp tuyến Mordukhovich
D∗ F (¯
x, y¯)(y ∗ ) = {x∗ ∈ X ∗ : (x∗ , −y ∗ ) ∈ N ((¯
x, y¯); gphF )}.

(1.16)

Nếu F (x) = {f (x)} là ánh xạ đơn trị thì ta viết D∗ f (¯
x) thay cho
D∗ f (¯
x, y¯) và D∗ f (¯
x) thay cho D∗ f (¯
x, y¯).


9

Nhắc lại rằng một ánh xạ đơn trị f : X → Y là khả vi Fréchet tại
x¯ nếu có một toán tử tuyến tính liên tục ∇f (¯
x) : X → Y , được gọi là
đạo hàm Fréchet của f tại x¯, sao cho
f (x) − f (¯
x) − ∇f (¯
x), x − x¯
lim
= 0.
x→¯
x

f : R → R,

f (x) = |x|,

và ánh xạ đa trị F : R ⇒ R được cho bởi công thức
F (x) = {f (x)} = |x|,

∀x ∈ R.

Khi đó,
gphF = {(x, y) ∈ R2 |y = |x|}.
Tại điểm (¯
x, y¯) = (0, 0) ∈ gphF , ta có
D∗ F (¯
x, y¯)(y ∗ ) = {x∗ ∈ R|(x∗ , −y ∗ ) ∈ N ((0, 0); gphF )}
= {x∗ ∈ R|y ∗ ≥ |x∗ |}
∅ nếu y ∗ < 0,

=

[ − y ∗ , ; y ∗ ] nếu y ∗ ≥ 0.

và
∗

∗

D F (¯
x, y¯)(y ) =



−ε . (1.19)

Các phần tử của tập hợp ở vế trái công thức này được gọi là các ε− dưới
gradient Fréchet của f tại x¯, còn bản thân tập hợp đó được gọi là ε−
dưới gradient Fréchet của f tại x¯.
• Tập hợp
ˆ (¯
∂f
x) := ∂ˆ0 f (¯
x),
được gọi là dưới vi phân Fréchet dưới (thường gọi là dưới vi phân
ˆ (¯
Fréchet) của f tại x¯. Rõ ràng ∂f
x) ⊂ ∂ˆε f (¯
x) với mọi ε 0.

• Tập hợp
ˆ
∂ˆ+ f (¯
x) := −∂(−f
(¯
x)),
được gọi là dưới vi phân Fréchet trên của f tại x¯.
Định nghĩa 1.5. Tập hợp
∂f (¯
x) := Limsup ∂ˆε f (x),
f
x→
− x¯


• Tập hợp
∂ ∞ f (¯
x) := Limsup λ∂ˆε f (x),
f
x→
− x¯

(1.21)

ε,λ↓0

được gọi là dưới vi phân qua giới hạn suy biến (thường gọi tắt là
dưới vi phân suy biến) của f tại x¯. Như vậy x∗ ∈ ∂ ∞ f (¯
x) khi và chỉ
f
ˆ ε f (xk ) sao
khi tồn tại các dãy xk →
− x¯, εk ↓ 0, λk ↓ 0, và x∗ ∈ λk ∂f
k

cho

ω∗
x∗k −→

k

x∗ . Ta có thể chứng minh được rằng ∂ ∞ f (¯
x) = {0} nếu

∂ ∞ f (¯
x) = D∗ Φ(¯
x, f (¯
x))(0) = {x∗ ∈ X ∗ |(x∗ , 0) ∈ N ((¯
x, f (¯
x)); epif )} .
Ví dụ 1.3. Xét hàm ϕ : R → R được cho bởi công thức ϕ(x) = −|x|.
Ta có
epiϕ = {(x1 , x2 ) ∈ R2 |x2 ≥ −|x1 |},
hypoϕ = {(x1 , x2 ) ∈ R2 |x2 ≤ −|x1 |}.


12

Sử dụng kết quả ở Ví dụ 1.1 với Ω = epiϕ và x¯ = 0 ta thu được
N ((¯
x, ϕ(¯
x)); epiϕ) = {(0, 0)},
N ((¯
x, ϕ(¯
x)); epiϕ) = {(x∗1 , x∗ − 2) ∈ R2 |x∗2 = −|x∗1 |}.
Do hypoϕ là tập lồi, nên ta có
N ((¯
x, ϕ(¯
x)); hypoϕ) = {(x∗1 , x∗ − 2) ∈ R2 |x∗2 | ≥ |x∗1 |}.
Vì vậy,
∂ϕ(¯
x) = ∅,

∂ + ϕ(¯



13

• Ánh xạ đa trị F : X ⇒ Y được gọi là chính quy pháp tuyến tại
(¯
x, y¯) ∈ gphF nếu
D∗ F (¯
x, y¯)(y ∗ ) = D∗ F (¯
x, y¯)(y ∗ ) ∀y ∗ ∈ Y ∗ .
• Tập Ω ⊂ X là compắc pháp tuyến theo dãy (SNC) tại x¯ nếu với
Ω

mọi dãy εk ↓ 0, xk −
→ x¯ và x∗k ∈ Nεk (xk , Ω) có
ω∗

[x∗k −→ 0] ⇒ [ x∗k → 0] khi k → 0,
ở đó εk có thể bỏ qua nếu X là không gian Asplund và Ω là đóng
địa phương quanh x¯. Một ánh xạ đa trị F : X ⇒ Y là SNC tại
(¯
x, y¯) ∈ gphF nếu đồ thị của nó có thuộc tính đó.
• Ánh xạ đa trị F : X ⇒ Y là compắc pháp tuyến một phần theo
dãy (PSNC) tại (¯
x, y¯) nếu với mọi dãy (εk , xk , yk , x∗k , yk∗ ) ∈ [0, ∞) ×
(gphF ) × X ∗ × Y ∗ thoả mãn
ω∗

εk ↓ 0, (xk , yk ) → (¯
x, y¯), x∗k ∈ D∗k F (xk , yk )(yk∗ ), x∗k −→ 0, yk∗ → 0

14

Định lý 1.3. (Quy tắc tính tổng cho dưới vi phân) [6, Theo¯ i = 1, 2, ..., n
rem 3.36] Cho X là một không gian Asplund, fi : X → R,
là các hàm nửa liên tục dưới trong một lân cận của x¯ và có ít nhất một
hàm số là SNEC tại x¯. Giả sử rằng điều kiện sau được thỏa mãn
[x∗i ∈ ∂ ∞ fi (¯
x) , i = 1, ..., n, x∗1 + ... + x∗n = 0] =⇒ x∗1 = ... = x∗n = 0.
(1.22)
Khi đó ta có các bao hàm thức
∂(f1 + ... + fn )(¯
x) ⊂ ∂f1 (¯
x) + ... + ∂fn (¯
x),

(1.23)

∂ ∞ (f1 + ... + fn )(¯
x) ⊂ ∂ ∞ f1 (¯
x) + ... + ∂ ∞ fn (¯
x).

(1.24)

Hơn nữa, nếu tất cả fi là chính quy dưới tại x¯ thì tổng f1 + ... + fn cũng
chính quy dưới tại điểm đó, và bao hàm thức trong (1.23) trở thành đẳng
thức.
Xét bài toán tối ưu
min{f (x, y) | y ∈ Φ(x)}


x, y¯) ∩ (−N ((¯
x, y¯); gphΦ)) = {0}

(1.28)

được thỏa mãn. Khi đó ta có các bao hàm thức
∂µ(¯
x) ⊂

[x∗ + D∗ Φ(¯
x, y¯)(y ∗ ) | (x∗ , y ∗ ) ∈ ∂f (¯
x, y¯)), y¯ ∈ S(¯
x)] ,
(1.29)

∂ ∞ µ(¯
x) ⊂

[x∗ + D∗ Φ(¯
x, y¯)(y ∗ ) | (x∗ , y ∗ ) ∈ ∂ ∞ f (¯
x, y¯)), y¯ ∈ S(¯
x)] .
(1.30)

Hơn nữa, µ là chính quy dưới tại x¯ và (1.29) trở thành một đẳng thức
nếu Φ là đơn trị trong một lân cận của x¯, f chính quy dưới tại (¯
x, Φ(¯
x))
và một trong hai điều sau xảy ra
(a) dimY < ∞, Φ Lipschitz tại x¯ với gphΦ chính quy tại (¯

N −1

X = X × U, Ω =

N

Xk , K = C × Z × Ω.

Ωk , Z =
k=0

k=1

Khi đó, bài toán (Pw ) được viết lại như sau:
µ(w) =

inf
z∈G(w)∩K

f (z, w),

(2.1)


17

ở đó,
G(w) := {z = (x, u) ∈ X | Az = T w},
A : X −→ Z và T : W −→ Z được xác định lần lượt bởi Az =
(−A0 x0 +x1 −B0 u0 , −A1 x1 +x2 −B1 u1 , . . . , −AN −1 xN −1 +xN −BN −1 uN −1 )

Định lý 2.1. [3, Theorem 1.1] Giả sử hàm giá trị tối ưu được xác định
bởi (2.1) là hữu hạn tại w,
¯ hk là khả dưới vi phân Fréchet tại (¯
xk , u¯k , w¯k ),
hN là khả dưới vi phân Fréchet tại xN và Ωk là chính quy pháp tuyến tại
u¯k với mọi k = 0, 1, . . . , N − 1. Giả thiết rằng
[ − N ((¯
x, u¯); K)] ∩ A∗ (kerT ∗ ) = {0}.

(2.2)

∗
Khi đó điều kiện cần để w∗ = (w0∗ , w1∗ , . . . , wN
¯ là tồn tại x∗0 ∈
−1 ) ∈ ∂V (w)
∗
u; Ω) và z ∗ = (z1∗ , z2∗ , . . . , zN
)∈
N (¯
x0 ; C), u∗ = (u∗0 , u∗1 , . . . , u∗N −1 ) ∈ N (¯

Z ∗ sao cho


18


∂hk

∗

∂xk



∂h

k
∗

)(¯
xk , u¯k , w¯k ) = −u∗k − Bk∗ zk+1
(
∂uk

với k = 0, 1, . . . , N − 1,
∗
,
∇hN (¯
xN ) = zN

với k = 0, 1, . . . , N − 1,
với k = 0, 1, . . . , N − 1.

Điều kiện trên cũng là đủ để w¯ ∗ ∈ ∂V (w)
¯ nếu ta giả sử thêm rằng ánh
xạ nghiệm S : G−1 (K) ⇒ X có một lát cắt Lipschitz trên địa phương tại
(w,
¯ x¯, u¯).
Chú ý rằng nếu Tk là toàn ánh với mọi k = 0, 1, . . . , N − 1 khi đó
kerT = {0} và (2.2) được thỏa mãn. Vì vậy, cùng với Ví dụ 2.1 chỉ ra

Cho hàm giá trị tối ưu µ xác định bởi (2.3) là hữu hạn tại w¯ ∈ domS,
và giả sử x¯ ∈ S(w)
¯ sao cho ∂ + f (¯
x, w)
¯ = ∅. Giả sử K là chính quy pháp
tuyến tại x và
[ − N (¯
x; K)] ∩ A∗ (kerT ∗ ) = {0}.

(2.4)

Khi đó
[v ∗ + T ∗ ((A∗ )−1 (x∗ + u∗ ))].

∂µ(w)
¯ ⊂

(2.5)

x;K)
(x∗ ,v ∗ )∈∂ + f (¯
x,¯
v ) u∗ ∈N (¯

Nếu thêm vào giả thiết f là khả dưới vi phân Fréchet tại (¯
x, w)
¯ và ánh
xạ nghiệm S : G−1 (K) ⇒ X có một lát cắt Lipschitz trên địa phương tại
(w,
¯ x¯) thì


Lưu ý rằng
D∗ H(w,
¯ x¯)(x∗ ) = {w∗ ∈ W ∗ | (w∗ , −x∗ ) ∈ N ((w,
¯ x¯); gphH)},
ở đó gphH = {(w, x) ∈ W × X | x ∈ H(w)} = P ∩ Q với P := W × K và
Q := gphH. Tiếp theo ta phải tính đối đạo hàm Fréchet D∗ H(w,
¯ x¯)(x∗ ).
Bước 1 (Tính nón N ((w,
¯ x¯); Q). Ta cần khẳng định rằng
N ((w,
¯ x¯); Q) = {(−T ∗ z ∗ , A∗ z ∗ ) | z ∗ ∈ Z ∗ }.

(2.8)

Thật vậy, giả sử rằng ϕ : W × X −→ Z là hàm được xác định bởi
ϕ(w, x) = −T w + Ax với mọi (w, x) ∈ W × X. Khi đó, ϕ là một ánh xạ
tuyến tính liên tục và ánh xạ liên hợp của nó ϕ∗ : Z ∗ −→ W ∗ × X ∗ được


20

xác định bởi ϕ∗ (z ∗ ) = (−T ∗ z ∗ , A∗ z ∗ ) với mọi z ∗ ∈ Z ∗ . Khi Q là không
gian véctơ,
N ((w,
¯ x¯); Q)
= {(w∗ , x∗ ) ∈ W ∗ ×X ∗ | (w∗ , x∗ ), (w−w,
¯ x−¯
x) ≤ 0 ∀(w, x) ∈ Q}
= {(w∗ , x∗ ) ∈ W ∗ × X ∗ | (w∗ , x∗ ), (w, x) = 0 ∀(w, x) ∈ Q}

Thật vậy, lấy tùy ý (w∗ , x∗ ) ∈ N ((w,
¯ x¯); Q) ∩ [ − N ((w,
¯ x¯); P )]. Từ (2.8)
và (2.10) ta có w∗ = 0, −x∗ ∈ N (¯
x; K) và w∗ = −T ∗ z ∗ , x∗ = A∗ z ∗ với
một vài z ∗ ∈ Z ∗ . Do đó, điều kiện chính quy pháp tuyến thỏa mãn. Theo
[6, Corollary 3.5],
N ((w,
¯ x¯); P ∩ Q) = N ((w,
¯ x¯); P ) + N ((w,
¯ x¯); Q).