№
Bộ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2
■ • ■ •
* ШсМ)
HÀ THỊ THU THỦY
ĐIÈU KIÊN TỐI ƯU CHO BÀI TOÁN TỐI ƯU
KHÔNG LỒI
LUẬN VĂN THẠC Sĩ TOÁN HỌC
• • •
HÀ NỘI, 2014
Ш

ítũ
Bộ GIÁO DỤC VÀ ĐÀO TẠO
■ * • TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2
* CữcM)
HÀ THỊ THU THỦY
ĐIÈU KIÊN TỐI ƯU CHO BÀI TOÁN TỐI ƯU
KHÔNG LỒI
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. Đỗ Văn Lưu
HÀ NỘI, 2014
Btl rftl
LỜI CẢM ƠN
Trong quá trình học tập và làm luận văn, cùng với sự nỗ lực của bản thân, tôi đã
nhận được sự quan tâm, giúp đỡ tận tình của các thầy, cô giáo của phòng sau đại học
trường đại học Sư Phạm Hà Nội 2 và thầy PGS.TS. Đỗ Văn Lưu. Tôi xin bày tỏ lòng
biết ơn chân thành và sâu sắc tới PGS.TS. Đỗ văn Lưu, người thầy đã trực tiếp hướng
dẫn, dìu dắt và chỉ bảo, giúp đỡ tôi hoàn thành bản luận văn này. Tôi xin chân thành cảm

Mục đích nghiên cứu
• Đọc và dịch tài liệu trong cuốn sách “Nonsmooth Analysis” (2006) của
W.Schirotzek.
• Tham khảo các tài liệu có liên quan.
• Phân tích, tổng hợp làm rõ các điều kiện tối ưu cho bài toán tối ưu không
lồi.
Nhiệm vụ nghiên cứu
• Các điều kiện tối ưu cơ bản.
• Điều kiện tối ưu cho bài toán điểm mút cuối cố định của phép tính biến
phân.
5
• Điều kiện tối ưu cho bài toán quy hoạch toán học.
Đối tượng và phạm vi nghiên cứu
Luận văn trình bày các điều kiện cần tối ưu cho bài toán biến phân và bài
toán quy hoạch toán học dưới ngôn ngữ dưới vi phân Clarke, dưới vi phân
Michel- Penot và dưới vi phân Préchet được w. Schirotzek trình bày trong cuốn
sách chuyên khảo “ Nonsmooth Analysis” (2006).
Những đóng góp mới của đề tài
Tác giả mong muốn có cách nhìn tổng quát hơn về điều kiện tối ưu cho các
bài toán tối ưu không lồi và hoàn chỉnh bản luận văn của mình.
Phương pháp nghiên cứu
Đọc và nghiên cứu tài liệu để phân tích, tổng hợp các nội dung của đề tài
luận văn.
Chương 1
Kiến thức chuẩn bị
Chương 1 trình bày một số kiến thức cơ bản về các dưới vi phân Clarke,
Michel - Penot, Préchet và các điều kiện tối ưu cơ bản. Các kiến thức trình bày
trong chương này được tham khảo trong các tài liệu [1] - [ 5 ] .
6
1.1. Dưới vi phân Clarke, dưới vi phân Michel - Penot và


(1.3)
b) Với bất kì y £ E, ta có: f ° ( x , — y ) = ( — f )° ( x , y ) .
Chứng minh.
7
a) Cho Y

€ E

cố định, từ giả thiết ta có:
- ự ( x + Ty ) - f ( x ) ) < - X ị ị r y ị ị = A|Ịy|Ị
T T
với ||a: — ^11 và T > 0 đủ nhỏ. Do đó F°(X, Y

) < A||y||.
b) Ta có:
f ° { x , - ỳ ) = l i m s u p — [ / ( x - T y ) - f ( x ) ]
TịO T
= limsup - [ { - f ) {x + r y ) - (-/)(x)] = { - f ) ° ( x
:
y )
:
TịO
trong đó X = X — T y
□
Định nghĩa 1.3.
Nếu f là hàm Lipschitz địa phương tại X thì
d o f ( x ) : = {x * £ E * \ { x * , y ) < f°( x , y ) V y € E } được gọi là dưới vi
phẫn Clarke hoặc gradient suy rộng Clarke của f tại
X .

f ° ( x, у ) = m a x { ( x * , у)\х* G d
0
f ( x ) } (Чу G E ).
Chứng minh.
Ta có: G(Y

) = F°(X,Y

) là một hàm lồi, thuần nhất dương và Lipschitz trên D

nên
D

0
F(X)

= DG(0) = {X*

e E*

I(X*,Y) <

F°(X,Y)WY

G E}

