Chương 1
Dưới vi phân
1.1 Định nghĩa và kí hiệu
Định nghĩa 1.1. Cho f : R
n
→ R là một hàm lồi. Một véctơ g ∈ R
n
là
dưới gradient của f tại x ∈ R
n
nếu
f(x + δ) ≥ f(x) + δ
T
g, ∀x + δ ∈ R
n
. (1.1)
Định nghĩa 1.2. Tập tất cả dưới gradient của f tại x được gọi là dưới
vi phân của hàm f tại x, kí hiệu là ∂f(x), tức là:
∂f(x) = { g : f(x + δ) ≥ f(x) + δ
T
g, ∀x + δ ∈ R
n
} (1.2)
Kí hiệu:
∂f
(k)
= ∂f(x
(k)
), f
(k)
= f(x
(k)
).
Ví dụ 1.1. Cho f(x) = |x|. Khi đó
∂f(0) = [−1, 1],
∂f(x) =
{1} nếu x > 0
{−1} nếu x < 0.
5
Ví dụ 1.2. Cho f(x) = e
x
− 1. Khi đó
∂f(0) = [0, 1],
∂f(x) =
{e
x
} nếu x > 0
{0} nếu x < 0.
Định nghĩa 1.3. Hàm f được gọi là khả dưới vi phân tại x nếu tập
∂f(x) = ∅.
1.2 Một số tính chất cơ bản của dưới vi phân
Bổ đề 1.1. Dưới vi phân ∂f(x) là một tập đóng, tức là: nếu ta có dãy
x
(k)
→ x
, g
(k)
→ g
, g
(k)
∈ ∂f
(k)
thì g
∈ ∂f
.
Chứng minh. Lấy y ∈ K, vì g
(k)
∈ ∂f
(k)
nên với mọi k ta có
f(y) ≥ f
(k)
+ (y − x
(k)
)
T
g
(k)
. (1.3)
Trong (1.3) cho k → ∞ ta được
f(y) ≥ f
+ (y − x
)
T
g
, ∀ y ∈ K
suy ra g
∈ ∂f
.
Bổ đề 1.2. ∂f(x) là tập bị chặn với mọi x ∈ B ⊂ Int(K) trong đó
K ⊂ R
n
và B là tập compact.
Chứng minh. Giả sử ngược lại, khi đó tồn tại dãy g
(k)
∈ ∂f(x
(k)
) và dãy
x
(k)
∈ B sao cho g
(k)
2
→ ∞. Do tính compact nên tồn tại x
(k)
→ x
.
Định nghĩa
δ
(k)
=
g
(k)
g
(k)
2
2
.
6
Khi đó x
(k)
+ δ
(k)
∈ K với k đủ lớn và theo (1.1) ta có
f(x
(k)
+ δ
(k)
) ≥ f
(k)
+ g
(k)
T
δ
(k)
= f
(k)
+ 1.
Nhưng qua giới hạn thì
f
(k)
→ f
, δ
(k)
→ 0.
Vì vậy f(x
(k)
+ δ
(k)
) → f
. Mâu thuẫn.
Nhận xét 1.1.
i) Từ hai bổ đề trên suy ra ∂f(x) là một tập compact.
ii) Nếu f khả vi tại x thì
f(x + δ) = f(x) + δ
T
∇f(x)) + 0(δ)
mà
f(x + δ) ≥ f(x) + δ
T
g
nên
δ
T
(g − ∇f(x)) ≤ 0(δ).
Chọn δ = θ(g − ∇f(x)), θ ↓ 0 sao cho g = ∇f. Từ đây ta có ∂f(x) là
vectơ ∇f(x).
Bổ đề 1.3. Xét hàm đa trị
∂f : K → 2
K
(K ⊂ R
n
)
x −→ ∂f(x)
Khi đó hàm đa trị ∂f đơn điệu, tức là với mọi x
1
, x
2
∈ K luôn tồn tại
g
1
∈ ∂f(x
1
), g
2
∈ ∂f(x
2
) sao cho
(g
2
− g
1
)
T
(x
2
− x
1
) ≥ 0.
7
Chứng minh. Lấy x
1
, x
2
∈ K, g
1
∈ ∂f(x
1
), g
2
∈ ∂f(x
2
). Theo định
nghĩa của dưới vi phân ta có
f(x
2
) ≥ f(x
1
) + g
T
1
(x
2
− x
1
)
f(x
1
) ≥ f(x
2
) + g
T
2
(x
1
− x
2
).
Cộng hai bất đẳng thức trên ta được
(g
2
− g
1
)
T
(x
2
− x
1
) ≥ 0.
Xét lớp các hàm lồi đa diện h : R
m
→ R
1
, h(c) được định nghĩa bởi
h(c) = max
i
c
T
h
i
+ b
i
(1.4)
trong đó h
i
là các cột của ma trận hữu hạn H cho trước. Định nghĩa
A = A(c) = { i : c
T
h
i
+ b
i
= h(c) } (1.5)
là tập các siêu phẳng tựa tại c và do đó đạt giá trị lớn nhất. Khi đó dễ
dàng nhận thấy các siêu phẳng này xác định dưới vi phân ∂h(c). Điều
này được nêu trong bổ đề sau:
Bổ đề 1.4. ∂h(c) = conv
i∈A
h
i
Chứng minh. Ta có
∂h(c) = { λ : h(c + δ) ≥ h(c) + δ
T
λ,∀δ } (1.6)
Lấy λ ∈ conv
i∈A
h
i
, ta có λ =
i∈A
h
i
µ
i
với µ
i
≥ 0,
i∈A
µ
i
= 1. Khi
đó với mọi δ ta có
h(c) + δ
T
λ = max
i∈A
(c
T
h
i
+ b
i
) +
i∈A
δ
T
h
i
µ
i
≤ max
i∈A
(c
T
h
i
+ b
i
) + max
i∈A
δ
T
h
i
= max
i∈A
(c + δ)
T
h
i
+ b
i
≤ h(c + δ).
8
Do đó λ ∈ ∂(h(c)) nên conv
i∈A
h
i
⊂ ∂h(c).
Ngược lại giả sử λ ∈ ∂h(c), λ ∈ conv
i∈A
h
i
. Khi đó theo Bổ đề 1.5 ở phần
dưới sẽ tồn tại s = 0, s
T
λ > s
T
µ, ∀µ ∈ conv
i∈A
h
i
.
Lấy δ = αs và từ h
i
∈ conv
i∈A
h
i
ta có
h(c) + δ
T
λ = max
i
(c
T
h
i
+ b
i
) + αs
T
λ
> c
T
h
i
+ b
i
+ αs
T
h
i
, ∀i ∈ A
= max
i∈A
(c + αs)
T
h
i
+ b
i
≥ max
i
(c + αs)
T
h
i
+ b
i
= h(c + δ)
nên
h(c) + δ
T
λ > h(c + δ).
Với α đủ nhỏ, khi đó max đạt được trên một tập con của A, mâu thuẫn
với λ ∈ ∂h(c).
Do đó với λ ∈ conv
i∈A
h
i
thì ∂h(c) ⊂ conv
i∈A
h
i
.
Vậy h(c) = conv
i∈A
h
i
.
Bổ đề 1.5. (Bổ đề về siêu phẳng tách các tập lồi)
Nếu K là một tập lồi, đóng, λ ∈ K. Khi đó tồn tại một siêu phẳng tách
λ và K.
Chứng minh. Lấy x
0
∈ K. Khi đó tập
{ x : x − λ
2
≤ x
0
− λ
2
}
là một tập bị chặn. Do đó tồn tại điểm cực tiểu x đối với bài toán
minx − λ
2
, x ∈ K.
Khi đó với bất kì x ∈ K ta có
(1 − θ)x + θx − λ
2
2
≥ x − λ
2
2
.
9
Cho θ → 0 ta được
(x − x)
T
(λ − x) ≤ 0, ∀x ∈ K.
Từ đó véctơ s = λ − x = 0 và thoả mãn đồng thời
s
T
(λ − x) > 0, s
T
(x − x) ≤ 0, ∀x ∈ K
nên
s
T
λ > s
T
x ≥ s
T
x
do đó
s
T
λ > s
T
x, ∀x ∈ K.
Vậy siêu phẳng s
T
(x − x) = 0 tách K và λ.
Bổ đề 1.6. Cho f(x) xác định trên một tập lồi K ⊂ R
n
, x
∈ int(K).
Nếu x
(k)
→ x
là dãy định hướng bất kì với δ
(k)
↓ 0 và s
(k)
→ s
( ở đây x
(k)
− x
= δ
(k)
s
(k)
, ∀k ) thì
lim
k→∞
f
(k)
− f
δ
(k)
= max
g∈∂f
s
T
g. (1.7)
Chứng minh. Ta có x
(k)
= x
+ δ
(k)
s
(k)
.
Nếu g
(k)
∈ ∂f
(k)
thì với mọi k đủ lớn ta có
f
= f(x
) = f(x
k
+ x
− x
k
)
≥ f(x
k
) + (x
− x
k
)
T
g(x
k
)
= f
(k)
− (x
k
− x
)
T
g
(k)
= f
(k)
− δ
(k)
s
(k)
T
g
(k)
và
f
(k)
≥ f
+ δ
(k)
s
(k)
T
g, ∀g ∈ ∂f
.
10
Từ đó
s
(k)
T
g
(k)
≥
f
(k)
− f
δ
(k)
≥ max
g∈∂f
s
T
g. (1.8)
Vì ∂f
(k)
là một tập bị chặn trong một lân cận của x
( theo Bổ đề 1.2 )
nên tồn tại dãy g
(k)
∈ ∂f
(k)
mà g
(k)
→ g
và g
∈ ∂f
( theo Bổ đề 1.1 ).
Nếu (1.8) không đúng thì (1.9) chỉ ra mâu thuẫn tại giới hạn của dãy
con nêu trên.
Nhận xét 1.2.
i) Nếu x
∗
là cực tiểu địa phương của hàm f(x) thì f
(k)
≥ f
∗
với k đủ
lớn và từ (1.8) ta có
max
g∈∂f
∗
s
T
g ≥ 0, ∀s : s = 1. (1.9)
Do đó điều kiện cần đối với cực tiểu địa phương là đạo hàm theo mọi
hướng phải không âm. Từ đó
f
(g; s) ≥ 0.
Điều này tương đương với
0 ∈ ∂f
∗
. (1.10)
Đó là điều kiện tổng quát của đòi hỏi g
∗
= 0 đối với các hàm trơn.
ii) Nếu 0 ∈ ∂f
thì theo Bổ đề 1.5 ( với λ = 0, K = ∂f
), tồn tại véctơ
s = −
g
g
2
sao cho s
T
g < 0, ∀g ∈ ∂f
với g là véctơ cực tiểu của g
2
.
Từ kết quả này tại x
∗
thì (1.10) và (1.11) là tương đương. Ta thấy rằng
cả (1.10) và (1.11) cũng là điều kiện đủ đối với cực tiểu toàn cục tại x
∗
.
Thật vậy, nếu 0 ∈ ∂f(x
∗
) thì
f(x
∗
+ δ) ≥ f(x
∗
) + δ
T
0
11
hay
f(x
∗
+ δ) ≥ f(x
∗
), ∀x
∗
+ δ ∈ K,
do đó x
∗
là cực tiểu toàn cục.
Cuối cùng để nghiên cứu sự tồn tại và duy nhất của điểm cực tiểu,
chúng ta có kết quả sau đây:
Mệnh đề 1.1. Cho f : R
n
→ R là một hàm lồi và C là một tập con lồi
đóng khác rỗng của R
n
. Khi đó
i) Nếu f lồi chặt thì f có nhiều nhất một cực tiểu trên C.
ii) Nếu f lồi mạnh thì f có duy nhất điểm cực tiểu trên C.
1.3 Phép toán về dưới vi phân
Bổ đề 1.7. Cho A và B là hai tập con lồi compact khác rỗng của R
n
.
Khi đó
i) A ⊆ B ⇔ Γ
A
≤ Γ
B
ii) A = B ⇔ Γ
A
= Γ
B
trong đó Γ
A
là hàm tựa của tập lồi A được định nghĩa bởi
Γ
A
(x) = sup
y∈A
y, x.
Chứng minh.
i) Theo định nghĩa của hàm tựa ta thấy ngay nếu A ⊆ B thì Γ
A
≤ Γ
B
.
Để chứng minh chiều ngược lại ta giả sử A ⊆ B, tức là tồn tại a ∈ A và
a ∈ B. Vì B là tập lồi đóng khác rỗng nên từ định lý tách các tập lồi, a
và B có thể được tách ngặt bởi một siêu phẳng, nghĩa là tồn tại s ∈ R
n
12
và γ ∈ R sao cho
s, b < γ < s, a, ∀ b ∈ B
mà
Γ
B
(s) ≤ γ < s, a ≤ Γ
A
(s)
trái với giả thiết Γ
A
≤ Γ
B
. Vậy A ⊆ B.
ii) Suy ra từ (i).
Trước hết ta xét dưới vi phân của một tổ hợp dương các hàm lồi:
Mệnh đề 1.2. Cho f
1
, f
2
: R
n
→ R là các hàm lồi và t
1
, t
2
> 0. Khi đó
∂(t
1
f
1
+ t
2
f
2
)(x) = t
1
∂f
1
(x) + t
2
∂f
2
(x) ∀x ∈ R
n
.
Chứng minh. Lấy x ∈ R
n
và đặt
A = ∂(t
1
f
1
+ t
2
f
2
)(x)
và
B = t
1
∂f
1
(x) + t
2
∂f
2
(x).
Cả hai tập này đều là các tập lồi, khác rỗng và compact. Theo Bổ đề
1.7, nếu Γ
A
= Γ
B
thì A = B.
Ta có
Γ
A
= (t
1
f
1
+ t
2
f
2
)
(x, .)
Γ
B
= t
1
Γ
∂f
1
(x)
+ t
2
Γ
∂f
2
(x)
= t
1
f
1
(x, .) + t
2
f
2
(x, .).
Mặt khác, theo tính chất của đạo hàm theo hướng thì
(t
1
f
1
+ t
2
f
2
)
(x, .) = t
1
f
1
(x, .) + t
2
f
2
(x, .)
nên Γ
A
= Γ
B
, do đó A = B.
13
Sau đây ta sẽ kiểm tra dưới vi phân của cận trên đúng của các
hàm lồi. Cho {f
j
}
j∈J
là tập hợp các hàm lồi từ R
n
vào R. Ta xét hàm
f : R
n
→ R ∪ {+∞} được định nghĩa bởi
f(x) = sup
j∈J
f
j
(x), ∀x
ở đây ta giả sử rằng f nhận giá trị hữu hạn. Dễ thấy f là hàm lồi và
liên tục trên R
n
. Lấy x ∈ R
n
. Một câu hỏi đặt ra là làm thế nào để tính
được ∂f(x) từ các ∂f
j
(x), j ∈ J. Để giải quyết câu hỏi đó ta đưa ra tập
J(x) = { j ∈ J|f
j
(x) = f(x) },
J(x) có thể rỗng. Ví dụ nếu J = N
0
và nếu f
j
(x) = −
1
j
với mọi x và j
thì f(x) = 0,∀x và J(x) = ∅.
Mệnh đề 1.3. Với mọi x ∈ R
n
ta có
∂f(x) ⊇ conv { ∪∂f
j
(x)|j ∈ J(x) }
trong đó conv kí hiệu cho bao lồi đóng.
Chứng minh. Nếu J(x) = ∅, mệnh đề luôn đúng.
Vì vậy ta giả sử J(x) = ∅. Từ ∂f(x) lồi, đóng, ta chứng minh
∂f
j
(x) ⊆ ∂f(x), ∀j ∈ J(x).
Lấy j ∈ J(x) và s ∈ ∂f
j
(x). Khi đó
f(y) ≥ f
j
(y) ≥ f
j
(x) + s, y − x, ∀y ∈ R
n
.
Từ f
j
(x) = f(x) suy ra s ∈ ∂f(x). Mệnh đề được chứng minh.
14
Không có nhận xét nào:
Đăng nhận xét