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

NGUYỄN HỮU ĐẠT

MỘT SỐ THUẬT TOÁN
GIẢI SỐ BÀI TOÁN TỐI ƯU PHI TUYẾN.

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

THÁI NGUYÊN - 2019


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

NGUYỄN HỮU ĐẠT

MỘT SỐ THUẬT TOÁN
GIẢI SỐ BÀI TOÁN TỐI ƯU PHI TUYẾN.
Chuyên ngành: Toán ứng dụng
Mã số
: 8 46 01 12

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

NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. Vũ Vinh Quang

THÁI NGUYÊN - 2019


i

Lời cảm ơn
Trước hết, em xin bày tỏ lịng kính trọng và lòng biết ơn sâu sắc tới TS.
Vũ Vinh Quang, người thầy đã tận tình hướng dẫn, chỉ bảo và cung cấp
những tài liệu rất hữu ích để em có thể hồn thành luận văn.
Xin cảm ơn lãnh đạo Trường Đại học Khoa học - Đại học Thái Nguyên
đã tạo điều kiện giúp đỡ tôi về mọi mặt trong suốt quá trình học tập và
thực hiện luận văn.
Em xin bày tỏ lịng biết ơn tới các thầy, cơ giáo giảng dạy lớp K11C
đã truyền đạt kiến thức và phương pháp nghiên cứu khoa học trong suốt
những năm học vừa qua.
Xin chân thành cảm ơn anh chị em học viên cao học K11C và bạn bè
đồng nghiệp đã động viên và khích lệ tơi trong q trình học tập, nghiên
cứu và làm luận văn.
Tơi xin bày tỏ lịng biết ơn sâu sắc đến gia đình, người thân, những
người ln động viên, khuyến khích và giúp đỡ về mọi mặt để tơi có thể
hồn thành cơng việc nghiên cứu.
Thái Ngun, tháng 4 năm 2019
Tác giả luận văn

Nguyễn Hữu Đạt


ii

Lời cam đoan

Tôi xin cam đoan:
Những nội dung trong luận văn này là do tôi thực hiện dưới sự hướng
dẫn trực tiếp của thầy giáo hướng dẫn TS. Vũ Vinh Quang.
Mọi tham khảo dùng trong luận văn đều được trích dẫn rõ ràng tác giả,
tên cơng trình, thời gian, địa điểm công bố.
Tôi xin chịu trách nhiệm với lời cam đoan của mình.
Thái Nguyên, tháng 4 năm 2019
Tác giả luận văn

Nguyễn Hữu Đạt


iii

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

i

Lời cam đoan

ii

Bảng ký hiệu

v

Mở đầu

1


1 Một số kiến thức cơ bản

3

1.1. Mơ hình tổng qt của bài tốn tối ưu hóa . . . . . . . . .

3

1.2. Phân loại bài toán tối ưu . . . . . . . . . . . . . . . . . . .

4

1.3. Một số phương pháp giải cơ bản bài tốn tuyến tính

. . .

5

1.3.1. Thuật tốn hình học . . . . . . . . . . . . . . . . .

5

1.4. Mơ hình bài tốn quy hoạch lồi tổng quát . . . . . . . . .

6

1.4.1. Khái niệm tập lồi, hàm lồi . . . . . . . . . . . . . .

6


1.4.2. Khái niệm về Gradient và đạo hàm hướng . . . . .

8

1.4.3. Bài toán quy hoạch lồi tổng quát, điều kiện tối ưu .

8

1.4.4. Cực tiểu hàm lồi một biến . . . . . . . . . . . . . .

10

1.5. Phương pháp giải bài tốn quy hoạch tuyến tính tổng qt
trên phần mềm MATLAB . . . . . . . . . . . . . . . . . .

15

2 Một số thuật toán giải số bài toán tối ưu phi tuyến không
ràng buộc

16


iv

2.1. Một số kiến thức cơ bản . . . . . . . . . . . . . . . . . . .

16


2.1.1. Định nghĩa . . . . . . . . . . . . . . . . . . . . . .

16

2.1.2. Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . .

17

2.2. Các thuật toán sử dụng đạo hàm . . . . . . . . . . . . . .

18

2.2.1. Thuật toán Gradient . . . . . . . . . . . . . . . . .

18

2.2.2. Thuật toán đường dốc nhất . . . . . . . . . . . . .

20

2.2.3. Thuật toán Newton . . . . . . . . . . . . . . . . . .

