B Ộ G IÁ O D Ụ C V À Đ À O T Ạ O
TRƯỜNG ĐẠI HỌC s ư PH ẠM HÀ NỘI 2
----------------------- * -------------------------

N G U Y ỄN THỊ TH A NH 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: T o á n g iả i tíc h
M ã số: 60 4 6 01 02

L U Ậ N V Ă N TH Ạ C SỸ T O Á N HỌC

N g ư ờ i h ư ớ n g d ẫ n k h o a h ọc: P G S .T S .N g u y ễ n Q u a n g H u y

H à N ộ i-2 0 1 5


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.
Cuối cùng, tôi xin được gửi lời cảm ơn chân thành tới gia đình và
bạn bè đã động viên, giúp đỡ và tạo điều kiện về mọi mặt trong quá


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

Y

dom F

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

gphF

đồ thị của F

IIжII

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

Bỵ

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

B p(x)

hình cầu đóng tâm

X*

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

limsup


bán kính p

(nón pháp tuyến Mordukhovich) của íĩ tại X
N(x-, ri)

nón pháp tuyến Fréchet của ri tại X

df(x)

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

d°° f ( x )

dưới v i ph ân su y biến của / tạ i X

df(x)

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

D*F(x,ỹ)

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

D*F(x,ỹ)
n _

đối đạo hàm Préchet của F tại (x , ỹ )



1

1

K iế n th ứ c c h u ẳ n b ị

4

1.1. Nón pháp tuyến

4

1.2. Đối đao hàm của ánh xa đa tri

8

2

3

1.3. Dưới vi phân

10

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

12

D ư ớ i v i p h â n F ré ch et và d ư ới v i p h â n M o r d u k h o v ic h

MỞ ĐẦU
1. Lý do chọn đề tài
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

E hk(xk, u k, w k) + hN (xN),

(0.1)

k=0
t r ê n v é c t ơ đ iề u k h i ể n u — ( u q , U i , . . . W jv -i) G ư

N- 1
n Uk v à c á c q ũ y

k=0
N

đạo X = (x0, x i , . . . ,XN) ẽ I

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

lực
Xk + 1 = A kx k+ B kuk+ Tkw k với

mọi k= 0 , 1 , . . . , JV - 1,


là tập con khác rỗng trong Uk,

c

là tập con lồi đóng khác rỗng của

xữ,

Ak '■Xỵ —> x k+1, Bỵ : Uỵ —>■Xfc_|_i, T ỵ : Wỵ —> Xj .+ 1 là những ánh xạ
tuyến tính.
Bài toán này đã được nhiều nhà toán học quan tâm nghiên cứu;
chẳng hạn, xem Ị5Ị [8Ị [0] và các tài liệu được trích dẫn trong đó. Một
ví dụ cổ điển cho bài toán (0.1) (0.4) là bài toán ổn định kinh tế; xem
[81121.
Gọi S ( w ) là tập nghiệm của bài toán (Vw) tương ứng với tham số
N-1

w = (w 0, w u . . . WN- 1 ) e W : = Y l Wỵ.
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
Pré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.

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;
dưới vi phân Préchet và dưới vi phân Mordukhovich.

5. Phương pháp nghiên cứu
Sử dụng phương pháp nghiên cứu trong giải tích biến phân và đạo
hàm suy rộng, giải tích đa trị, đại số tuyến tính và lý thuyết tối ưu.

6. D ự kiến đóng góp của luận văn
Nội dung của luận văn trình bày công thức tính dưới vi phân Fréchet
và dưới vi phân Mordukhovich của hàm giá trị tối ưu trong điều khiển
tối ưu tuyến tính rời rạc; sử dụng kết quả đạt được như là công cụ để
thiết lập điều kiện đủ cho tính chất Aubin của ánh xạ nghiệm.


4

Chương 1
K iến thứ c chuẩn bị
1.1.

N ón pháp tu yến
Trong toàn bộ luận văn chúng ta sẽ sử dụng các khái niệm, kí hiệu

của giải tích biến phân và đạo hàm suy rộng; chi tiết đọc giả có thể tham
khảo bộ sách của Mordukhovich p , un]. Trừ khi phát biểu khác, tất cả
các không gian được xét là các không gian Banach với chuẩn kí hiệu bởi
II • II. 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*. B x và B x * 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


x*,x*k G F ( x k),Vk G N }.