khác
rỗng, lồi, compact yếu * và do mệnh đề 4.1.6 [4] ta có
F°{X,Y)


Giả sử rằng ( X k ) hội tụ đến X £ E khi к — > • o o và X* G E* là một
điểm tụ yếu* của ( x*
k
) . Khi đó X* G д о f ( x ) (Đồ thị của (do/ ) là một
tập con đóng yếu* của E X E*).
c) Ánh xạ dưới vi phân dof : E E* là nứa liên tục trên yếu*.
Chứng minh.
1
0
a) Lấy (XỴ

) và (Y

k
) là các dãy hội tụ về X e E

và Y G

E

tương ứng.
r
k
+ M\ yk- ỹ \\ -
Trong số hạng cuối л > 0 là hằng số Lipschitz của / tại X . Khi К

—> 00, từ
định nghĩa của giới hạn trên ta có limsup F°(X]

C

Cho К

—>

oo từ kết quả (a) ta có (X*,Y

) < F°(X,Y).
Do Y

G E

là bất kì, nên X * G D

0
F(X).
c) Ta có từ (b) ỡo/ là ánh xạ đóng. Từ mệnh đề 1.3 suy ra ỡo/ bị chặn địa
phương tại mọi X £ E.

Từ mệnh đề 4.3.2 [4] ta suy ra D

0

F

là nửa liên tục
trên yếu*.
□
Định lý 1.2. [3]
Nếu f : M " —> M là Lipschitz địa phương tại X và s с ш
п

)
1.1.2. Dtfdi vi phân Michel- Penot
Dinh nghïa 1.4.
Cho E là không gian Banach thuc, D Ç E là mô, x G D và f : D —ï №
_ l _ _
N é u y & E t h ï f ° ( x , y) \= sup\imsup—( f(x + r y + r z ) — f ( x + r z ))
dilôc
z e E t|0
T
goi là âao hàm Michel-Penot cüa f theo phUdng y tai x.
Dinh lÿ 1.3.
Cho f là Lipschitz âia phucfng tai x vâi hang so A > 0 . Khi dô,
a ) / ° ( x , . ) là duôi tuyén tinh và Lipschitz vâi hang so A trên E và
7H{X,V) <

Hz,.) < A||y|| (Vy e E),

(1.4)
trong dô f
H
( x , y ) = limsup ~ ( f { x + T Z ) - f ( x ) )
r ,|,0 T z—ïy
b ) V â i b â t kï y G E t a c ô : /
ô
(âf, —y ) = ( — f y ( x , y ).
Chûng minh.
a) Ta cô F°(X

:


ị 0 thì /°(ж, У) <

F°(X,

У), УУ

€ Е.
Cho У Е Е

CỐ

định, cho £ >

о, với mọi т > 0 đủ nhỏ và z € E

sao cho \\y —
z|| đủ nhỏ, ta có,
-ự{x + TZ) - f{x)) = -ự{x + ry + T{Z - y)) - f(x + T{Z - y))) r r
+ ỉ(/(z + г(г - у ) ) - f ( x )) т
< -(/(æ + ri/ + r(2-y)) - /(ж + T(Z
- У))) +

X\\Z

- У\\
< Г { х , у ) + е + Л||г - у \ \ .
Cho т ị о, 2: У


<

О,
0, nếu у > О ,
0, NẾU Y

< 0,
f * { n , v ) = ỉ ° { n , v ) = ị
Ị 2y, nếu y > 0,
Ta thấy rằng trong ba đạo hàm theo phương, hàm F

H

(

7T,.) là không
lồi.
1
3
Định nghĩa 1.5.
Nếu f l à hàm Lipschitz địa phương tại X thì
ỡ o f ( x ) : = { x * G E * \ { x * , y ) < f
0
( x , y ) \/y
£ E } được gọi là dưới vi phẫn Michel - Penot của f tại X .
Mệnh đề 1.5.
Nếu f là hàm Lipschitz địa phương tại X và À G R , ta có
d
0

cực đại địa phương của f thì O e d
ộ
f ( x ) .
Chứng minh.
Do D(—F)

= —DF

vì thế ta chỉ cần chứng minh cho cực tiểu là đủ.
Giả sử X là cực tiểu địa phương của /, thì với bất kì Y

€E E