23

2.3. Các thuật tốn khơng sử dụng đạo hàm

. . . . . . . . . .

26


2.3.1. Phương pháp tìm trực tiếp (Direct search) . . . . .

26

2.3.2. Phương pháp Powell . . . . . . . . . . . . . . . . .

27

2.3.3. Phương pháp Nelder và Mead . . . . . . . . . . . .

28

3 Một số thuật toán giải số bài toán tối ưu phi tuyến có ràng
buộc

32

3.1. Một số kiến thức cơ bản . . . . . . . . . . . . . . . . . . .

32

3.1.1. Hàm Lagrange . . . . . . . . . . . . . . . . . . . .

32

3.1.2. Thiết lập điều kiện tối ưu Kuhn - Tucker . . . . . .

33

3.2. Một số thuật toán . . . . . . . . . . . . . . . . . . . . . . .


35

3.2.1. Thuật toán Gradient . . . . . . . . . . . . . . . . .

35

3.2.2. Phương pháp hàm phạt (Penalty function method)

38

Kết luận

52

Tài liệu tham khảo

53


v

Bảng ký hiệu
QHTT Quy hoạch tuyến tính;
xi

tọa độ thứ i của x;

xT


vectơ hàng (chuyển vị của x );

||x||

= chuẩn Euclide của x;

∂f (x)

dưới vi phân của f tại x;

∇f (x)

hoặc đạo hàm của f tại x;

f (x)

đạo hàm f tại x


1

Mở đầu
Mơ hình bài tốn quy hoạch phi tuyến nói chung là một mơ hình quan
trọng trong lớp các bài tốn tối ưu hóa. Mơ hình này có rất nhiều ứng
dụng trong các bài toán cơ học và vật lý, kinh tế và thương mại. Về mặt lý
thuyết, đã có rất nhiều các tài liệu trình bày các thuật tốn lý thuyết giải
mơ hình các bài tốn này trên mơ hình tổng quát. Tuy nhiên việc nghiên
cứu và cài đặt chi tiết các thuật toán và ứng dụng vào một số mơ hình đối
với một số bài tốn cụ thể trong cơ học và vật lý là chưa nhiều người đề
cập đến.

Nội dung chính của luận văn là nghiên cứu cơ sở toán học của các thuật
toán cơ bản giải bài tốn quy hoạch phi tuyến tính khơng ràng buộc và
có ràng buộc, tìm hiểu chi tiết các bước mơ tả thuật toán, xây dựng sơ đồ
khối và cài đặt các thuật tốn trên ngơn ngữ lập trình cụ thể.
Nội dung luận văn gồm ba chương, phần phụ lục được cấu trúc như sau:
Chương 1. Một số kiến thức cơ bản
Trình bày mơ hình tổng qt của bài tốn tối ưu hóa, phân loại bài tốn tối
ưu, các phương pháp biến đổi cơ bản, một số thuật toán giải bài toán tối ưu
hàm lồi một biến, giải bài toán quy hoạch tuyến tính trên MATLAB. Các
kết quả là những kiến thức quan trọng được ứng dụng trong các chương
sau của luận văn.
Chương 2. Mơ hình bài tốn tối ưu hóa phi tuyến
Trong chương này, trình bày một số thuật tốn giải số bài toán tối ưu phi


2

tuyến không ràng buộc. Cụ thể của chương nêu mô hình tổng qt, điều
kiện tối ưu, các thuật tốn sử dụng đạo hàm như thuật toán Gradient,
thuật toán đường dốc nhất, thuật toán Newton, thuật toán Gradient liên
hợp, các thuật tốn khơng sử dụng đạo hàm như thuật tốn tìm trực tiếp,
thuật toán Powell, thuật toán Nelder và Mead.
Chương 3. Một số thuật toán giải số bài toán tối ưu phi tuyến có ràng
buộc
Nội dung của chương là tìm hiểu một số thuật toán giải số bài toán tối ưu
phi tuyến có ràng buộc như khái niệm hàm Lagrange, phương pháp hàm
phạt, các thuật tốn tìm nghiệm xấp xỉ. Các thuật tốn đã được cài đặt
trên mơi trường MATLAB version 7.0.



3

Chương 1

