ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ HỒNG
ĐỘ NHẠY CỦA NGHIỆM HỮU HIỆU
VÀ ĐIỀU KIỆN TỐI ƯU
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - Năm 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ HỒNG
ĐỘ NHẠY CỦA NGHIỆM HỮU HIỆU
VÀ ĐIỀU KIỆN TỐI ƯU
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số : 60.46.36
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TS. ĐỖ VĂN LƯU
Thái Nguyên - Năm 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
i
Mục lục
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Mở đầu 1
Nội dung 4
1 ĐỘ NHẠY CỦA NGHIỆM HỮU HIỆU CỦA BÀI TOÁN
ĐA MỤC TIÊU TUYẾN TÍNH 4
1.1 Bài toán nhiễu . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Độ nhạy của đỉnh . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Độ nhạy của diện . . . . . . . . . . . . . . . . . . . . . . . 14
2 ĐỘ NHẠY VÀ ĐIỀU KIỆN TỐI ƯU CHO NGHIỆM CỦA

lập các điều kiện đủ để nghiệm hữu hiệu của bài toán nhiễu là Lipschitz
địa phương theo tham số nhiễu.
Luận văn trình bày các kết quả nghiên cứu về độ nhạy của đỉnh hữu
hiệu và diện hữu hiệu của bài toán đa mục tiêu tuyến tính nhiễu, độ nhạy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2
Fréchet và độ nhạy Lipschitz của nghiệm hữu hiệu của bài toán đa mục
tiêu phi tuyến với hàm các hàm khả vi Fréchet.
Luận văn bao gồm phần mở đầu, hai chương, kết luận và danh mục
các tài liệu tham khảo.
Chương 1 trình bày các kết quả nghiên cứu của E. El Maghri [8] về
độ nhạy của nghiệm hữu hiệu của bài toán đa mục tiêu tuyến tính nhiễu.
Chú ý rằng các đỉnh của tập chấp nhận được có thể suy biến hoặc không
suy biến. Các điều kiện cần và đủ cấp 2 cho đỉnh hữu hiệu và diện hữu
hiệu của bài toán nhiễu được trình bày trong chương này.
Chương 2 trình bày các điều kiện cần và đủ cấp 1 và cấp 2 của S.
Bolitinéanu và E. El Maghri [6] cho nghiệm hữu hiệu của bài toán tối ưu
đa mục tiêu phi tuyến với các hàm mục tiêu và ràng buộc khả vi Fréchet
trong không gian Banach cùng với các điều kiện đủ để nghiệm hữu hiệu
của bài toán nhiễu thuộc lớp C
1
theo tham số nhiễu. Trong trường hợp
hữu hạn chiều, các điều kiện đủ để nghiệm hữu hiệu của bài toán nhiễu
là Lipschitz địa phương theo tham số nhiễu cũng được trình bày trong
chương này.
Nhân dịp này tác giả xin bày tỏ lòng biết ơn sâu sắc tới PGS. TS. Đỗ
Văn Lưu đã hướng dẫn và chỉ bảo tận tình trong suốt quá trình làm luận
văn. Thầy đã dành nhiều thời gian hướng dẫn và giải đáp các thắc mắc
trong suốt quá trình làm luận văn. Tôi xin được bày tỏ lòng biết ơn sâu
sắc đến thầy.

) min C(p)x,
A(p)x = b(p),
x ≥ 0,
trong đó [C(.), A(.), b(.)] : N (0) → R
r×n
× R
m×n
× R
m
là các hàm của
tham số nhiễu p ∈ N (0), N (0) là lân cận của điểm gốc 0 ∈ R
q
. Ở đây ta
có thể giả thiết rằng bài toán không nhiễu tương ứng với p = 0. Đa diện
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
5
chấp nhận được của (P
p
) là
Γ(p) = {x ∈ R
n
: A(p)x = b(p), x ≥ 0}.
Với mỗi p, tập các nghiệm hữu hiệu (nghiệm Pareto) và tập các nghiệm
hữu hiệu yếu của (P
p
) tương ứng là
E
e
(p) = {x ∈ Γ(p) : x


x∈Γ(p)
λ
T
C(p)x, (1.1)
trong đó λ
T
là chuyển vị của vectơ λ. Ta có kết quả vô hướng hóa sau đây
(xem [14]):
E
σ
(p) = E(Λ
σ
, p), (1.2)
trong đó
Λ
σ
=

R
r
+
\{0}, nếu σ = w,
intR
r
+
, nếu σ = e.
Tất cả các kết quả trình bày trong chương này đúng trong trường hợp
tổng quát hơn khi nón thứ tự R
r
+

tại B ⊂ {1, . . . , n} sao cho (sắp xếp lại các hàng nếu cần):
v =

A
−1
B
b
0

(1.3)
trong đó A
−1
B
b ≥ 0, A
−1
B
là ma trận nghịch đảo của A
B
(rank A
B
= m)với
phân hoạch A = [A
B
A
N
] (sắp xếp lại các cột của A nếu cần) và N =
{1, . . . , n}\B. Cũng sắp xếp lại các biến, ta có thể viết:
Γ = {x =

x

x
B
x
N

∈ R
n
: x
B
+ A
−1
B
(p)A
N
(p)x
N
= A
−1
B
(p)b(p), x ≥ 0}.
(1.5)
Vì vậy ta có thể xác định nhiễu của v bởi
v(p) =

A
−1
B
(p)b(p)
0


= p,
x
1
≥ 0, x
2
≥ 0.
Ta có v = (0, 0) là đỉnh suy biến của đa diện không nhiễu Γ(p = 0).
Nhưng với mọi p < 0, v(p) = (p, 0) cho bởi (1.6) với B = {1} là không
chấp nhận được, và với mọi p > 0, v(p) = (0, −p) với B = {2} cũng không
chấp nhận được.
Do đó, ta tìm một số điều kiện đảm bảo rằng với mọi p gần 0, v(p) là
đỉnh chấp nhận được của đa diện Γ(p). Ta xét các tập chỉ số:
D = {i ∈ B : (A
−1
B
b)
i
= 0}, (1.8)
và
D
c
= {i ∈ B : (A
−1
B
b)
i
> 0}. (1.9)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
8
Sắp xếp lại phân hoạch các cột của A

Với mọi chỉ số i ∈ D, ta kí hiệu hàng thứ i của (A
−1
B
)
D
bởi A
−1
i
và với bất
kỳ chỉ số j, k ∈ {1, . . . , q},
∂
j
b :=
∂b
∂p
j
(0), ∂
2
kj
b :=
∂
2
b
∂p
j
∂p
k
(0),
∂
j

1. Các điều kiện sau đây là các điều kiện cần để với mọi p gần 0, v(p) ∈
Γ(p):
(i) Với mọi i ∈ D, vectơ
J
(i)
= (A
−1
i
{∂
j
b − ∂
j
A
D
c
(A
−1
B
)
D
c
b})
j=1 q
= 0,
và
(ii) Với mọi i ∈ D, q × q− ma trận đối xứng thực
H
(i)
=


D
c
− ∂
2
kj
A
D
c
)
× (A
−1
B
)
D
c
b − (∂
k
A
D
c
(A
−1
B
)
D
c
+ ∂
j
A
D

(A
−1
B
)
D
(p)b(p) = (A
−1
i
(p)b(p))
i∈D
≥ 0,
bởi vì theo (1.9) và tính liên tục (A
−1
B
)
D
c
(p)b(p) > 0 với mọi p gần 0. Kí
hiệu v
i
(p) = A
−1
i
(p)b(p) với mỗi i ∈ D. Sử dụng (1.8) ta suy ra v
i
(p) ≥ 0
tương đương với v
i
(p) ≥ v
i

bán xác định dương là các điều kiện cần. Điều kiện đủ là (1.10) đúng và
ma trận Hessian cho bởi (1.11) là xác định dương. Như vậy ta sẽ chỉ ra
rằng (1.10) và (1.11) tương ứng là J
(i)
và H
(i)
được cho trong bổ đề.
Từ A
−1
B
(p)A
B
(p) = I
m
, trong đó I
m
là m × m− ma trận đồng nhất.
Với mọi j ∈ {1, . . . , q}, ta có
∂A
−1
B
∂p
j
(p) = −A
−1
B
(p)
∂A
B
∂p

(p) =
∂(A
−1
i
(p)b(p))
∂p
j
(p)
= A
−1
i
(p)

−
∂A
B
∂p
j
(p)A
−1
B
(p)b(p) +
∂b
∂p
j
(p)

.
(1.14)
Với p = 0, theo (1.8), (1.14) ta nhận được J

(p)b(p) +
∂b
∂p
j
(p)

+ A
−1
i
(p)

−
∂
2
A
B
∂p
k
∂p
j
(p)A
−1
B
(p)b(p)
−
∂A
B
∂p
j
(p)

B
)
D
c

