BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
——————–o0o——————–

HOÀNG MINH QUÂN

PHƯƠNG PHÁP TỐI ƯU TOÀN CỤC
GIẢI BÀI TOÁN MALFATTI SUY RỘNG

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

HÀ NỘI, 2018


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
——————–o0o——————–

HOÀNG MINH QUÂN

PHƯƠNG PHÁP TỐI ƯU TOÀN CỤC
GIẢI BÀI TOÁN MALFATTI SUY RỘNG

Chuyên ngành: Toán Giải Tích
Mã số: 8 46 01 02

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

Người hướng dẫn khoa học: PGS.TS. Tạ Duy Phượng

HÀ NỘI, 2018

3

Mục lục
Mở đầu

5

Chương 1 Tổng quan về bài toán Malfatti

10

1.1. Lịch sử phát triển của bài toán Malfatti . . . . . . . . . . . . 10
1.2. Cách dựng các đường tròn giải bài toán Malfatti . . . . . . 14
1.2.1. Cách dựng của Malfatti năm 1803 . . . . . . . . . . . . . . 14
1.2.2. Cách dựng của Steiner năm 1826 . . . . . . . . . . . . . . . 15
1.2.3. Cách dựng của Lob – Richmond . . . . . . . . . . . . . . . 17
1.2.4. Lời giải của V. A. Zalgaller và G. A. Los’ (1994) . . . . . . 18
1.2.5. Phương pháp tối ưu toàn cục giải bài toán Malfatti . . . . . 19
Chương 2 Phương pháp tối ưu toàn cục giải bài toán Malfatti
suy rộng

24

2.1. Điều kiện tối ưu Strekalovsky . . . . . . . . . . . . . . . . . . 24
2.1.1. Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.2. Cực biên và tập bao hàm . . . . . . . . . . . . . . . . . . . 27
2.1.3. Cực đại hóa lồi trên tập chấp nhận được . . . . . . . . . . . 32
2.1.4. Cực tiểu trên phần bù của tập lồi . . . . . . . . . . . . . . . 35

2.2. Thuật toán tìm cực đại hàm lồi trên tập đơn giản . . . . . 42
2.2.1. Xây dựng điều kiện cho baì toán tối ưu . . . . . . . . . . . 42
2.2.2. Sự hội tụ của thuật toán . . . . . . . . . . . . . . . . . . . . 45


4

2.3. Sử dụng thuật toán MAX giải bài toán Malfatti với bốn
hình tròn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.3.1. Bài toán Malfatti và cực đại hóa trên tập lồi

. . . . . . . . 50

2.3.2. Tối ưu toàn cục và thuật toán cho bài toán Malfatti . . . . 53
2.3.3. Các kết quả . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.4. Phương pháp tối ưu toàn cục giải bài toán Malfatti suy
rộng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.4.1. Phương pháp tối ưu toàn cục và thuật toán . . . . . . . . . 66
2.4.2. Một số kết quả . . . . . . . . . . . . . . . . . . . . . . . . . 68
Kết luận

71


5

Mở đầu
1. Lí do chọn đề tài
Vào năm 1803, nhà toán học Ý Malfatti (1731 − 1807) đã phát biểu bài toán
(sau này được gọi là bài toán đá hoa cương Malfatti - Malfatti’s marble Problem)

như sau: Cho một hình lăng trụ đứng tam giác được làm từ một loại chất liệu,
thì dụ khối đá hoa cương. Hãy cắt từ khối đá đó ba hình trụ không chồng lên
nhau có cùng chiều cao bằng chiều cao hình trụ và có tổng thể tích lớn nhất có
thể.

