ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

LƯƠNG QUỐC ĐĂNG

ĐIỀU KIỆN CHÍNH QUY GUIGNARD VÀ ĐIỀU KIỆN TỐI ƯU
CHO NGHIỆM HỮU HIỆU CỦA BÀI TOÁN TỐI ƯU ĐA MỤC
TIÊU KHÔNG TRƠN
CHUYÊN NGÀNH: TOÁN ỨNG DỤNG
MÃ SỐ: 60460112

2015


Mục lục
Mở đầu

1

1 Điều kiện chính quy Guignard và điều kiện KuhnTucker cho bài toán bán khả vi

3

1.1 Các định nghĩa và khái niệm . . . . . . . . . . . . . . .

3

1.2 Điều kiện chính quy Guignard . . . . . . . . . . . . . .

6




Mở đầu

1. Lý do chọn đề tài

Lý thuyết các điều kiện tối ưu là một bộ phận quan trọng của tối ưu
hóa. Các điều kiện Kuhn - Tucker cho nghiệm hữu hiệu của bài toán
tối ưu đa mục tiêu mà tất cả các nhân tử Lagrange ứng với các thành
phần của hàm mục tiêu là dương và được gọi là các điều kiện Kuhn
- Tucker mạnh. Với điều kiện chính quy kiểu Guignard cho bài toán
tối ưu đa mục tiêu khả vi có ràng buộc bất đẳng thức. V. Preda và I.
Chitescu ([10], 1999) đã phát triển các điều kiện tối ưu kiểu Maeda [8]
cho bài toán tối ưu đa mục tiêu bán khả vi. Với điều kiện chính quy
Guignard, X. J. Long và N. J. Huang ([7], 2014) đã thiết lập các điều
kiện Kuhn - Tucker mạnh cho bài toán tối ưu đa mục tiêu với các hàm
Lipschitz địa phương dưới ngôn ngữ dưới vi phân suy rộng. Đây là đề
tài được nhiều tác giả quan tâm nghiên cứu. Chính vì vậy em chọn đề
tài : “Điều kiện chính quy Guignard và điều kiện tối ưu cho nghiệm hữu
hiệu của bài toán tối ưu đa mục tiêu không trơn”.
2. Mục đích của đề tài

Luận văn trình bày các kết quả nghiên cứu về điều kiện chính quy
Guignard và điều kiện tối ưu Kuhn - Tucker mạnh của V. Preda và
I. Chitescu (1999) và điều kiện Kuhn - Tucker của X. J. Long - N. J.
Huang (2014) cho nghiệm hữu hiệu của bài toán tối ưu đa mục tiêu
1


không trơn có ràng buộc bất đẳng thức.

Chương 1 trình bày các kết quả nghiên cứu của V. Preda và I.
Chitescu ([10], 1999) về điều kiện chính quy Guignard cho bài toán
tối ưu đa mục tiêu có ràng buộc bất đẳng thức và điều kiện cần KuhnTucker mạnh cho nghiệm hữu hiệu của bài toán đó với các hàm bán
khả vi.
1.1

Các định nghĩa và khái niệm

Cho hai vectơ x và y trong Rn , ta sử dụng các quy ước sau:
x < y nếu và chỉ nếu xi < yi , ∀i, i = 1, 2, ..., n;
x ≤ y nếu và chỉ nếu x < y nhưng x = y;
x < y nếu và chỉ nếu xi < yi , ∀i, i = 1, 2, ..., n.

Chúng ta xét bài toán quy hoạch toán học đa mục tiêu sau đây:
(VP)

min f (x),
g(x) ≤ 0,

