1
TRƯỜNG ĐẠI HỌC SƯ PHẠM HUẾ
KHOA TOÁN
*********
TIỂU LUẬN
HÀM LỒI SUY RỘNG VÀ GRADIENT SUY RỘNG
Đề tài:
TÍNH LỒI SUY RỘNG VÀ ĐIỀU KIỆN TỐI ƯU
TRONG VECTƠ VÔ HƯỚNG TỐI ƯU
GIẢNG VIÊN HƯỚNG DẪN:
PGS. TS. PHAN NHẬT TĨNH
HỌC VIÊN THỰC HIỆN:
ĐẶNG THỊ NHƯ Ý
Lớp: Giải Tích K20
Huế-04/2013
Mục lục
MỞ ĐẦU 3
1 Hàm Lồi Suy Rộng Và Điều Kiện Tối Ưu 4
2 Hàm Vô Hướng 9
3 Tính Lồi Suy Rộng Và Sự Xác Định Ràng Buộc 12
4 Giá Trị Cực Đại Và Tính Lồi Suy Rộng 14
2
MỞ ĐẦU
Trong các định lý tối ưu, tính tối ưu cơ bản có các thuộc tính như: một
cực tiểu địa phương cũng là cực tiểu toàn cục, một điểm dừng là một cực
tiểu toàn cục và điều kiện tối ưu là điều kiện đủ để một điểm là cực tiểu toàn
cục. Nhiều mô hình toán học được sử dụng trong khoa học, kinh tế,lý thuyết
ngẫu nhiên, ứng dụng toán học vào ngành kĩ sư, khái niệm tính lồi là chưa
đủ cho nên hàm lồi suy rộng được đưa vào tìm hiểu. Nhiều hàm đảm bảo
một hoặc nhiều thuộc tính của hàm lồi và có nhiều mô hình được áp dụng
trên thế giới. Bước đầu cho công việc này là Arrow-Enthoven đã nghiên cứu

+ λx
2
) ≤ f(x
1
) (1.1.1)
với mọi x
1
, x
2
∈ S và 0 ≤ λ ≤ 1 Khi f là một hàm khả vi, f là tựa lồi khi và
chỉ khi:
f(x
2
) ≤ f(x
1
) ⇒ ((x
2
− x
1
)
T
∇f(x
1
)) ≤ 0; x
1
, x
2
∈ S (1.1.2)
Định nghĩa 1.2. Hàm f là hàm tựa lồi chặt trong S nếu
f(x

∇f(x
1
)) < 0 (1.3.1)
Chúng ta thấy rằng, trong trường hợp khả vi một hàm giả lồi là tựa lồi
chặt, là tựa lồi.
Mối quan hệ giữa giả lồi và tựa lồi được thể hiện qua định lý sau:
Định lý 1.4. Cho f là một hàm khả vi trong một tập mở lồi S ⊂ 
n
. Nếu
∇f(x) = 0 ∀x ∈ S thì f là giả lồi khi và chỉ khi nó là tựa lồi.
4
Chứng minh 1. Chúng ta đã biết rằng một hàm giả lồi cũng là tựa lồi.
Chúng ta cần chứng minh một hàm tựa lồi là giả lồi
Giả sử ngược lại ∃x
1
, x
2
∈ S, f(x
2
) < fx
1
và (x
2
− x
1
)
T
∇f(x
1
) ≥ 0. Do f là

) = (y − x
2
) + (x
2
− x
1
)
khi đó (y − x
1
)
T
∇f(x
1
)) = (y − x
2
)
T
∇f(x
1
)) + (x
2
− x
1
)
T
∇f(x
1
)) = . 
∇f(x
1

(1.4.1)
và điểm x
0
= 1, chúng là cực tiểu địa phương nhưng không phải là cực tiểu
toàn cục.
Nếu x
0
là điểm cực tiểu địa phương chặt của một hàm tựa lồi thì nó cũng
là điểm cực tiểu toàn cục chặt. Lớp hàm tựa lồi chặt là lớp hàm suy rộng
khi một giá trị cực tiểu địa phương cũng là cực tiểu toàn cục. Nếu f là một
hàm tựa lồi liên tục thì f là tựa lồi chặt khi và chỉ khi mỗi điểm cực tiểu địa
phương cũng là cực tiểu toàn cục.
Định nghĩa 1.5. Cho f là một hàm được định nghĩa trong tập hình sao S
tại x
0
i)f tựa lồi tại x
0
nếu f(x) ≤ f(x
0
) ⇒ f((1−λ)x
0
+λx) ≤ f(x
0
), ∀x ∈ S; λ ∈
[0, 1]
5
ii)f là tựa lồi chặt tại x
0
nếu f(x) < f (x
0

0
= (0, 0) là điểm cực tiểu với mọi hướng d ∈ 
2
+
; d = 0 nhưng nó
không là cực tiểu địa phương.
Định lý 1.6. Cho f là một hàm được định nghĩa trong tập hình sao S tại
x
0
i) Nếu f là tựa lồi tại x
0
∈ S và x
0
là điểm cực tiểu địa phương chặt với mọi
hướng d = x − x
0
, x ∈ S, x = x
0
thì x
0
là điểm cực tiểu toàn cục trong S.
ii)Nếu f là tựa lồi chặt tại x
0
∈ S và x
0
là điểm cực tiểu địa phương với
mọi hướng d = x − x
0
, x
0