Gianfrancesco Malfatti
Bài toán này dẫn đến bài toán hình học trên mặt phẳng: Hãy cắt từ một tam
giác đã cho ba hình tròn có tổng diện tích lớn nhất.
Malfatti và nhiều người khác cho rằng, ba hình tròn phải tiếp xúc nhau từng đôi
một và mỗi hình tròn phải tiếp xúc với hai cạnh của tam giác. Các hình tròn
thỏa mãn tính chất trên sau này được gọi là hình tròn Malfatti.
Vào năm 1930, Lob và Richmond [6] đã chỉ ra rằng, hình tròn nội tiếp tam giác
đều cùng với hai hình tròn nhỏ hơn lại có tổng diện tích lớn hơn tổng diện tích
các hình tròn Malfatti. Như vậy, hình tròn Malfatti không phải là nghiệm của


6

bài toán Malfatti. Lưu ý rằng, trong thí dụ này, điều kiện “hai đường tròn tiếp
xúc nhau từng đôi một” không thỏa mãn.
Từ đó đến nay đã có khá nhiều lời giải khác nhau dùng công cụ của hình học,
đại số và lượng giác để giải quyết bài toán Malfatti.
Bài toán Malfatti được coi là bài toán đầu tiên của bài toán xếp hình tròn (circle
packing problems), có nhiều ứng dụng trong thực tế.
Bài toán Malfatti có nhiều mở rộng. Hai trong những mở rộng trực tiếp là thay
ba đường tròn bằng một số đường tròn hay thay tam giác bằng tứ diện.
Gần đây, Rensen Enkbat [1] đã phát biểu bài toán Malfatti dưới dạng một bài
toán tìm cực tiểu của hàm lõm (hay cực đại của hàm lồi) và sử dụng các công
cụ của tối ưu toàn cục (điều kiện tối ưu toàn cục cho bài toán cực đại hàm lồi,
được phát biểu bởi Strekalovsky, xem [7]) để xây dựng thuật toán hội tụ giải

bài toán Malfatti.
Sau đó, Rensen Enkbat và M. Barkova [2] đã phát triển phương pháp cho bài
toán Malfatti suy rộng: Xếp bốn hình tròn trong tam giác đã cho sao cho tổng
diện tích của chúng là lớn nhất.
Bài toán Malfatti suy rộng với công cụ giải hiện đại (tối ưu toàn cục) vừa có ý
nghĩa lý thuyết và thực tế, vừa có ý nghĩa khoa học và thời sự. Đó chính là lí do
mà tôi chọn đề tài Phương pháp tối ưu toàn cục giải bài toán Malfatti suy rộng
làm đề tài luận văn cao học.

2. Mục đích nghiên cứu
1) Trình bày tổng quan về bài toán Malfatti.
2) Trình bày lời giải bài toán Malfatti suy rộng nhờ công cụ của tối ưu toàn cục.


7

3. Nhiệm vụ nghiên cứu
1) Đọc và tổng hợp các tài liệu về bài toán Malfatti.
2) Viết một luận văn tổng quan về lời giải bài toán Malfatti suy rộng.

4. Đối tượng và phạm vi nghiên cứu
Nghiên cứu “Phương pháp tối ưu toàn cục giải bài toán Malfatti suy rộng".

5. Phương pháp nghiên cứu
1) Thu thập các tài liệu liên quan tới bài toán Malfatti.
2) Phân tích, tổng hợp và hệ thống các kiến thức liên quan tới đề tài và viết
luận văn trình bày một phương pháp mới giải bài toán Malfatti suy rộng.

6. Dự kiến đóng góp mới
Cố gắng xây dựng bản luận văn như một bản tổng quan về bài toán Malfatti

suy rộng và trình bày phương pháp tối ưu toàn cục giải bài toán Malfatti suy
rộng.

6. Nội dung của luận văn
Ngoài phần mở đầu, kết luận và tài liệu tham khảo. Luận văn gồm hai chương:
Chương 1: Tổng quan về bài toán Malfatti.
Trong chương này, tôi trình bày về lịch sử phát triển của bài toán Malfatti và
một số cách dựng các đường tròn của bài toán Malfatti.
Chương 2: Phương pháp tối ưu toàn cục giải bài toán Malfatti suy rộng.
Trong chương này, tôi trình bày về điều kiện tối ưu toàn cục Strekalovsky cho
bài toán cực đại hàm lồi và việc đưa bài toán Malfatti suy rộng về bài toán cực
đại hàm lồi trên tập lõm.