trong đó x ∈ Rn , f : Rn → Rp , f = (f1 , f2 , ..., fp ), g : Rn → Rm , g =
(g1 , g2 , ..., gm ). Kí hiệu
X = { x ∈ Rn | g(x)
cho với mọi x, u ∈ S và mọi λ ∈ [0, 1], ta có
ϕ(u + λη(x, u)) < λϕ(x) + (1 − λ)ϕ(u).
4


Trong trường hợp này ta nói rằng ϕ là tiền lồi bất biến theo η. Một
hàm vectơ k-chiều ψ : S → Rk là tiền lồi bất biến theo η nếu mỗi thành
phần của nó là tiền lồi bất biến trên S theo η.
Bổ đề 1.1.1. [11]
Giả sử S là một tập khác rỗng trong Rn và ψ : S → Rk là hàm
tiền lồi bất biến trên S theo η. Khi đó,
hoặc ψ(x) < 0 có một nghiệm x ∈ S,
hoặc là λT ψ(x)> 0, ∀x ∈ S, với λ ∈ Rk nào đó, λ ≥ 0,
nhưng không thể đồng thời cả hai. Ở đây

T

là ma trận chuyển vị.

Giả sử rằng các hàm fi , i ∈ P = {1, 2, ..., p} và gj , j ∈ M =
{1, 2, ..., m} là bán khả vi tại các điểm mà ta đang xét. Nếu p > 1
và i ∈ P, ta kí hiệu P i = P \{i}.
Định nghĩa 1.1.6.
Ta nói rằng ϕ : Rn → R bán khả vi tại x0 ∈ Rn là gần tuyến tính
tại x0 , nếu với mọi x ∈ Rn ,
ϕ(x) = ϕ(x0 ) + ϕ+ (x0 , x − x0 ).

Định nghĩa 1.1.7.
Ta nói rằng ϕ : Rn → R bán khả vi tại x0 ∈ Rn là tựa lồi tại x0 ,
nếu suy luận sau đây đúng với x ∈ Rn :

gi+ (x0 , h) < 0, j ∈ B(x0 )}.

Mệnh đề 1.2.1.
Nếu fi+ (x0 , ·), i ∈ P và gj+ (x0 , ·), j ∈ B(x0 ) là các hàm lồi trên
Rn thì C(Q(x0 ); x0 ) là nón lồi đóng.
Chứng minh.
Cho α > 0 và h ∈ C(Q(x0 ); x0 ). Khi đó, αh ∈ C(Q(x0 ); x0 ), bởi vì
fi+ (x0 , αh) = αfi+ (x0 , h) < 0, i ∈ P,

và tương tự,
gi+ (x0 , αh) < 0, j ∈ B(x0 ).

Bây giờ, giả sử h1 , h2 ∈ C(Q(x0 ); x0 ), và λ ∈ [0, 1] . Bởi vì các hàm
fi+ (x0 , ·), gi+ (x0 , ·) lồi, ta có với i ∈ P,
fi+ (x0 , λh1 + (1 − λ)h2 ) < λfi+ (x0 , h1 ) + (1 − λ)fi+ (x0 , h2 ) < 0,
6


và tương tự, với i ∈ B(x0 ),
gj+ (x0 , λh1 + (1 − λ)h2 ) < 0.

Cuối cùng, C(Q(x0 ); x0 ) là đóng, do sự kiện là nếu ta lấy một dãy
(hk )k ⊂ C(Q(x0 ); x0 ) sao cho hk → h0 , ta suy ra
fi+ (x0 , hk ) < 0, ∀k,

và do đó,
lim fi+ (x0 , hk ) = fi+ (x0 , h0 ) < 0, i ∈ P.
k

Tương tự, ta nhận được

(1.2)

i∈P

Bây giờ ta sẽ chỉ ra rằng với mọi i ∈ P,
T (Qi (x0 ); x0 ) ⊆ C(Qi (x0 ); x0 ).

(1.3)

Giả sử i ∈ P và d ∈ T (Qi (x0 ); x0 ). Ta có dãy (xk )k ⊆ Qi (x0 ) và dãy
(tk )k trong R với tk > 0 sao cho
lim xk = x0 ,

k→∞

lim tk (xk − x0 ) = d.

k→∞

Với k ≥ 1, ta đặt
dk = tk (xk − x0 ).

Khi đó, với mọi j ∈ B(x0 ) và với mọi k ,
gj (xk ) = gj (x0 + (1/tk )dk ) < 0 = gj (x0 ),

(1.4)

f (x0 + (1/tk )dk ) < f (x0 ).

(1.5)

lim dk = d,

k→∞

ta nhận được
gj+ (x0 , d) < 0,

j ∈ B(x0 ),
8

(1.10)


fs+ (x0 , d) < 0,

s ∈ P i,

(1.11)

cho nên (1.3) đúng. Vì vậy, do sự kiện là mọi C(Qi (x0 ); x0 ) lồi đóng,
ta có
co T (Qi (x0 ); x0 ) ⊆ C(Qi (x0 ); x0 ),
clco T (Qi (x0 ); x0 ) ⊆ C(Qi (x0 ); x0 ).

Vì vậy,
clco T (Qi (x0 ); x0 ) ⊆
i∈P

C(Qi (x0 ); x0 ).
i∈P

9