Một số kiến thức cơ bản
Nội dung chính của chương là trình bày mơ hình tổng qt của bài tốn
tối ưu hóa, phân loại bài tốn tối ưu, các phương pháp biến đổi cơ bản,
một số thuật toán giải bài toán tối ưu hàm lồi một biến, giải bài tốn quy
hoạch tuyến tính trên MATLAB. Các kết quả là các kiến thức quan trọng
được ứng dụng trong các chương sau của luận văn. Các kiến thức được
tham khảo trong các tài liệu [1], [2], [4].

1.1.

Mơ hình tổng qt của bài tốn tối ưu hóa

Tối ưu hóa là một trong những lĩnh vực quan trọng của bài tốn có ảnh
hưởng đến hầu hết các lĩnh vực khoa học, công nghệ, kinh tế và xã hội.
Việc tìm giải pháp tối ưu cho một bài tốn thực tế nào đó chiếm một vai
trò hết sức quan trọng như việc tiến hành lập kế hoạch sản xuất hay thiết
kế hệ thống điều khiển các quá trình... Nếu sử dụng các kiến thức trên
nền tảng của toán học để giải quyết các bài toán cực trị, người ta sẽ đạt
được hiệu quả kinh tế rất cao. Điều này phù hợp với mục đích của các bài
tốn đặt ra trong thực tế hiện nay.
Mơ hình bài toán tối ưu tổng quát được phát biểu như sau:


4

Cực đại hóa (cực tiểu hóa) hàm:

f (X) → max/min
Với các điều kiện:
gi (X) = bi , i ∈ J1

(1.1)

gj (X) ≤ bj , j ∈ J2

(1.2)

gk (X) ≥ bk , k ∈ J3

(1.3)

x1 , x2 , ..., xn ≥ 0.

(1.4)

Trong đó f (X) được gọi là hàm mục tiêu, các điều kiện (1.1) được
gọi là ràng buộc đẳng thức. Các điều kiện (1.2), (1.3) được gọi là ràng
buộc bất đẳng thức. Các điều kiện (1.4) được gọi là ràng buộc về dấu.
X = (x1 , x2 , ..., xn )T là vectơ thuộc không gian Rn . Tập các vectơ X thỏa
mãn hệ ràng buộc lập nên một miền D được gọi là miền phương án (hay
miền chấp nhận được), mỗi điểm X ∈ D gọi là một phương án. Một
phương án X ∗ ∈ D làm cho hàm mục tiêu f (X) đạt cực đại hoặc cực tiểu
được gọi là phương án tối ưu.

1.2.

Phân loại bài toán tối ưu


Dựa trên mơ hình tổng qt, người ta thường phân loại lớp các bài toán
tối ưu như sau:
- Quy hoạch tuyến tính: Là những bài tốn mà hàm mục tiêu f (X)
và tất cả các hàm ràng buộc gi (X), gj (X), gk (X) là tuyến tính.
- Quy hoạch phi tuyến: Là những bài toán một trong hàm mục tiêu
f (X) hoặc các hàm ràng buộc gi (X), gj (X), gk (X) là phi tuyến.
- Quy hoạch lồi: Là các bài toán quy hoạch mà các hàm mục tiêu
f (X) là lồi trên tập các ràng buộc D lồi.


5

- Quy hoạch lõm: Là các bài toán quy hoạch mà các hàm mục tiêu
f (X) là lõm trên tập các ràng buộc D lõm.
- Quy hoạch rời rạc: Bài toán tối ưu được gọi là quy hoạch rời rạc
nếu miền ràng buộc D là tập hợp rời rạc. Trong trường hợp riêng khi các
biến chỉ nhận giá trị nguyên thì ta có quy hoạch ngun.
- Quy hoạch đa mục tiêu: Nếu trên cùng một miền ràng buộc ta
xét đồng thời các hàm mục tiêu khác nhau.
Trong các lĩnh vực kinh tế kỹ thuật thì quy hoạch phi tuyến, quy hoạch
tuyến tính là những bài tốn thường gặp.

1.3.
1.3.1.

Một số phương pháp giải cơ bản bài tốn tuyến tính
Thuật tốn hình học

Xét bài toán:

f (x1 , x2 ) = c1 x1 + c2 x2 → M ax;
a11 x1 + a12 x2 ≤ b1 ;
a21 x1 + a22 x2 ≤ b2 ;
...
an1 x1 + an2 x2 ≤ bn ;
x1 ≥ 0; x2 ≥ 0.
Nhận xét
1. Vì các ràng buộc của bài tốn ln ln là các nửa mặt phẳng, do
đó miền phương án luôn luôn là một đa giác lồi (là giao của các nửa
mặt phẳng).
2. Xét đường thẳng f = m được gọi là đường mức. Hiển nhiên khi
đường mức chuyển động song song trong miền phương án thì điểm chạm