8

LỜI CẢM ƠN
Với lòng trân trọng và biết ơn sâu sắc, tôi xin chân thành cảm ơn PGS.TS.
Tạ Duy Phượng, người thầy đã tận tình hướng dẫn, giúp đỡ tôi trong suốt quá
trình thực hiện luận văn này.
Tôi cũng xin bày tỏ lời cảm ơn tới các thầy cô giáo trong khoa Toán, Trường
Đại học Sư phạm Hà Nội 2, đã tạo mọi điều kiện thuận lợi giúp đỡ tôi trong
suốt quá trình học tập và hoàn thành luận văn này.
Tôi xin cảm ơn sự giúp đỡ của ban giám hiệu, các thầy cô Trường THPT Ngọc
Tảo, Hà Nội, cảm ơn gia đình cùng toàn thể các bạn, những người thân, đã luôn
ở bên động viên, giúp đỡ và khích lệ tôi hoàn thành luận văn này.
Tôi xin chân thành cảm ơn!
Hà Nội, ngày 12 tháng 6 năm 2018
Học viên Cao học


Hoàng Minh Quân


9

LỜI CAM ĐOAN
Tôi xin cam đoan luận văn này là của chính tôi được thực hiện dưới sự hướng
dẫn của PGS.TS. Tạ Duy Phượng. Nội dung luận văn không sao chép và không
trùng với bất kỳ luận văn nào. Những trích dẫn, kết quả nghiên cứu có trong
luận văn lấy từ các công bố chính thức và có ghi chú rõ ràng. Nếu sai tôi xin
chịu hoàn toàn trách nhiệm.
Hà Nội, ngày 12 tháng 6 năm 2018
Học viên Cao học

Hoàng Minh Quân


10

Chương 1
Tổng quan về bài toán Malfatti
1.1.

Lịch sử phát triển của bài toán Malfatti

Vào năm 1803, nhà toán học Ý Malfatti (1731–1807) đã phát biểu bài toán
(sau này được gọi là bài toán cắt đá hoa cương Malfatti - Malfatti’s marble Problem) như sau: Cho một hình lăng trụ đứng tam giác được làm từ một loại chất
liệu, thí dụ khối đá hoa cương. Hãy cắt từ khối đá đó ba hình trụ không chồng
lên nhau có cùng chiều cao bằng chiều cao hình trụ và có tổng thể tích lớn nhất
có thể. Bài toán này dẫn đến bài toán hình học trên mặt phẳng: Hãy cắt từ một

tam giác đã cho ba hình tròn không chườm lên nhau và có tổng diện tích lớn nhất.

Malfatti và nhiều người khác cho rằng, ba hình tròn là lời giải bài toán phải
tiếp xúc nhau từng đôi một và mỗi hình tròn phải tiếp xúc với hai cạnh của
tam giác. Các hình tròn thỏa mãn tính chất trên sau này được gọi là hình tròn
Malfatti.


11

Malfatti đã dựng ba đường tròn sao cho mỗi đường tròn tiếp xúc với hai đường
còn lại và tiếp xúc với hai cạnh của tam giác (Hình 1.1). Trường hợp tam giác
cân đã được nhà toán học người Thụy Sĩ Jacob Bernoulli (1654 − 1705) xem
xét từ trước. Năm 1826 Jakob Steiner (1796 − 1863) đã tìm ra một cách dựng
“tinh tế” hơn đối với một tam giác cho trước. Các nhà toán học khác như B.
Pl¨
ucker, Cayley và Clebsch cũng quan tâm nghiên cứu vấn đề này. Nhưng tất
cả đều cùng suy nghĩ như Malfatti – đều cho rằng mỗi đường tròn tiếp xúc với
hai cạnh của tam giác. Một thời gian dài sau năm 1803, không ai nghi ngờ lời
giải của Malfatti.

