10/6/2010 1
MaMH C02012 Chương 4: QHPT có ràng buộc
NỘI DUNG
− Bài toán QHPT có ràng buộc
− Điều kiện tối ưu
−
Một
số
phương
pháp
giải
bài
toán
QHPT
có
−
Một
số
phương
pháp
giải
bài
toán
QHPT
có
ràng buộc.
10/6/2010 2
MaMH C02012 Chương 4: QHPT có ràng buộc
Bài toán Quy hoạch phi tuyến có ràng buộc có
dạng:
trong đó và hàm f xác định trên .

đến
theo
{ }
q n
x ⊂
ℝ
0
.
n
x
∈
ℝ
{ }
q
x
0
x
Ta
nói
dãy
hội
tụ
đến
theo
hướng , ký hiệu nếu tồn
tại dãy số dương sao cho
.
x
∈
ℝ

x x
→
{ }, lim 0
q q
q
t t
→∞
=
0
lim .
q
x x
v
−
=
lim .
q
q
v
t
→ ∞
=
10/6/2010 6
MaMH C02012 Chương 4: QHPT có ràng buộc
Định nghĩa 2. Cho .
Nón tiếp xúc với tại được kí hiệu là
với
n
X
⊂

n
X
⊂
ℝ
0
x X
∈
X
{ }
q
x
0
q
x x
−
0
0
0
( ), lim .
q
q
t
q
x x
f x v
t
+
→
−
∇ =

f x v v T X x
∇ ∀ ∈>
*
x X
∈
*
x
( )
rb
P
10/6/2010 9
MaMH C02012 Chương 4: QHPT có ràng buộc
Hệ quả 1. Giả sử và là điểm cực
tiểu địa phương của bài toán .
Khi đó
Định
lý
2
.
Cho
f
là
hàm
lồi
khả
vi
trên
một
tập
*

X
⊂
ℝ
*
x X
∈
min{ ( ): }
f x x X
∈
* *
( ), 0 ( , ).
f x v v T X x
∇ ≥ ∀ ∈
10/6/2010 10
MaMH C02012 Chương 4: QHPT có ràng buộc
Hệ quả 2. Cho f là hàm lồi khả vi trên tập một
tập mở chứa tập lồi . Điểm là
điểm cực tiểu toàn cục của bài toán quy hoạch
n
X
⊂
ℝ
*
x X
∈
lồi khi và chỉ khi
min{ ( ): }
f x x X
∈
* *


= =


, , 1, ,
i
f g i m
=
, 1, ,
j
h j k
=
n
ℝ
10/6/2010 12
MaMH C02012 Chương 4: QHPT có ràng buộc
Cho Đặt
là tập các chỉ số của các ràng buộc
thỏa mãn chặt tại
0
.
x X
∈
0 0
( ) { {1, , } ( ) 0}
i
I x i m g x
= ∈ =
( ) 0, 1, , ,
i

thỏa
mãn
tại
nếu
0
x X
∈
0 0
( , ) ( ).
T X x S x
⊆
0
x
thỏa
mãn
tại
nếu
x
0 0
( , ) ( ).
T X x S x
=
10/6/2010 14
MaMH C02012 Chương 4: QHPT có ràng buộc
Định lý 3. Điều kiện chính quy được thỏa mãn tại
nếu có một trong các điều kiện sau:
i) Các hàm và đều
là các hàm afin.
ii)
Các

là độc lập tuyến tính.
, 1, ,
j
h j k
=
, 1, ,
i
g i m
=
: ( ) 0, 1, , ; ( ) 0, 1, , ;
n
i j
x g x i m h x j k
∃ ∈ < = = =
ℝ
0 0
( ), ( )
i
g x i I x
∇ ∈
0
( ), 1, ,
j
h x i k
∇ =
10/6/2010 15
MaMH C02012 Chương 4: QHPT có ràng buộc
Định lý 4.(Định lý Karush – Kuhn – Tucker KKT)
Cho các hàm và
là các hàm khả vi liên tục trên một tập mở chứa

h x j k
= =
i)
và
ii) và sao cho
iii) (Điều kiện bù) (6.3)
*
( ) 0, 1, ,
i
g x i m
≤ =
*
( ) 0, 1, , ; (6.1)
j
h x j k
= =
0, 1, ,
i
i m
λ
≥ =
0, 1, ,
j
j k
µ
≥ =
* * *
1 1
( ) ( ) ( ) 0 (6.2)
m k

liên tục trên một tập mở chứa X.
{ : ( ) 0, 1, , },
i
X x g x i m
= ≤ =
, 1, , ,
i
g i m
=
10/6/2010 17
MaMH C02012 Chương 4: QHPT có ràng buộc
Định lý 5. (Định lý KKT cho quy hoạch lồi)
Giả sử các hàm f , là các hàm lồi
khả vi trên một tập mở chứa X và đk Slater được
thỏa mãn. Khi đó là nghiệm cực tiểu của
bài toán khi và chỉ khi thỏa mãn đk
KKT
(
đk
(
6
.
4
)
–
(
6
.
6
))

sau
:
i)
ii) Tồn tại các số sao cho
iii)
*
( ) 0, 1, , ; (6.4)
i
g x i m≤ =
0, 1, ,
i
i m
λ
≥ =
* *
1
( ) ( ) 0 (6.5)
m
i i
i
f x g x
λ
=
∇ + ∇ =
∑
*
( ) 0, 1, , . (6.6)
i i
g x i m
λ

P
1 1
0, , 0, , , ,
m k
λ λ µ µ
≥ ≥
10/6/2010 19
MaMH C02012 Chương 4: QHPT có ràng buộc
Ký hiệu là gradient của hàm L theo x.
x
L
∇
10/6/2010 20
MaMH C02012 Chương 4: QHPT có ràng buộc
Thuật toán 1
Bước 1. Lập hàm Lagrange
Bước
2
.
Giải
hệ
KKT :
1 1
1 1
( , , , , , , ) : ( ) ( ) ( ).
m n
m k i i i j
i j
L x f x g x h x
λ λ µ µ λ µ


≥ ≥


= =


≤ =


= =

10/6/2010 21
MaMH C02012 Chương 4: QHPT có ràng buộc
Mỗi một nghiệm của hệ trên tương ứng với một
bộ tham số là một điểm KKT
của bài toán đang xét.
Ví
dụ
1
Giải
bài
toán
sau
bằng
pp
nhân
tử
Lagrange
x

2. Phương pháp Frank – Wolfe giải bài toán quy
hoạch lồi với ràng buộc tuyến tính.
Xét bài toán QH lồi
trong
đó
f
là
hàm
lồi
trên
và
là
tập
min{ ( ): },
f x x X
∈
2
( )
conv
P
n
ℝ
n
X
⊂
ℝ
trong
đó
f
là

với mọi t thỏa mãn
0
.
x X
∈
n
d ∈
ℝ
0
x
*
0
t
>
0
x td X
+ ∈
*
0 .
t t
< ≤
10/6/2010 25
MaMH C02012 Chương 4: QHPT có ràng buộc