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

TÔ MINH QUYẾT

PHƯƠNG PHÁP HÀM PHẠT MINIMAX
CHÍNH XÁC CHO BÀI TOÁN TỐI ƯU
KHÔNG TRƠN

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

Thái Nguyên - 2017


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

TÔ MINH QUYẾT

PHƯƠNG PHÁP HÀM PHẠT MINIMAX
CHÍNH XÁC CHO BÀI TOÁN TỐI ƯU
KHÔNG TRƠN

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

NGƯỜI HƯỚNG DẪN KHOA HỌC

PGS. TS. ĐỖ VĂN LƯU

Thái Nguyên - 2017


i

Mục lục
Lời cảm ơn

ii

Bảng ký hiệu

1

Mở đầu

2

1 Cận dưới của tham số phạt của phương pháp hàm phạt minimax chính xác cho bài toán tối ưu đơn mục tiêu không khả
vi
1.1 Các khái niệm và kết quả liên quan . . . . . . . . . . . . . . .
1.2 Phương pháp hàm phạt minimax chính xác . . . . . . . . . . .
1.3 Sự tương đương của bài toán tối ưu có ràng buộc và bài toán
tối ưu phạt . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4
4
6


2 Phương pháp hàm phạt minimax chính xác và định
yên ngựa cho bài toán tối ưu véc - tơ lồi không trơn
2.1 Các khái niệm và kết quả bổ trợ . . . . . . . . . . . . .
2.2 Phương pháp hàm phạt minimax chính xác và định lí
yên ngựa cho bài toán tối ưu véc - tơ không trơn . . . .
2.3 Trường hợp đặc biệt . . . . . . . . . . . . . . . . . . .

7

lí điểm
22
. . . . 22
điểm
. . . . 25
. . . . 42

Kết luận

44

Tài liệu tham khảo chính

45


ii

Lời cảm ơn
Tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy tôi PGS.TS. Đỗ Văn Lưu,

người đã trực tiếp hướng dẫn luận văn, đã tận tình chỉ bảo và hướng dẫn tôi
tìm ra hướng nghiên cứu, tìm kiếm tài liệu, giải quyết vấn đề,... nhờ đó tôi
mới có thể hoàn thành luận văn cao học của mình. Từ tận đáy lòng, tôi xin
bày tỏ lòng biết ơn chân thành và sâu sắc nhất tới Thầy của tôi và tôi sẽ cố
gắng hơn nữa để xứng đáng với công lao của Thầy.
Tôi xin chân thành cảm ơn Ban giám hiệu, phòng Đào tạo trường Đại học
Khoa học - Đại học Thái Nguyên đã quan tâm và giúp đỡ tôi trong suốt thời
gian học tập tại trường. Tôi xin cảm ơn quý thầy cô Khoa Toán - Tin và đặc
biệt là PGS.TS. Nguyễn Thị Thu Thủy, trưởng Khoa Toán - Tin, đã luôn
quan tâm, động viên, trao đổi và đóng góp những ý kiến quý báu trong suốt
quá trình học tập, nghiên cứu và hoàn thành luận văn.
Cuối cùng, tôi muốn bày tỏ lòng biết ơn sâu sắc tới những người thân
trong gia đình, đặc biệt là bố mẹ. Những người luôn động viên, chia sẻ mọi
khó khăn cùng tôi trong suốt thời gian qua và đặc biệt là trong thời gian tôi
theo học khóa thạc sỹ tại trường Đại học Khoa học - Đại học Thái Nguyên.
Thái Nguyên, ngày 24 tháng 4 năm 2017
Tác giả luận văn

Tô Minh Quyết


1

Bảng ký hiệu
R
Rn
Rm
+
T
KKT

B
∂fi (x)
∧
∨
I(¯
x)
+
gi
L(x, µ, ν)
P∞ (x, c)
(P∞ (c))
V P∞ (x, c)
(V P∞ (c))

trường số thực
không gian Euclide n-chiều
orthant không âm của Rm
chuyển vị của véc - tơ
Karush-Kuhn-Tucker
là hình cầu đơn vị mở trong Rn
dưới vi phân của hàm lồi fi tại x
và
hoặc
tập các chỉ số ràng buộc tích cực
bằng 0 nếu gi (x) ≤ 0, bằng gi (x) nếu gi (x) > 0
hàm Lagrange
hàm phạt minimax chính xác
bài toán tối ưu phạt
hàm phạt minimax chính xác véc - tơ
bài toán tối ưu véc - tơ phạt



2

Mở đầu
Phương pháp hàm phạt chính xác cho phép đưa một bài toán tối ưu phi
tuyến có ràng buộc về một bài toán tối ưu không có ràng buộc sao cho nghiệm
của bài toán tối ưu phạt cũng là nghiệm của bài toán tối ưu có ràng buộc
ban đầu. Antczak ([2], 2013) đã nghiên cứu mối quan hệ giữa nghiệm của
bài toán tối ưu vô hướng có ràng buộc và nghiệm của bài toán tối ưu không
có ràng buộc với hàm mục tiêu là một hàm phạt minimax chính xác và chỉ
ra cận dưới của tham số phạt để hai bài toán đó tương đương. Jayswall Choudhury ([7], 2016) đã thiết lập các định lí điểm yên ngựa cho bài toán tối
ưu véc - tơ có ràng buộc bằng phương pháp hàm phạt minimax chính xác và
xác định các điều kiện để bài toán tối ưu véc - tơ có ràng buộc tương đương
với bài toán không có ràng buộc bằng phương pháp hàm phạt minimax chính
xác. Đây là đề tài nhiều tác giả quan tâm nghiên cứu. Chính vì vậy, tôi chọn
đề tài: "Phương pháp hàm phạt minimax chính xác cho bài toán tối ưu không
trơn".
Mục đích của luận văn trình bày phương pháp hàm phạt minimax chính
xác và các định lí điểm yên ngựa cho bài toán tối ưu đơn mục tiêu của T.
Antczak (đăng trong Tạp chí J. Optim. Theory Appl. 159 (2013), 437 - 453)
và cho bài toán tối ưu véc - tơ của A. Jayswal - S. Choudhury (đăng trong
Tạp chí J. Optim. Theory Appl. 169 (2016), 179 - 199) có ràng buộc đẳng
thức và bất đẳng thức.
Bố cục luận văn gồm phần mở đầu, hai chương trình bày nội dung của
luận văn, phần kết luận và danh mục tài liệu tham khảo.