Hình 1.1
Tuy nhiên, Lob và Richmond (1930, [6]) đã phát hiện ra rằng: Các đường tròn
Malfatti không phải là lời giải của bài toán Malfatti. Lob và Richmond nhận
xét rằng, trong tam giác đều, đường tròn nội tiếp tam giác, với hai đường
tròn nhỏ nằm hoàn toàn trong các góc, có diện tích lớn hơn các đường tròn
Malfatti. Lời giải của Malfatti (Hình 1.2) cho tổng diện tích trong tam giác đều
√
3
là

3−
π ≈ 0, 729, gần bằng 73%.
2


12

Hình 1.2 Cách dựng của Malfatti
Lob và Richmond xây dựng ba đường tròn, trong đó đường tròn lớn nhất nội
tiếp tam giác và tiếp xúc với hai đường tròn còn lại; hai đường tròn nhỏ nội tiếp
trong hai góc của tam giác đều
√ và tiếp xúc với đường tròn lớn (Hình 1.3). Tổng
11 3
diện tích ba đường tròn là
≈ 0, 739, gần bằng 74%.
81

Hình 1.3 Cách dựng của Lob và Richmond
Tổng diện tích chỉ tăng 1%, nhưng phát hiện của Lob và Richmond thật ấn
tượng!
Năm 1965, Howard W. Eves (1911 − 2004) tìm ra điều kì lạ hơn: Nếu tam giác
vuông đã cho dài và hẹp, bằng mắt thường cũng có thể thấy lời giải của Malfatti
là không đúng: Các đường tròn kề nhau (Hình 1.4) có tổng diện tích (độ phủ)
xấp xỉ 50%, một tỉ lệ lớn hơn các đường tròn Malfatti (Hình 1.5) có độ phủ vào
khoảng 35%.

Hình 1.4 Độ phủ khoảng 50%


13


Hình 1.5 Các đường tròn Malfatti (Độ phủ khoảng 35%)
Như vậy, các đường tròn Malfatti không phải là lời giải tối ưu của bài toán
Malfatti. Và ta có một bài toán tối ưu hóa:
Tìm ba hình tròn không chườm lên nhau nằm trong tam giác cho trước sao cho
tổng diện tích ba hình tròn là lớn nhất.
Năm 1967, Goldberg [5] đã khẳng định rằng lời giải của Malfatti không đúng
với bất kể hình dạng của tam giác nào được chọn! Đó thực sự là một tiếng sét
giữa trời quang!
Lời giải đúng luôn sử dụng các đường tròn nội tiếp của tam giác ban đầu như
một trong ba đường tròn, cụ thể là, một trong các đường tròn sẽ luôn tiếp xúc
với tất cả các cạnh của tam giác. Cấu hình như vậy là do một trong các cách
sắp xếp sau:

Hình 1.6
Goldberg sử dụng các tính toán và các hình vẽ cho lời giải của ông. Một chứng
minh toán học hoàn chỉnh được đưa ra lần đầu tiên bởi Zalgaller và Los’ [8] năm
1994.
Tuy nhiên, lại có sự ngạc nhiên tiếp theo: Nhà toán học Mông Cổ Rensen Enkbat
đã sử dụng phương pháp tối ưu toàn cục xây dựng thuật toán xấp xỉ hội tụ giải
bài toán Malfatti cho ba hình tròn (2016) [1] và cùng với đồng nghiệp giải bài
toán Malfatti suy rộng với bốn hình tròn (2016) [2], sau đó tiếp tục mở rộng bài
toán Malfatti cho n hình tròn và cho n hình cầu trong không gian (2017) [3].


14

1.2.
1.2.1.