6

cuối cùng của đường mức với miền luôn luôn là một trong các đỉnh của đa
giác (hoặc một cạnh của đa giác). Đấy chính là phương án tối ưu cần tìm.
Xuất phát từ nhận xét trên, chúng ta có thuật tốn hình học gồm các
bước như sau:
Thuật tốn:
Bước 1: Vẽ miền phương án D là đa giác lồi bằng cách xác định miền
giao của các nửa mặt phẳng trong hệ ràng buộc.
Bước 2 : Xác định tọa độ của các đỉnh đa giác: Giả sử là các điểm
A1 , A2 , ..., Ak .
Bước 3: Xác định phương án tối ưu
fmax = max(f (A1 ), f (A2 ), ..., f (Ak )).
Chú ý
Trong trường hợp khi miền phương án không phải là miền kín thì tùy
thuộc vào hướng di chuyển của đường mức, chúng ta sẽ xác định được

phương án tối ưu của bài tốn.

1.4.
1.4.1.

Mơ hình bài tốn quy hoạch lồi tổng quát
Khái niệm tập lồi, hàm lồi

a. Tập lồi
Định nghĩa:
Tập C ⊂ Rn được gọi là tập lồi nếu x, y ∈ C ⇒ λx + (1 − λ)y ∈ C,
∀λ ∈ [0; 1]. Nghĩa là nếu x, y ∈ C thì đoạn thẳng [x, y] ∈ C
b. Hàm lồi
Định nghĩa:
Hàm số f (x) là lồi (convex function) trên tập C nếu với mọi cặp điểm
(x1 , x2 ) thuộc C và mọi số λ ∈ [0, 1], ta có:
f [λx1 + (1 − λ)x2 ] ≤ λf (x1 ) + (1 − λ)f (x2 )


7

có nghĩa là điểm x = λx1 + (1 − λ)x2 trong [x1 , x2 ] thì mọi điểm của đồ
thị luôn nằm dưới M1 M2

Điểm A: x = λx1 + (1 − λ)x2
Điểm B: f (x) = λf (x1 ) + (1 − λ)f (x2 )
Điểm C: f (x) = f (λx1 + (1 − λ)x2 )
Một số điều kiện
- Hàm f (x) là lồi, nếu đối với hai điểm x1 , x2 thỏa mãn điều kiện f (x2 ) ≥
f (x1 ) +


f (x1 ).(x2 − x1 )

- Hàm f (x) là hàm lồi, nếu ma trận Hesian H(x) = [∂ 2 f (x)/∂x2 ∂x2 ] là
bán xác định dương. Khi H(x) xác định dương thì hàm f (x) gọi là hàm
lồi chặt.
Cực trị của hàm lồi
Bất cứ cực tiểu địa phương nào của hàm lồi trên tập lồi cũng là cực tiểu
của hàm trên tập đó.
Ta sẽ chứng minh tính chất này bằng phản chứng:
Giả thiết hàm f (x) có hai điểm cực tiểu là x1 và x2 . Vì f (x) là lồi nên:
f (x2 ) − f (x1 ) ≥
Hay

f (x2 )(x2 − x1 )

f (xs ).s ≤ 0

Trong đó s = (x2 − x1 ) là vectơ nối điểm x1 và x2 . Theo (*), hàm f (x)
giảm khi di chuyển theo hướng s khi xuất phát từ điểm x1 . Điều này trái


8

với giả thiết x1 là cực tiểu. Do đó f (x) chỉ có một cực tiểu duy nhất.
Như vậy trong quy hoạch lồi thì giá trị tối ưu địa phương cũng là giá
trị tối ưu toàn cục.
1.4.2.

Khái niệm về Gradient và đạo hàm hướng


+ Gradient của f (x) là một vectơ có các thành phần là đạo hàm riêng
∂f (x)/∂x1
∂f
∂f ∂f
,
, ...,
f (x) =
∂x1 ∂x2
∂xn
+ Vectơ

T

f (x0 ) vng góc với đường mức của f (x) tại x0 , tốc độ hàm f (x)

tăng nhanh nhất theo hướng của

f (x0 ). Nếu đi theo hướng −

f (x0 )