ta có:
0 < sup lim inf — ự ( x + т у + T Z ) — f ( x + T Z ))
z e
E
T
i° T
< sup lim sup —(F(X

+ ТУ

+

TZ)

— F(X

+ TZ

và
ị
Sự hội tụ này là đồng đều theo V

trên các tập compact. Ta gọi Л là đạo
hàm Hadamard của / tại X và kí hiệu là
Mệnh đề 1.7.
Cho f là hàm Lipschitz địa phương tại X với hằng số Л > 0 . Khi đó,
a) Dưới vi phân d o f i x ) là khác rỗng, lồi và compact yếu* thỏa mãn:
ôof ( x ) С д о f ( x ) С В
Е
,(о, Л).
Ь) Та có:
Г{Х,У)

= тах{(ж*,;г/)|ж* G DOF(X)} {VY

G E)
Chứng minh.
Mệnh đề được chứng minh tương tự mệnh đề 1.3. □
1
5
Mệnh đề 1.8. [4]
a) Nếu f c { x , . ) tồn tại và là dưới tuyến tính trên E thì f
ữ
( x , y ) : =
f c { x , y ) với mỗi y G E . Dặc biệt nếu f là khả vi Gâteaux tại X thì
ỡ o / ( x ) = { f
r
G

E E*

sao cho
Ĩ G { ^ ) V = Ỉ G { Ẽ , y) ( V y e E).
b) / khả vi Hadamard tại X

khi và chỉ khi tồn tại F

H

(X)

E E*

sao cho
/я(®)г/ = Ỉ H { X , V ) (Vị/ E E ) .
Ví dụ 1.2.
Cho E

:= M và
Ỉx
2
sin — , nếu x ^ O ,
0, nếu X = 0
Khi đó / là Lipschitz địa phương và khả vi tại 0, với /# (0) = 0. Ta có /°(0, Y) =

0
với mỗi Y

e R và ôo/(0) = {0}.

dưới đạo hàm nhớt của f tại X
dp f i x ) = tập tất cả dưới gradient gần kề của f tại X
được gọi tương ứng là dưới vi phẫn Fréchet (F - dưới vi phẫn), dưới vi
phẫn nhớt và dưới vi phăn gần kề.
Mệnh đề 1.9. [4]
Giả sử E là không gian Banach, f : E —ì M là chính thường, nửa liên tục
dưới v à x E d o m f . K h i đ ó : d v f { x ) ç d p f i x ) .
Mệnh đề 1.10. [4]
Nếu hàm f : E — > M là chính thường, nửa liên tục dưới đạt cực tiểu địa
phương tại X, thì 0 G d
v
f { x ) v à do đ ó 0 G d
F
f ( x ) .
1
7
Định nghĩa 1.7.
Không gian Banach E được gọi là trơn Fréchet nếu nó nhận một chuẩn
tương đương mà khả vi Fréchet trên E \ { 0 } .
Định lý 1.4. [4]
Cho E là một không gian Banach trơn Fréchet, hàm f : E —> M là chính
thường, nửa liên tục dưới v à x E d o m f . K h i đó d y f ( x ) = d
F
f ( x ) .
Mệnh đề 1.11.
Cho E là một không gian Banach trơn Fréchet, hàm f : E M. là chính
thường, nửa liên tục dưới.
a) Nếu G - đạo hàm theo phương f ũ { x , . ) của f tại X G domf tồn tại trên
E, thì
Vx* G d

Khi đó tồn tại C

1

-

hàm G

số £ 0 sao cho
G'(X)

= X*

và với mỗi X

G В(Х,

E),

ta có:
(/ - g ) { x ) > (/ - g ) ( x ) , Va: G B ( x , e ) .
C h o y G E. K h i đ ó , v ớ i m ỗ i г > 0 đ ủ n h ỏ t a c ó X + т у G
в ( х , г ). Vậ y ~ ( f ( x + т у ) - f ( x ) ) > ~ ( д (х + т у ) - д ( х ) ) .
C h o r ị O s u y га f
G
{ x , y ) > { g '(x ) , y ) = { x *,y).
Nếu / là khả vi Gâteaux tại X

) c DPF(X

) c DPF{X),

Va: e DOMF.
C h o X * G d
F
f ( x ) .
Như trong chứng minh (a) cho G

và £

sao cho G'(X

) = X*

và với mỗi X

e
-B(x,È)

ta có: (/ — g)(x) > (/ — g)(x), Vx e -B(x,e).
Cho X € E.

Nếu T € (0,1) đủ nhỏ, thì (1 — r)x + raẼ -SỘẼ, e) và sử dụng
tính lồi của / ta có:
(l-T)/(®) + Tf(®) > /((l-r)x + ra:) > /(a:) + ^((l — r ) x + rx) — y(x)
g ( x + T ( X - x ) ) - g ( x )
S u y r a : f(x ) - f ( x ) >
T