Cách dựng các đường tròn giải bài toán Malfatti
Cách dựng của Malfatti năm 1803

Hình 1.7
Cho tam giác ABC, có ba cạnh BC = a, CA = b, AB = c; ba góc α, β, γ và ba
đường phân giác tương ứng là ωα , ωβ , ωγ . Gọi k(I, r) là đường tròn nội tiếp tam
giác. Các đường tròn Malfatti lần lượt là kA (MA , rA ), kB (MB , rB ), kC (MC , rC )
tiếp xúc với hai cạnh của tam giác và tiếp xúc hai đường tròn còn lại. Sử dụng
định lý Pythagoras và tam giác đồng dạng, ta được ba phương trình:
√
√
√
2r xy
2r zy
2r xz
x+y+ √
= s + t,
z +y+ √
= u + t,
x+z + √
= s + u.
su
st
ut
Độ dài tiếp tuyến x, y, z của các đường tròn Malfatti với các cạnh tam giác
(Xem [10]) là các nghiệm của hệ phương trình trên:
1
s+t+u−r+
2
1

y=
s+t+u−r+
2
1
s+t+u−r+
z=
2

x=

r2 + s2 −

r2 + u2 −

r2 + t2 ,

r 2 + u2 −

r2 + s2 −

r2 + t2 ,

r 2 + t2 −

r 2 + s2 −

r2 + u2 .


15


Từ các phương trình này các đường tròn Malfatti cũng được dựng bằng thước
kẻ và compa.
Tâm I của đường tròn nội tiếp với các bán kính AI, BI, CI dựng được và
s, t, u (độ dài đoạn tiếp tuyến của I trên các cạnh) cũng dựng được. Cách dựng
hình khá dễ dàng nếu nhận ra các mối quan hệ sau:
AI =

r2 + s2 ,

BI =

r 2 + t2 ,

CI =

r 2 + u2 ,

Cách dựng:
Dựng tam giác ABC, các đường phân giác cắt nhau tại tâm I của đường tròn
K (I, r) nội tiếp tam giác sao cho độ dài các đoạn tiếp tuyến của đường tròn
tâm I lần lượt là s, t, u.
Dựng các đoạn phụ tương ứng có độ dài là x, y, z. Đặt các độ dài phụ trong
tam giác được các tiếp điểm A1 , A2 , B1 , B2 , C1 , C2 .
Dựng đường vuông góc với các cạnh của tam giác tại các tiếp điểm
A1 , A2 , B1 , B2 , C1 , C2 cắt các đường phân giác trong tại MA , MB , MC là
tâm của các đường tròn Malfatti kA , kB , kC với các bán kính rA , rB , rC .

1.2.2.


Cách dựng của Steiner năm 1826

Năm 1826, Steiner có nhận xét rằng "Mỗi tiếp tuyến chung của các đường
tròn Malfatti cũng là tiếp tuyến của hai trong số ba đường tròn nội tiếp của
ba tam giác ∆BCI, ∆CAI, ∆ABI, trong đó I là tâm đường tròn nội tiếp
∆ABC."


16

Hình 1.8

Hình 1.9
Trong hình vẽ trên các đường tròn nội tiếp được vẽ bằng đường nét mảnh màu
đỏ, còn các đường tròn Malfatti được vẽ bằng các đường nét đậm màu xanh.
Cách dựng:

Hình 1.10
• Dựng ∆ABC biết ba cạnh a, b, c, các đường phân giác ωα , ωβ , ωγ cắt nhau
tại tâm I của đường tròn k(I, r) nội tiếp ∆ABC.
• Dựng các đường tròn kP , kQ , kR nội tiếp các tam giác ∆BCI, ∆CAI, ∆ABI.
• Gọi P, Q, R lần lượt là tiếp điểm của các đường tròn trên các cạnh tam giác.
• Từ P, Q, R dựng các tiếp tuyến tương ứng với các cặp đường tròn đối diện.
• Dựng phân giác của các góc XQY , XP B và XP C.