3


Chương 1: "Cận dưới của tham số phạt của phương pháp hàm phạt minimax chính xác cho bài toán tối ưu đơn mục tiêu không khả vi" trình bày các
kết quả của Antczak [2] về phương pháp hàm phạt minimax chính xác, và sự
tương đương của bài toán tối ưu có ràng buộc và bài toán tối ưu không có
ràng buộc phạt được chứng minh khi tham số phạt lớn hơn một giá trị cận
dưới.
Chương 2: "Phương pháp hàm phạt minimax chính xác và định lí điểm
yên ngựa cho bài toán tối ưu véc - tơ lồi không trơn" trình bày các kết quả
của Jayswal - Choudhury [7], phương pháp hàm phạt minimax chính xác và
các định lí điểm yên ngựa cho bài toán tối ưu véc - tơ lồi không trơn với các
hàm Lipschitz địa phương.


4

Chương 1

Cận dưới của tham số phạt của
phương pháp hàm phạt minimax
chính xác cho bài toán tối ưu đơn
mục tiêu không khả vi
Chương này trình bày phương pháp hàm phạt minimax chính xác và sự
tương đương của bài toán tối ưu có ràng buộc và bài toán tối ưu phạt không
có ràng buộc. Các kết quả trình bày trong chương này là của T. Antczak [2].
1.1

Các khái niệm và kết quả liên quan

Hàm f : X → R xác định trên tập lồi X ⊂ Rn được gọi là lồi nếu với
∀z, x ∈ R và λ ∈ [0, 1], ta có
f (λz + (1 − λ)x) ≤ λf (z) + (1 − λ)f (x).

Định nghĩa 1.1.1 Dưới vi phân của hàm lồi f : Rn → R tại x ∈ Rn được
xác định như sau:
∂f (x) := {ξ ∈ Rn : f (z) − f (x) ≥ ξ T (z − x), ∀z ∈ Rn }.
Định nghĩa 1.1.2 Trên vi phân của hàm lõm f : Rn → R tại x ∈ Rn được
xác định như sau:
∂f (x) := {ξ ∈ Rn : f (z) − f (x) ≤ ξ T (z − x), ∀z ∈ Rn }.


5

Nhận xét 1.1.3 Từ định nghĩa của hàm lồi f : Rn → R tại x, suy ra:
f (z) − f (x) ≥ ξ T (z − x), ∀ξ ∈ ∂f (x),

(1.1)

đúng với ∀z ∈ Rn , trong đó ∂f (x) kí hiệu dưới vi phân của f tại x. Tương
tự, với hàm lõm f : Rn → R tại x, ta có bất đẳng thức:
f (z) − f (x) ≤ ξ T (z − x), ∀ξ ∈ ∂f (x),

(1.2)

đúng với ∀z ∈ Rn .
Trước khi chứng minh kết quả chính cho bài toán (P ), ta cần bổ đề sau
đây:
Bổ đề 1.1.4 Giả sử ϕk , k = 1, ..., p, là hàm giá trị thực xác định trên X ⊂
Rn . Với x ∈ X, ta có
p

max ϕk (x) = max
α∈Ω


1≤k≤p

αk ϕk (x),
k=1

p

trong đó Ω := {α = (α1 , ..., αp ) ∈

Rp+

:

αk = 1}.
k=1

Bài toán cực trị đã xét ở đây là bài toán tối ưu phi tuyến tổng quát có
ràng buộc đẳng thức và bất đẳng thức:
(P ) min f (x), x ∈ D = {x ∈ X : gi (x) ≤ 0, i ∈ I, hj (x) = 0, j ∈ J},
trong đó I = {1, ..., m}, J = {1, ..., s}, f : X → R và gi : X → R,
i ∈ I, hj : X → R, j ∈ J là các hàm Lipschitz địa phương trên tập khác rỗng
X ∈ Rn và D là tập chấp nhận được của bài toán (P ).
Để đơn giản ta sẽ đưa vào một số kí hiệu: g := (g1 , ..., gm ) : X → Rm và
h := (h1 , ..., hs ) : X → Rs .
Hơn nữa, ta kí hiệu tập các chỉ số ràng buộc bất đẳng thức tích cực tại
x∈D
I(¯
x) := {i ∈ I : gi (¯
x) = 0}.



6

Định lý 1.1.5 [9] Giả sử x¯ là nghiệm của bài toán (P ) và một điều kiện
chính quy thích hợp thỏa mãn tại x¯. Khi đó tồn tại các nhận tử Lagrange
¯ ∈ Rm và µ
λ
¯ ∈ Rs sao cho
m

s

¯ i ∂gi (¯
λ
x) +

0 ∈ ∂f (¯
x) +
i=1

µ
¯i ∂hj (¯
x),

(1.3)

j=1

¯ i gi (¯

λ
x) = 0,

i ∈ I,

(1.4)

¯ ≥ 0.
λ

(1.5)

Định nghĩa 1.1.6 Điểm x¯ ∈ D được gọi là điểm Karush-Kuhn-Tucker trong
¯ ∈ Rm và µ
bài toán (P ) nếu tồn tại nhân tử Lagrange λ
¯ ∈ Rs sao cho điều
kiện cần tối ưu Karush-Kuhn-Tucker (1.3) − (1.5) đúng.
1.2

Phương pháp hàm phạt minimax chính xác

