BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC THĂNG LONG

NGÔ THỊ NGỌC YẾN

ĐIỀU KIỆN TỐI ƯU CHO BÀI TOÁN
TỐI ƯU VÉC TƠ VỚI CÁC HÀM CÓ
ĐẠO HÀM LIPSCHITZ ĐỊA PHƯƠNG

LUẬN VĂN THẠC SĨ TOÁN HỌC

HÀ NỘI - 2015


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC THĂNG LONG

NGÔ THỊ NGỌC YẾN

ĐIỀU KIỆN TỐI ƯU CHO BÀI TOÁN
TỐI ƯU VÉC TƠ VỚI CÁC HÀM CÓ
ĐẠO HÀM LIPSCHITZ ĐỊA PHƯƠNG

Chuyên ngành: Toán ứng dụng
Mã số:

60. 46. 01. 12

LUẬN VĂN THẠC SĨ TOÁN HỌC

Hướng dẫn khoa học:


Lời cảm ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1 ĐIỀU KIỆN TỐI ƯU CHO BÀI TOÁN TỐI ƯU VÉC TƠ C 1,1

2

KHÔNG RÀNG BUỘC

5

1.1

Dưới vi phân cấp 2 của hàm lớp C 1,1 . . . . . . . . . . . . . . .

5

1.2

Hàm véc tơ C − lồi . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.3

Điều kiện tối ưu cho nghiệm lý tưởng . . . . . . . . . . . . . . .

10

Kết luận

33

1


Tài liệu tham khảo

34

2

Thang Long University Libraty


Mở đầu
1. Lý do chọn đề tài
Lý thuyết điều kiện tối ưu là một bộ phận quan trọng của lý thuyết tối ưu
hóa. Nhiều bài toán tối ưu nảy sinh trong kinh tế, kỹ thuật có các hàm dữ liệu
lớp C 1,1 , tức là các hàm có đạo hàm Lipschitz địa phương. Hiriart - Urruty,
Strodiot và Hien Nguyen ([8], 1984) đã khai triển Taylor một hàm C 1,1 qua các
ma trận Hessian suy rộng và dẫn các điều kiện tối ưu cấp 2 cho bài toán tối
ưu vô hướng với các hàm C 1,1 . A. Guerraggio và D.T. Luc đã nghiên cứu các
bài toán tối ưu đa mục tiêu hay bài toán tối ưu véc tơ với các hàm lớp C 1,1
và dẫn các điều kiện tối ưu cần và đủ cho các nghiệm hữu hiệu của bài toán
không ràng buộc ([5], 2001) và có ràng buộc ([6], 2003) dưới ngôn ngữ dưới vi
phân cấp 2 của hàm véc tơ. Đây là đề tài được nhiều tác giả trong và ngoài
nước quan tâm nghiên cứu. Chính vì vậy tôi chọn đề tài: Điều kiện tối ưu cho
bài toán tối ưu véc tơ với các hàm có đạo hàm Lipschitz địa phương.

sự góp ý của các thầy cô để luận văn được hoàn thiện hơn.
Tôi xin chân thành cảm ơn!
Hà Nội, tháng 5 năm 2015.
Người thực hiện
Ngô Thị Ngọc Yến

4

Thang Long University Libraty


Chương 1

ĐIỀU KIỆN TỐI ƯU CHO BÀI
TOÁN TỐI ƯU VÉC TƠ C 1,1
KHÔNG RÀNG BUỘC
Chương 1 trình bày các điều kiện cần và đủ tối ưu cấp 2 cho bài toán tối
ưu véc tơ không có ràng buộc với hàm mục tiêu lớp C 1,1 dưới ngôn ngữ dưới vi
phân cấp 2 cùng với các điều kiện đặc trưng cho hàm C − lồi và C − đơn điệu
lớp C 1,1 . Các kết quả được trình bày trong chương này là của Guerraggio - Luc
([5], 2001).
1.1

Dưới vi phân cấp 2 của hàm lớp C 1,1