thì f (x) giảm nhanh nhất.
+ Đạo hàm theo hướng z của hàm f (x) tại điểm x0 :
fz (x0 ) =

f (x0 ), z = |

Đó là hình chiếu của vectơ


f (x0 )|.|z|.cos( f (x0 ), z)

f (x0 ) lên hướng z.

+ Ma trận Hessian H(x) là ma trận có các thành phần là Gradient cấp
hai của f (x)


∂2f
 ∂x12∂x1
 ∂f
 ∂x2 ∂x1

H(x) = ∇2 f (x) = 
 ...
 2

∂ f
∂xn ∂x1

1.4.3.

∂2f
∂x1 ∂x2
∂2f
∂x2 ∂x2

...
2


∂ f
∂xn ∂x2

...
...

∂2f
∂x1 ∂xn
∂2f
∂x2 ∂xn

...

...

...

∂2f
∂xn ∂xn









Bài toán quy hoạch lồi tổng quát, điều kiện tối ưu


a. Phát biểu bài tốn
Tìm x sao cho hàm mục tiêu
f (x) → min
Các ràng buộc:
x ∈ C : gi (x) ≤ 0; i = 1, 2, ..., m.


9

trong đó C là tập lồi, f , gi là các hàm lồi trên C.
b. Điều kiện tối ưu
+ Miền nghiệm chấp nhận được:
D = {x ∈ C : gi (x) ≤ 0} : i = 1, 2, ..., m.
+ Khái niệm về điểm yên ngựa (saddle point)
m

Ký hiệu hàm Lagrange L(x, λ) = f (x) +

λi gi (x) = f (x) + λT g(x)

i=1

Khi đó điểm yên ngựa của hàm L(x, λ) là điểm (x∗ , λ∗ ) với x∗ ∈ D; λ∗ ≥ 0
sao cho: L(x, λ∗ ) ≤ L(x∗ , λ∗ ) ≤ L(x∗ , λ). Các thành phần λi của vectơ
λ = [λ1 , ..., λm ]T được gọi là các nhân tử Lagrange.
Khi λ = λ∗ thì điểm (x∗ , λ∗ ) là điểm cao nhất của L(x, λ).
Khi x = x∗ thì điểm (x∗ , λ∗ ) là điểm thấp nhất của L(x, λ).
Phương pháp xác định điểm yên ngựa: Điểm (x∗ , λ∗ ) là điểm yên ngựa của
hàm L(x∗ , λ∗ ) khi và chỉ khi:
+ L(x, λ) = 0

+gi (x) ≤ 0; i = 1, 2, ..., m
+λi gi (x) ≤ 0; i = 1, 2, ..., m
+ Điều kiện cần và đủ của tối ưu
Định lí 1.1
Điểm x∗ là tối ưu khi và chỉ khi
fz (x∗ ) =

f (x∗ ), z ≥ 0; ∀z ∈ D(x∗ )

Tức là nếu xuất phát từ x∗ theo hướng bất kỳ z mà f (x) tăng thì f (x)
đạt giá trị min tại x∗ .
Định lí 1.2 (Định lý Kuhn - Tucker, phát biểu năm 1951)
Giả sử bài toán quy hoạch lồi thỏa mãn điều kiện Slater:
∃x0 ∈ C : gi (x0 ) ≤ 0; i = 1, 2, ..., m


10

Khi đó điều cần và đủ để x∗ trở thành nghiệm tối ưu là tồn tại một vectơ
m chiều, không âm λ∗ = [λ∗1 , λ∗2 , ..., λ∗m ]T sao cho cặp (x∗ , λ∗ ) là điểm yên
ngựa của hàm Lagrange L(x, λ).
Chú ý Điều kiện Slater không được thỏa mãn thì có thể khơng tồn tại
điểm n ngựa của hàm L(x, λ) loại (x∗ , λ∗ ).
Ví dụ 1
Tìm min của f (x) = −x với ràng buộc g = x2 < 0
Ta có x∗ = 0. Hàm Lagrange L(x, λ) = −x + λ.x2
Xác định điểm dừng:
∂L
= −1 + 2λ.x = 0
∂x

Điều kiện Slater không thỏa mãn khi x = 0, do đó khơng tồn tại λ và hàm
L(x, λ) khơng có điểm n ngựa loại (0, λ).
1.4.4.

Cực tiểu hàm lồi một biến