Năm 1978 Charalambous [4] đưa vào một lớp các hàm phạt chính xác
không khả vi như sau:
[αi gi+ (x)]p +

Pp (x, α, β, c) := f (x) + c
i=1

1
p


s

m

p
[βj |h+
j (x)|]
j=1

trong đó c là tham số phạt, p ≥ 1, αi > 0, i = 1, ..., m, βj > 0, j = 1, ..., s. Với
một ràng buộc bất đẳng thức gi (x) ≤ 0, hàm gi+ (x) được định nghĩa bởi
gi+ (x) :=

0,
gi (x) ≤ 0,
gi (x), gi (x) > 0.

(1.6)

là bằng 0 với mọi x thỏa mãn ràng buộc và có giá trị dương khi ràng buộc
này bị vi phạm. Hơn nữa, sự vi phạm lớn ở gi (x) ≤ 0 đạt giá trị gi+ (x). Như
vậy hàm gi+ (x) có được điểm phạt liên quan với ràng buộc gi (x) ≤ 0.
Với p = 1 và xét các tham số αi , i = 1, ..., m, βj , j = 1, ..., s bằng 1, ta
nhận được hàm phạt chính xác không khả vi được gọi là hàm phạt chính xác
l1 (ta cũng gọi là hàm phạt giá trị tuyệt đối). Phương pháp hàm phạt chính
xác l1 đã được đưa vào bởi Pietrzykowski [8]. Đa số các tài liệu về phương
pháp hàm phạt chính xác không khả vi nghiên cứu các điều kiện đảm bảo
nghiệm tối ưu của bài toán có ràng buộc đã cho cũng là cực tiểu địa phương
của bài toán với hàm phạt chính xác không có ràng buộc.



7

Với p = ∞, ta nhận được hàm phạt minimax chính xác được cho bởi:
P∞ (x, c) := f (x) + c max {gi+ (x), |hj (x)|}.
1≤i≤m
1≤j≤s

(1.7)

Bây giờ, ta sử dụng hàm phạt minimax chính xác giải các bài toán cực trị
(P ). Với bài toán cực trị (P ), ta xây dựng bài toán tối ưu phạt:
(P∞ (c)) P∞ (x, c) := f (x) + c max {gi+ (x), |hj (x)|} → min .
1≤i≤m
1≤j≤s

(1.8)

Ta gọi bài toán tối ưu không ràng buộc xác định ở trên là bài toán tối ưu
phạt minimax hay là bài toán tối ưu phạt với hàm phạt minimax chính xác.
Ý tưởng của phương pháp hàm phạt minimax chính xác là giải bài toán
tối ưu có ràng buộc phi tuyến (P ) qua bài toán tối ưu không có ràng buộc
(P∞ (c)). Hàm phạt minimax chính xác của (P ) là P∞ (x, c) được cho bởi
(1.7), trong đó c > 0 là tham số phạt, với tính chất là tồn tại một cận dưới
c¯ ≥ 0 sao cho với c > c¯ nghiệm tối ưu bất kì của (P ) cũng là một cực tiểu
của bài toán tối ưu phạt (P∞ (c)) với hàm phạt minimax chính xác.
1.3

Sự tương đương của bài toán tối ưu có ràng buộc và bài toán

tối ưu phạt

Trước hết, ta chỉ ra một điểm Karush-Kuhn-Tucker (KKT) trong bài toán
tối ưu có ràng buộc (P ) sẽ cho ta một cực tiểu của hàm phạt minimax chính
xác trong bài toán tối ưu phạt (P∞ (c)) với tham số phạt c trên một ngưỡng
thích hợp nào đó.
Định lý 1.3.1 Giả sử x¯ là điểm Karush-Kuhn-Tucker và điều kiện cần tối ưu
Karush-Kuhn-Tucker (1.3) − (1.5) thỏa mãn tại x¯ với các nhân tử Lagrange
¯ ∈ Rm và µ
λ
¯ ∈ Rs . Kí hiệu J + (¯
x) := {j ∈ J : µ
¯j > 0} và J − (¯
x) :=
{j ∈ J : µ
¯j < 0}. Hơn nữa, ta giả sử hàm mục tiêu f và hàm ràng buộc
gi , i ∈ I(¯
x), hj , j ∈ J + (¯
x) là lồi trên X, còn hàm ràng buộc hj , j ∈ J − (¯
x)
m

s

λ¯i +

là lõm trên X. Nếu c đủ lớn (tức là c ≥
i=1

|¯

µj |, trong đó λ¯i , i =
i=1

1, ..., m, µ
¯j , j = 1, ..., s là các nhân tử Lagrange ứng với gi và hj ), thì x¯ cũng
là cực tiểu của bài toán tối ưu phạt (P∞ (c)) với hàm phạt minimax chính
xác.


8

Chứng minh.
Xét hai trường hợp:
m

s

¯i +
λ

(i)
i=1

|¯
µj | > 0.
i=1

Theo giả thiết, ta có hàm mục tiêu f và hàm ràng buộc gi , i ∈ I(¯
x), hj , j ∈
J + (¯

x) là lồi trên X. Hơn nữa, các hàm ràng buộc hj , j ∈ J − (¯
x) là lõm
trên X. Khi đó, từ (1.1) và (1.2), ta có
f (x) − f (¯
x) ≥ ξ T (x − x¯),

(1.9)

gi (x) − gi (¯
x) ≥ ηiT (x − x¯), i ∈ I(¯
x),

(1.10)

hj (x) − hj (¯
x) ≥ ζjT (x − x¯), j ∈ J + (¯
x),

(1.11)

hj (x) − hj (¯
x) ≤ ζjT (x − x¯), j ∈ J − (¯
x)

(1.12)

