1
2
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
Công trình ñược hoàn thành tại
ĐẠI HỌC ĐÀ NẴNG
NGUYỄN VIẾT MINH
GIẢ JACOBIAN VÀ TỐI ƯU LIÊN TỤC
Người hướng dẫn khoa học: PGS.TS. Phan Nhật Tĩnh
Phản biện 1 : TS. Lê Hải Trung
Phản biện 2 : TS. Hoàng Quang Tuyến
Chuyên ngành: Phương pháp Toán sơ cấp
Mã số:
60 46 40
Luận văn ñược bảo vệ trước Hội ñồng chấm Luận văn
tốt nghiệp Thạc sĩ khoa học họp tại Đại học Đà Nẵng
vào ngày 30 tháng 6 năm 2011.
TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC
Đà Nẵng - 2011
* Có thể tìm hiểu luận văn tại :
- Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng
- Thư viện trường Đại học Sư phạm, Đại học Đà Nẵng.
3
Mở ñầu
4
Phạm vi nghiên cứu: nghiên cứu các tài liệu về giải tích lồi, giả
Jacobian trong và ngoài nước
1. Lý do chọn ñề tài
Bài toán tối ưu hóa là hình thức là làm tối ưu (nhỏ nhất hoặc lớn
nhất) một hàm mục tiêu với các ràng buộc nhất ñịnh. Công cụ chính ñể
nghiên cứu bài toán là phép tính vi phân của các hàm khả vi ñược xây
4. Phương pháp nghiên cứu
Thu thập các bài báo khoa học, các tài liệu của các tác giả nghiên
cứu liên quan ñến Giả Jacobian và tối ưu liên tục
Tham khảo thêm các tài liệu liên quan ñến ñề tài có trên mạng
dựng bởi Leibnitz và Newton vào thế kỉ 17. Trong những năm ñầu của
Internet
thế kỉ 21, hai nhà toán học V. Jeyakumar và Đ.T. Luc ñã ñề xuất khái
5. Ý nghĩa khoa học và thực tiễn của ñề tài
niệm giả Jacobian như là một mở rộng của khái niệm Jacobian cho các
Luận văn ñã trình bày một cách có hệ thống về một dạng ñạo hàm
hàm vectơ liên tục. Đây ñược xem như là một công cụ hiệu quả cho việc
suy rộng cho lớp các hàm vectơ liên tục, ñó là giả Jacobian. Đây là một
nghiên cứu các bài toán tối ưu liên tục. Như vậy, các vấn ñề về phép
dạng ñạo hàm suy rộng có tính tổng quát cao. Ngoài ra luận văn còn ñưa
tính các giả Jacobian và các ứng dụng của chúng trong bài toán tối ưu
ra các ñiều kiện cực trị cho các bài toán tối ưu. Do ñó, luận văn có thể
liên tục thực sự là một vấn ñề hiện ñại trong lý thuyết tối ưu, nó vừa
xem như là một tài liệu tham khảo cho sinh viên sư phạm và hệ cử nhân
mang tính thời sự, ñồng thời lại mang tính kế thừa sâu sắc và ñạt ñến
toán.
một trình ñộ khái quát cao. Từ những lí do ñó, chúng tôi quyết ñịnh
chọn ñề tài với tên: Giả Jacobian và tối ưu liên tục ñể tiến hành
nghiên cứu.
2. Mục ñích nghiên cứu
Mục ñích của luận văn là trình bày một cách có hệ thống, các kiến
thức cơ bản và quan trọng nhất về giả Jacobian.
6. Cấu trúc của luận văn
Ngoài phần mở ñầu và kết luận, luận văn ñược chia làm 3 chương.
Chương 1 sẽ trình bày những kiến thức cơ bản về giả Jacobian.
Trong chương này, ngoài việc chỉ ra các ñạo hàm suy rộng thường gặp
như Jacobian suy rộng Clarke, dưới vi phân của hàm lồi vô hướng, dưới
vi phân Michel-Penot là những trường hợp riêng của giả Jacobian,
Chứng minh chặt chẽ, chi tiết các ñịnh lí, mệnh ñề về mối quan hệ
chúng tôi cũng chứng tỏ rằng dưới vi phân của hàm vectơ lồi cũng là
giữa Jacobian và các loại ñạo hàm suy rộng khác ñồng thời xét một số
một giả Jacobian của hàm vectơ ñó. Đây là kiến thức bổ trợ cho chương
ví dụ ñiển hình của giả Jacobian trong tối ưu hóa.
2 và chương 3.
3. Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu: ñề tài nghiên cứu về giả Jacobian và tối ưu
liên tục
Chương 2 ñề cập ñến các quy tắc tính toán trong giả Jacobian, ñịnh
lí giá trị trung bình, khai triển Taylor và một số tính chất cơ bản của nó.
Chương 3 sẽ trình bày các ñiều kiện cực trị (ñiều kiện tối ưu cấp
một, ñiều kiện tối ưu cấp hai) cho các bài toán quy hoạch với các ràng
buộc khác nhau (ràng buộc ñẳng thức, ràng buộc bất ñẳng thức,…).
5
6
Cho φ :
Chương 1
Ma trận giả Jacobian
Trong chương này, chúng ta sẽ nhắc lại một số kiến thức ñã biết có
liên quan ñến giải tích lồi, giải tích vectơ ñồng thời nghiên cứu về khái
niệm giả Jacobian, một dạng ñạo hàm suy rộng của hàm vectơ liên tục.
Bố cục chương này như sau. Trong mục 1.1 chúng ta sẽ nhắc lại một số
kiến thức ñã biết và ñưa ra ñịnh nghĩa giả Jacobian, sau ñó là các tính
chất cơ bản của nó. Mục 1.2 nêu lên mối quan hệ giữa giả Jacobian và
một số ñạo hàm suy rộng khác cũng trong mục này ñưa ra khái niệm giả
Hessian của hàm vô hướng khả vi liên tục. Các khái niệm giả Jacobian
lùi xa và giả Jacobian riêng ñược nêu ở mục 1.3. Mục 1.4 dành cho việc
n
là một hàm số và x, u ∈
→
Dini trên của φ tại x theo hướng u kí hiệu φ + ( x, u ) , ñược xác ñịnh bởi
φ ( x + tu ) − φ ( x )
φ + ( x, u ) = lim sup
.
t ↓0
t
Tương tự như vậy, ñạo hàm theo hướng Dini dưới của φ tại x
theo hướng u kí hiệu φ − ( x, u ) ; ñược xác ñịnh bởi
φ ( x + tu ) − φ ( x )
φ − ( x, u ) = lim inf
.
t ↓0
t
Các giới hạn trên có thể nhận giá trị thực mở rộng - ∞ và + ∞ .
Khi φ + ( x, u ) = φ − ( x, u ) , thì các giá trị ñó ñược kí hiệu chung là
φ / ( x, u ) và gọi là ñạo hàm theo hướng của φ tại x theo hướng u . Nếu
ñiều này ñúng với mọi hướng u thì hàm φ ñược gọi là khả vi theo
hướng tại x .
n
Định nghĩa 1.1.1. Cho f :
∂f ( x ) ⊆ L
1.1. Định nghĩa và một số tính chất cơ bản
Cho L
(
,
m
)
là không gian ma trận thực cấp m × n , mỗi ma
n
trận M là một toán tử tuyến tính từ
x∈
n
có một ma trận M ( x ) ∈
m
→
m
. Ma trận chuyển vị của M kí hiệu
m
là M và cũng coi như là một toán tử tuyến tính từ
viết vM, với v ∈
L
(
n
,
m
m
→
n
, ñôi khi ta
) với chuẩn tuyến tính như sau
= Sup
M ( x) .
trong ñó M1 , M 2 , …, M n ∈
ñóng ñơn vị của không gian L
2
+ M2
m
(
2
+ ... + M n
,
m
gồm các ma trận cấp m × n ñược gọi là giả
( vf ) ( x, u ) ≤
+
sup
M ∈ ∂f ( x )
n
và với mọi v ∈
m
v, M ( u ) .
, ta có
(1.1)
m
trong ñó vf là hàm thực xác ñịnh bởi vf := v, f =
∑v f .
i i
i =1
Mỗi phần tử của ∂f ( x ) ñược gọi là một ma trận giả Jacobian của
Mệnh ñề 1.1.2. (i) Một tập ñóng ∂f ( x ) ⊆ L
2
(
n
,
m
) là một ma trận
giả Jacobian của f tại x nếu và chỉ nếu với mọi u ∈
,
là n cột của ma trận M . Hình cầu
n
)
là hàm vectơ liên tục. Tập ñóng
Jacobian chính quy của f tại x .
Chuẩn ở ñây tương ñương với chuẩn Euclide
M1
,
m
f tại x . Nếu dấu ñẳng thức ở (1.1) xảy ra thì ∂f ( x ) ñược gọi là giả
x ≤1
M =
m
→
Jacobian của f tại x nếu với mọi u ∈
thay vì viết M tr ( v ) . Chúng ta trang bị trên
M
(
n
, vì vậy với mỗi vectơ
tr
. Đạo hàm theo hướng
1.1.1. Giả Jacobian
nghiên cứu một số tính chất của ánh xạ giả Jacobian
n
n
) ñược kí hiệu bằng B
mn
.
v∈
m
, ta có ( vf )
−
( x; u ) ≥ M inf
∈ ∂f ( x )
(
⊆ L(
(ii) Nếu ∂f ( x ) ⊆ L
tập con ñóng A
n
n
,
,
và với mọi
(1.2)
) là giả Jacobian của f tại x , thì mọi
) chứa ∂f ( x ) ñều là giả Jacobian của
m
m
v, M ( u ) .
n
8
7
Cho u ∈
f tại x .
(iii) Nếu {∂ i f ( x )}i =1 ⊆ L(
∞
n
,
m
) là một dãy giảm các giả Jacobian bị
∞
chặn của f tại x , thì I ∂ i f ( x) cũng là một giả Jacobian của f tại x .
i =1
1.1.2. Đạo hàm Gâteaux, ñạo hàm Fréchet và ñạo hàm chặt
Giả sử rằng f :
n
→
m
, ta nói rằng f khả vi Gâteaux tại x nếu
có một ma trận M cấp m × n sao cho với mọi u ∈ , ta có
f ( x + tu ) − f ( x)
lim
= M (u ) .
t ↓0
t
Khi ñó M ñược gọi là ñạo hàm Gâteaux của f tại x .
Nếu f khả vi Gâteaux tại x thì ñạo hàm Gâteaux M của nó trùng
với ma trận Jacobian ∇f ( x) của f tại x.
f ( x + u ) − f ( x ) − M (u )
= 0 . Nó ñược gọi
Khi ma trận M thỏa mãn lim
u →0
u
là ñạo hàm Fréchet của f tại x và f gọi là khả vi Fréchet tại x .
n
Mệnh ñề 1.1.3. Cho f :
n
→
m
là hàm vectơ liên tục, khả vi Gâteaux
tại x , khi ñó {∇f ( x)} là một giả Jacobian của f tại x . Ngược lại, nếu
f là một giả Jacobian tại x chỉ gồm một phần tử thì f khả vi
Gâteaux tại ñiểm ñó và ñạo hàm Gâteaux của nó trùng với ma trận giả
Jacobian này.
Mệnh ñề 1.1.4. Cho f :
n
→
m
v∈
[ ∇f ( x ) ]
tr
m
có ma trận M
(v ) = M
tr
(v) .
, ñạo hàm Clarke theo hướng của hàm số φ tại x theo
hướng u ñược ký hiệu φ o ( x; u ) và xác ñịnh bằng
φ ( x '+ tu ) − φ ( x ')
.
φ o ( x; u ) := lim sup
t ↓ 0 x '→ x
t
Dưới vi phân Clarke của φ tại x ñược kí hiệu ∂ Cφ ( x ) và xác ñịnh bởi
{
}
∂ Cφ ( x ) = ξ ∈ n : ξ , u ≤ φ o ( x; u ) , với u ∈ n .
Một chú ý của tính chất dưới vi phân này là một tập lồi, compact trong
n
và φ o ( x; u ) thỏa mãn φ o ( x; u ) = max
ξ , u với mọi u ∈ n .
C
ξ ∈∂ φ ( x )
n
Giả sử f :
→
m
là hàm Lipschitz gần x. Khi ñó Jacobian suy
rộng Clarke của f tại x, kí hiệu là ∂ C f ( x ) và xác ñịnh bởi
{
}
∂ C f ( x ) := co lim ∇f ( xi ) : xi ∈ Ω, xi → x ,
i →∞
trong ñó Ω là tập tất cả các ñiểm của U mà tại ñó f khả vi.
{
}
Tập hợp ∂ B f ( x ) := lim ∇f ( xi ) : xi ∈ Ω, xi → x ,
i →∞
ñược gọi là B-dưới vi phân của f tại x.
Mệnh ñề 1.1.5. Cho f :
n
→
m
là hàm Lipschitz gần x. Khi ñó
Jacobian suy rộng Clarke ∂ f ( x ) của f tại x là một giả Jacobian của
C
f tại ñiểm này.
1.2. Giả vi phân và giả Hessian của những hàm vô hướng
là hàm vectơ liên tục, khả vi Gâteaux
tại x và ∂f ( x) là một giả Jacobian bị chặn của f tại x , khi ñó với
mỗi
n
của bao lồi co∂f ( x) sao cho
Trong trường hợp riêng khi m = 1 ta có
∇f ( x) ∈ co∂f ( x) .
1.1.3. Jacobian suy rộng Clarke
Hàm φ : n → ñược gọi là Lipschitz gần x nếu tồn tại lân cận U
ñóng ∂f ( x ) ⊆
với mọi x1 , x2 ∈U
n
n
→
là hàm liên tục. Ta nói rằng tập con
là một giả vi phân của hàm f tại x nếu xem như
một tập con của L
(
n
,
) thì nó là một giả Jacobian của
f tại x.
Như vậy ∂f ( x ) là một giả vi phân của hàm f tại x khi và chỉ khi
f + ( x, u ) ≤ sup ξ , u và f − ( x, u ) ≥ inf ξ , u , ∀u ∈ n .
ξ ∈∂f ( x )
ξ ∈∂f ( x )
1.2.1. Dưới vi phân của hàm lồi
Cho f :
của x và một hằng số k > 0 sao cho
φ ( x1 ) − φ ( x2 ) ≤ k x1 − x2
Định nghĩa 1.2.1. Cho f :
n
→
∪ {∞} là một hàm vô hướng có giá trị thực mở
rộng. Miền xác ñịnh hữu hiệu của f là tập
10
9
{
dom( f ) = x ∈
n
}
và trên ñồ thị của nó là một tập hợp
epi( f ) =
{( x, t ) ∈
n
∂ MP f ( x ) := {ξ ∈
: f ( x) < +∞
×
Mệnh ñề 1.2.4. Cho f :
}
: f ( x) ≤ t .
tập hợp ∂
Dưới vi phân của f (theo ñịnh nghĩa của giải tích lồi) là một tập
{
∂ ca f ( x ) = ξ ∈
n
: ξ , u ≤ f / ( x; u ) , với mọi u ∈
n
}.
ñịnh hữu hiệu của f , khi ñó
n
tồn
tại và ñược xác ñịnh bởi
f ( x0 + tu ) − f ( x0 )
f ( x0 + tu ) − f ( x0 )
f / ( x0 ; u ) = lim
= inf
.
t ↓0
t >0
t
t
Mệnh ñề 1.2.3. Giả sử rằng f :
n
→
∪ {∞} là một hàm lồi và cho x
là ñiểm thuộc miền xác ñịnh hữu hiệu của
∂ ca f ( x ) của f tại x trùng với tập của vectơ ξ ∈
f . Dưới vi phân
n
xác ñịnh
ξ ,u ≤ f ( x + u ) − f ( x ) , với mọi u ∈ .
Dưới vi phân này cũng trùng với dưới vi phân của Clarke. Do ñó dưới
vi phân ∂ ca f ( x ) cũng là một giả vi phân của f tại x.
n
là một hàm Lipschitz gần x. Khi ñó
f ( x ) là một giả vi phân của hàm f tại ñiểm này.
hàm ∇f
→
n
là hàm khả vi liên tục. Ánh xạ ñạo
n
là hàm vectơ liên tục từ
∂ f ( x) ⊆ L
(
n
,
n
n
vào
. Tập con ñóng
) gồm các ma trận vuông cấp n ñược gọi là một giả
là hàm liên tục. Đạo hàm theo hướng Michel-
Penot trên của f tại x theo hướng u ñược xác ñịnh bởi
f ( x + tz + tu ) − f ( x + tz )
f o ( x; u ) := sup limsup
t
t ↓0
z∈ n
và ñạo hàm theo hướng Michel-Penot dưới của f tại x theo hướng u
ñược xác ñịnh bởi
f o ( x; u ) := infn liminf
t ↓0
f ( x + tz + tu ) − f ( x + tz )
t
Dưới vi phân Michel-Penot của f tại x là tập hợp
này.
Giả Hessian cũng có các tính chất như giả Jacobian.
Mệnh ñề 1.2.6. Cho f :
(i)
Nếu ∂ 2 f ( x ) ⊆ L
(
n
n
→
,
n
)
là hàm khả vi liên tục. Khi ñó
là một giả Hessian của hàm f tại x ,
thì mọi tập con ñóng A ⊆ L
(
n
,
n
)
chứa ∂ 2 f ( x ) là một giả
Hessian của hàm f tại x .
{
}
(ii) Nếu f là khả vi Gâteaux hai lần tại x thì ma trận ∇ 2 f ( x ) là
một giả Hessian của hàm f tại x. Hơn nữa, f là khả vi Gâteaux
hai lần tại x nếu và chỉ nếu nó có một giả Hessian chỉ gồm một
phần tử tại x .
1.3. Ma trận giả Jacobian lùi xa và giả Jacobian riêng
1.2.2. Dưới vi phân Michel-Penot
z∈
}.
Hessian của hàm f tại x nếu nó là một giả Jacobian của ∇f tại ñiểm
ii) Đạo hàm theo hướng của hàm f tại x0 theo hướng u ∈
→
→
n
1.2.3. Giả Hessian
2
i) f Lipschitz gần x0.
n
MP
: f o ( x; u ) ≥ ξ , u với mọi u ∈
n
Định nghĩa 1.2.5. Cho f :
Mệnh ñề 1.2.2. Cho f là hàm lồi, x0 là một ñiểm trong của miền xác
Cho f :
n
.
1.3.1. Ma trận giả Jacobian lùi xa
Cho A ⊆
n
là một tập không rỗng. Nón lùi xa của tập hợp A kí
hiệu A∞ và ñược xác ñịnh bởi
{
}
A∞ := lim ti ai : ai ∈ A, ti ↓ 0 .
Mỗi phần tử của A∞ gọi là một hướng lùi xa của tập hợp A .
Giả sử rằng f : n → m là hàm vectơ liên tục. Cho ∂f ( x ) là giả
Jacobian của f tại x. Khi ñó nón lùi xa của ∂f ( x ) , kí hiệu là ( ∂f ( x ) )∞
12
11
ñược gọi là giả Jacobian lùi xa của f tại x. Mỗi phần tử của ( ∂f ( x ) )∞
Mệnh ñề 1.3.5. Cho f :
ñược gọi là một ma trận giả Jacobian lùi xa của f tại x.
cho ∂f ( x, y ) ⊂ L
Mệnh ñề 1.3.1.
Bổ ñề 1.3.2.
Khi ñó ta có
n
Bây giờ giả sử rằng f :
→
m
liên tục. Gọi ∂f ( x ) là giả
Jacobian của hàm f tại x. Khi ñó ( ∂f ( x ) )∞ biểu thị như một nón lùi xa
của ∂f ( x ) . Phần tử của ( ∂f ( x ) )∞ gọi là ma trận lùi xa của ∂f ( x ) .
Mệnh ñề 1.3.3. Giả sử rằng ∂f ( x ) là một giả Jacobian của hàm f tại
x. Khi ñó (i) ∂f ( x ) bị chặn nếu và chỉ nếu ( ∂f ( x ) )∞ = {0} ;
hai biến ( x, y ) ∈
n1
×
n2
n2
hàm x → f ( x, y ) với y ∈
→
m
n2
(
n2
,
n1
m
)
{ (
Proj Q := { N ∈ L (
Projx Q := M ∈ L
(
n1
n1
,
m
)
của
của hàm
,
m
n2
,
m
y
Mệnh ñề 1.3.4. Cho f :
n1
∂f ( x, y ) ⊂ L
m
(
n1
×
n2
,
) , ta kí hiệu
) : sao cho ∃N ∈ ( , ) , ( MN ) ∈ Q} ,
) : sao cho ∃M ∈ ( , ) , ( MN ) ∈ Q} .
×
×
n2
n2
,
→
m
m
n2
m
n1
m
) là một giả Jacobian của
f tại (x,y).
Projx ( ∂f ( x, y ) )∞ ⊂ ( Projx ∂f ( x, y ) )∞ ;
(
)
∞
.
1.4. Ánh xạ giả Jacobian nửa liên tục trên
1.4.1. Ánh xạ ña trị nửa liên tục trên
Một ánh xạ ña trị F từ
ánh xạ từ
n
n
m
vào
n
, kí hiệu là F :
vào họ tất cả các tập con của
{( x, y ) ∈
n
×
m
m
là một
m
}
: y ∈ F ( x) .
F ñược gọi là bị chặn ñịa phương tại x ∈
y → f ( x, y ) ñược gọi là giả Jacobian riêng của f tại (x,y) theo biến y.
Cho tập con Q ⊂ L
m
là một hàm vectơ liên tục và
n
×
m
ñược
x∈ n
không ñổi ñược gọi là giả Jacobian riêng
tại (x,y) theo biến x, và ∂ y f ( x, y ) ⊂ L
của f
(
,
m
Tập hợp Im ( F ) := U F ( x ) , ñược gọi là ảnh của ánh xạ ña trị F.
là một hàm vectơ liên tục theo cả
. Giả Jacobian ∂ x f ( x, y ) ⊂ L
n2
xác ñịnh bởi graph ( F ) :=
1.3.2. Giả Jacobian riêng
×
×
→
n2
Proj y ( ∂f ( x, y ) )∞ ⊂ Proj y ∂f ( x, y )
(iii) Nếu ∂f ( x ) là tập lồi và 0 ∈ ∂f ( x ) thì ( ∂f ( x ) )∞ ⊂ ∂f ( x ) .
n1
n1
×
Đồ thị của ánh xạ ña trị F là tập hợp graph ( F ) ⊂
(ii) Nếu ∂f ( x ) là tập lồi thì ∂f ( x ) = ∂f ( x ) + ( ∂f ( x ) )∞ ;
Giả sử rằng f :
(
n1
n
nếu tồn tại lân cận U
của x sao cho tập hợp F (U ) = U F ( x ) là tập bị chặn.
x∈U
Ánh xạ ña trị F ñược gọi là nửa liên tục trên tại x nếu với mọi
ε > 0 , tồn tại số δ > 0 sao cho
F ( x + δ Bn ) ⊆ F ( x ) + ε Bm .
Khi F là ánh xạ ñơn trị thì tính nửa liên tục trên theo ñịnh nghĩa
trên chính là tính liên tục theo nghĩa thông thường.
Cho F : n m là một ánh xạ ña trị. Giới hạn trên KuratowskiPainleve của F tại x ñược xác ñịnh bởi
lim sup F ( x ') := {lim yi : yi ∈ F ( xi ) , xi → x khi i → ∞} .
x '→ x
Giới hạn trên này ñược kí hiệu F ( x ) . Từ các ñịnh nghĩa trên cho
là một hàm vectơ liên tục. Nếu
) là một giả Jacobian của hàm
f tại (x,y)
thì Projx ∂f ( x, y ) là một giả Jacobian riêng của f tại (x,y) theo biến x,
và Proj y ∂f ( x, y ) là một giả Jacobian riêng của f tại (x,y) theo biến y.
ta thấy rằng F ( x ) là một tập ñóng.
Mệnh ñề 1.4.1. Cho F :
n
m
là một ánh xạ ña trị nhận giá trị
compact và nửa liên tục trên. Khi ñó nếu A là một tập compact trong
n
thì F ( A ) = U F ( x ) cũng là tập compact trong
x∈A
m
.
13
14
Mệnh ñề 1.4.2. Giả sử rằng F là bị chặn ñịa phương tại x, khi ñó ánh
Chương 2
xạ ña trị G xác ñịnh bởi
Các quy tắc tính toán trên giả Jacobian
F ( x ') neáu x ' ≠ x
G ( x ') =
F ( x ) neáu x ' = x
2.1. Quy tắc cơ bản
là nửa liên tục trên tại x. Hơn nữa, nếu F bị chặn ñịa phương thì ánh xạ
2.1.1. Tích vô hướng và tổng
ña trị F là nhỏ nhất theo quan hệ bao hàm trong lớp các ánh xạ ña trị
Định lí 2.1.1. Cho f và g :
nửa liên tục trên nhận giá trị ñóng và chứa F.
∂f ( x ) và ∂g ( x ) lần lượt là các giả Jacobian của f và g tại x thì
n
→
m
n
. Khi
ñó ánh xạ ña trị x a ∂f ( x ) ñược gọi là ánh xạ giả Jacobian của f .
Định lí 1.4.4. Cho ∂f là một ánh xạ giả Jacobian của f . Khi ñó các
(i)Nếu ∂f là bị chặn ñịa phương tại x thì ánh
∇f ( x ) ∈ ∂f ( x ) khi ∇f
x∈
n
.
f
sao cho
tồn tại, khi ñó ∂ f ( x ) ⊆ ∂f ( x ) với mọi
B
vào
. Khi ñó với mỗi x ∈
∂
C
(f
n
, ta có
+ g )( x ) ⊆ ∂ f ( x ) + ∂ C g ( x ) .
C
2.1.2. Tích Decartes
n
→
m
n
n
và g :
vào
m +l
→
l
, kí hiệu f × g ñược
, xác ñịnh bởi
tục. Nếu ∂f ( x ) ⊆ L
(
n
n
,
Jacobian của hàm f
→
m
m
và g :
n
→
) và ∂g ( x ) ⊆ L (
l
n
,
là các hàm vectơ liên
l
) lần lượt là các giả
và g tại x thì ∂f ( x ) × ∂g ( x ) cũng là giả
Jacobian của hàm f × g tại x.
là Lipschitz ñịa phương . Nếu ∂f là
một ánh xạ giả Jacobian nửa liên tục trên của
n
Định lí 2.1.3. Cho f :
ánh xạ giả Jacobian nửa liên tục trên chứa ∂f .
→
;
( f × g )( x ) = ( f ( x ) , g ( x ) ) .
(ii) Nếu ∂f là bị chặn ñịa phương, thì ∂f là nhỏ nhất trong tất cả các
m
từ
sử dụng ñể chỉ hàm vectơ từ
là nửa liên tục trên tại x.
Mệnh ñề 1.4.5. Cho f :
là các hàm vectơ liên tục. Nếu
Mệnh ñề 2.1.2. Giả sử rằng f và g là hai hàm Lipschitz ñịa phương
Với hàm vectơ f :
xạ giả Jacobian I f xác ñịnh bởi
∂
f ( x ') neáu x ' ≠ x
I f ( x ') =
∂f ( x ) neáu x ' = x
n
m
(ii) cl ( ∂f ( x ) + ∂g ( x ) ) là giả Jacobian của f + g tại x.
là một hàm vectơ liên tục và
∂f ( x ) là một giả Jacobian cho trước của f tại x, với mọi x ∈
khẳng ñịnh sau ñúng.
→
(i) α∂f ( x ) là giả Jacobian của f tại x với mọi α ∈
1.4.2. Ánh xạ giả Jacobian
Định nghĩa 1.4.3. Cho f :
n
2.1.3. Tích và thương
Định lí 2.1.4. Cho f , g :
n
→
là hàm liên tục. Cho ∂f ( x ) và
∂g ( x ) lần lượt là các giả vi phân của f và g tại x. Nếu một trong các
tập ∂f ( x ) và ∂g ( x ) bị chặn hoặc ít nhất một trong các giá trị f ( x )
và g ( x ) khác không khi cả hai tập ∂f ( x ) và ∂g ( x ) không bị
chặn, thì bao ñóng của tập hợp f ( x ) ∂g ( x ) + g ( x ) ∂f ( x ) là giả vi
phân của hàm tích fg tại x.
16
15
Định lí 2.1.5. Cho f , g : n →
là hàm liên tục với g ( x ) ≠ 0 . Cho
∂f , ∂g lần lượt là các giả vi phân của f và g tại x. Khi ñó bao ñóng
của tập
g ( x ) ∂f ( x ) − f ( x ) ∂g ( x )
g
2
( x)
tại x.
Mệnh ñề 2.1.6. Cho f , g :
ta có
∂
C
,là giả vi phân của hàm thương
n
f
g
→
là hàm Lipschitz ñịa phương. Thì
Mệnh ñề 2.2.2. Cho a, b ∈
( fg )( x ) ⊆ f ( x ) ∂ g ( x ) + g ( x ) ∂ f ( x )
g ( x)∂ f ( x) + f ( x)∂ g ( x)
C
C
2
( x)
n
lượt ñược xác ñịnh như sau: f ( x ) := max { fi ( x ) : i = 1,..., k } và
n
→
. Khi
lần
g ( x ) := min { f i ( x ) : i = 1,..., k }.
Kí hiệu I ( x ) là tập của tất cả các chỉ số i ∈ {1,..., k} sao cho
fi ( x ) = f ( x ) và J ( x ) là tập của tất cả các chỉ số j ∈ {1,..., k } , sao
cho f j ( x ) = g ( x ) .
Định lí 2.1.8. Giả sử rằng ∂f1 ( x ) ,..., ∂f k ( x ) lần lượt là giả vi phân của
n
n
{
n
và f :
phương. Khi ñó f ( b ) − f ( a ) ∈ co∂ C f
→
([ a, b])}( b − a ) .
m
là hàm Lipschitz ñịa
([ a, b])}( b − a ) .
n
và f :
→
là hàm liên tục. Giả sử
2.2.2. Đặc trưng của hàm Lipschitz ñịa phương
Như phần trước ñã nêu, ánh xạ ña trị G :
2.2. Định lí giá trị trung bình và khai triển Taylor
2.2.1. Định lí giá trị trung bình
n
→
m
là hàm vectơ liên tục.
Giả sử rằng với mỗi x ∈ [ a, b ] , ∂f ( x ) là một giả Jacobian của hàm f
{ ([ a, b]) ( b − a )} ,
(
n
,
m
) ñược gọi
liên tục trên tại x và bị chặn, thì G là bị chặn ñịa phương tại x.
Mệnh ñề 2.2.5. Cho f :
n
→
m
là hàm vectơ liên tục. Khi ñó f có
một ánh xạ giả Jacobian bị chặn ñịa phương tại x nếu và chỉ nếu f
Lipschitz gần x.
x, y ∈
∂ C f ( x ) ⊆ co U ∂ C fi ( x ) .
i∈I ( x )
L
dương α sao cho A ≤ α , với mọi A ∈ G (U ) . Rõ ràng, nếu G là nửa
Mệnh ñề 2.1.9. Giả sử rằng f1 ,..., f n là hàm Lipschitz ñịa phương. Khi
i∈I ( x )
n
là bị chặn ñịa phương tại x nếu tồn tại một lân cận U của x và một số
2.2.3. Khai triển Taylor
tại x. Khi ñó f ( b ) − f ( a ) ∈ co ∂f
{
trên ñoạn [ a, b ] . Khi ñó f ( b ) − f ( a ) ∈ co∂f
hàm f1 ,..., f k tại x. Thì U ∂fi ( x ) là một giả vi phân của hàm f tại x.
và cho f :
là hàm vectơ liên tục,
k →∞
ñó hàm max và hàm min của chúng là các hàm f và g :
n
m
tồn tại c ∈ ( a, b ) và dãy {ξ k } ⊂ co ( ∂f ( c ) ) sao cho
f ( b ) − f ( a ) = lim ξ k , b − a .
, khi g ( x ) ≠ 0.
Định nghĩa 2.1.7. Cho fi , i = 1,..., k là các hàm liên tục trên
Định lí 2.2.1. Cho a, b ∈
→
n
và f :
rằng với mỗi x ∈ [ a, b ] , ∂f ( x ) là một giả vi phân của f tại x. Khi ñó
2.1.4. Hàm max và hàm min
ñó
n
giả sử ∂f là ánh xạ giả Jacobian bị chặn và nửa liên tục trên của f
Mệnh ñề 2.2.4. Cho a, b ∈
C
g
([ a, b]) ( b − a ) = {M ( b − a ) : M ∈ ∂f ( x ) , x ∈ [ a, b]} .
Mệnh ñề 2.2.3. Cho a, b ∈
C
∂ C ( f g )( x ) ⊆
ở ñây ∂f
Định lí 2.2.6. Cho f :
n
n
→
là hàm khả vi liên tục trên
x, y ∈
và
. Giả sử với mỗi z ∈ [ x, y ] , ∂ f ( z ) là giả Hessian của f tại
2
ñiểm này. Khi ñó tồn tại c ∈ ( x, y ) sao cho
1
f ( y ) ∈ f ( x ) + ∇f ( x ) , y − x + co ∂ 2 f ( c )( y − x ) , y − x .
2
n
→
là hàm khả vi liên tục trên
Hệ quả 2.2.7. Cho f :
n
n
n
và
. Giả sử với mỗi z ∈ [ x, y ] , ∂ f ( z ) là giả Hessian lồi của f
2
tại ñiểm này. Khi ñó tồn tại c ∈ ( x, y ) và M ∈ ∂ 2 f ( c ) sao cho
1
f ( y ) = f ( x ) + ∇f ( x ) , y − x + M ( y − x ) , y − x .
2
18
17
3.2. Điều kiện tối ưu cấp một
Chương 3
Một số ứng dụng giả Jacobian
trong tối ưu
3.2.1. Bài toán với ràng buộc ñẳng thức
n
Cho U là một tập con mở trong
, cho f , h1 ,...hm : U →
là các
hàm nhận giá trị thực. Ta xét bài toán quy hoạch với m ràng buộc ñẳng
Trong chương này, sử dụng các kết quả của những chương trước ñể
thức mà ñược kí hiệu là (PE):
f ( x)
nêu lên ñiều cần cực trị của các hàm vectơ liên tục. Bố cục chương này
Min
bao gồm các mục như sau. Mục 3.1 nêu lên các ñịnh lí ñiều kiện cần ñể
Với ñiều kiện
hàm vectơ ñạt cực trị ñịa phương. Mục 3.2 ñiều kiện tối ưu cấp một sẽ
hi ( x ) = 0, i = 1,..., m ,
Hàm vectơ với các thành phần hi , h2 ,..., hm ñược kí hiệu h . Hàm f ñược
ñược ñưa ra ñối với bài toán tối ưu với dữ kiện là một hàm vectơ liên
gọi là hàm mục tiêu và tập ràng buộc (hay tập chấp nhận ñược) của bài
tục. Mục 3.3 dành cho việc nêu lên ñiều kiện tối ưu cấp hai cho bài toán
toán, kí hiệu là C ñược xác ñịnh bởi
C = { x ∈U : hi ( x ) = 0, i = 1,..., m} .
tối ưu với dữ kiện là khả vi liên tục.
3.1. Điều kiện cần của cực trị của hàm vectơ liên tục
Cho f :
n
→
là hàm vectơ liên tục. Điểm x0 ñược gọi là cực
tiểu ñịa phương của f nếu có một lân cận U của x0 trong
n
sao cho
f ( x ) ≥ f ( x0 ) với mọi x ∈U .
Mỗi phần tử của C ñược gọi là ñiểm chấp nhận ñược.
Điểm x ∈ C ñược gọi là nghiệm ñịa phương của bài toán (PE) nếu
tồn tại lân cận V của x sao cho f ( x ) ≤ f ( x ) với mọi x ∈V ∩ C .
Ta kí hiệu:
Sau ñây là một số ñiều kiện cần cho cực tiểu ñịa phương.
Định lí 3.1.1. Nếu x0 là cực tiểu ñịa phương của f
giả vi phân của f tại x0, thì
và ∂f ( x0 ) là một
Lagrange hay ñiều kiện tối ưu Fritz-John.
(i) ∇f ( x0 ) = 0 , khi f là hàm khả vi Gâteux tại x0 ;
(ii) 0 ∈ ∂ MP f ( x0 ) , khi f là hàm Lipschitz ñịa phương tại x0.
n
→
n
và cho
là hàm vectơ liên tục. Nếu x ∈ C là ñiểm cực tiểu ñịa
phương của f trên C và ∂f ( x ) là một giả vi phân của f tại x, thì
sup ξ , u ≥ 0, ∀u ∈ T ( C , x ) .
ξ ∈∂f ( x )
Trong ñó T ( C , x ) = cl {t ( c − x ) : c ∈ C , t ≥ 0} là nón tiếp xúc của C tại
x0.
Trong ñó ∂h ( x ) là giả Jacobian của h tại x. Định lí sau cho ta ñiều
toán (PE). Đôi khi ñiều kiện này còn ñược xem như là quy tắc nhân tử
Mệnh ñề 3.1.2. Nếu x0 là cực tiểu ñịa phương của f , thì
f:
)
kiện cần ñể một ñiểm chấp nhận ñược là nghiệm ñịa phương của bài
0 ∈ co∂f ( x0 ) .
Định lí 3.1.3. Cho C là một tập lồi khác rỗng trong
(
∂%h ( x ) := co∂h ( x ) U co ( ∂h ( x ) )∞ \ {0} .
Định lí 3.2.1. Xét bài toán (PE) trong ñó f và h là các hàm liên tục
trên U. Giả sử thêm rằng hàm F = ( f , h ) có ∂F là ánh xạ giả jacobian
nửa liên tục trên tại x ∈U và x là một nghiệm ñịa phương của bài
toán (PE). Khi ñó tồn tại các số λ0 ≥ 0, λ1 ,..., λm không ñồng thời bằng
0 sao cho
(
(
))
0 ∈ λ o co∂F ( x ) U co ( ∂F ( x ) )∞ \ {0} ,
trong ñó λ = ( λ0 ,..., λm ) .
20
19
Mệnh ñề 3.2.2. Xét bài toán (PE), cho F = ( f , h ) là hàm Lipschitz gần
0
∂f ( 0 ) = 2α
2
2α
x ∈U và x là một nghiệm ñịa phương của bài toán (PE). Khi ñó tồn tại
các số λ0 ≥ 0, λ1 ,...λm không ñồng thời bằng 0 sao cho
0 ∈ ∂ C ( λ o F )( x ) .
trong ñó λ = ( λ0 , λ1 ,..., λm ) .
( ∂f ( 0) )∞
Đối với các nhân tử Lagrange mà ở ñó thành phần λ0 = 0 sẽ rất ít
ñược quan tâm, vì nó không chứa một thông tin nào có liên quan ñến
hàm mục tiêu f. Chính vì vậy mà người ta cố gắng ñưa ñến những kết
quả mà ở ñó nhân tử Lagrange có thành phần λ0 khác không. Điều kiện
ñể có nhân tử Lagrange như vậy thường ñược gọi là ñiều kiện KuhnTucker hay ñiều kiện chính quy. Mệnh ñề sau cho ta một ñiều kiện
Mệnh ñề 3.2.3. Với các giả thuyết của ñịnh lí 3.2.1 và bổ sung thêm
giả sử hệ m vectơ lấy từ m dòng cuối của các phần tử của ∂%F ( x ) ñều
ñộc lập tuyến tính. Khi ñó tồn tại các số λ1 ,..., λm sao cho
0 ∈ λ o ∂%F ( x ) với λ = (1, λ ,..., λ ) .
1
m
x3 + x42
2 x12/3 sgn
2 x11/3
Cho f = ( f 0 , f1 , f 2 ) , ở ñây
0
mỗi
M ∈ co∂f ( 0 )
có
bậc
0 1
0 −2 : β ≥ 0 .
0 0
tối
ña.
Vì
vậy
( λ0 , λ1 , λ2 ) o M ≠ 0 , với mọi ( λ0 , λ1 , λ2 ) ≠ 0 . Nhưng với bất kì ma trận
N ∈ ( ∂f ( 0 ) )∞ , (1,1,0 ) o N = 0 . Do ñó theo kết luận của ñịnh lí 3.1.1 thì
x = 0 là một nghiệm tối ưu ñịa phương của bài toán.
3.2.2. Bài toán với ràng buộc ñẳng thức và bất ñẳng thức
f , gi , h j :
n
→ , i = 1,..., p;
j = 1,..., q là các hàm nhận giá trị thực. Ta xét bài toán sau kí hiệu là (P)
( x1 ) + x24 − 2 x3 = 0
f1 ( x1 , x2 , x3 , x4 ) = 2 x12/3 sgn ( x1 ) + x24 − 2 x3 = 0
f 2 ( x1 , x2 , x3 , x4 ) = 2 x11/3 + x22 − 2 x4 .
Ta ñang quan tâm ñến ñiểm x = 0, rõ ràng tại ñó f liên tục nhưng
không Lipschitz . Giả Jacobian của f tại 0 và nón suy thoái tại ñó ñược
f ( x)
Min
gi ( x ) ≤ 0, i = 1,... p
Với ñiều kiện
+ x22 − 2 x4 .
f 0 ( x1 , x2 , x3 , x4 ) = x3 + x42
xác ñịnh bằng
ràng,
0
0
0 : α ≥ 1 ∪ 0
β
0 − 2
0 1
0 −2
ñẳng thức và bất ñẳng thức. Cho
Xét bài toán sau :
Với ñiều kiện
0
∂% f ( 0 ) = co 2α
2
2α
Trong phần này ta sẽ nghiên cứu bài toán quy hoạch với ràng buộc
Ví dụ 3.2.1.
Min
Do ñó,
Rõ
chính quy của bài toán (PE).
0
0 : α ≥ 1 ,
0 0 − 2
0 0 1
= 0 0 −2 : β ≥ 0 ,
β 0 0
0 1
0 −2
(
)
(
h j ( x ) = 0, j = 1,...q
)
Ta kí hiệu g = g1 ,..., g p , h = h1 ,..., hq và F = ( f , g , h ) . Dưới ñây là
một quy tắc nhân tử cho bài toán (P).
Định lí 3.2.4. Giả sử F liên tục và có ánh xạ giả Jacobian ∂F ( x ) là
nửa liên tục trên tại x ∈
n
. Nếu x là một nghiệm tối ưu ñịa phương
của bài toàn (P), thì tồn tại vectơ khác không (α , β , γ ) ∈ ×
(
)
trong ñó α ≥ 0, β = β1 ,..., β p với βi ≥ 0 sao cho
p
×
q
22
21
βi gi ( x ) = 0, i = 1,..., p
Và
(
Ta ñã biết phần trước rằng nếu f , g và h là các hàm khả vi liên
)
0 ∈ (α , β , γ ) o co∂F ( x ) U co ( ∂F ( x ) )∞ \ {0} .
tục và x0 là một nghiệm tối ưu ñịa phương của bài toán (P), thì ñiều kiện
Mênh ñề 3.2.5. Giả sử rằng F là Lipschitz ñịa phương và x là một
nghiệm tối ưu ñịa phương của bài toán (P). Khi ñó tồn tại một vectơ
khác không (α , β , γ ) ∈ ×
p
×
q
(
kiện sau thỏa mãn.
Hệ q vectơ lấy từ q dòng cuối của mỗi phần tử của ∂%F ( x ) ñều ñộc
lập tuyến tính.
(ii) Với phần tử M ∈ ∂% F ( x ) với các hàng là M0, M1,…, Mp+q, tồn tại
sao cho
( β ,γ ) ∈
p
β = ( β1 ,..., β p ) với βi ≥ 0 , sao cho
βi gi = 0, i = 1,..., p
và
×
q
trong ñó
(
)
0 ∈ (1, β , γ ) co∂F ( x ) U co ( ∂F ( x ) )∞ \ {0} .
→
, g:
n
→
vectơ
p
và h :
n
khác
không
sao cho
λ0∇f ( x0 ) + λ , ∇g ( x0 ) + µ , ∇h ( x0 ) = 0 ,
λ0 ≥ 0, λi ≥ 0 và λi g i ( x0 ) = 0, i = 1,..., p .
Hessian và ma trận lùi xa.
Định lí 3.3.1. Giả sử rằng các ñiều kiện sau thỏa mãn
Các hàm f , g và h khả vi liên tục và x0 là một nghiệm ñịa phương
của bài toán (P);
(ii) Điều kiện Kuhn-Tucker thỏa mãn tại x0 với ( λ , µ ) ∈ p × q ;
(iii) ∂ 2 L ( x0 ) là một giả Hessian của L tại x0 . Khi ñó với mỗi
(
→
q
. Ta xét bài toán
)
∞
\ {0} sao cho
u, M ( u ) ≥ 0 .
Hơn nữa, nếu L có ánh xạ giả Hessian ∂ 2 L là nửa liên tục trên tại
quy hoạch (P) xác ñịnh bởi
Min
tại
u ∈ T0 ( X , x0 ) tồn tại M ∈ ∂ 2 L ( x0 ) U ∂ 2 L ( x0 )
3.3.1. Điều kiện cần
n
tồn
( λ , µ ) ∈ p × q . Ta kí hiệu
L ( x ) := f ( x ) + λ , g ( x ) + µ , h ( x ) ,
X := { x ∈ n : g ( x ) ≤ 0, λ , g ( x ) = 0 và h ( x ) = 0} ,
T ( X , x0 ) := {v ∈ n : v = lim ti ( xi − x0 ) , xi ∈ X , xi → x0 , ti > 0} ,
T0 ( X , x0 ) := {v ∈ n tồn tại δ > 0 sao cho x0 + tv ∈ X , t ∈ [ 0, δ ]} .
Hàm Lagrange L liên kết với nhân tử ( λ , µ ) , tập hợp X là tập tất cả
các ñiểm chấp nhận ñược thỏa mãn λi gi ( x ) = 0, i = 1,..., p , tập T ( X , x0 )
là nón tiếp xúc của X tại x0 và tập T ( X , x0 ) là tập tất cả các hướng
(i)
3.3. Điều kiện tối ưu cấp hai
Cho f :
là
(P). Các ñiều kiện này sẽ ñược biểu diễn bằng cách sử dụng ma trận giả
M i , v = 0 với j = p + 1,..., p + q .
tồn tại một vectơ
×
nghĩa
q
chấp nhận ñược của X. Ta thiết lập ñiều kiện tối ưu cấp hai cho bài toán
M i , v < 0 nếu gi ( x ) = 0, i ∈ {1,..., p} ,
Khi ñó
×
p
Khi λ0 = 1 ta thu ñược ñiều kiện tối ưu Kuhn-Tucker. Cho
tối ưu ñịa phương của bài toán (P). Giả sử rằng thêm rằng các ñiều
n
ñúng,
John
( λ0 , λ , µ ) ∈
)
Mênh ñề 3.2.6. Giả sử rằng F là Lipschitz ñịa phương và x là nghiệm
vectơ v ∈
Fritz
trong ñó α ≥ 0 , β = β1 ,..., β p với
βi ≥ 0 , γ = ( γ 1 ,..., γ p ) sao cho
βi gi ( x ) = 0, i = 1,..., p
0 ∈ (α , β , γ ) o ∂ C F ( x ) .
(i)
g ( x) ≤ 0 , h ( x) = 0 .
Với ñiều kiện
f ( x)
x0 thì kết luận trên cũng ñúng với mỗi u ∈ T ( X , x0 ) .
23
24
Định lí 3.3.2. Giả sử rằng bài toán (P) có một nghiệm ñịa phương là x0.
Thì ∂ 2 L xác ñịnh như trên là một ánh xạ giả Hessian của L nửa liên tục
Cho ñiều kiện Kuhn-Tucker thỏa mãn tại x0 với ( λ , µ ) ∈
sử rằng với mỗi x ∈
n
p
×
q
. Giả
, ∂ L ( x, λ , µ ) là một giả Hessian của L (., λ , µ )
2
tại x. Nếu ánh xạ ∂ L (., λ , µ ) bị chặn ñịa phương tại x0, thì với mọi
2
trên tại ( 0,0 ) . Ta có X :=
(
)
α
=
0
Ví dụ 3.3.1.
1 0
2
M =
∈ ∂ L ( 0,0 )
0 0
(
x4 3 − y 4
Với ñiều kiện
− x2 + y 4 ≤ 0 ,
Tập chấp nhận ñược của bài toán là
C=
Đặt
{( x, y ) ∈
2
} và nón lùi xa của ∂ 2 L ( 0,0 )
)
∞
\ {0} thì u , M ( u ) ≥ 0.
3.3.2. Điều kiện ñủ
Bây giờ ta xét ñiều kiện ñủ cho nghiệm của bài toán (P). Tập
nghiệm chấp nhận ñược của bài toán này kí hiệu là S, nón tiếp xúc của S
}
: − x2 + y 4 ≤ 0 .
f ( x, y ) = x 4 3 − y 4 và g ( x, y ) = − x 2 + y 4 . Có thể thấy rằng
x0 = ( 0,0 ) là một nghiệm ñịa phương của bài toán. Ta có
4 13
∇f ( x, y ) = x , −4 x 3 , ∇g ( x, y ) = −2 x, 4 y 3
3
(
)
Suy ra ∇f ( 0,0 ) + ∇g ( 0,0 ) = 0 , có nghĩa là ñiều kiện Kuhn-Tucker thỏa
mãn tại x0 = ( 0,0 ) . Hàm Lagrange ñược cho bởi
L ( x ) = x 4 3 − y 4 − x 2 + y 4 = x 4 3 − x 2 . Vì
4
ánh xạ gradient của L là ∇L ( x, y ) = x1 3 − 2 x,0 không Lipschitz gần
3
( 0,0 ) nên Hessian suy rộng của L tại ( 0,0 ) không tồn tại. Đặt
và
∞
}
: x 2 = y 4 . Nón tiếp xúc của X tại
0
: α ≥ 0 . Với u = ( 0, β ) ∈ T ( X , ( 0,0 ) ) , chọn
0
là ∂ 2 L ( 0,0 )
Min
2
x0 = ( 0,0 ) là T ( X , ( 0,0 ) ) = {( 0, β ) : β ∈
u ∈ T ( X , x0 ) tồn tại M ∈ ∂ 2 L ( x0 , λ , µ ) sao cho M ( u ) , u ≥ 0.
Xét bài toán
{( x, y ) ∈
4
2 3 − 2 0
2
∂ L ( x, y ) := 9 x
với x ≠ 0
0
0
α
0
2
∂ L ( 0, y ) :=
1 : α ≥ 2
0 − α
tại x ∈ S ñược kí hiệu bằng T ( S , x ) .
Định lí 3.3.4. Giả sử các ñiều kiện sau ñây thỏa mãn
(i)
Các hàm f , g và h là khả vi liên tục;
(ii) Điều kiện Kuhn-Tucker thỏa mãn tại x0 , với ( λ , µ ) ∈ p × q ;
(iii) Ánh xạ Giả Hessian ∂ 2 L của L là nửa liên tục trên tại x0 sao cho
với mọi
(
)
u ∈ T ( S , x0 ) \ {0} và M ∈ ∂ 2 L ( x0 ) U ∂ 2 L ( x0 ) \ {0} , ta
∞
có u , M ( u ) > 0. Khi ñó x0 là nghiệm ñịa phương của bài toán.
Ví dụ 3.3.2.
Xét bài toán
Min
− x4 3 − y 4
Với ñiều kiện
y4 − x2 = 0 .
Tập chấp nhận ñược của bài toán là
{
}
C = ( x, y ) ∈ 2 : y 4 − x 2 = 0 .
Đặt f ( x, y ) = − x 4 3 − y 4 và h ( x, y ) = y 4 − x 2 .f và h là các hàm khả vi
(
4 13
liên tục với ∇f ( x, y ) = − x , −4 x3 , ∇h ( x, y ) = −2 x, 4 y 3
3
)
25
26
Suy ra ∇f ( 0,0 ) + ∇g ( 0,0 ) = 0 , có nghĩa là ñiều kiện Kuhn-Tucker thỏa
Kết luận
mãn
tại
L ( x) = −x
43
x0 = ( 0,0 ) .
Hàm
− y − x + y = −x
4
2
4
43
Và
cho
bởi
− x . Và ánh xạ gradient của L là
4
∇L ( x, y ) = − x1 3 − 2 x,0 . Đặt
3
4
− 2 3 − 2 0
2
∂ L ( x, y ) := 9 x
0
0
−α
2
∂ L ( 0, y ) :=
0
ñược
Lagrange
2
ñạo hàm suy rộng cho lớp các hàm vectơ liên tục, ñó là giả Jacobian.
Đây là một dạng ñạo hàm suy rộng có tính tổng quát cao và mối quan hệ
giữa giả Jacobian và các loại ñạo hàm suy rộng khác cũng ñược trình
với x ≠ 0
0
: α ≥ 2
1
α
Khi ñó ∂ 2 L xác ñịnh như trên là một ánh xạ giả Hessian của L nửa liên
( 0,0 ) . Ta có nón tiếp xúc của C tại x0 = ( 0,0 ) là
T ( C , ( 0,0 ) ) = {( 0, β ) : β ∈ } , với mỗi u = ( 0, β ) ∈ T ( C , ( 0,0 ) ) mà
β ≠ 0 và với mỗi M ∈ ∂ 2 L ( 0,0 ) ta có
tục trên tại
u, M ( u ) =
β2
> 0 , do α ≥ 2 .
α
Tuy nhiên, ( 0,0 ) không phải là nghiệm ñịa phương của bài toán và ñiều
này hoàn toàn hợp lí khi ñiều kiện ñủ của bài toán không thỏa mãn ñối
với ma trận giả Hessian lùi xa. Thật vậy, ta có
−α 0
∂ 2 L ( 0,0 ) =
: α ≥ 0 .
∞
0 0
−1 0
2
Chọn M =
∈ ∂ L ( 0,0 ) ∞ \ {0} thì u , M ( u ) = 0.
0
0
(
)
(
)
Như vậy, luận văn ñã trình bày một cách có hệ thống về một dạng
bày trong luận văn này. Một phần không thể thiếu khi ñề cập ñến các
khái niệm ñạo hàm ñó là các quy tắc tính toán và ñối với giả Jacobian
cũng vậy, chúng tôi ñã lần lượt trình bày các quy tắc xác ñịnh giả
Jacobian cho tổng, hiệu, tích, thương, tích Decartes của các hàm vectơ
ñịnh lí giá trị trung bình, khai triển Taylor cho hàm vô hướng khả vi liên
tục. Đây chính là những công cụ ñể ñưa ñến các ứng dụng trong tối ưu
mà chúng tôi ñã trình bày trong phần cuối của luận văn.
Chúng tôi cho rằng việc ứng dụng giả Jacobian vào các hàm vectơ
liên tục là một vấn ñề mở và có thể phát triển theo nhiều hướng khác
nhau. Một trong các hướng ñó là có thể mở rộng các ñiều kiện tối ưu
cho các hàm vectơ thay vì các hàm vô hướng như ñã trình bày trong
luận văn.
Trên ñây là toàn bộ luận văn, tác giả ñã có rất nhiều có gắng nghiên
cứu và thực hiện. Tuy nhiên, do những hạn chế nhất ñịnh về trình ñộ
khoa học, thời gian thực hiện và phương pháp nghiên cứu nên chưa thể
thực hiện hết tất cả các ý tưởng liên quan ñến nội dung của luận văn. Hy
vọng trong thời gian tới tác giả sẽ giải quyết vấn ñề này trọn vẹn hơn.
Tác giả mong muốn luận văn sẽ phục vụ thiết thực cho sinh viên sư
phạm hệ cử nhân toán, xem như tài liệu tham khảo, ở hiện tại cũng như
tương lai.
- Xem thêm -