Ta nói f là một hàm véc tơ trong lớp C 0,1 có nghĩa là f là hàm Lipschitz
địa phương từ Rm vào Rn . Theo định lý Rademacher, f khả vi hầu khắp nơi,
tức là trừ ra một tập có độ đo 0. Khi đó Jacobian suy rộng Clarke của f tại
điểm bất kì x◦ ∈ Rm , kí hiệu bởi ∂f (x◦ ), tồn tại và cho bởi tập hợp
∂f (x◦ ) := cl conv{lim f ′ (xi ) : xi → x◦ , f ′ (xi ) tồn tại},

1.2

Hàm véc tơ C − lồi

Cho f : Rm −→ Rn là một hàm véc tơ và C là nón lồi, đóng, nhọn có đỉnh
tại gốc 0 (C ∩ −C = {0}) và int C = ∅. Thứ tự bộ phận được sinh bởi C, kí
hiệu ≥C , được định nghĩa như sau:
a ≥C b ⇐⇒ a − b ∈ C.
Nhắc lại rằng f là C − lồi nếu ∀x, y ∈ Rm và ∀t ∈ [0, 1], ta có
f (tx + (1 − t)y) ≤C tf (x) + (1 − t)f (y).

(1.2)

6

Thang Long University Libraty


Hàm C − lồi đóng vai trò quan trọng trong tối ưu véc tơ.
Trong mục này ta sử dụng dưới vi phân cấp 2 để đặc trưng các hàm C − lồi.
Nhắc lại rằng ánh xạ đa trị F từ Rm vào L(n,m) là C − đơn điệu nếu ∀x, y ∈
Rm , ∀α ∈ F (x) và ∀β ∈ F (y), ta có
α(y − x) + β(x − y) ≤C 0.
Khi n = 1 và C là nón các số dương, định nghĩa trên quy về định nghĩa thông
thường của ánh xạ đa trị đơn điệu từ Rm đến Rm . Dưới đây là một số tính chất
cơ bản của ánh xạ C − đơn điệu:
(i) Nếu F là C − đơn điệu thì tF là C − đơn điệu, ∀t ≥ 0.
(ii) Nếu F1 và F2 là C − đơn điệu và F3 ⊆ F1 thì F1 + F2 và F3 là C − đơn điệu.
(iii) F là C − đơn điệu nếu và chỉ nếu ξF là đơn điệu ∀ξ ∈ C ′ , trong đó C ′ là
nón cực dương của C, nghĩa là

Ngược lại, cho F là C − đơn điệu. Giả sử x ∈ Rm là một điểm sao cho
F ′ (x) tồn tại. Khi đó, ∀t ≥ 0 và ∀u ∈ Rm , ta có
F (x + tu) − F (x) ∈ C.
Điều này kéo theo
F ′ (x)(u, u) = lim [F (x + tu) − F (x)](u)/t ∈ C,
t→+ 0

vì C là đóng. Do đó,
F ′ (x)(u, u) ≥C 0,
∀u ∈ Rm và với mọi x tại đó F là khả vi. Do C là đóng, bất đẳng thức trên đúng
cho mọi giới hạn: lim F ′ (xi ) khi xi → x và F ′ (xi ) tồn tại. Do vậy, bất đẳng thức
đó cũng đúng với mọi tổ hợp lồi của các giới hạn đó, cũng như đúng với các giới
hạn của các tổ hợp lồi. Điều này nghĩa là ∂F là C − bán xác định dương.
Ví dụ 1.2.1.
Xét hàm f : R → R


 x,
f (x) = x
 ,
2

x ≥ 0,
x < 0.

8

Thang Long University Libraty




+ + ,
4
2 4
f (x) =
3

2
x


+ ,
3
3
x 1
 + ,
g(x) = f ′ (x) = 2 2
 2
x,

x ≤ 1,
x ≥ 1.

x ≤ 1,
x ≥ 1.

Ta có f lồi, f ′ Lipschitz.

v
 ,