Thuật tốn chia đơi
Cho hàm số f (x) xác định trên đoạn [a, b] với điều kiện f (x) lồi trên
[a, b]. Cần xác định điểm xopt để hàm f (x) đạt min.

Tư tưởng: Thu hẹp dần miền tìm kiếm để xác định được xopt
Bước 1: Chọn hai điểm x1 , x2 ∈ (a, b) bất kỳ
Bước 2: Nếu f (x1 ) < f (x2 ) thì xopt ∈ [a, x2 ]
Nếu f (x1 ) > f (x2 ) thì xopt ∈ [x1 , b]
Nếu f (x1 ) = f (x2 ) thì xopt ∈ [x1 , x2 ]
Thuật tốn chia đơi:
Bước 1: Đặt L = (b − a)
Bước 2: While L > ε


11

x1 = a + L4 , x2 = b −

L
4

f (x1 ) < f (x2 ) thì b := x2
f (x1 ) > f (x2 ) thì a := x1
f (x1 ) = f (x2 ) thì a := x1 , b := x2

L = b − a;
Lặp lại cho đến khi L < ε
Nhận xét
+ Thuật toán chắc chắn hội tụ sau hữu hạn bước lặp, tốc độ hội tụ phụ
thuộc vào việc chọn vị trí của hai điểm x1 , x2 sau từng bước lặp.
+ Phương pháp chia đơi dễ lập trình nhưng khơng tối ưu về tính tốn
vì việc chọn x1 , x2 là tùy ý.
Thuật tốn được mơ phỏng dưới ngơn ngữ lập trình MATLAB.
function cd=chia_doi(a, b, epxilon)
L=b-a;
count = 0;
while L > epxilon
count=count + 1
x1=a + L/4;
x2=b - L/4;
if f(x1) < f(x2)
b = x2;
elseif f(x1) > f(x2)
a = x1;
elseif f(x1) == f(x2)
a = x1;
b = x2;
end;
L= b - a;
end;


12

cd = x1;

Sau đây là kết quả chạy thuật toán giải bài toán
54
f (x) = x2 + , x ∈ [−10, 10].
x
Hiển nhiên hàm f (x) là hàm lồi trên đoạn [1, 10], cực tiểu đạt tại x=3.
Kết quả chạy thuật tốn chia đơi cho trong bảng 2.1
Bảng 2.1: Nghiệm xấp xỉ tối ưu sau các bước lặp
Số bước lặp

Nghiệm tối ưu

Số bước lặp

Nghiệm tối ưu

5

3.6738

35

2.9938

10

3.3165

40

2.9999


15

3.1148

45

2.9982

20

3.0113

50

3.0001

25

3.0275

55

3.0004

30

3.0003

60


3.0000

Nhận xét Thuật toán hội tụ tốt sau 60 bước lặp đạt đến nghiệm
tối ưu.
Thuật tốn mặt cắt vàng
Phương pháp này sử dụng tính chất của dãy Fibonacci {Fn }.

F1 = F2 = 1
(n=3, 4,...)
F = F
+F
n

n−1

n−2

Dãy số Fibonacci có tính chất đặc biệt đáng chú ý là: Tỷ số giữa hai số kế
tiếp nhau của dãy tiến tới tỷ số vàng:
Fn−1
lim
=
n→∞ Fn

√

5−1
2


+ Tư tưởng phương pháp
Đặt bk − ak = 1 và chia [ak , bk ] theo tỷ lệ:
1 − p 1 − 2(1 − p)
=
⇔ p2 + p − 1 = 0
p
1−p


13

Phương trình p2 + p − 1 = 0 có nghiệm dương: p =

√
−1+ 5
2

≈ 0, 61803

Hai số p và (1-p)=0,38197 được gọi là hằng số Fibonacci
+ Trong đoạn [ak , bk ] lấy hai điểm αk , βk theo tỷ lệ:
βk − ak
b k − αk
=
=p
bk − ak
bk − ak

(*)