−
∂A
D
c
∂p
k
(0)(A
−1
B
)
D
c
b +
∂b
∂p
k
(0)

. (1.15)
Cuối cùng, bằng cách sử dụng (1.8), (1.15 ) để đánh giá (∂
2
v
i
/∂p
k

trong đó (A
−1
i
)
j
(tương ứng b
j
) là thành phần thứ j của vectơ A
−1
i
(tương
ứng b) và ∇ là toán tử đạo hàm.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
11
Ví dụ sau đây cho thấy rằng ngay cả khi v là σ- hữu hiệu, thì v(p) vẫn
có thể không là σ- hữu hiệu với bất kỳ p = 0.
Ví dụ 1.2
Với mỗi tham số nhiễu p > 0, xét bài toán
min (x
2
− px
1
, x
2
− 2px
1
),

0 ≤ x
1

B
+ C
N
x
N
=

C
N
x
N
+ C
v
, (1.16)
trong đó

C
N
là rút gọn của ma trận C theo N tức là

C
N
= C
N
− C
B
A
−1
B
A

N
> 0,
hoặc
(ii) Ma trận A(p) ≡ A(0), C(p) ≡ C(0) không phụ thuộc vào p, (tức
là chỉ có nhiễu vế phải của tập chấp nhận được) và
∃λ ∈ Λ
σ
, ∃B ∈ B(v) : λ
T

C
N
≥ 0.
Chứng minh
1. Ta có thể tách chặt một đỉnh từ đa diện của nó:
∃d ∈ R
n
\ {0} : ∀x ∈ Γ \ {v}, d
T
v < d
T
x. (1.19)
Mặt khác, bởi vì v là σ-hữu hiệu của (P), theo (1.2) tồn tại λ ∈ Λ
σ
sao
cho v ∈ E(λ, 0), tức là ∀x ∈ Γ, λ
T
Cv ≤ λ
T
Cx. Từ (1.19) suy ra với mọi

N
k
(k) − C
B
k
(k)A
−1
B
k
A
N
k
là hàm mục tiêu rút gọn và
N
k
= {1, , n}\B
k
. Mặt khác, ta có

c
N
k
(k) = λ
T

C
N
k
+
1

C
N
k
cho bởi (1.17). Nhưng dãy
(B
k
)
k
thuộc tập hữu hạn B(v) cho bởi (1.7). Do đó tồn tại dãy dừng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
13
(B
k
j
)
j
⊂ B(v), tức là
∃J ∈ N
∗
: ∀j ≥ J, B
k
j
= B
k
J
.
Đặt B = B
k
J
. Khi đó N = N

C
N
x
N
+ Cv) ≥ λ
T
Cv,
có nghĩa là v ∈ E(λ, 0). Do đó theo (1.2) v là σ- hữu hiệu của (P).
2. Bây giờ giả thiết rằng tồn tại B ∈ S(v), trong đó S(v) được cho
bởi (1.18). Theo bổ đề 1.1, với mọi p gần 0, v(p) cho bởi (1.6) theo cơ sở
B, tức là B ∈ B(v(p)) là đỉnh của Γ(p). Giả sử rằng điều kiện (i) đúng và
xét ma trận sau:

C
N
(p) = C
N
(p) − C
B
(p)A
−1
B
(p)A
N
(p). (1.23)
Bởi vì p →

C
N
(p) liên tục tại p = 0, từ (i) suy ra với mọi p gần 0

Nhận xét 1.4
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
14
Trong trường hợp không suy biến, ta có thể bỏ cụm từ ”∃B ∈ B(v)”
trong định lí 1.1 bởi vì bất kì đỉnh không suy biến nào cũng xác định bởi
cơ sở duy nhất B (tức là B(v) có một phần tử). Ta cũng có thể bỏ cụm
từ ”∃B ∈ S(v)” bởi vì do nhận xét 1.1, v(p) ∈ Γ(p) với mọi p gần 0.
1.3 Độ nhạy của diện
Cho F là một diện của đa diện đi qua một đỉnh của nó (suy biến hoặc
không suy biến), trong đó đỉnh v cho bởi (1.3). Ta biết rằng F có thể được
xác định bởi B ∈ B(v) và I ⊂ {1, , n} (nói chung I ⊂ N trừ khi v là
không suy biến) tức là
F = {x = (x
B
, x
N
) ∈ Γ : x
I
= 0} (1.24)
Nhiễu của F là diện sau đây của đa diện nhiễu Γ(p)
F (p) = {x ∈ Γ(p) : x
I
= 0} (1.25)
Cũng như trong phần trước, ta sẽ trình bày các điều kiện cần và đủ để
diện F (p) là σ- hữu hiệu (tức là F (p) ⊂ E
σ
(p)) với mọi p gần 0.
Định lý 1.2
Giả sử F là một diện đi qua đỉnh v (suy biến hoặc không) của đa diện
Γ.

).
2. Mỗi khẳng định sau đây là một điều kiện đủ để với mọi p gần 0,
F (p) cho bởi (1.25) là diện σ- hữu hiệu của (P
p
):
(i) Các cột của ma trận