được kí hiệu bằng Ac .
Cho M là một trong các nón C c , C \ {0} và int C. Bài toán tối ưu véc tơ
không ràng buộc tương ứng với cặp (f, M ) như sau:
minM f (x),

x ∈ Rm ,

theo nghĩa tìm x◦ ∈ Rm (gọi là nghiệm tối ưu) sao cho không có x ∈ Rm mà
f (x) ∈ f (x◦ ) − M . Nếu điều này đúng trong một lân cận nào đó của x◦ thì ta
gọi x◦ là nghiệm tối ưu địa phương. Các nghiệm tối ưu tương ứng với (f, C c ),
(f, C \ {0}), (f, int C) được gọi tương ứng là các nghiệm lý tưởng (ideal
solutions), nghiệm hữu hiệu (efficient solutions), nghiệm hữu hiệu yếu (weakly
efficient solutions). Từ định nghĩa ta suy ra x◦ là một nghiệm lý tưởng địa
phương nếu và chỉ nếu tồn tại một lân cận U ⊂ Rm của x◦ sao cho
f (x) − f (x◦ ) ∈ C,

∀x ∈ U.

Nếu tồn tại một nón nhọn lồi K ⊂ Rn sao cho C \ {0} ⊂ int K và nếu không
có x ∈ Rm sao cho f (x) ∈ f (x◦ ) − int K thì ta nói x◦ là một nghiệm hữu hiệu
chính thường địa phương (local properly efficient solution). Định nghĩa nghiệm
hữu hiệu chính thường này là của Henig [7].
Trong mục này, ta sẽ trình bày các điều kiện tối ưu cấp 1 và cấp 2 cho
nghiệm lý tưởng. Mặc dù những nghiệm này không phải là chủ đề chính của lý
10

Thang Long University Libraty


thuyết tối ưu véc tơ, nhưng chúng vẫn được chú ý bởi vì cấu trúc đơn giản của

11


Ngược lại, nếu (i)(b) là không đúng thì ∃ξ ∈ C ′ sao cho 0 ∈ ξ∂f (x◦ ). Áp
dụng định lý tách cho các tập {0} và tập lồi, compact ξ∂f (x◦ ), ta có thể tìm
được một số u ∈ Rm sao cho
∀α ∈ ∂f (x◦ ).

ξα(u) < 0,
Điều này chứng tỏ rằng

∂f (x◦ )(u) ∩ C = ∅.
Bây giờ, giả sử rằng f lớp C 1,1 . Khi đó, ∂f (x◦ ) = {f ′ (x◦ )} và do phần trước,
ξf ′ (x◦ ) = 0,

∀ξ ∈ C ′ .

Vì C là nhọn và đóng, khi đó int C ′ = {0}. Do đó,
ξf ′ (x◦ ) = 0

∀ξ ∈ Rn ,

và vì vậy, f ′ (x◦ ) = 0.
Ta xét điều kiện (ii)(b), giả sử ngược lại ∃u ∈ Rm sao cho ∂ 2 f (x◦ )(u, u) ∩
C = ∅. Tập ∂ 2 f (x◦ ) là lồi và compact, do đó ∂ 2 f (x◦ )(u, u) cũng là tập lồi
compact trong Rn . Áp dụng định lý tách cho tập này và C, ta nhận được véc
tơ ξ ∈ Rn \{0} sao cho
∀φ ∈ ∂ 2 f (x◦ ) và ∀v ∈ C.

ξ, φ(u, u) < 0 ≤ ξ, v ,

Bây giờ, giả sử rằng f là lớp C 1,1 và hai điều kiện (ii)(a) và (ii)(b) đúng.
Khi đó, ∀u ∈ Rm \{0} với u = 1, do tính nửa liên tục trên của dưới vi phân
cấp 2, tồn tại một hình cầu Vu tâm x◦ sao cho
∂ 2 f (x)(u, u) ⊂ int C,

∀x ∈ Vu .

Bởi vì mặt cầu đơn vị trong Rm là compact, tồn tại một hình cầu V tâm x◦
sao cho
∂ 2 f (x)(u, u) ⊂ int C,