Định lí 1.3.1.
Giả sử x0 ∈ X là nghiệm hữu hiệu của bài toán (VP); p > 1 và
giả sử rằng:
(B1) Điều kiện chính quy (GGCQ) đúng tại x0 ;
(B2) fk , k ∈ P i , và gj , j ∈ B(x0 ) là tựa lồi tại x0 , fi tựa lõm tại
x0 ;
(B3) fi+ (x0 , ·) là hàm lõm trên Rn ;
(B4) fk+ (x0 , ·), k ∈ P i và gj+ (x0 , ·), j ∈ B(x0 ) là hàm lồi trên Rn .
Khi đó, hệ
fk+ (x0 , d) < 0,

k ∈ P i,

fi+ (x0 , d) < 0,
gj+ (x0 , d) < 0,

(1.13)
(1.14)

j ∈ B(x0 ),

(1.15)

không có nghiệm d ∈ Rn .
Chứng minh.
Giả sử ngược lại tồn tại d ∈ Rn sao cho (1.13)-(1.15) đúng.
Như vậy, ta có d ∈ C(Q(x0 ); x0 ). Sử dụng giả thiết (B1), ta có

lim tnmk (xnmk − x0 ) = dmk .

n→∞

Nếu
dnmk = tnmk (xnmk − x0 )
10

(1.18)


thì với bất kỳ n, ta có
fs (xnmk ) = fs (x0 + (1/tnmk )dnmk ) < fs (x0 ),

s ∈ P i,

(1.19)

gj (xnmk ) = gj (x0 + (1/tnmk )dnmk ) < 0 = gj (x0 ), j ∈ B(x0 ). (1.20)

Bởi vì x0 là nghiệm hữu hiệu của bài toán (VP), với bất kỳ n, ta có
fi (xnmk ) = fi (x0 + (1/tnmk )dnmk ) > fi (x0 ).

(1.21)

Sử dụng (1.19)-(1.20) và giả thiết (B2), ta nhận được
fi (x0 , dnmk ) > 0,

(1.22)



Do (1.25)-(1.27), ta suy ra mâu thuẫn. Định lý được chứng minh.
Nhận xét 1.3.1.
Giả thiết (A1) trong Bổ đề 1.2.1 kéo theo giả thiết (B4).
Bây giờ ta trình bày điều kiện cần Kuhn-Tucker sau đây.
Định lí 1.3.2.
Giả sử rằng các giả thiết của Định lý 1.3.1 đúng. Khi đó, tồn tại
các vectơ λ ∈ Rn và µ ∈ Rm sao cho, với d ∈ Rn ,
i∈P

λi fi+ (x0 , d) +

j∈M

µi gj+ (x0 , d) > 0,

µi gj (x0 ) = 0,

(1.28)
(1.29)

j∈M

11


λ > 0,

(1.30)


trong chương này được tham khảo trong [5], [7].
2.1

Các khái niệm

Giả sử rằng X là không gian Banach thực, không gian đối ngẫu của
X là X ∗ được trang bị tô pô yếu*. Với bất kỳ A ⊂ X , ta kí hiệu clA,
coA và clcoA lần lượt là bao đóng, bao lồi và bao lồi đóng của tập hợp
A. Nón tiếp tuyến liên hoặc nón Bouligand của tập hợp A tại x ∈ clA
là
T (A, x) = {d ∈ X : ∃(tn , dn ) → (0+ , d) sao cho x + tn dn ∈ A}.

Chú ý T (A, x) là nón đóng trong X .

13


Giả sử f : X → R = R ∪ {∞} là hàm giá trị thực mở rộng. Đạo hàm
theo phương Dini dưới và trên của f tại x ∈ X theo phương d ∈ X
được định nghĩa bởi
f (x + td) − f (x)
,
t
t↓0
f (x + td) − f (x)
f + (x; d) = lim sup
.
t
t↓0
f − (x; d) = lim inf

f − (x; d) ≤

x∗ , d , ∀d ∈ X.

sup
x∗ ∈ ∂ ∗ f (x)

Một tập đóng yếu* ∂∗ f (x) được gọi là dưới vi phân suy rộng của f
tại x nếu nó là dưới vi phân suy rộng trên và dưới của f tại x
14


Nhận xét 2.1.1.
Chú ý rằng dưới vi phân suy rộng không nhất thiết là compact yếu*
hoặc lồi. Chẳng hạn, hàm f : R → R, xác định bởi
√
x,
nếu x ≥ 0;
√
f1 (x) =
− −x, nếu x < 0,
có dưới vi phân suy rộng không compact tại 0 là [α; ∞) với α ∈ R.
Mặt khác, hàm f xác định bởi f (x) = − |x| có dưới vi phân suy
rộng không lồi ∂ ∗ f (0) = {1, −1} tại 0.
Định nghĩa 2.1.3.
Hàm f : X → R được gọi là có dưới vi phân suy rộng bán chính
quy trên ∂ ∗ f (x) ⊆ X ∗ tại x ∈ X nếu ∂ ∗ f (x) là đóng yếu* và
f + (x; d) ≤