Nếu chia [ak , bk ] thành hai đoạn thỏa mãn (*) thì ở mỗi phép lặp chỉ cần
tính một giá trị của f(x). Do đó việc tìm giá trị tối ưu x∗ sẽ nhanh hơn so
với việc chia đều [ak , bk ] thành những đoạn bằng nhau.
Các mặt cắt [αk , βk ] thỏa mãn (*) được gọi là mặt cắt vàng và p là
số vàng.
Thuật toán lát cắt vàng
+ Chọn αk , βk theo tỷ lệ vàng (*).
+ Tính giá trị hàm f tại αk và βk và rút ngắn đoạn [ak , bk ]
Nếu f (αk ) < f (βk ) thì lấy giá trị [ak+1 , bk+1 ] = [ak , bk ]
Nếu f (αk ) > f (βk ) thì lấy giá trị [ak+1 , bk+1 ] = [ak , bk ]
Nếu f (αk ) = f (βk ) thì lấy giá trị [ak+1 , bk+1 ] = [ak , bk ]
Giá trị tối ưu x∗ đạt được khi độ dài đoạn còn lại nhỏ hơn sai số
cho trước.
Nhận xét
a/ Trong cả hai trường hợp ta đều có:
bk+1 − ak+1 := p(bk − ak );
b/ Một trong hai điểm chia ở bước sau trùng với điểm chia ở bước trước.
Do đó thuật tốn này cho phép giảm số phép tính.
Thuật tốn mặt cắt vàng được mô phỏng bằng ngôn ngữ MATLAB
function mc=mat_cat_vang_1(a, b, epxilon)
L=b-a;
p=(-1 + sqrt(5))/2; count=0;
while L > epxilon


14

count=count +1
alpha=b - p*L;
beta=a + p*L;

if f(alpha) <= f(beta)
b = beta;
end;
if f(alpha) >f(beta)
a = alpha;
end;
L= b - a;
end;
mc = a;
Sau đây là kết quả chạy thuật toán giải bài toán
f (x) = x2 +

54
, x ∈ [0, 10].
x

Bảng 1.3: Nghiệm xấp xỉ tối ưu sau các bước lặp
Số bước lặp

Nghiệm tối ưu

Số bước lặp

Nghiệm tối ưu

5

3.2204

20


2.9999

10

3.0148

25

3.0000

15

2.9998

30

3.0000

Nhận xét Thuật toán hội tụ tốt sau 30 bước lặp đạt đến nghiệm tối ưu,
tốc độ hội tụ của thuật toán mặt cắt vàng là nhanh hơn thuật tốn chia đơi.


15

1.5.

Phương pháp giải bài tốn quy hoạch tuyến tính tổng
qt trên phần mềm MATLAB


Trong phần mềm MATLAB, bài toán Quy hoạch tuyến tính có dạng
mặc định là:
Hàm mục tiêu: f = C T X → min
Các ràng buộc:
AX < b
Aeq X = beq
Các giới hạn biên của nghiệm lb ≤ X ≤ ub (lb: lower bounds, ub: upper
bounds)
Khi gặp bài toán f = C T X → max, chỉ cần đặt maxf = −min(−f )
Lệnh thường dùng để giải QHTT là:
[X, f val, exitf lag, output] = linprog(C, A, b, A ∈ q, beq, lb, ub)
[X, f val, exitf lag, output] = intprog(C, A, b, Aeq, beq)
Trong đó:
Lệnh linprog để lấy các nghiệm không âm
Lệnh bintprog để lấy các nghiệm nguyên có giá trị 1 hoặc 0.
Trong dấu () là các vectơ và ma trận đã cho của hàm mục tiêu và các ràng
buộc.
Trong dấu [ ] là các đại lượng cần tính:
X - giá trị tối ưu của nghiệm,
f val - giá trị min của hàm mục tiêu.
Exitf lag - số ngun thơng báo kết thúc tính tốn. Các kết quả tính khi
exitf lag = 1, được coi là thành công tốt đẹp, nghĩa là hàm số hội tụ về
một nghiệm. Các kết quả tính tương ứng exitf lag ≤ 0 được coi là không
thành công với các giải thích tương ứng.
Output- cho các thơng tin về phép tính đã thực hiện.


16

Chương 2


Một số thuật toán giải số bài toán
tối ưu phi tuyến không ràng buộc
Nội dung của chương 2 là trình bày một số thuật tốn giải số bài tốn
tối ưu phi tuyến khơng ràng buộc: mơ hình tổng qt, điều kiện tối ưu, các
thuật toán sử dụng đạo hàm như thuật toán Gradient, thuật toán đường
dốc nhất, thuật toán Newton, thuật tốn Gradient liên hợp; các thuật tốn
khơng sử dụng đạo hàm như thuật tốn tìm trực tiếp, thuật toán Powell,
thuật toán Nelder và Mead. Các kết quả được tham khảo trong các tài
liệu [2], [3], [6], [7], [8], [9].