là một điểm cực tiểu toàn cục của hàm f trong
S.
Định lý trên là không đúng nếu giả thiết tính giả lồi thay bởi tính tựa lồi
hoặc tựa lồi chặt.
6
Ví dụ như hàm f(x) = x
3
là hàm tăng chặt cho nên nó có cả tính tựa lồi
chặt và tựa lồi nhưng điểm dừng x
0
= 0 nó không phải là điểm cực tiểu của
f.
Bây giờ chúng ta sẽ thấy giả thiết của tính lồi suy rộng là rất quan trọng
đủ để bảo đảm cho điều kiện tối ưu trước. Khi S là tập hình sao tại x
0
một trong những điều kiện được biết để x
0
là điểm cực tiểu địa phương:
d
T
∇f(x
0
) ≥ 0; ∀d ∈ F (S, x
0
) với F(S, x
0
) là một nón mà mọi hướng của S
tại x
0
cho bởi:

và d
T
.∇f(x
0
) = d
2
> 0, ∀d ∈ F (S, x
0
) nhưng x
0
không là điểm cực tiểu.
Định lý 1.8. Cho S ⊂ X là một tập hình sao tại x
0
∈ S và cho f là
giả lồi tại x
0
thì x
0
là một điểm cực tiểu của f trong S khi và chỉ khi
(x − x
0
)
T
.∇f(x
0
) ≥ 0, ∀x ∈ S
Chú ý rằng nếu x
0
là điểm dừng và điều kiện (x − x
0

là điểm cực tiểu của
f trong S.
Bây giờ chúng ta xét bài toán sau:
P : minf(x), x ∈ S = {x ∈ X : g
i
(x) ≤ 0, i = 1, , m}
7
Với f, g
i
: X →  là các hàm khả vi được định nghĩa bởi tập mở X ⊂ 
n
Trên điều kiện ràng buộc tối ưu KT-dừng cho x
0
là điểm chấp nhận được và
tập I(x
0
) = {i ∈ {1, , m} : g
i
(x
0
) = 0}
Nếu x
0
là điểm cực tiểu địa phương của bài toán P và có một điều kiện ràng
buộc nhất định thì ∃λ
i
∈ ; i ∈ I(x
0
). Khi đó:
∇f(x

(x
0
, λ) thỏa điều kiện KT-dừng. Nếu f là giả lồi tại x
0
thì x
0
là điểm cực
toàn cục của bài toán P.
Chứng minh 2. Giả sử tồn tại điểm chấp nhận được x thỏa f(x) < f(x
0
).
Từ tính giả lồi của f chúng ta có (x −x
0
)
T
∇f(x
0
) < 0 và từ tính tựa lồi của
g
i
; i ∈ I(x
0
) chúng ta có (x − x
0
)
T
∇g
i
(x
0

mục đích mở rộng tính hiệu lực của điều kiện KT-dừng. Từ những bài báo
của Hanson và Craven cách đây 30 năm, một số ý kiến phát triển cho sự
đóng góp đến hàm invex đặc biệt là đối với bài toán tối ưu.
Định nghĩa 2.1. Hàm thực khả vi f được định nghĩa trong tập X ⊂ 
n
là
invex nếu tồn tại một vectơ hàm η(x, y) = (x − y) được định nghĩa trong
X × X như sau:
f(x) − f(y) ≥ η
T
(x, y)∇f(y); ∀x, y ∈ X.
Hiển nhiên hàm lồi khả vi (trong tập mở X) là invex (η(x, y) = (x − y))
Định lý 2.2. Một hàm khả vi là hàm invex khi và chỉ khi mỗi điểm dừng là
một điểm cực tiểu toàn cục.
Chứng minh 3. Cho hàm f với vectơ hàm η(x, y). Nếu x
0
là điểm dừng
của f thì ta có f(x) − f(x
0
) ≥ η
T
(x, x
0
)∇f(x
0
) = 0; ∀x ∈ X, khi đó x
0
là
điểm cực tiểu toàn cục. Bây giờ chúng ta sẽ chứng minh rằng nó đúng cho
hàm η(x, y) được định nghĩa như sau

Ví dụ 3. Xét hàm f(x, y) = y(x
2
− 1)
2
trong tập mở X = {(x, y) ∈ 
2
:
y > 0}
Dễ dàng kiểm tra rằng điểm dừng (1, y); (−1, y); y > 0 của f là cực tiểu
toàn cục, khi đó f là invex. Mặt khác tập A = (−1, 1); B = (
1
2
, 1) ta có
f(A) = 0 < f(B) =
9
16
và (A − B)
T
∇f(B) = (
−3
2
; 0)(
−3
2
;
9
16
)
T
=

tiểu được cho bởi {(1, y) : y > 0 ∪ {(−1; y) : y > 0} chúng là tập không lồi,
do đó hàm invex là tập tất cả các điểm cực tiểu không có tính chất của một
tập lồi.
Định lý 2.3. Cho x
0
là điểm chấp nhận được của bài toán P và giả sử rằng
(x
0
, λ) thỏa điều kiện KT-dừng. Nếu f, g
i
, i ∈ I(x
0
) là hàm invex với vectơ
η(x, y) thì x
0
là một điểm cực tiểu toàn cục của bài toán P.
10
Chứng minh 4. Với mỗi x ∈ S,chúng ta có
f(x)−f(x
0
) ≥ η
T
(x, x
0
)∇f(x
0
) = −

i∈I(x
0


n
là η − invex nếu ∀x, y ∈ X đoạn [y, y + η(x, y)] chứa trong X.
Định nghĩa 2.4. Cho f là một hàm thực được định nghĩa trên một η −invex
tập X,f là một trước invex với mô tả η nếu bất đẳng thức sau xác định
f(y + λη(x, y)) ≤ λf(x) + (1 − λ)f(y), ∀x, y ∈ X, ∀λ ∈ [0, 1]
Cũng như hàm lồi, hàm trước invex thì mọi cực tiểu địa phương đều là
cực tiểu toàn cục.
11
Chương 3
Tính Lồi Suy Rộng Và Sự Xác
Định Ràng Buộc
Như chúng ta đã biết điều kiện dừng là điều kiện tối ưu cần thiết cho bài
toán P khi điều kiện ràng buộc chính quy được thỏa mãn. Mục đích của phần
này nói đến vai trò của tính lồi suy rộng và thuộc tính invex trong điều kiện
ràng buộc.
Với mục đích đó, chúng ta định nghĩa các tập như sau:
G
0
= {d ∈ 
n
: d
T
∇g
i
(x
0
) < 0, i ∈ I(x
0
)}

Với J = {i ∈ I(x
0
) : g
i
(x) là giả lồi tại x
0
}
Chú ý với coT (S, x
0
) là bao đóng của bao lồi nón tiếp xúc T (S, x
0
) đến
miền chấp nhận S tại x
0
∈ S chúng ta có mối quan hệ sau clG
0
⊆ clG
p
⊆
coT (S, x
0
) ⊆ G
Điều kiện trên bảo đảm điều kiện KT-dừng, ta có coT (S, x
0
) = G trở thành
ràng buộc xác định.
Định lý 3.1. Nếu một trong những điều kiện sau đây được xác định thì điều
kiện ràng buộc là được thỏa mãn:
i) Hàm g
i

) < 0, i ∈ I(x
0
)
12
iii) Hàm g
i
(x); i ∈ I(x
0
) là giả lồi tại x
0
và ∃x
∗
∈ S khi đó g
i
(x
∗
) < 0, i ∈
I(x
0
)\J
iv) Hàm g
i
(x); i ∈ I(x
0
) là invex tại x
0
với η(x, x
0
)và ∃x
∗

0
và G
0
= ∅
ii) Suy ra từ i)dựa vào tính tựa lồi của g
i
(x) tại x
0
và giả thiết ∇g
i
(x
0
) = 0
bao hàm tính giả lồi của g
i
(x) tại x
0
iii) Mỗi j ∈ J hàm g
i
(x) là giả lồi và giả lõm khi đó g
i
(x
∗
) < g
i
(x
0
) = 0 bao
hàm (x − x
0

và hơn nữa G
p
= ∅
iv) Chúng ta có g
i
(x
∗
) < g
i
(x
0
) = 0; i ∈ I(x
0
) với mỗi g
i
, i ∈ I(x
0
). Khi đó:
d = η(x
∗
, x
0
) ∈ G
0
Định lý 3.2. Cho x
0
là nghiệm tối ưu của bài toán (P ) ở đây hàm g
i
; i ∈
I(x

0
∇f(x
0
) +

i∈I(x
0
)
λ
i
∇g
i
(x
0
)) = 0 (3.2.2)
Giả sử rằng λ
0
= 0 khi đó