x∗ , d , ∀ d ∈ X.

ξ, d , ∀d ∈ X.


Chú ý rằng, với mọi x ∈ X , ∂C f (x) là một tập compact yếu* khác
rỗng của X ∗ . Hơn nữa, với mọi x và d ∈ X , ta có
f − (x; d) ≤ f + (x; d) ≤ f 0 (x; d),

cho nên dưới vi phân Clarke ∂C f (x) là một dưới vi phân suy rộng bán
chính quy trên lồi compact yếu* của f tại x. Mặt khác, Ví dụ 2.1 của
[5] chỉ ra rằng bao lồi của dưới vi phân suy rộng trên của một hàm
Lipschitz địa phương có thể bao hàm hẳn trong dưới vi phân Clarke.
Do đó, với bài toán tối ưu bao gồm các hàm Lipschitz địa phương, các
kết quả về điều kiện cần tối ưu biểu diễn dưới ngôn ngữ dưới vi phân
suy rộng bán chính quy trên và dưới vi phân suy rộng trên là tốt hơn
điều kiện tối ưu biểu diễn dưới ngôn ngữ dưới vi phân Clarke.
Giả sử f : X → R hữu hạn tại điểm x ∈ X . Nếu f là nửa liên tục
dưới tại x thì dưới đạo hàm trên Clarke-Rockafellar của f tại x theo
phương v (xem [5]) được xác định bởi
f ↑ (x, v) = lim sup inf [f (x + tv ) − f (x )]/t,
x →f x v →v
t↓0

trong đó x → f x nghĩa là x → x và f (x ) → f (x).
Nếu f là nửa liên tục trên tại x thì dưới đạo hàm dưới ClarkeRockafellar của f tại x theo v được xác định bởi
f ↓ (x, v) = lim sup inf [f (x + tv ) − f (x )]/t.
x →f x v →v
t↓0

Nếu f liên tục tại x thì sự hội tụ x → f x trong các định nghĩa dưới
đạo hàm trên và dưới có thể được đơn giản hóa thành x → x. Dưới

trong đó
f ◦ (x, v) = lim sup [f (x + tv) − f (x )]/t,
x →x
t↓0

f◦ (x, v) = lim inf [f (x + tv) − f (x )]/t
x →x
t↓0

là các đạo hàm theo phương suy rộng dưới và trên Clarke của f tại x
theo v . Dưới vi phân suy rộng Clarke được cho bởi
∂ ◦ f (x) = {x∗ ∈ X ∗ : x∗ , v ≤ f ◦ (x; v), ∀v ∈ X} .

Hơn nữa,
f ◦ (x, v) =

max

x∗ ∈ ∂ ◦ f (x)

x∗ , v ,

f◦ (x, v) =

min

x∗ ∈ ∂◦ f (x)

x∗ , v .



f♦ (x, v) =

min

x∗ ∈ ∂ ♦ f (x)

x∗ , v .

(xem [5]).Do đó, ∂ ♦ f (x) cũng là dưới vi phân suy rộng của f tại x, bởi
vì
fd− (x, v) ≤ f ♦ (x, v) và fd+ (x, v) ≥ f♦ (x, v), với mỗi v ∈ X.

Hơn nữa, nếu X = Rn thì
∂ ◦ f (x) = co v ∈ Rn : ∃{xk } : xk → x, xk ∈ K, f (xk ) → v .

Như vậy, tập compact
v ∈ Rn : ∃{xk } : xk → x, xk ∈ K, f (xk ) → v

là dưới vi phân suy rộng của f tại x. Ở đây K là tập các điểm của Rn ,
trong đó f khả vi với đạo hàm f (x) tại x. Ví dụ sau đây minh họa cho
bao lồi của dưới vi phân suy rộng của hàm Lipschitz địa phương có thể
nằm hẳn trong cả dưới vi phân Clarke và Michel-Penot.
Ví dụ 2.1.1.
Định nghĩa f : R2 → R bởi
f (x, y) = |x| − |y| .

Ta có
∂ ∗ f (0) = {(1, −1), (−1, 1)}


Hàm giá trị vectơ f : X → Rp được gọi là tựa lồi tại x0 ∈ X nếu
với mọi x ∈ X ,
f (x) < f (x0 ) ⇒ f + (x0 ; x − x0 ) < 0.

Ta định nghĩa các tập sau:
Q(x) = {y ∈ X : f (y) < f (x) và g(y) < 0},
Qi (x) = {y ∈ X : fk (y) < fk (x), k ∈ I\{i} và g(y) < 0},
Qi (x) = Q(x), nếu p = 1,
−
C(Q(x), x) = {d ∈ X : f −
i (x) < 0, i ∈ I, và gj (x) < 0, j ∈ J(x)},

C(Qi (x), x) = {d ∈ X : f −
k (x) < 0, k ∈ I\{i},
và gj− (x) < 0, j ∈ J(x)}.

Kết quả sau chỉ ra mối quan hệ giữa nón tiếp tuyến T (Qi (x), x) và
tập C(Q(x), x).
19


Mệnh đề 2.2.1.
Giả sử x ∈ S . Nếu fi− (x; ·) và gj− (x; ·), với i ∈ I và j ∈ J(x) là
các hàm lồi trên X thì
clcoT (Qi (x), x) ⊆ C(Q(x), x).
i∈I

Chứng minh.
Trước tiên, ta chỉ ra rằng C(Qi (x), x) là lồi và đóng với mọi i ∈ I .
Cho α > 0 và d ∈ C(Qi (x), x) . Khi đó, αd ∈ C(Qi (x), x) bởi vì


Phần còn lại của chứng minh ta chứng minh tương tự Bổ đề 1.2.1.
20


Nhận xét 2.2.1.
Chú ý rằng một hàm dưới tuyến tính là một hàm lồi, nhưng điều
ngược lại không đúng. Giả sử, hàm f : [−1, 1] → R được xác định
√
bởi f (x) = 1 − x2 là một hàm lồi nhưng không dưới tuyến tính trên
[−1, 1]. Do đó, Mệnh đề 2.2.1 bổ sung Mệnh đề 3.1 của Li và Zhang [6].
Nhận xét 2.2.2.
Nếu f − (x; d) = f + (x; d) với mọi d ∈ X thì Mệnh đề 2.2.1 bổ sung
cho Mệnh đề 3.1 của Preda và Chitescu [10] bởi vì điều kiện f tựa lồi
tại x có thể bỏ được.
Để nhận được điều kiện cần của bài toán (MP) cho nghiệm hữu hiệu,
ta cần điều kiện chính quy và Bổ đề sau đây.
Định nghĩa 2.2.3.
Ta nói rằng bài toán (MP) thỏa mãn điều kiện chính quy Guignard suy rộng (GGCQ) tại x ∈ S nếu
clcoT (Qi (x), x).

C(Q(x), x) ⊆
i∈I

Bổ đề 2.2.1. [6]
Giả sử x là nghiệm hữu hiệu của bài toán (MP). Nếu fi+0 (x; ·) là
lõm với i0 ∈ X nào đó thì
{d ∈ X : fi+0 (x; ·) < 0} ∩

clcoT (Qi (x), x) = θ.

Bởi vì x0 ∈ S là nghiệm hữu hiệu của bài toán (MP), cho nên hệ sau
đây không có nghiệm d ∈ X :
fi+0 (x0 ; d) < 0,
fk+ (x0 ; d) < 0,

k ∈ I\{i0 },

gj− (x0 ; d) < 0,

j ∈ J(x0 ).

Thật vậy, giả sử ngược lại tồn tại v ∈ X là nghiệm của hệ trên. Điều
đó kéo theo rằng hệ
fi−0 (x0 ; d) < 0,
fk− (x0 ; d) < 0,

k ∈ I\{i0 },

gj− (x0 ; d) < 0,

j ∈ J(x0 ),

có nghiệm v ∈ X . Từ đó ta có v ∈ C(Q(x0 ), x0 ). Vì vậy, với điều kiện
(i) ta có
v ∈ {d ∈ X :fi+0 (x0 ; d) < 0} ∩

clcoT (Qi (x0 ), x0 ).
i∈I

Điều này mâu thuẫn với Bổ đề 2.2.1.


sup
x∗ ∈∂ ∗ fi (x0 )

βj

y ∗ , d > 0, ∀d ∈ X.

sup
y ∗ ∈∂ ∗ gj (x0 )

j∈J(x0 )

Kí hiệu
αi ∂ ∗ fi (x0 ) +

C(x0 ) =
i∈I

βj ∂ ∗ gj (x0 ).
j∈J(x0 )

Ta suy ra
z∗, d

sup
z ∗ ∈C(x0 )

=



0 ∈ cl(
i∈I

βj co∂ ∗ gj (x0 )).
j∈J(x0 )

23