x—^x

(1.1)

Đ ịn h n g h ĩa 1 .1 . (N ó n p h á p tu y ế n ) Cho Q ỉà tập con khác rỗng trong
không gian Banach X , X G íĩ và e ^ 0.
(i) Tập các £ - vécíơ p/ìáp tuyến Fréchet của fỉ tại X được xác định bởi
N e(x-, ri) :=

X € X

* ,
(x*,x — X)
: lim sup -Ỉ7——-----— ^ £
X —X
íỉ _
x^x

(1.2)

ở đó X A ’ X nghĩa là X —> X và X E fỉ. Khi £ = 0, ta có N ( x ; í ì ) :=
N ữ(x-, ri) nón pháp tuyến Fréchet của ri tại X.
(ii) Nón pháp tuyến Mordukhovich hay nón pháp tuyến qua giới hạn của
íĩ tại X là tập
N(x] ri) := Lim sup N e(x\ ri),

(1-3)

(1-5)


6

B ổ đ ề 1 .2 . (T ập cá c £— v é c tơ p h á p tu y ế n đ ố i vớ i tậ p lồ i) p ,
Proposition 1.3] Cho Q là một tập lồi trong không gian Banach X . Khi
đó,
N e (x; í ỉ ) : = {x* € X * : ( x * , x — x) ^ £ ỊỊíc — x || , V x € í ỉ } ,

với mỗi £ > 0 và X G

(1 .6 )

Trường hợp đặc biệt với £ = 0, ta có

N{x; Q) := {x* € X* : (x*, X - x) ^ 0, Vx € n } ,

(1.7)

là nón pháp tuyến trong giải tích lồi.
Đ ịn h n g h ĩa 1 .2 . (T ập c h ín h q u y p h á p tu y ế n ) Một tập
chính quy (pháp tu y ế n) tại X €

c X

là

nếu

—|x i|} và


x\ u\ 4- ^ 2^2
0 > lim SUD —
-----=
k->oo y j (u\ ) 2 + (uị)

*

— х л.

Do đó, ж* > 0. Vạy æï = 0. Do tính chất đối xứng của x\ và x *2 ta cũng
có x*2 — 0. Ngược lại, với (x\,x*2) = (0,0) thì (1.12)được thỏa mãn. Vậy
N { x \ ũ ) = {0 }. Vói (Xị,X 2 ) G ri, ía có
{0}
N { { x ị , z 2);fì)

nếu ( x i , x 2) ẽ intíỉ,

{(a, —a)\a > 0}
{(a, a)|a < 0}

nếu Xi = x 2,
nếu Xi = —x 2.

Khi đó, ta có
N(x-,íì)=

Lim sup N ( ( x i , x 2) \ rỉ)
(Ж1,ж2)—
>(0,0)


(1.14)

(ii) Đối đạo hàm Mordukhovich hay đối đạo hàm qua giới hạn của F tại
(x, ỹ) € gphF là ánh xạ đa trị D*F(x, ỹ) : Y*

X* xác định bởi

D*F( x, ỹ) ( ỹ*) := Limsup D*F(x, y) (y*) .
{x,y)^-{x,ỹ)
w*\ _
y*--->y*
eịo

(1.15)

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 ’) = К

6 X* : ự , - у ' ) € J V ((ä ,s);g p h F )}.

(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 , ỹ ) và D * f ( x ) thay cho D * f ( x , ỹ ) .


9

Nhắc lại


thì