17

• Giao điểm của các đường phân giác đó với ωα , ωβ , ωγ là MA , MB , MC và là
tâm của các đường tròn Malfatti kA , kB , kC .

• Dựng các đường tròn kA , kB , kC có tâm là MA , MB , MC và bán kính bằng
khoảng cách từ các tâm đến hai cạnh của tam giác.

Hình 1.11 cách dựng của Steiner

1.2.3.

Cách dựng của Lob – Richmond

Hình 1.12 Cách dựng của Lob và Richmond
Cách dựng sau đây của Lob – Richmond (xem [6]) luôn luôn đạt diện tích lớn
hơn các đường tròn Malfatti.
Đầu tiên nội tiếp một đường tròn trong tam giác cho trước. Sau đó nội tiếp
đường tròn thứ hai trong góc nhỏ nhất của tam giác và tiếp xúc với đường tròn
thứ nhất. Đường tròn thứ ba có thể nội tiếp trong cùng góc đó hoặc góc lớn hơn
( góc lớn thứ hai của tam giác ) cho phép đường tròn lớn hơn.


18

1.2.4.

Lời giải của V. A. Zalgaller và G. A. Los’ (1994)

Kí hiệu các góc của tam giác lần lượt là A, B, C và các đỉnh đối diện với
chúng là A, B, C. Giả sử rằng
0 < A ≤ B ≤ C < π.

(1.1)


Kết quả chính: Ba đường tròn không chườm lên nhau có diện tích lớn nhất
khi chúng được sắp xếp trong tam giác theo cách dưới đây: Trong tam giác bất
kì với A ≤ B ≤ C, lời giải của bài toán Malfatti là ba đường tròn k1 , k2 , k3 với
k1 là đường tròn nội tiếp tam giác; k2 là đường tròn nội tiếp trong góc A và
tiếp xúc ngoài với đường tròn k3 ; đường tròn k3 cũng nội tiếp trong góc A và
tiếp xúc ngoài với đường tròn k2 hoặc nội tiếp trong góc B và tiếp xúc ngoài với
A
B
đường tròn k3 , phụ thuộc vào sin ≥ tan hay không.
2
4

Hình 1.13
Hệ rigid Hệ gồm ba đường tròn không chườm nhau được gọi là hệ rigid nếu
mỗi đường tròn với vị trí không đổi so với hai đường tròn khác không thể liên
tục di chuyển trong tam giác bằng cách tăng bán kính, đồng thời thỏa mãn điều
kiện các đường tròn không chườm lên nhau.
Ta có thể thấy rằng có tất cả 14 hệ rigid. Chúng được mô tả như trong các hình
vẽ sau


19

Hình 1.14
Các trường hợp từ 3–14 được loại trừ: ba vòng tròn tương ứng có tổng diện tích
nhỏ hơn các trường hợp 1 hoặc 2 ở hai hình vẽ đầu tiên.

1.2.5.

Phương pháp tối ưu toàn cục giải bài toán Malfatti


Gần đây, nhà toán học Mông Cổ Rensen Enkbat [1] đã phát biểu bài toán
Malfatti dưới dạng một bài toán tìm cực tiểu của hàm lõm (hay cực đại của
hàm lồi) và sử dụng các công cụ của tối ưu toàn cục (điều kiện tối ưu toàn cục
cho bài toán cực đại hàm lồi lần đầu tiên phát biểu bởi Strekalovsky, xem [7])


20

để xây dựng thuật toán hội tụ giải bài toán Malfatti.
Năm 2016, Rensen Enkbat và M. Barkova [2] đã phát triển phương pháp trong
[1] cho bài toán Malfatti suy rộng: Xếp bốn hình tròn trong tam giác đã cho sao
cho tổng diện tích của chúng là lớn nhất.

Trường hợp 1

Trường hợp 2