∀x ∈ V và ∀u ∈ Rm với u = 1.

Do đó ∀u ∈ Rm \{0} bao hàm thức trên cũng đúng. Theo Hệ quả 1.2.1, f là
C − lồi quanh x◦ . Từ đó suy ra, điều kiện (i) thỏa mãn và do đó x◦ là nghiệm
lý tưởng địa phương.
Chúng ta có thể đặt câu hỏi liệu có một dạng tương tự như trường hợp
vô hướng: 0 ∈ ∂f (x◦ ) có thể thay thế trong điều kiện (i) của định lý 1.3.1.
Đáng tiếc, câu trả lời là không, như được chỉ ra trong ví dụ sau đây. Cho
m = 1, n = 2, C = R2 + và

f (x) =


 (−x, 0),
 (0, x),

13

nếu x ≤ 0,

trên của Jacobian suy rộng, ∃ǫ sao cho ∂f (x)(u) ⊂ V với mọi x ∈ [x◦ , x◦ + ǫu].
Do V lồi và đóng, ta có
cl conv{δf (x)(u) : x ∈ [x◦ , x◦ + ǫu]} ⊂ V.
14

Thang Long University Libraty


Áp dụng định lý giá trị trung bình với f trên [x◦ , x◦ + ǫu], ta thu được
f (x◦ + tu) − f (x◦ )
∈ cl conv{∂f (x)(tu) : x ∈ [x◦ , x◦ + ǫu]} ⊂ tV ⊂ −int C,

∀t ∈ (0, ǫ).

Điều này mâu thuẫn với giả thiết của định lý.
Bây giờ, chúng ta chỉ ra (i)(a) ⇔ (i)(b). Thật vậy, nếu (i)(a) không đúng,
nghĩa là,
với u ∈ Rm nào đó,

∂f (x◦ )(u) ⊂ −int C,

thì ∀ξ ∈ C ′ \{0} và ∀α ∈ ∂f (x◦ ), ta có ξ, α(u) < 0 và (i)(b) không đúng.
Ngược lại, nếu (i)(b) không đúng, nghĩa là,
∀ξ ∈ C ′ \{0},

0∈
/ ξ∂f (x◦ ),

thì ta có thể áp dụng định lý tách điểm gốc của không gian và tập lồi, compact
{ξ∂f (x◦ ) : ξ ∈ B}, trong đó tập B là cơ sở lồi và compact của C ′ .


∀t ∈ (0, ǫ].

Điều này mẫu thuẫn với giả thiết.
Cuối cùng, rõ ràng là với φ ∈ ∂ 2 f (x◦ ) nào đó với φ(u, u) ∈
/ −int C, ta có
thể tìm được véc tơ η ∈ C ′ \{0} sao cho
η, φ(u, u) ≥ 0.
Điều ngược lại cũng đúng bởi vì với φ như trên, ta có φ(u, u) ∈
/ −int C và từ
đó suy ra
∂ 2 f (x◦ )(u, u) ∩ (−int C)c = ∅.

Bằng cách đặt n = 1 ta nhận được mệnh đề 5.1 của [9] cho hàm vô hướng
C 1,1 .
Hệ quả 1.4.1.
Giả sử n = 1 và f lớp C 1,1 . Khi đó, các điều kiện sau đây là điều kiện cần cho
để x◦ là điểm cực tiểu địa phương của f :
(i) f ′ (x◦ ) = 0.
(ii) ∀u ∈ Rm , ∃φ ∈ ∂ 2 f (x◦ ) sao cho φ(u, u) ≥ 0.
Chứng minh.
Điều kiện đầu tiên có được do f ′ (x◦ )(u) ≥ 0, với mọi u ∈ Rm , kéo theo
f ′ (x◦ ) = 0. Điều kiện thứ hai được suy ra từ điều kiện (ii)(b) của định lý 1.4.1,
vì mỗi u ∈ Rm thỏa mãn
f ′ (x◦ )(u) = 0 ∈ −(C \ int C),

trong đó C = R+ .