D * f ( x ) ( y *) = ( V f ( x ) Ỵ ( y * )

V

G Y*

D*f(x)(y*) = (V /(ĩ))* (y * )

Vy* e Y*.

(1.17)

và

V í d ụ 1.2. X é t hàm số thực
/ : M —>■M,

f ( x ) = |ж|,

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

Mx € К.

Khỉ đó,
gphF = { (x , y ) G M2|y = ỊxỊ}.
Tại điểm (x, ỹ ) = (0,0) G gph-F, ta có


(1.18)


10

1.3.

Dưới vi phân
Cho X là không gian Banach và / : X —»• R hàm nhận giá trị trong

tập số th ự c suy rộng, hữu hạn tạ i X.
Đ ịn h n g h ĩa 1 .4 . Với mỗi E ^ ũ, đặt
â ,m

:= ụ

l

€ X* : lim inf я » ) - / ( g ) - <»’ . » - *) > _ л

x~*x

If —æl

J

. (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


Ta nhận thấy rằng

X*

E d f ( x ) khi và chỉ khi tồn tại các dãy

0, và x*k € ồfgkf ( x k ) sao cho x*ỵ —> X*. Hiển nhiên ta có
ỗ f(x) С df(x).

Xỵ

-4

X, Eỵ ị


11

• Tập hợp
d°°f ( x) := Limsup XÔef ( x ) ,
A7 -X
X —
£,AịO

(1-21)

đượ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 / tại X. Như vậy X* e



1) = {ж* к được cho bởi công thức
F được gọi là liên tục ở trên X .


13

• Ánh xạ đa trị F : X =4 Y được gọi là chính quy pháp tuyến tại
(ж, ỹ) € gphF nếu
D * F ( x : ỹ ) ( y *) = D*F( x, ỹ ) ( y*)

Vy* € y*.

• Tập ri С 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 G N Ek(xk, rỉ) có
[4

= И Н 4 Н -> °]

khi A; > 0,

ở đó £ỵ CÓ thể bỏ qua nếu X là không gian Asplund và ri là đóng
địa phương quanh X. Một ánh xạ đa trị F : X = ị y là SNC tại
( x , ỹ ) € g p h F nếu đồ th ị của nó có th u ộ c tín h đó.

• Ánh xạ đa trị F : X =4 Y là compắc pháp tuyến một phần theo
dãy (PSNC) tại (x , ỹ ) nếu với mọi dãy {е-ịk ,xk, y k,x*k, y l ) € [о, oo) X
(gphF) X X* X Y* thoả mãn
£k ị 0, {xk, y k) -> {x,ỹ),x*k e D*ekF ( x k, y k)(y*k),x*k
ta có \\xị\\

0, \\y*k\\0

[x*ị G d°°fi ( x ) , i = 1

, n, x{ + ... + x*n = 0]

X]

< = 0(1.22)

Khi đó ta có các bao hàm thức
d { h + ••• +

c d f i ( x ) + ... + d f n(x),

ỡ °°(/i + ... + fn)(x) c d ^ h i x ) + ... + d°°fn(x).
Hơn nữa, nếu tất cả fi là chính quy dưói tại

X

(1.23)
(1.24)

thì tổng / i + ... + 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
m in{ f { x , y ) I y

tại (x , y )hoặc Ф

/à SNC tại ( x, ỹ) và điều kiện chính quy
ỹ) П

ỹ); gplrô)) = {0}

(1.28)

được thỏa mẫn. Khi đó ta có các bao hàm thức
dụ,(x) c Ị J [x-- + 0 ' ф ( х . y)(y' ) I ( x \ y ' j € d f ( x . y ) ) , y

e S (ỉ)],
(1.29)

ỡ ° > ( â ) С I J b * + 0 'ф ( х , »)(»*) I (z * ,y ‘ ) € 3 “7 ( x , » )),!/ e S (x )].
(1.30)
Hơn nữa, ịi 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, ф(ж))

và một trong hai điều sau xảy ra
(a) d im y < oo; Ф Lipschitz tại X với gphф chính quy tại (X, ф(х)), hoặc
(b) Ф khả vi chặt tại X.