21

Trường hợp 3

Trường hợp 4


22

Trường hợp 5


Trường hợp 6
Sau đó, R. Enkbat, M. Barkova (2016, [2]); R. Enkhbat, E. Finkelstein, A. Anikin


23

and A. Gornov (2017, [3]) đã mở rộng bài toán Malfatti trong mặt phẳng cho n
hình tròn trong mặt phẳng và cho n hình cầu trong không gian như sau: Hãy
phân chia từ một khối đa diện đã cho thành n hình cầu không giao vào nhau và
có tổng thể tích lớn nhất.
Như vậy trải qua hơn 200 năm, bài toán Malfatti vẫn hấp dẫn, được nghiên cứu
và phát triển bởi nhiều nhà toán học trên thế giới, vì có nhiều ý nghĩa thực tế
cũng như lý thuyết. Để giải quyết và mở rộng bài toán này, khó có thể chỉ dùng
công cụ của toán sơ cấp, mà phải dùng các kiến thức và công cụ của toán học
hiện đại.


24

Chương 2
Phương pháp tối ưu toàn cục giải
bài toán Malfatti suy rộng
Mục này trình bày nội dung bài báo [7] về điều kiện tối ưu cho bài toán cực
đại hàm lồi.

2.1.

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

2.1.1.


Giới thiệu

Xét bài toán tối ưu
f (x) → min,

x ∈ D,

(2.1)

trong đó f (.) là hàm lồi khả vi và D là tập lồi. Điều kiện cần tối ưu cho bài
toán (2.1) là
< ∇f (z) , x − z > ≥ 0,

∀x ∈ D.

(2.2)

Điều này có nghĩa là để kiểm tra một điểm z bất kì có phải là một nghiệm của
bài toán (2.1) hay không, ta phải giải bài toán tuyến tính hóa
< ∇f (z) , x > → min,

∀x ∈ D.

(2.3)

Sau đó kiểm tra bất đẳng thức
< ∇f (z) , x (z) − z > ≥ 0,

(2.4)



25

trong đó x(z) là một nghiệm của (2.3).
Do đó, điều kiện tối ưu (2.2) bao gồm, thứ nhất là thay hàm ban đầu f (x) bằng
tuyến tính hóa bởi ∇f (x) , thứ hai, nếu bất đẳng thức (2.4) không thỏa mãn,
có nghĩa là
< ∇f (z) , x(z) − z > < 0,

∀x ∈ D

thì có thể tạo một điểm chấp nhận được
x (α) = αx (z) + (1 − α) z, α ∈ ]0, 1[
tốt hơn z : f (x (α)) < f (z) . Nói cách khác, điều kiện tối ưu (2.2) cho phép ta
quyết định xem một điểm chấp nhận được là một nghiệm của (2.1) hay không,
và nếu không, (2.2) cho phép ta xây dựng một điểm chấp nhận được tốt hơn.
Trong phần tiếp theo, tính chất này của điều kiện tối ưu sẽ được gọi là tính chất
thuật toán.
Ta có thể thấy rằng điều kiện tối ưu địa phương cổ điển
< ∇f (z) , x − z > ≤ 0,

∀x ∈ D

(2.5)

cho bài toán cực đại hàm lồi
f (x) → max,

x∈D


(2.6)

(trong đó f (.) là hàm lồi và D là tập lồi ) bảo toàn tính chất thuật toán của điều
kiện tối ưu (2.2). Cũng như vậy ta có thể nói về điều kiện tối ưu của Rockafeller
như sau.
∂f (z) ⊂ N (z/D) ,

(2.7)

Trong đó kí hiệu N (z/D) là tập
{w| w, x − z ≤ 0,

∀x ∈ D}

là nón lồi đóng. Vì (2.7) có thể được biểu diễn dưới dạng
∀z ∗ ∈ ∂f (z) :< z ∗ , x − z > ≤ 0

∀x ∈ D.