16


Bởi vì {xi } hội tụ đến x◦ và {ui } hội tụ tới u, ta có
xi − x◦ < ǫ và ui − u < ǫ, với i đủ lớn.
Với i như trên, sử dụng định lý giá trị trung bình, ta nhận được
f (xi ) − f (x◦ ) ∈ cl conv{∂f (x)(xi − x◦ ) : x ∈ [x◦ , xi ]} ⊂ xi − x◦ V ⊂ (−C)c .
Điều này mâu thuẫn (1.4).
17


Bây giờ, giả sử rằng f là lớp C 1,1 . Nếu x◦ không là nghiệm hữu hiệu địa
phương thì (1.4) thỏa mãn. Điều kiện (ii)(a) cho thấy
f ′ (x◦ )(u) ∈
/ −C \{0}.
Có hai trường hợp xảy ra:
f ′ (x◦ )(u) ∈ (−C)c

và

f ′ (x◦ )(u) = 0.

Như ở trên trường hợp đầu tiên là không xảy ra. Vì vậy, ta xét trường hợp còn
lại u ∈ Kerf ′ (x◦ ). Do (ii)(b), tồn tại một lân cận lồi đóng V của ∂ 2 f (x◦ )(u, u)
trong int C sao cho
∂ 2 f (x)(v, v) ⊂ V, khi x − x◦ < ǫ, v − u < ǫ,
với ǫ dương đủ nhỏ. Sử dụng khai triển Taylor, ta nhận được
f (xi ) − f (x◦ )
∈ f ′ (x◦ )(xi − x◦ ) + cl conv{∂ 2 f (x)(xi − x◦ , xi − x◦ ) : x ∈ [x◦ , xi ]}
⊂ xi − x◦ {f ′ (x◦ )(ui )
+ xi − x◦ cl conv{∂ 2 f (x)(ui , ui ) : x ∈ [x◦ , xi ]}}.

(1.5)


Với n > 1, ta có điều kiện đủ cấp một đơn giản cho hàm véc tơ C 1 .
Hệ quả 1.4.3.
Giả sử f là lớp C 1 và f ′ (x◦ )(u) ∈ (−C)c , ∀u ∈ Rm \{0}. Khi đó, x◦ là nghiệm
hữu hiệu địa phương.
Chứng minh.
Vì ∂f (x◦ ) = {f ′ (x◦ )}, điều kiện của hệ quả này kéo theo điều kiện (i) của định
lý 1.4.2. Do đó ta được điều phải chứng minh.

Ta chú ý điều kiện có trong hệ quả 1.4.3 không đúng cho hàm vô hướng bởi
vì với n = 1, bất đẳng thức
f ′ (x◦ )(u) > 0,

tồn tại u ∈ Rm \{0} nào đó,

kéo theo
f ′ (x◦ )(−u) < 0,
do tính chất tuyến tính của f ′ . Tuy nhiên, dưới đây chúng ta cho một ví dụ
chỉ ra rằng điều này không đúng cho hàm véc tơ. Cho m = 1, n = 2, C = R2+
và f được cho bởi
f (x) = (x, −x),

với x ∈ R.

Khi đó, với mọi x◦ ∈ R, ta có
f ′ (x◦ )(u) = (u, −u) ∈ (−C)c ,

với u ∈ R\{0}.

Do hệ quả 1.4.3, x◦ là một nghiệm hữu hiệu địa phương. Thực ra x◦ là nghiệm

2.1

Khái niệm bổ trợ