C
N\I
sau đây là độc lập tuyến tính trong
R
r
, và
∃λ ∈ intΛ
σ
, ∃B ∈ S(v), ∃I ⊂ N : λ
T

C
I
> 0, λ
T

C
N\I
= 0,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
15
hoặc
(ii) Các ma trận A(p) ≡ A(0), C(p) ≡ C(0) là hằng số (tức là chỉ

T
x.
Chứng minh
Ta biết rằng mỗi đa diện P ⊂ R
n
có thể viết dưới dạng:
P = {x ∈ R
n
: a
T
j
x ≤ b
j
, ∀j ∈ {1, . . . , l}},
và mỗi diện F của P có dạng:
F = {x ∈ R
n
: a
T
j
x = b
j
, ∀j ∈ J},
trong đó J ⊂ {1, . . . , l}. Đặt d = −

j∈J
a
j
. Lấy x ∈ P \ F , khi đó tồn
tại j


j∈J\{j

}
a
T
j
x = d
T
x.
Bổ đề được chứng minh . 
Bây giờ ta chứng minh định lý 1.2.
1. Bởi vì F là diện σ- hữu hiệu của (P), tồn tại λ ∈ Λ
σ
sao cho
F ⊂ E(λ, 0) cho bởi (1.1) (xem [14]) và từ bổ đề 1.2, ta suy ra
∀k ∈ N
∗
, F = arg min
x∈Γ
c(k)x, (1.26)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
16
trong đó c(k) = λ
T
C + (1/k)d
T
, và d được cho bởi bổ đề 1.2. Do v ∈ F,
theo nhận xét 1.3 và khẳng định 1 của định lý 1.1 áp dụng với mỗi bài
toán vô hướng (1.26), ta nhận được:

= 0}, (1.28)
trong đó I
k
= {i ∈ N
k
:

c
i
(k) > 0}. Do đó, theo (1.27), N
k
\ I
k
= {i ∈
N
k
:

c
i
(k) = 0}. Nhưng dãy (B
k
)
k
nằm trong tập hữu hạn B(v) cho bởi
(1.7). Vì vậy tồn tại một dãy dừng (B
k
j
)
j

(k
j
) = λ
T

C
I
+
1
k
j

d
T
I
> 0,
λ
T

c
N\I
(k
j
) = λ
T

C
N\I
+
1

A
−1
B
A
N
x
N
≤ A
−1
B
b,
x
N
≥ 0,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
17
là
λ
T

C
N
− µ
T
N
+ ν
T
B
A
−1

µ
N
≥ 0, ν
B
≥ 0, x
N
≥ 0, A
−1
B
A
N
x
N
− A
−1
B
b ≤ 0.
Theo (1.4), (1.24 ) ta suy ra với mọi

x = (

x
B
,

x
N
) ∈ F , các điểm
x
N


C
N
(p), ta suy ra
với mỗi λ gần λ và mỗi p gần 0.
λ
T

C
I
(p) > 0. (1.29)
Bởi vì với p = 0, ma trận

C
N\I
(p) = [

C
i
(p)]
i∈N\I
có hạng cột đầy (sắp
xếp lại các hàng nếu cần) ta có thể viết

C
N\I
(p) =


C

λ
T
= [λ
T
λ
T
], λ
T
= −λ
T

C

N\I
(0)

C