i∈I(x
0
)
λ
i
∇g
i
(x
0
)) = 0 (3.2.3)
Từ giả thiết ta có g


i∈I(x
0
)
λ
i
∇g
i
(x
0
)) = 0 (3.2.4)
và điều này mâu thuẫn với điều kiện ràng buộc.
13
Chương 4
Giá Trị Cực Đại Và Tính Lồi Suy
Rộng
Trong phần này chúng ta thấy rằng một hàm lồi suy rộng với một cực đại
toàn cục, nó đạt được tại biên của tập chấp nhận được S.
Chúng ta sẽ bắt đầu chứng minh rằng nếu giá trị cực đại của hàm là đạt tại
điểm trong tương ứng của S thì f là hằng số trên S, chúng được gọi là điểm
trong tương ứng của tập lồi C ⊂ 
n
. Kí hiệu: riC
riC = x ∈ affC : ∃ > 0; (x + B) ∩ affC ⊂ C với B là hình cầu đơn vị
trong 
n
Bổ đề 1. Cho hàm f là liên tục và tựa lồi chặt trong tập lồi S. Nếu x
0
∈ riS
khi đó

thì nó đạt cực trị tại một điểm.
Chứng minh 8. Nếu f là hằng số thì điều trên là tầm thường.
Lấy x
0
thỏa
f(x
0
) = max
x∈S
f(x) (4.2.1)
Từ định lý trên, x
0
∈ bdS. Cho C là một mặt cực tiểu của S chứa x
0
, nếu
x
0
không là điểm cực trị thì x
0
∈ riC. Từ bổ đề trên cho thấy rằng f là hằng
số trên C. Mặt khác C là một tập lồi đóng, khi đó C có một điểm cực trị x,
chúng là điểm cực trị của S. Mặt khác ta có hàm
f(x) =








n

i=1
λ
i
= 1; λ
i
≥ 0. (4.3.2)
Từ f là tựa lồi chúng ta có f(x) ≤ max f(x
1
), , f(x
k
) và định lý được chứng
minh.
15
Hệ quả 2. Cho f là giả lồi trong một tập lồi đóng S. Giả sử f có giá trị
cực đại trên S thì nó đạt tại biên.
Hệ quả 3. Cho f là một hàm giả lồi trong một tập lồi đóng S. Giả sử f có
giá trị cực đại trên S thì nó đạt cực trị tại một điểm
16
TÀI LIỆU THAM KHẢO.
Tiếng Việt
1. Phan Nhật Tĩnh, Hàm Lồi Suy Rộng và gradient suy rộng.
Tiếng Anh
1. Generalized convexty and generalized monotonicity-2005.
17