Giả sử f : Rn → Rm là một hàm véc tơ lớp C 0,1 , nghĩa là f Lipschitz địa
phương. Theo định lý Rademacher (xem [4]), f là khả vi hầu khắp nơi, tức là
trừ ra một tập có độ đo không. Jacobian suy rộng Clarke của f tại mọi điểm
x◦ ∈ Rn , được ký hiệu là ∂f (x◦ ), tồn tại và cho bởi tập
∂f (x◦ ) := cl conv {lim ∇f (xi ) : xi → x◦ , ∇f (xi ) tồn tại},
trong đó cl conv{· · · } kí hiệu bao lồi đóng của tập trong dấu ngoặc.
Bây giờ, giả sử f : Rn → Rm lớp C 1,1 , nghĩa là, ∇f là lớp C 0,1 , Jacobian suy
rộng Clarke của ∇f tại x◦ , được gọi là dưới vi phân cấp 2 của f tại x◦ :
∂ 2 f (x◦ ) := cl conv {lim ∇2 f (xi ) : xi → x◦ , ∇2 f (xi ) tồn tại}.
Gọi L(n,m) là không gian tuyến tính gồm tất cả các toán tử tuyến tính từ Rn
vào Rm và gọi L(n,m) là không gian tuyến tính của tất cả các toán tử tuyến tính
21


từ Rn vào L(n,m) . Ta có ∂ 2 f (x◦ ) là một tập con của không gian hữu hạn chiều
L(n,m) . Do đó, các phần tử của ∂ 2 f (x◦ ) có thể xem như các hàm song tuyến
tính từ Rn vào Rm . Theo cách xây dựng, dưới vi phân cấp 2 có tất cả các tính
chất của Jacobian suy rộng. Ta liệt kê một vài tính chất quan trọng của dưới
vi phân cấp 2:
(i) ∂ 2 f (x◦ ) là tập khác rỗng, lồi và compact của không gian L(m,n) .
(ii) Ánh xạ đa trị x → ∂ 2 f (x) là nửa liên tục trên.
(iii) Hợp thành với một hàm tuyến tính: ∀ξ ∈ Rm , ta có
ξ∂ 2 f (x) = ∂ 2 (ξf )(x).
(iv) Định lý giá trị trung bình: Cho f là lớp C 0,1 và a, b ∈ Rn . Khi đó,
f (b) − f (a) ∈ cl conv {∂f (x)(b − a) : x ∈ [a, b]},
trong đó [a, b] = conv{a, b}.

x◦ ∈ S, nón tiếp tuyến Bouligand cấp 1 và nón tiếp tuyến cấp 2 của S tại x◦
được định nghĩa lần lượt như sau:
T1 (S, x◦ ) := {u ∈ Rn : ∃ti > 0, xi = x◦ + ti u + o(ti ) ∈ S},
T2 (S, x◦ ) := {(u, v) ∈ Rn × Rn : ∃ti > 0, xi = x◦ + ti u + (1/2)ti 2 v + o(ti 2 ) ∈
S},
trong đó
o(ti )/ti → 0 và o(ti 2 )/ti 2 → 0,

khi ti → 0+ .

Đặt
Λ := {λ ∈ C ′ : λ = 1},
và với δ > 0,
Sδ (x◦ ) := {t(x − x◦ ) : t ≥ 0, x ∈ S, x − x◦ ≤ δ}.
Phần bù của tập A ⊂ Rn được kí hiệu là Ac .
Định lý 2.2.1.
Giả sử f : Rn → Rm là hàm lớp C 1,1 và x◦ ∈ S là một nghiệm hữu hiệu yếu
địa phương của bài toán (P ). Khi đó, với mỗi (u, v) ∈ T2 (S, x◦ ).
(i) Tồn tại λ ∈ Λ sao cho λ, ∇f (x◦ ) ≥ 0.
(ii) Khi ∇f (x◦ )(u) = 0, tồn tại λ′ ∈ Λ và M ∈ ∂ 2 f (x◦ ), sao cho
λ′ , ∇f (x◦ )(v) + M (u, u) ≥ 0.
Chứng minh.
Lấy (u, v) ∈ T2 (S, x◦ ). Khi đó ∃ti > 0 sao cho
2
2
{ti }∞
1 → 0 và xi = x◦ + ti u + (1/2)ti v + o(ti ) ∈ S.

Vì x◦ là nghiệm hữu hiệu yếu địa phương, tồn tại i◦ ≥ 1 thỏa mãn
f (xi ) − f (x◦ ) ∈ (−int C)c ,