là một nón.
Mệnh đề 1.12. [4]
Cho X là cực tiểu địa phương của f trên A.
2
0
f { x + T y ) - f ( x )
Ỉ G (
X
Ì y ) ■ = limsup
rịo
(G - đạo hàm theo phương trên)
r
f { x + T y ) - f ( x )
F H

{
X
1 Y ) :
= limsup
rịo
z - ỳ y
(H - đạo hàm theo phương trên)
T
a) Ta có f c {
x
, y ) > 0 với m ọ i y e T
r


và £

> 0. Khi đó tồn tại Y € A

sao cho \\Y

— z|| < ( Ỉ A {Z ) + £.
S u y r a : f(x ) + X d
A
( x ) = f(x ) < f ( y ) < f ( z ) + Ằ \ \ y - z \ \ < f ( z ) +
X d j ị 4 " A £ .
Cho £

ị 0 ta suy ra điều phải chứng minh. □
Nhắc lại:
Nón tiếp tuyến Clarke của tập A tại X £ A

là tập
T
C
{ A , X ) : = {y e E\\/x
k
- ^ x , x
k
e A , V r
f e
ị 0 , 3y
k
y M k \ X


:=

А

п B(X,

77). Khi đó
0 < ( / + X d
A
J ° ( x , y ) < + Xd°
Atì
My e E, ( 1 . 5 )
Theo mệnh đề 1.13 và định nghĩa đạo hàm theo phương Clarke.
Bởi vì T

C

(A

:

X

) = {Y

G E \D°

A


{ A , X ) cho nên 0 £ d
0
f ( x ) + N
C
( A , X ) □
Chương 2
Điều kiện tối líu cho bài toán điểm mút cuối cố
định của phép tính biến phân
Chương 2 trình bày các điều kiện tối ưu cho bài toán điểm mút cuối cố định
của phép tính biến phân cho các trường hợp trơn và không trơn. Các kiến thức trình
bày trong chương này được tham khảo trong
[4].
2.1. Phát biểu bài toán
Gọi £
p
[a, B](P

e [1, +oo)) là không gian véctơ của các hàm đo được Lebesgue
G

: [a, 6] —»• M sao cho \G\

P

khả tích Lebesgue trên [a, 6]; L°°

[a, 6] là không gian
véctơ các hàm đo được Lebesgue G :

[a, 6] —> M sao cho esssup |y(a:)| < +oo Kí

) !-»■ íp(t, X , V

) là liên tục trên Ị a , ỉ )]xM x K và có
đạo hàm riêng cấp 1 liên tục theo X và v \ cho a , b , a , ß là các số thực và A

<

b .
Nếu X G E

ta đặt:
ĩp{t) = (p{t,x{t),x(t)),t e [a,b].
Hàm / là khả vi Gâteaux (thậm chí khả vi liên tục) tại mỗi X G E

và
(/ớ(^)
5
y) = / (ф х ( * ) ' У { *) + Vv V ( t ) )
d t
> y
e
E
-
J a
Ta có:
T ( A , X ) = T
r
( A , x ) = {ĩỄ E \ x ( a ) = x ( b ) = 0} =: E
0
(2.2)


) = Ụ>

X

{T

), với hầu hết T

€ [a, &] (2.4)
Lấy tích phân số hạng đầu của vế trái công thức (2.3), ta nhận được:
[ ỢPv{t) - Q ( t ) ) . ỷ ( t ) d t = 0 , V ỉ / € E
0
. ( 2 . 5 )
J a
Bây giờ ta sử dụng bổ đề cơ bản sau đây của tính toán biến phân Bổ đề 2.1. (DU
BOỈS - REYMOND)
Giả sử g,h e ^ [ a , & ] và Ị ( h(t).y(t) + g ( t ). ỳ ( t ) ) d t = 0 , y & E
ữ
.Khi đó
J a
hàm g là tuyệt đối liên tục và thỏa mãn g(t) = h(t) với hầu hết t £ [a, &].
Áp dụng bổ đề 2.1 với H

= 0 cho (2.5) ta có kết quả sau:
Mệnh đề 2.1.
Giả sử giả thiết (A) thỏa mãn. Nếu X là một nghiệm địa phương của
(2.1) , thì tồn tại hàm tuyệt đối liên tục p : [ a , b ] M sao cho:
0
=

- đại số tất cả tập con Borel của R " , và £1 X B

N

là Ơ

- đại số tích tương ứng.
Cho X G M

ta giả thiết:
(^4) Hàm IP

: [a, B]

X M X R —»• M u {+00} là L\

X B

2
- đo được. Tồn tại £ >

0 và
một hàm dương G

€ c
l
[ a , b ] sao cho với hầu hết í Ễ [a, &], hàm (X, V

) I—^ IP{T