đúng với ∀x ∈ X và ∀ξ ∈ ∂f (¯
x), ηi ∈ ∂gi (¯
x), i ∈ I(¯
x), ζj ∈ ∂hj (¯

x), j ∈
+
−
+
¯ i ≥ 0, i ∈ I, µ
J (¯
x) ∪ J (¯
x), tương ứng. Vì λ
¯j > 0, j ∈ J (¯
x), và
−
µ
¯j < 0, j ∈ J (¯
x), cho nên (1.10) − (1.12) kéo theo, ∀x ∈ X,
¯ i gi (x) − λ
¯ i gi (¯
¯ i η T (x − x¯), i ∈ I(¯
λ
x) ≥ λ
x),
i
µ
¯j hj (x) − µ
¯j hj (¯
x) ≥ µ
¯j ζjT (x − x¯), j ∈ J + (¯
x) ∪ J − (¯
x).
Sử dụng các nhân tử Lagrange bằng 0, ta nhận được
¯ i gi (x) − λ

¯ i gi (¯
¯ i η T (x − x¯), i ∈ I,
λ
x) ≥ λ
i

(1.13)

µ
¯j hj (x) − µ
¯j hj (¯
x) ≥ µ
¯j ζjT (x − x¯), j ∈ J.

(1.14)

Lấy tổng hai vế của (1.13) và (1.14) theo i và j, ta được
m

m

¯ i gi (x) −
λ
i=1
s

i=1

(1.15)


µ
¯j ζjT (x − x¯).

(1.16)

s

µ
¯j hj (¯
x) ≥
j=1

¯ i η T (x − x¯),
λ
i
i=1

s

µ
¯j hj (x) −
j=1

m

¯ i gi (¯
λ
x) ≥

j=1



9

Bây giờ, ta cộng hai vế của (1.9), (1.15) và (1.16), ta nhận được
m

m

s

¯ i gi (x) −
λ

f (x) − f (¯
x) +
i=1

s

¯ i gi (¯
λ
x) +
i=1

µ
¯j hj (x) −
j=1

µ

¯j hj (¯
x)
j=1

s

m

¯iηT +
λ
i

T

≥ ξ +

µ
¯j ζjT (x − x¯).
j=1

i=1

Do điều kiện cần tối ưu Karush-Kuhn-Tucker (1.3), ta suy ra
m

m

¯ i gi (x) −
λ


f (x) − f (¯
x) +
i=1

s

s

¯ i gi (¯
λ
x) +
i=1

µ
¯j hj (x) −
j=1

µ
¯j hj (¯
x) ≥ 0.
j=1

Như vây, ta có
m

s

¯ i gi (x) +
λ


f (x) +
i=1

µ
¯j hj (x)
j=1
m

s

¯ i gi (¯
λ
x) +

≥ f (¯
x) +
i=1

µ
¯j hj (¯
x).

(1.17)

j=1

Bây giờ, sử dụng điều kiện cần tối ưu Karush-Kuhn-Tucker (1.4) cùng
với tính chất nhận được của x¯ trong bài toán (P ), ta có bất đẳng thức
m


s

¯ i gi (x) +
λ

f (x) +
i=1

µ
¯j hj (x) ≥ f (¯
x)
j=1

đúng với mọi x ∈ X. Như vậy, do (1.6), ta suy ra
m

s

¯ i g + (x)
λ
i

f (x) +
i=1

|¯
µj ||hj (x)| ≥ f (¯
x).

+

j=1

m

s

¯i +
λ

Chia hai vế của bất đẳng thức trên cho
i=1

|¯
µj | > 0.
j=1


10

Khi đó,
m

1
m

s

¯i +
λ
i=1


m

s

¯i +
λ

j=1
i=1

¯i +
λ
i=1

|hj (x)| ≥

1
m

¯i +
λ

¯i
λ

α
¯k =

¯i +

λ

|¯
µj |
j=1

(1.19)

|¯
µj |
j=1

i=1

α
¯ m+k =

(1.18)

, k = 1, ..., m.

s

m

f (¯
x).

s


i=1

Ta kí hiệu

|¯
µj |
j=1

|¯
µj |
j=1

gi+ (x)

s

i=1

|¯
µj |

|¯
µj |

+

m

j=1


s

λ¯i

f (x) +

|¯
µj |
m

, k = 1, ..., s.

s

¯i +
λ
i=1

(1.20)

|¯
µj |
j=1

ϕk (x) = gk+ (x), k = 1, ..., m.

(1.21)

ϕm+k (x) = |hj (x)|, k = 1, ..., s.


(1.22)

Chú ý rằng, theo (1.19) và (1.20), ta có
m+s

α
¯ k ≥ 0, k = 1, ..., m + s,

α
¯ k = 1.

(1.23)

k=1

Kết hợp (1.18) − (1.22), ta suy ra với mọi x ∈ X,
m+s

1
m

¯i +
λ
i=1

α
¯ k ϕk (x) ≥

f (x) +


s

|¯
µj |

1
m

f (¯
x).

s

¯i +
λ

k=1

j=1

i=1

|¯
µj |
j=1

Như vậy, do (1.19) − (1.22), ta suy ra
m+s

1

¯i +
λ
i=1

α∈Ω

|¯
µj |
j=1

αk ϕk (x) ≥

f (x) + max

s

m

1
¯i +
λ

k=1
i=1

f (¯
x),

s


m

|¯
µj |
j=1


11
m+s

trong đó Ω := {α = (α1 , ..., αm+s ) ∈

Rm+s
+

:

αk = 1}. Theo bổ đề
k=1

1.1.4, suy ra
1
¯i +
λ

1

f (x) + max ϕk (x) ≥

s


m

1≤k≤m+s

¯i +
λ

|¯
µj |
j=1

i=1

f (¯
x).

s

m

|¯
µj |
j=1

i=1

Vì vậy, (1.21) và (1.22) kéo theo
1


f (x) + max {gi+ (x), |hj (x)|}

s

m

¯i +
λ

1≤i≤m
1≤j≤s

|¯
µj |
j=1