2.1.
2.1.1.

Một số kiến thức cơ bản
Định nghĩa

Cho dãy {xk } hội tụ về dãy x∗ , ta nói:
- Dãy {xk } hội tụ với tốc độ một cấp số nhân công bội q nếu tồn tại k0 ,
0 < q < 1, C < +∞ sao cho ∀k > k0 : Khi đó ta có các đánh giá
||xk+1 − x∗ || ≤ q||xk − x∗ || hoặc ||xk − x∗ || ≤ q k .C
- Dãy {xk } hội tụ với tốc độ trên cấp số nhân nếu ta có:
||xk+1 − x∗ || ≤ qk ||xk − x∗ || hoặc ||xk − x∗ || ≤ q1 .q2 ...qk .C với dãy ||qk || → 0


17

khi k → +∞, C < +∞.
- Dãy {xk } hội tụ với tốc độ bậc hai nếu tồn tại C>0, tồn tại k0 sao cho:
||xk+1 − x0 || ≤ ||xk − x0 ||2 , ∀k > k0 .

2.1.2.

Điều kiện tối ưu

Xét bài tốn: Tìm x∗ để f (x) → min, x ∈ E n trong đó x = [x1 , x2 , ..., xn ]T
+ Điều kiện cần của tối ưu địa phương
1/ f (x) khả vi tại x∗ .
2/

f (x∗ ) = 0 nghĩa là x∗ là điểm dừng

Chú ý Khi thỏa mãn điều kiện cần thì x∗ có thể là cực tiểu địa phương,
cực đại địa phương hoặc điểm yên ngựa.
+ Điều kiện đủ của cực tiểu địa phương
H(x) =

2

f (x) > 0, nghĩa là ma trận Hessian xác định dương.

Ví dụ 2
Xác định các điểm dừng của hàm mục tiêu: f (x) = x31 + x32 + 2x21 + 4x22 + 6
∂f
= 3x21 + 4x1 = 0
∂x1
+ Xác định điểm dừng:

f (x) = 0

Nghiệm của hệ phương trình là các điểm: (0, 0); (0, -8/3); (-4/3, 0); (-4/3,

-8/3)
+ Xác định loại điểm dừng. Tính

2

f (x) :

∂ 2f
∂ 2f
∂ 2f
= 6x1 + 4; 2 = 6x2 + 8;
=0
∂x21
∂x2
∂x1 ∂x2
Ma trận Hessian:
H(x) =

6x1 + 4

0

0

6x2 + 8


18

Các định thức:

D1 = |6x1 + 4|; D2 =

6x1 + 4

0

0

6x2 + 8

Giá trị D1 , D2 và loại điểm dừng cho ở bảng sau:
Điểm x∗
D1
D2
H(x)
Loại điểm dừng

f (x)

(0,0)

4

32

Xác định dương Min địa phương

6

(0, -8/3)


4

-32

Không xác định

Điểm yên ngựa

418/27

(-4/3, 0)

-4

-32

Không xác định

Điểm yên ngựa

194/27

(-4/3, -8/3)

-4

32

Xác định âm


Max địa phương

50/3

Nhận xét Trong trường hợp tổng quát khi hàm mục tiêu là phi tuyến
thì việc xác định các điểm dừng là khơng thực hiện được. Do đó chúng ta
phải nghiên cứu các thuật toán xác định nghiệm xấp xỉ.

2.2.
2.2.1.

Các thuật toán sử dụng đạo hàm
Thuật toán Gradient

Đây là phương pháp phổ biến nhất, ln ln hội tụ.
Thuật tốn sử dụng sơ đồ lặp
x(k+1) = x(k) − λk

f (x(k) )

Trong đó λk là hệ số xác định độ dài của bước đi theo hướng Gradient. Ta
có thể chọn bước đi bằng hằng số cho cả q trình hoặc tính giá trị bước
đi tối ưu theo phương pháp tối ưu một tham số.
Điều kiện dừng lặp ||x(k+1) − x(k) || ≤ ε.
Quy tắc Armijo xác định bước đi tối ưu tổng quát
Bước 1: Chọn λ tùy ý như nhau với mọi bước lặp (chẳng hạn λk = 1),
Xác định điểm x = x(k) − λ

f (x(k) ) là một điểm trên hướng giảm.


Bước 2: Tính f (x) = f (x(k) − λ

f (x(k) ))