(w0, w 2, ■■■, W n - i) & w ta đặt
N- 1

f ( x , u , w ) = ^ 2 hk{xk,uk, w k) + hN(xN).
k=0
Giả sử
N- 1

X = X X u,n =

N

nk,z = Ỵ[xk,K = c
k=0

X

z X n.

k= 1

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

inf
z€G(w)nK

(2.1)


_ D*~*

-°0Zl5

_ D=*= *
_ D*
4
d 1z2 ì - - - 5 ^TV—
1^лг /

và
T

ở đó A* và

T*

/71**/Т1*\
* _ /Г71*
2 — (Ìq ^1? -М -^25 • • • 5^ N - \ Zn ) i

lần lượtlà cáctoán tử liên hợp của A và T.

Ta kí hiệu S ( w ) làtập nghiệm của bài toán (V w) và giả sử rằng (X, ũ)
là một nghiệm của ựPỹj) tức là (X, ũ) G S( w) ồ đó X := (xữ, X i , . . . , XN),
ũ := (й0, M l , , Wjv-i) và w := (w 0, Wị , . . . , WN- 1). Giả sử thêm rằng Qk
là bao đóng địa phương của Wỵ với mọi к — 0 , 1 , . . . , N — 1.
Kết quả chính của mục này là thiết lập đánh giá cho dưới vi phân
Fréchet của hàm giá trị tối ưu.
Đ ịn h lý 2 .1 . p , Theorem 1.1] Giả sử hàm giá trị tối ưu được xác định

Ẽ ^ ) { x k, ũ k, w k) = -z*k - A*kz*fe+i

với k = 0 , 1 , . . . , N — ĩ,

dhk
*
{ q ^ - ) { x k, ũ k, w k) = -u*k - Bịz*fe+
i

với k — 0 , 1 , . . . , N — 1.

Điều kiện trên cũng là đủ để
xạ nghiệm

s

W*

e d v ( ũ j ) nếu ta giả sử thêm rằng ánh

: G ~ l { K ) ^ X có một lát cắt Lipschitz trên địa phương tại

( w , X, ũ ) .

Chú ý rằng nếu Tk là toàn ánh với mọi k = 0 , 1 , . . . ,

iV — 1 khi

đó



(2.3)

xeG(w)nK

Đặt S ( w ) là tập nghiệm của bài toán (2.3) tương ứng với tham số w G w .
Giả sử rằng
w

tức là

X G

X

là một nghiệm của bài toán (2.3) tương ứng với tham số

S ( w ) và K là đóng địa phương tại

X.

Kết quả sau cho ta một công thức tính dưới vi phân Fréchet của
tại w.
Đ ịn h lý 2 .2 . p , Theorem 2.1]

ỊJL


19



+ »•))].

(2.6)

u*€N (х',к)
Chứng minh. Giả sử ĩ Ẽ S ( w ) và H ( w ) := G ( w ) п K . Khi đó ịi{w) =
inf

f ( x , w ) . Bởi Щ Theorem 1],

x e H (w )

dịi(w) С

Pl

[v*+ D*H(w,x)(x*)].

(2.7)

(x*,v*)ç.d+f (x,w)
Lưu ý rằng
D*H( w, x) ( x*) — {w* £ w * I (w*, —x*) £ N( ( w, x ) ; g p h . H) } ,
ỗ đó g p h # = { ( w , x ) G w X X I X G H ( w ) } = P n Q với p := w X к và
Q := gphiJ. Tiếp theo ta phải tính đối đạo hàm Fréchet D*H(ũj,x)(x*).
Bước 1 (Tính nón N ( ( w , x ); Q). Ta cần khẳng định rằng
N ((ũ), x); Q) = { ( - T*Z*,A*Z*) I

G z*}.

= (kery?)-1.
Bởi p , Proposition 2.173],
(ker^)1- = im^* = { ( - T V , i 4 V ) I z*