i=1

1

≥

m

f (¯
x).

s

¯i +

λ
i=1

(1.24)

|¯
µj |
j=1

Theo giả thiết, x¯ là nghiệm tối ưu của bài toán (P ). Do đó, nó là điểm
chấp nhận được của bài toán (P ). Vì vậy, do (1.6), ta có
max {gi+ (¯
x), |hj (¯
x)|} = 0.

1≤i≤m
1≤j≤s

Kết hợp (1.24) và (1.25), ta thu được
1
m

f (x) + max {gi+ (x), |hj (x)|}

s

¯i +
λ
i=1


≥

|¯
µj |
j=1

1
m

f (¯
x) + max {gi+ (¯
x), |hj (¯
x)|}.

s

¯i +
λ
i=1

1≤i≤m
1≤j≤s

|¯
µj |
j=1

1≤i≤m
1≤j≤s


(1.25)


12
m

s

¯i +
λ

Nhân bất đẳng thức trên với
i=1
m

j=1

s

¯i +
λ

f (x) +
i=1

|¯
µj |
j=1

m


max {gi+ (x), |hj (x)|}

1≤i≤m
1≤j≤s

s

¯i +
λ

≥ f (¯
x) +
i=1

|¯
µj |
j=1

m

max {gi+ (¯
x), |hj (¯
x)|}.

1≤i≤m
1≤j≤s

s


¯i +
λ

Theo giả thiết, c ≥
i=1

sau

|¯
µj | > 0, ta nhận được

|¯
µj |. Vì vậy, theo (1.25), bất đẳng thức
j=1

x), |hj (¯
x)|}
x) + c max {gi+ (¯
f (x) + c max {gi+ (x), |hj (x)|} ≥ f (¯
1≤i≤m
1≤j≤s

1≤i≤m
1≤j≤s

đúng với mọi x ∈ X. Theo định nghĩa của hàm phạt minimax chính xác
P∞ (x, c), ta suy ra
P∞ (x, c) ≥ P∞ (¯
x, c)
(1.26)

đúng với mọi x ∈ X. Điều này có nghĩa x¯ là nghiệm tối ưu của bài toán
phạt (P∞ (c)) với hàm phạt minimax chính xác.
m

s

¯i +
λ

(ii)
i=1

|¯
µj | = 0.
i=1

Khi đó, sử dụng (1.9) và điều kiện cần tối ưu Karush-Kuhn-Tucker (1.3),
ta có
f (x) ≥ f (¯
x)
m

s

¯i +
λ

đúng với mọi x ∈ X. Vì
i=1


|¯
µj | = 0, nên bất đẳng thức trên
i=1

kéo theo
m

s

¯i +
λ

f (x) +
i=1

|¯
µj | max {gi+ (x), |hj (x)|}
j=1

m

s

¯i +
λ

≥ f (¯
x) +
i=1


1≤i≤m
1≤j≤s

|¯
µj | max {gi+ (¯
x), |hj (¯
x)|}.
j=1

1≤i≤m
1≤j≤s


13
m

s

¯i +
λ

Theo giả thiết, c ≥
i=1

|¯
µj | = 0. Do đó, kết hợp với bất đẳng
i=1

thức trên và (1.25), ta có bất đẳng thức sau
f (x) + c max {gi+ (x), |hj (x)|} ≥ f (¯

x) + c max {gi+ (¯
x), |hj (¯
x)|}
1≤i≤m
1≤j≤s

1≤i≤m
1≤j≤s

đúng với mọi x ∈ X. Theo định nghĩa của hàm phạt minimax chính xác
P∞ (x, c), ta suy ra bất đẳng thức sau
P∞ (x, c) ≥ P∞ (¯
x, c)

(1.27)

đúng với mọi x ∈ X. Điều này có nghĩa là x¯ là nghiệm tối ưu của bài
toán phạt (P∞ (c)) với hàm phạt minimax chính xác. Vì vậy, từ (1.26)
s
¯
µj |, điểm Karush-Kuhn-Tucker
và (1.27), với mọi c ≥ m
i=1 |¯
i=1 λi +
x¯ của bài toán tối ưu có ràng buộc là một cực tiểu của bài toán phạt
(P∞ (c)) với hàm phạt minimax chính xác. Định lý được chứng minh.
Hệ quả 1.3.2 Giả sử x¯ là một nghiệm tối ưu của bài toán (P ). Hơn nữa,
giả sử rằng hàm mục tiêu f và hàm ràng buộc gi , i ∈ I(¯
x), hj , j ∈ J + (¯
x)

−
là lồi trên X, các hàm ràng buộc hj , j ∈ J (¯
x) là lõm trên X. Nếu tồn tại
m

s

¯i +
λ

tham số phạt c là đủ lớn (sao cho c ≥
i=1

¯i, i =
|¯
µj |, trong đó λ
i=1

1, ..., m, µ
¯j , j = 1, ..., s là các nhân tử Lagrange ứng với gi và hj ), thì x¯ cũng
là cực tiểu của bài toán phạt (P∞ (c)) với hàm phạt minimax chính xác.
Mệnh đề 1.3.3 Giả sử x¯ là cực tiểu của bài toán phạt (P∞ (c)) với hàm phạt
minimax chính xác. Khi đó, ta có bất đẳng thức
f (x) ≥ f (¯
x)
đúng với mọi x ∈ D.
Chứng minh.
Vì x¯ là nghiệm của bài toán phạt (P∞ (c)) với hàm phạt minimax chính
xác, bất đẳng thức
P∞ (x, c) ≥ P∞ (¯

x, c)
đúng với mọi x ∈ X. Theo định nghĩa của hàm phạt minimax chính xác


14

P∞ (x, c), ta suy ra bất đẳng thức sau
f (x) + c max {gi+ (x), |hj (x)|} ≥ f (¯
x) + c max {gi+ (¯
x), |hj (¯
x)|}
1≤i≤m
1≤j≤s

1≤i≤m
1≤j≤s

đúng với mọi x ∈ X. Như vậy, từ (1.6), mọi x ∈ D, ta có
f (x) ≥ f (¯
x) + c max {gi+ (¯
x), |hj (¯
x)|}
1≤i≤m
1≤j≤s

Lại sử dụng (1.6), ta có bất đẳng thức
f (x) ≥ f (¯
x)
đúng với mọi x ∈ D. Mệnh đề được chứng minh.
Bây giờ, với giả thiết lồi thích hợp cho các hàm có trong bài toán (P ), ta

chứng minh kết quả ngược lại. Như vậy, ta sẽ chỉ ra rằng tồn tại một ngưỡng
c¯ sao cho mọi tham số phạt c vượt quá giá trị này, x¯, là một cực tiểu trong
bài toán phạt (P∞ (c)) với hàm phạt minimax chính xác cũng là nghiệm tối
ưu của bài toán cực trị (P ).
Định lý 1.3.4 Giả sử x¯ là một cực tiểu của bài toán phạt (P∞ (c)) với hàm
m

˜i +
λ

phạt minimax chính xác và tham số phạt c đủ lớn (có nghĩa là c >
s

i=1

|µ˜j |, trong đó x˜ là một điểm Karush-Kuhn-Tucker của (P ) với các nhân
j=1

˜ ∈ Rm và µ
tử Lagrange λ
˜ ∈ Rs ). Hơn nữa, giả sử rằng hàm mục tiêu f và
hàm ràng buộc gi , i ∈ I(˜
x), hj , j ∈ J + (˜
x) là lồi trên X, các hàm ràng buộc
hj , j ∈ J − (˜
x) là lõm trên X. Nếu D là tập các nghiệm chấp nhận được của
bài toán (P ) là tập compact thì x¯ cũng là nghiệm của bài toán cực trị (P ).
Chứng minh.
Để chứng minh x¯ là nghiệm tối ưu của (P ), trước hết chỉ ra x¯ là điểm chấp
nhận được của (P ). Dùng phương pháp phản chứng, chúng ta giả sử x¯ là

không chấp nhận được của (P ). Vì f liên tục, bị chặn dưới trên tập compact
D, theo định lý Weierstrass, f đạt cực tiểu x˜ trên D. Vì vậy, bài toán cực
trị (P ) có nghiệm tối ưu x˜. Do đó điều kiện cần tối ưu Karush-Kuhn-Tucker
˜ ∈ Rm và µ
thỏa mãn tại x˜ với các nhân tử Lagrange λ
˜ ∈ Rs . Theo giả thiết,
hàm mục tiêu f và hàm ràng buộc gi , i ∈ I(˜
x), hj , j ∈ J + (˜
x) là lồi trên X,


15

các hàm ràng buộc hj , j ∈ J − (˜
x) là lõm trên X. Vì vậy, theo (1.1) và (1.2),
ta có các bất đẳng thức sau
f (x) − f (˜
x) ≥ ξ T (x − x˜),
gi (x) − gi (˜
x) ≥ ηiT (x − x˜), i ∈ I(˜
x),
hj (x) − hj (˜
x) ≥ ζjT (x − x˜), j ∈ J + (˜
x),
hj (x) − hj (˜
x) ≤ ζjT (x − x˜), j ∈ J − (˜
x)
đúng với mọi x ∈ X và mọi ξ ∈ ∂f (˜
x), ηi ∈ ∂gi (˜
x), i ∈ I(˜

x), ζj ∈ ∂hj (˜
x), j ∈
J + (˜
x) ∪ J − (˜
x), tương ứng. Do đó, nó cũng thỏa mãn với x = x¯. Như vậy,
f (¯
x) − f (˜
x) ≥ ξ T (¯
x − x˜),

(1.28)

gi (¯
x) − gi (˜
x) ≥ ηiT (¯
x − x˜), i ∈ I(˜
x),

(1.29)

hj (¯
x) − hj (˜
x) ≥ ζjT (¯
x − x˜), j ∈ J + (˜
x),

(1.30)

hj (¯
x) − hj (˜

x) ≤ ζjT (¯
x − x˜), j ∈ J − (˜
x).

(1.31)

Bởi vì các điều kiện cần tối ưu Karush-Kuhn-Tucker (1.3) − (1.5) thỏa mãn
˜ ∈ Rm và µ
˜ i ≥ 0, i ∈
tại x˜ với các nhân tử Lagrange λ
˜ ∈ Rs , và hơn nữa, λ
I, µ
˜j > 0, j ∈ J + (˜
x), µ
˜j < 0, j ∈ J − (˜
x), ta nhận được
˜ i gi (¯
˜ i gi (˜
˜ i η T (¯
λ
x) − λ
x) ≥ λ
˜), i ∈ I,
i x−x

(1.32)

µ
˜j hj (¯
x) − µ

˜j hj (˜
x) ≥ µ
˜j ζjT (¯
x − x˜), j ∈ J.

(1.33)

Lấy tổng hai vế của (1.32) và (1.33) theo i và j, ta được
m

m

˜ i gi (¯
λ
x) −
i=1

m

˜ i gi (˜
λ
x) ≥
i=1

s

j=1

(1.34)


µ
˜j ζjT (¯
x − x˜).

(1.35)

i=1

s

µ
˜j hj (¯
x) −

˜ i η T (¯
λ
˜),
i x−x
s

µ
˜j hj (˜
x) ≥
j=1

j=1

Bây giờ, ta cộng hai vế của (1.28), (1.34) và (1.35), ta nhận được
m


m

˜ i gi (¯
λ
x) −

f (¯
x) − f (˜
x) +
i=1

s

˜ i gi (˜
λ
x) +
i=1

s

µ
˜j hj (¯
x) −
j=1

µ
˜j hj (˜
x)
j=1



16
s

m

˜iηT +
λ
i

T

≥ ξ +

µ
˜j ζjT (¯
x − x˜).
j=1

i=1

Do điều kiện cần tối ưu Karush-Kuhn-Tucker (1.3), ta suy ra
˜ i gi (˜
λ
x) +

˜ i gi (¯
λ
x) −


f (¯
x) − f (˜
x) +

µ
˜j hj (¯
x) −
j=1

i=1

i=1

s

s

m

m

µ
˜j hj (˜
x) ≥ 0.
j=1

Như vậy, ta có
m

s


m

˜ i gi (¯
λ
x) +

f (¯
x) +

˜ i gi (˜
λ
x) +

µ
˜j hj (¯
x) ≥ f (˜
x) +

i=1

j=1

s

i=1

µ
˜j hj (˜
x).

j=1

Từ tính chất nhận được của x˜ trong bài toán (P ) và điều kiện cần tối ưu
Karush-Kuhn-Tucker (1.2), ta suy ra
m

s

˜ i gi (¯
λ
x) +

f (¯
x) +
i=1

µ
˜j hj (¯
x) ≥ f (˜
x).
j=1

Sử dụng (1.6), ta nhận được
s

m

˜ i g + (¯
λ
i x)


f (¯
x) +

j=1

i=1
m

i=1
m

s

˜i +
λ
i=1

|˜
µj | > 0.
j=1

s

˜i +
λ

Bây giờ, ta giả sử

|˜

µj | hj (¯
x) ≥ f (˜
x).

+

|˜
µj | > 0. Ta chia bất đẳng thức trên cho
j=1


17

Như vậy
m

1
m

f (¯
x) +

s

˜i +
λ
i=1

m


s

˜i +
λ

j=1
i=1

˜i +
λ
i=1

|hj (¯
x)| ≥

1
m

˜i +
λ

λ˜i

α
˜k =

m

(1.36)


|˜
µj |
j=1

, k = 1, ..., m.

s

˜i +
λ

(1.37)

|˜
µj |

i=1

α
˜ m+k =

f (˜
x).

s

i=1

Ta kí hiệu


|˜
µj |
j=1

|˜
µj |
j=1

gi+ (¯
x)

s

i=1

|˜
µj |

|˜
µj |

+

m

j=1

s

λ˜i


j=1

|˜
µj |
m

, k = 1, ..., s.

s

˜i +
λ
i=1

(1.38)

|˜
µj |
j=1

ϕk (¯
x) = gk+ (¯
x), k = 1, ..., m.

(1.39)

ϕm+k (¯
x) = |hj (¯
x)|, k = 1, ..., s.


(1.40)

Chú ý rằng, theo (1.37) và (1.38), ta có
m+s

α
˜ k ≥ 0, k = 1, ..., m + s,

α
˜ k = 1.

(1.41)

k=1

Kết hợp (1.36) − (1.40), ta nhận được
m+s

1
m

s

˜i +
λ
i=1

α
˜ k ϕk (¯

x) ≥

f (¯
x) +

1
m

˜i +
λ

k=1

|˜
µj |
j=1

f (˜
x).

s

i=1

|˜
µj |
j=1

Vì vậy, (1.37) − (1.40) kéo theo
m+s


1
m

s

˜i +
λ
i=1

α∈Ω

|˜
µj |
j=1

αk ϕk (¯
x) ≥

f (¯
x) + max

1
m

˜i +
λ

k=1
i=1


f (˜
x).

s

|˜
µj |
j=1


18
m+s

trong đó Ω := {α = (α1 , ..., αm+s ) ∈

Rm+s
+

:

αk = 1}. Theo bổ đề 1.1.4,
k=1

suy ra
1
m

f (¯
x) + max ϕk (¯

x) ≥

s

˜i +
λ
i=1

1≤k≤m+s

1
m

f (˜
x).

s

˜i +
λ

|˜
µj |
i=1

j=1

|˜
µj |
j=1


Như vậy, (1.39) và (1.40) kéo theo
1
m

s

˜i +
λ
i=1

f (¯
x) + max {gi+ (¯
x), |hj (¯
x)|} ≥
1≤i≤m
1≤j≤s

|˜
µj |

1
m

˜i +
λ

j=1

i=1


f (˜
x).

s

|˜
µj |
j=1

Sử dụng (1.6) cùng với tính chất nhận được của x˜ trong bài toán tối ưu (P ),
ta nhận được
1
m

x), |hj (¯
x)|}
f (¯
x) + max {gi+ (¯

s

˜i +
λ
i=1

≥

1≤i≤m
1≤j≤s


|˜
µj |
j=1

1
m

x), |hj (˜
x)|}.
f (˜
x) + max {gi+ (˜

s

˜i +
λ

1≤i≤m
1≤j≤s

|˜
µj |

i=1

j=1
m

s


˜i +
λ

Nhân bất đẳng thức trên với
i=1
m

|˜
µj | > 0, ta nhận được
j=1

s

˜i +
λ

f (¯
x) +
i=1

|˜
µj |
j=1

m

s

˜i +

λ

≥ f (˜
x) +

max {gi+ (¯
x), |hj (¯
x)|}

1≤i≤m
1≤j≤s

i=1

|˜
µj |
j=1

max {gi+ (˜
x), |hj (˜
x)|}.

1≤i≤m
1≤j≤s

(1.42)

Theo giả thiết, x¯ ∈
/ D, và vì x˜ ∈ D, từ (1.6) ta có
max {gi+ (˜

x), |hj (˜
x)|} = 0,

1≤i≤m
1≤j≤s

(1.43)


19

max {gi+ (¯
x), |hj (¯
x)|} > 0.

1≤i≤m
1≤j≤s
m

(1.44)

s

˜i +
λ

Theo giả thiết, c >
i=1

|˜

µj |. Kết hợp, (1.42), (1.43) và (1.44), ta được
j=1

f (¯
x) + c max {gi+ (¯
x), |hj (¯
x)|}
1≤i≤m
1≤j≤s

≥ f (˜
x) + c max {gi+ (˜
x), |hj (˜
x)|}.
1≤i≤m
1≤j≤s

(1.45)

Vì vậy, theo định nghĩa của hàm phạt minimax chính xác P∞ (x, c), ta suy
ra bất đẳng thức
P∞ (¯
x, c) > P∞ (˜
x, c).
(1.46)
Điều này mâu thuẫn với tính tối ưu của x¯ trong bài toán tối ưu phạt (P∞ (c))
với hàm phạt minimax chính xác.
m

s


˜i +
λ

Trong trường hợp
i=1

|˜
µj | = 0, bất đẳng thức (1.42) suy ra từ
j=1

điều kiện cần tối ưu Karush-Kuhn-Tucker (1.3) và bất đẳng thức (1.28). Vì
m

s

˜i +
λ

vậy, theo giả thiết c >
i=1

|˜
µj |, ta suy ra bất đẳng thức (1.46) thỏa
j=1

mãn. Điều này mâu thuẫn với tính tối ưu của x˜ trong bài toán tối ưu phạt
(P∞ (c)) với hàm phạt minimax chính xác.
Vì vậy, ta đã thiết lập được x¯ là điểm chấp nhận được của bài toán cực
trị có ràng buộc (P ).

Như vậy, tính tối ưu của x¯ trong bài toán (P ) được suy ra trực tiếp từ
Mệnh đề 1.3.3. Định lý được chứng minh.
Từ Hệ quả 1.3.2 và Định lý 1.3.4, ta suy ra kết quả sau:
Hệ quả 1.3.5 Giả sử các giả thiết của Hệ quả 1.3.2 và Định lý 1.3.4 thỏa
mãn. Khi đó, tập các nghiệm tối ưu của bài toán (P ) và tập các điểm cực
tiểu của bài toán phạt minimax (P∞ (c)) là trùng nhau.
Chúng ta sẽ minh họa kết quả đã nhận được bằng một ví dụ cho bài toán
tối ưu phi tuyến với các hàm lồi. Chúng ta sẽ sử dụng phương pháp hàm
phạt minimax chính xác.


20

Ví dụ 1.3.6 Xét bài toán tối ưu sau:
(P 1)

min f (x) = |x1 − 1| + |x2 |,

x ∈ D = {x ∈ R2 : g1 (x) = x21 − 3x1 + 2 ≤ 0, h1 (x) = x22 − x2 = 0}.
Chú ý rằng D = {(x1 , x2 ) ∈ R2 : 1 ≤ x1 ≤ 2 ∧ (x2 = 0 ∨ x2 = 1)} và x¯ = (1, 0)
là nghiệm tối ưu của bài toán (P 1). Hơn nữa, dễ chỉ ra cả hàm mục tiêu f
và các hàm ràng buộc g1 và h1 là lồi trên R2 . Để giải bài toán tối ưu đã xét
ta sử dụng phương pháp hàm phạt minimax chính xác. Như vậy, bài toán tối
ưu không ràng buộc sau đây được xây dựng theo phương pháp này:
(P 1∞ (c)) P 1∞ (x, c) = |x1 − 1| + |x2 |
+ c max{max{0, x21 − 3x1 + 2}, |x22 − x2 |} → min .
Chú ý rằng x¯ = (1, 0) là điểm chấp nhận được trong bài toán (P 1) và điều
kiện cần tối ưu Karush-Kuhn-Tucker (1.3) − (1.5) thỏa mãn tại điểm này với
¯ 1 = ξ1 , µ
các nhân tử Lagrange λ

¯1 = ξ2 , trong đó ξ = (ξ1 , ξ2 ) ∈ ∂f (¯
x). Khi
¯ 1 + |¯
đó, theo Định lý 1.3.1 với tham số phạt c thỏa mãn c ≥ λ
µ1 | = 2, thì
x¯ = (1, 0) cũng là một cực tiểu của bài toán tối ưu phạt (P 1∞ (c)) với hàm
phạt minimax chính xác đã cho ở trên.
Ngược lại, bởi vì tất cả các giả thiết của Định lý 1.3.4 đều thỏa mãn, cho
nên x¯ = (1, 0) là cực tiểu của bài toán (P 1∞ (c)), trong đó c > 2 cũng là
nghiệm tối ưu của bài toán (P 1).
Ví dụ tiếp theo xét bài toán tối ưu mà trong đó không phải tất cả các hàm
là lồi. Với những bài toán như thế thì sự tương đương có thể không đúng.
Ví dụ 1.3.7 Xét bài toán tối ưu sau:
(P 2)

min f (x) = x3 ,

x ∈ D = {x ∈ R : g1 (x) = −x − 1 ≤ 0, g2 (x) = −x2 − 3x − 2 = 0}.
Chú ý rằng D = {x ∈ R : x ≥ −1}; x = −1 là nghiệm tối ưu của bài toán
(P 2). Hơn nữa, dễ chỉ ra cả hai hàm mục tiêu f và hàm ràng buộc g2 không
lồi trên R. Tuy nhiên, chúng ta sử dụng phương pháp hàm phạt minimax
chính xác để quyết bài toán cực trị (P 2). Khi đó, ta xây dựng bài toán không


21

ràng buộc sau đây:
(P 2∞ (c)) P 2∞ (x, c) = x3
+ c max{max{0, −x − 1}, max{0, −x2 − 3x − 2}} → min .
Dễ chỉ ra rằng bài toán phạt minimax (P 2∞ (c)) không có cực tiểu tại x = −1

với bất kỳ tham số phạt c > 0. Trong trường hợp này không có sự tương
đương giữa tập nghiệm của bài toán (P 2) và tập cực tiểu của bài toán phạt
(P 2∞ (c)) với hàm phạt minimax chính xác với tham số phạt c.