N\I
(0)
−1
. (1.31)
Với mọi p gần 0, xét vectơ
λ
T
(p) = [−λ
T

C


(p)

C
N\I
(p) = 0.
Như vậy với mọi p gần 0, khẳng định 1 áp dụng cho diện F (p) chỉ ra
rằng nó là σ- hữu hiệu của bài toán nhiễu (P
p
). Điều kiện đủ cho (ii) ta
có ngay bởi vì

C
N\I
(p) ≡

C
N\I
và

C
I
(p) ≡

C
I
kéo theo λ
T

C
N\I


σ
là hình chiếu của Λ
σ
trên trục λ

.
Nhận xét 1.7
Trường hợp riêng, diện F quy về đỉnh v, xảy ra khi và chỉ khi I = N.
Khi đó, ma trận

C
N\I
là rỗng và nó có hạng cột đầy. Hơn nữa, do nhận
xét trước, do λ

là rỗng, ta có thể bỏ "int" trong định lý 1.2.
Nhận xét 1.8
Trong trường hợp không suy biến, như nhận xét 1.4, chúng ta có thể
bỏ "∃B ∈ B(v)" và " ∃B ∈ S(v)" trong định lý 1.2. Ta cũng có thể bỏ
"∃I ⊂ N" do sự không suy biến của v ∈ F .
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
19
Chương 2
ĐỘ NHẠY VÀ ĐIỀU KIỆN TỐI
ƯU CHO NGHIỆM CỦA BÀI
TOÁN ĐA MỤC TIÊU PHI
TUYẾN
Chương này trình bày các điều kiện cần và đủ cấp 1, cấp 2 cho nghiệm
hữu hiệu của bài toán tối ưu đa mục tiêu phi tuyến khả vi có ràng buộc,

S = {x ∈ X : G(x) = 0, H(x) ∈ R
m
−
}.
Ta xét ba loại nghiệm của bài toán (VOP). Điểm x
∗
∈ S là:
(i) Nghiệm hữu hiệu yếu của bài toán (VOP) khi và chỉ khi x ∈ S
sao cho F (x
∗
) − F (x) ∈ intQ, trong đó intQ là phần trong (tô pô) của Q;
(ii) Nghiệm hữu hiệu của (VOP) khi và chỉ khi x ∈ S sao cho :
F (x
∗
) − F (x) ∈ Q \ {0};
(iii) Nghiệm hữu hiệu chính thường của (VOP) (xem [4]) khi và chỉ
khi tồn tại một nón lồi đóng nhọn K với Q \ {0} ⊂ intK, sao cho x ∈
S để F(x
∗
) − F (x) ∈ K \ {0}.
Các tập điểm hữu hiệu chính thường, điểm hữu hiệu và điểm hữu hiệu
yếu được kí hiệu lần lượt là E
p
, E
e
, E
w
. Rõ ràng là
E
p

và Z
∗
là các đối ngẫu tô pô
của Y và Z; λ, y là giá trị của λ ∈ Y
∗
tại y ∈ Y . Kí hiệu
(h
i
)
i=1, ,m
= H
Với x
∗
∈ S, ta kí hiệu tập chỉ số của các ràng buộc tích cực là
I(x
∗
) = {i ∈ {1, . . . , m} : h
i
(x
∗
) = 0}.
Nón cực và nón cực chặt là
Q
+
= {λ ∈ Y
∗
: λ, y ≥ 0, ∀y ∈ Q},
Q
0
+

\{0}, nếu σ = w,
Q
0
+
, nếu σ = p.
(2.2)
Nhắc lại kết quả vô hướng hóa sau (xem [12]):
E
σ
⊃

λ∈Λ
σ
E(λ). (2.3)
(2.3) trở thành đẳng thức nếu Y là phản xạ và (VOP) là lồi (tức là S là
tập lồi và F là Q-lồi:
∀x, x

∈ X và α ∈ [0, 1], αF (x)+(1−α)F (x

)−F(αx+(1−α)x

) ∈ Q).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
22
Chú ý rằng trong trường hợp này ta giả thiết G là afin và h
i
(i = 1 . . . m)
là các hàm lồi.
Điểm x

, . . . , f
r
).
với tập chỉ số I ⊂ {1, . . . , l} và V = (v
1
, . . . , v
l
), ta kí hiệu |I| là bản số
của I và V
I
= (v
i
)
i∈I
.
Với x
∗
∈ S, ta xét tập
K
σ
(x
∗
) = arg max
J∈J
σ
(x
∗
)
|J|,
trong đó :

) ∈ intR
|J|
+
}, nếu σ = w.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn