10/6/2010 1
MaMH C02012 Chương 3: QHPT không ràng buộc
NỘI DUNG
1. Bài toán QHPT không ràng buộc.
2.
Điều
kiện
tối
ưu
.
2.
Điều
kiện
tối
ưu
.
3. Một số phương pháp giải bài toán QHPT
không ràng buộc.
10/6/2010 2
MaMH C02012 Chương 3: QHPT không ràng buộc
Bài toán Quy hoạch phi tuyến không ràng buộc
có dạng:
( ) min{ ( ) : },
krb n
P f x x ∈
ℝ
trong đó
là hàm phi tuyến.
:
n
f →

bài toán thì
x
∈
ℝ
*
( ) 0.
f x
∇ =
10/6/2010 4
MaMH C02012 Chương 3: QHPT không ràng buộc
Định lý 2
Giả sử là hàm lồi khả vi trên . Khi đó,
là nghiệm cực tiểu toàn cục của bài toán
khi và chỉ khi
f
n
ℝ
*
n
x ∈
ℝ
*
( ) 0.
f x
∇ =
( )
krb
P
10/6/2010 5
MaMH C02012 Chương 3: QHPT không ràng buộc

( ) 0
f x
∇ =
2 *
( )
f x
∇
*
x
n
ℝ
f
10/6/2010 6
MaMH C02012 Chương 3: QHPT không ràng buộc
Ví dụ1:
Cho hàm số
Ta
có
:
2 2
3
3
1 2 1 1
( , ) 3
x x
f x x e x e x
= − +
2
2
1

2
2 2 2
2
1
3
1
6 3
( )
3 9 3
x
x x x
x e
f x
e e xe
 
−
∇ =
 
− −
 
10/6/2010 7
MaMH C02012 Chương 3: QHPT không ràng buộc
II. Phương pháp hướng giảm
1. Ý tưởng
2. Lược đồ chung
3. Định nghĩa hướng giảm
4.
Xác
định
độ

ℝ
1 2
, , , ,
k
x x x
0 1 2
( ) ( ) ( ) ( )
k
f x f x f x f x
≥ ≥ ≥ ≥
và dãy hội tụ đến điểm dừng của
hàm
0 1 2
( ) ( ) ( ) ( )
k
f x f x f x f x
≥ ≥ ≥ ≥
{ }
k
x
*
n
x ∈
ℝ
.
f
(
)
*
( ) 0

: 0;
k
=
1
( )
k
k
x
If
thỏa
mãn
điều
kiện
dừng
Then
dừng thuật toán
Else xác định sao cho
Gán Quay lại bước lặp k.
1
( )
k
x
1
k k k
k
x x t d
+
= +
1
( ) ( )

ta
có
0
n
x ∈
ℝ
n
d ∈
ℝ
f
0
x
0
ε
>
0
t
ε
< <
với
mọi
t
thỏa
mãn
ta
có
0
t
ε
< <

khi d là hướng giảm của tại .
f
n
ℝ
0
n
x ∈
ℝ
n
d∈
ℝ
0
( ), 0
f x d
∇ <
f
0
x
10/6/2010 15
MaMH C02012 Chương 3: QHPT không ràng buộc
Hệ quả 1.Cho hàm khả vi trên và điểm
Nếu thì là một hướng giảm của
tại .
Mệnh
đề
3
.
Giả
sử
hàm

đề
3
.
Giả
sử
hàm
khả
vi
trên
và
.Trong các hướng giảm d của hàm tại có
thì hàm giảm nhanh nhất theo hướng
f
ℝ
( ) 0
f x
∇ ≠
f
0
x
1
d
=
f
0
0
( )
( )
f x
d

trong đó, đối xứng, xác định dương,
và
Cho
và
hướng
giảm
của
hàm
1
( ) ,
2
T T
f x x Ax b x c
= − +
n n
A
×
n
b∈
ℝ
.
c
∈
ℝ
k n
x
∈
ℝ
k
d

t
d Ad
−
= − >
10/6/2010 19
MaMH C02012 Chương 3: QHPT không ràng buộc
ii) Thủ tục quay lui
(xác định khi đã biết )
Mệnh đề 5.Cho hàm khả vi trên , điểm
và
véctơ
thỏa
mãn
.Cho
số
1
k
x
+
k
d
f
n
ℝ
k n
x ∈
ℝ
k n
d
∈

Đầu vào: điểm và hướng giảm của
hàm tại ;
Đầu ra: điểm trên tia
thỏa mãn
k n
x ∈
ℝ
k
d
f
k
x
1
k
x
+
, 0
k k
k k
x t d t
+ >
1
( ) ( )
k k
f x f x
+
<
- Bước 1: Tùy chọn và (chẳng
hạn ). Đặt
- Bước 2: Tính và

( ) ( ) ( ),
k k k k
k
f x f x mt f x d
+
≤ + ∇
1
k
x
+
10/6/2010 21
MaMH C02012 Chương 3: QHPT không ràng buộc
Else và quay về Bước 2.
:
k k
t t
α
=
10/6/2010 22
MaMH C02012 Chương 3: QHPT không ràng buộc
1. Ý tưởng
2. Lược đồ chung
3. Định nghĩa hướng giảm
4. Xác định độ dài bước
+ Thủ tục tìm chính xác theo tia
+ Thủ tục quay lui
5. Tốc độ hội tụ
Tuyến tính; Trên tuyến tính; Bậc 2
10/6/2010 23
MaMH C02012 Chương 3: QHPT không ràng buộc

k sao cho k k x x x x
γ γ
∃ < < ∃ ∀ > − ≤ −
*
x
1 * *
: ;
k k
k
k x x c x x
+
∀ − ≤ −
0 ;
k
c
→
*
x
2
1 * *
0 0
0, : .
k k
k x x x x k k
γ γ
+
∃ > ∃ − ≤ − ∀ >
10/6/2010 24
MaMH C02012 Chương 3: QHPT không ràng buộc
Phương pháp Gradient

k
=
1
( )
k
1
: ( ),
k k k
k
x x t f x
+
= − ∇
arg min{ ( ): ( ( )), 0}
k k
k k
t t f x t f x t
ϕ
= = − ∇ >
10/6/2010 25
MaMH C02012 Chương 3: QHPT không ràng buộc