Khóa luận tốt nghiệp

Đinh Thị Trang

LỜI CẢM ƠN
Bước đầu làm quen với việc tiến hành nghiên cứu khoa học nên em
không khỏi bỡ ngỡ và gặp nhiều khó khăn. Để hoàn thiện được khóa luận em
đã nhận được sự giúp đỡ của các thầy cô trong khoa Toán cùng các thầy cô
trong trường ĐHSP Hà Nội 2 và đặc biệt là sự tận tình chỉ bảo, đóng góp
những ý kiến quý báu của thầy Hoàng Ngọc Tuấn trong thời gian qua.
Do điều kiện thời gian cùng vốn kiến thức còn hạn chế chắc chắn sẽ
không tránh khỏi những sai sót. Em rất mong nhận được ý kiến đóng góp của
thầy cô và các bạn để tìm được những ý tưởng tốt hơn bổ sung cho khóa luận
được hoàn thiện hơn nữa và sẽ là tài liệu tham khảo thật sự bổ ích cho tất cả
những độc giả có niềm đam mê môn Toán.
Qua đây em xin gửi lời cảm ơn chân thành tới các thầy cô trong tổ Giải
tích, các thầy cô trong khoa Toán và đặc biệt là thầy Hoàng Ngọc Tuấn đã
hướng dẫn em hoàn thành khóa luận này.
Em xin chân thành cảm ơn!

Hà Nội, tháng 05 năm 2012
Sinh viên
Đinh Thị Trang


LỜI CAM ĐOAN
Tôi xin cam đoan bản khóa luận này được hoàn thành do sự cố gắng nỗ
lực tìm hiểu, nghiên cứu của bản thân, cùng với sự giúp đỡ tận tình của thầy
Hoàng Ngọc Tuấn.
Bản khóa luận này không trùng với kết quả của tác giả khác. Nếu trùng
tôi xin hoàn toàn chịu trách nhiệm.

Rất mong được sự đóng góp ý kiến của bạn đọc để bản khóa luận được
hoàn thiện hơn.
Hà Nội, tháng 05 năm 2012
Sinh viên
Đinh Thị Trang


MỤC LỤC

Trang

MỞ ĐẦU........................................................................................................... 1
NỘI DUNG.......................................................................................................3
Chương 1. Kiến thức chuẩn bị........................................................................ 3
1.1. Bài toán tối ưu............................................................................................. 3
1.2. Bài toán quy hoạch lồi................................................................................ 5
1.3. Bài toán quy hoạch toàn phương trên tập lồi đa diện..................................9
Chương 2. Các định lý về sự tồn tại nghiệm................................................13
2.1. Định lý Frank – Wolfe............................................................................... 13
2.2. Định lý Eaves............................................................................................ 19
Chương 3. Điều kiện cần và đủ tối ưu.......................................................... 27
3.1. Điều kiện tối ưu bậc một........................................................................... 27
3.2. Điều kiên để tối ưu bậc hai........................................................................31
KẾT LUẬN..................................................................................................... 44
TÀI LIỆU THAM KHẢO............................................................................. 45



MỞ ĐẦU
1. Lý do chọn đề tài

Quy hoạch toàn phương trên tập lồi đa diện, hay quy hoạch toàn
phương với ràng buộc tuyến tính, là một dạng đặc biệt của bài toán quy hoạch
toán học. Chúng nảy sinh trong nhiều lĩnh vực khác nhau của ứng dụng, từ tối
ưu tổ hợp cho tới các bài toán dữ liệu.
Các điều kiện cần và đủ cho sự tồn tại nghiệm của một bài toán tối ưu
đã được nghiên cứu kĩ lưỡng bởi nhiều nhà toán học trong nhiều cuốn sách
chuyên môn cũng như những bài báo trên các tạp chí. Nhưng Quy hoạch toàn
phương trên tập lồi đa diện là một trường hợp riêng của bài toán tối ưu với
những cấu trúc đặc biệt, nên ngoài những điều kiện tổng quát đã có, nó còn có
những đặc trưng riêng khá đơn giản và tiện lợi, và rất đáng để tìm hiểu,
nghiên cứu.
Vì những lý do trên nên em chọn đề tài:
Quy hoạch toàn phương trên tập lồi đa diện
với hi vọng hiểu sâu được nội dung bài toán và tầm quan trọng của nó.
2. Mục đích nghiên cứu
Bước đầu làm quen với việc nghiên cứu khoa học và tìm hiểu cấu trúc
Quy hoạch toàn phương trên tập lồi đa diện.
3. Nhiệm vụ nghiên cứu
Nghiên cứu các điều kiện cần và đủ cho sự tồn tại nghiệm của Quy
hoạch toàn phương trên tập lồi đa diện.
4. Đối tượng và phạm vi nghiên cứu
Quy hoạch toàn phương trên tập lồi đa diện.
5. Phương pháp nghiên cứu
Sử dụng các lý luận, các công cụ toán học và phương pháp nghiên cứu
của lý thuyết tối ưu.
1


6. Cấu trúc khóa luận
Ngoài phần mở đầu, kết luận và danh mục tài liệu tham khảo, khóa luận

của em gồm ba chương:
Chương 1. Kiến thức chẩn bị
Chương 2. Các định lý về sự tồn tại nghiệm
Chương 3. Điều kiện cần và đủ tối ưu


CHƯƠNG 1. KIẾN THỨC CHUẨN BỊ
1.1 Bài toán tối ưu
Nhiều bài toán lý thuyết và thực tế thường được mô tả dưới dạng
(P) min f( ) với x ,
n

trong đó f : □  □ là một hàm xác định, □ . Ở đó, □ =
[ , +] = □
+ là

n

□ là kí hiệu của không gian

tập số thực mở rộng, Euclidean n – chiều
với chuẩn
=
với mọi x = (

n

) □ và tích vô hướng
=


với mọi x = (x1,…, xn), y = (y1,…, yn)


n

□ , mũ

T

là kí hiệu chuyển vị ma

n

trận. Hình cầu mở trong □ có tâm x và bán kính > 0 được kí hiệu bởi B(x,
). Hình cầu đóng được kí hiệu bởi
B(x, ) =
y 

n

□ :
y 

(x, ). Ta có
< , (x, ) =

Hình cầu đơn vị (0, 1) được kí hiệu
int,

n


□:
.



. Với tập  , các kí hiệu


và bd, tương ứng, được sử dụng trong tôpô là phần trong, tôpô
đóng và biên của . Do đó
nhất trong □

n

là tập con đóng nhỏ

có chứa , và

int= x : > 0 : B(x, ) ,
bd =
(int).
n

Ta nói tập U □
là một lân cận của x □
nếu tồn tại > 0 sao cho B(x, )
U.
Ta có thể viết lại bài toán (P) như sau:



minf(x) : x .
Định nghĩa 1.1. (P) được gọi là một bài toán quy hoạch toán học. Ta gọi f
là hàm mục tiêu và là tập ràng buộc (hay miền ràng buộc thỏa mãn
n

(P)). Các
phần tử của là các vectơ chấp nhận được của (P).
Nếu =

□ thì (P) là bài

toán không có tập ràng buộc. Khi đó (P) được gọi là bài toán không có giới
hạn.
Định nghĩa 1.2. Một vectơ chấp nhận được được gọi là
nghiệm của (P) nếu

+ và

với mọi x . Vectơ

 được gọi là nghiệm địa phương của (P) nếu
tồn tại lân cận U của

+và

sao cho
.

(1.1)


Tập tất cả các nghiệm (tương ứng, tập các nghiệm địa phương) của (P) được
kí hiệu là Sol(P) (tương ứng, loc(P) ).
Định nghĩa 1.3. Giá trị tối ưu v(P) của (P) được xác định bởi biểu thức
.
Nếu =

(1.2)

thì, quy ước v(P) = +.

Nhận xét 1.1. Có thể xảy ra trường hợp Sol(P) loc(P). Hiển nhiên là
.
Nhận xét 1.2. Có thể xảy ra trường hợp loc(P) \ Sol(P)

.

Nhận xét 1.3. Thay vì tìm giá trị cực tiểu, một bài toán đưa ra là tìm giá trị
cực đại
(

) max f(x) với x .


Một điểm

thỏa mãn là nghiệm của bài toán (

), nếu


và với mọi x . Điểm
được gọi là nghiệm địa phương của
bài toán ( ) nếu f( )
f(x)

và tồn tại một lân cận U của

sao cho


f( ) với mọi x 

U. Rõ ràng là nghiệm của bài toán ( )

khi và chỉ khi là nghiệm của bài toán cực tiểu
min - f(x) với x .
Do đó các giá trị cực đại của bài toán (

) có thể được đưa về giá trị cực tiểu

của bài toán (P).
Nhận xét 1.4. Trong trường hợp v(P) là một số thực hữu hạn, có thể xảy ra
Sol(P) = .
1.2 Bài toán quy hoạch lồi
Định nghĩa 1.4. Ta nói □ là một tập lồi nếu
.

(1.3)

n


□ được gọi là bao lồi của tập và

Tập lồi nhỏ nhất chứa tập


được kí

hiệu là Co.
n

Định nghĩa 1.5. Một hàm f : □ □ là hàm lồi nếu đồ thị trên
epif

n

(x, ) : x □ ,



,

(1.4)

n

là tập con lồi của không gian tích □  □ . Một hàm lồi được cho là lồi
chính
n
thường nếu f(x) < +có ít nhất một

□ và f(x) > với mọi x
x

Một hàm f :

là hàm lõm nếu hàm

f được định nghĩa bởi hệ thức

là hàm lồi.
Ta có các quy ước thường dùng như sau
với
( ∞)

với
,

,
,
với

,

.


,
=

với


,


=

, inf

Tổ hợp

=

, sup

=

và

.
không có ý nghĩa và có thể bỏ qua.

n

Chú ý hàm f : □ □ {+ } là lồi khi và chỉ khi
x,

n

y □ , t


 (0, 1). (1.5) Thật vậy, theo định nghĩa, f là hàm lồi khi và chỉ khi tập
epif được định nghĩa như trong (1.4). Có nghĩa là

n

với mọi t (0, 1) và mọi x, y□ , , □ thỏa mãn 


,
.

n

Tổng quát hơn, hàm f : □ □ {+ } là lồi khi và
chỉ khi
) (Bất đẳng thức Jensen)
n

trong đó

□

và i 0 (i =

),

.

Định nghĩa 1.6. (P) được gọi là một bài toán lồi (bài toán trên tập lồi)
nếu 

là tập lồi và f là một hàm lồi .
Mệnh đề 1.1. Nếu (P) là bài toán lồi thì
Sol(P) = loc(P).

(1.6)

Định nghĩa 1.7. Nếu không là tập lồi (không lồi) hoặc f không là hàm
lồi thì ta nói (P) không là bài toán lồi (dạng toán không có tính lồi).
n

Định nghĩa 1.8. Cho hàm f : □ □ , tập
domf

n

{x □ :

+}

< f(x) <

(1.7) được gọi là miền xác định hữu hạn

của f. Cho một điểm

n

domf và một vectơ v □ , nếu giới hạn

( ; v)


(1.8)


(có thể bằng các giá trị +và

) tồn

tại thì f được gọi là khả vi theo hướng v tại

và giá trị

( ; v) được gọi là đạo hàm có hướng của f tại

theo

hướng
n

v. Nếu ( ; v) tồn tại với mọi v □
thì f được cho là khả vi có hướng tại

.

Trong hai định lý tiếp theo, f :

là một hàm lồi chính

thường.
Định lý 1.1. Nếu


n

□ và > 0 như vậy hình cầu mở B( , ) chứa trong

domf, thì giới hạn của f trên hình cầu B( , ) là một hàm thực liên tục.
Định lý 1.2. Nếu
hạn

n

domf với vectơ v □ bất kì thì tồn tại giới
( ; v) =

và có

( ; v) =

,

.
n

Định nghĩa 1.9. Dạng nón chính tắc


( ) trên một tập lồi

□ tại


được định nghĩa bởi công thức

( )=

(1.9)

n
Định nghĩa 1.10. Các dưới vi phân f( ) của một hàm lồi f : □
□ tại
n □
điểm 
được xác định bởi cách đặt

f( ) =
Định nghĩa 1.11.


(1.10)
Một tập M

□

n

được gọi là một tập afin nếu


n

M với mọi xM, y M và t □ . Cho một tập lồi

□ ,
bao affin affcủa là tập affin nhỏ nhất chứa . Phần trong tương
đối của 
được định nghĩa bởi công thức
: tồn tại
ri= {x
aff }.

> 0 sao cho B(x, )


Các khẳng định sau đây mô tả mối quan hệ giữa đạo hàm có hướng và vi
phân dưới của hàm lồi.
Định lý 1.3. (Định lý Morean - Rockafellar) Cho f là hàm lồi chính thường
n

trên □ . Nếu x domf thì

= . Nếu x ri(domf) thì

= sup {

:



và

n


f(x)} v □ .

Ngoài ra, f(x) là tập bị chặn khác rỗng khi và chỉ khi x int(domf),
n

là hữu hạn với mỗi v □ .

trong trường hợp này
Định lý 1.4. Cho

, trong đó

n

trên □ . Nếu

là hàm lồi chính thường

thì

□n .
n

Định lý 1.5. Giả sử f là một hàm lồi chính thường trên □ và
 
lồi khác rỗng. Nếu giả thiết đưa ra

n

□ là tập


0  f( ) +
(1.11)
n

là thỏa mãn với □ , thì

( )

là một nghiệm của (P). Ngược lại, nếu

ri(domf) ri
thì (1.11) là một điều kiện cần và đủ để


(1.12)
n

□ là một nghiệm của (P). Đặc

n

biệt, nếu = □
thì
nghiệm của (P) khi và chỉ khi 0 
Giả thiết (1.11) có nghĩa là tồn tại  f( ) và
cho
+

là một

f( ).
 ( ) sao

= 0. Lưu ý (1.12) là điều kiện chính quy để bài toán min{

}

thuộc loại bài toán lồi.
n


Ta xét bài toán min{
hàm lồi và
n

= { x □ : (x)
0, … ,
(x) = 0},

} với giả thiết rằng f : □
□ là một
0, … ,
(1.13)

(x)

0,

(x) =



trong đó
hàm lồi,

: □n
:

□ với i =

n
□
=
là một

là

n

hàm afin, tồn tại


□ sao cho

□ và
x

□ với j

(x) =+ với mọi


n

□ . Ta thừa nhận rằng đẳng thức ràng buộc có thể không có trong
(1.11). Để đơn giản, ta xét m = 0 (tương ứng, s = 0) để chỉ ra rằng tất cả
các đẳng thức ràng buộc có thể không xuất hiện trong (1.13).
Định lý 1.6. Cho (P) là một bài toán lồi trong đó xác định bởi (1.13).
Các giả thiết của f,

(i=

) và

(j =

) ở trên đều thỏa mãn. Giả sử

tồn tại
n

một vectơ z □ sao cho
(z) < 0 với i =
Thế thì

và

(z) = 0 với j =

.

(1.14)


là một nghiệm của (P) khi và chỉ khi tồn tại (m + s) số thực

, , … , , được gọi là các nhân tử Lagrange tương ứng với

,…,

, sao cho

các điều kiện Kuhn – Tucker sau thỏa mãn:
(a)

0, ( ) 0, ( ) = 0 (i =

(b)

( ) = 0 (j =

),

),

(c) 0  f( ) +

+

.

1.3 Bài toán quy hoạch toàn phương
Định nghĩa 1.12. Tập

 

n

□ được gọi là tập lồi đa diện nếu có thể
biểu

n

diễn bởi giao hữu hạn các nửa không gian con đóng của
các vectơ khác không
sao cho

,…,


n □

□ ; nghĩa là, tồn tại

và các số thực

,…,


=

.

(1.15)


Nói cách khác, là tập nghiệm của một hệ gồm hữu hạn các đẳng thức
tuyến tính. (Ta thừa nhận rằng giao của mọi họ rỗng các nửa không gian
đóng củan
□ n

là □ . Do đó
=

n

□ là tập lồi đa diện.) Một điểm x gọi là
điểm cực


biên của nếu không biểu diễn được dưới dạng
đó y , z , y

trong

z, và t (0, 1). Tập các điểm cực

biên của kí hiệu là extr.
Cho A là ma trận cấp m
đó

là thành phần thứ j của

n với các phần tử


(i =

,j=
m

□

. Đặt b =

) trong
. Thế thì

(1.15) có thể được viết lại như sau
=

.

Khi đó, hai vectơ bất kỳ y =

có y

z nếu

□

m
m

□


và z =
, ta

với i = 1, 2, …, m. Ta cũng có y

z nếu

với i =

1, 2, …, m. Vì
=
dẫn đến

,

là tập lồi đa diện.


□ là hàm toàn phương nếu tồn

Định nghĩa 1.13. Ta nói f : □ n 

tại một ma
trận D 
□
nn
sao cho
f(x) =

, một vectơ c □


và một số thực

+

(1.16)

n

với mọi x □ .
Nếu D =

,c=

,x=

, thì (1.16) dẫn đến
+

10

.


Do


=

với mọi x


nếu ta thay D bởi các ma trận đối xứng

□ n , biểu diễn (1.16) vẫn đúng

(D +

). Do đó, ta coi ma trận

vuông trong biểu diễn của một hàm toàn phương là một ma trận đối xứng.
Định nghĩa 1.14. Bài toán (P) là một bài toán quy hoạch toàn phương (bài
toán toàn phương) nếu f là hàm toàn phương và là tập lồi đa diện.
Trong (1.16), nếu D là ma trận không thì f là một hàm afin. Do đó lớp
các bài toán tuyến tính là lớp con của lớp các bài toán quy hoạch toàn
phương. Trường hợp tổng quát, các bài toán toàn phương là các bài toán
không lồi.
Rõ ràng nếu ta bỏ đi hằng số trong biểu diễn (1.16) của f thì
tập
n
nghiệm của bài toán min
 

là không đổi, trong đó

□ là tập

lồi đa diện. Do đó, cách viết khác của (1.16) ta thường sử dụng dạng đơn giản
của hàm mục tiêu f

=


.

Sử dụng thuật ngữ bài toán tuyến tính, ta gọi các dạng của các bài toán
toàn phương sau
min
min

,
,

min
tương ứng là dạng chuẩn, dạng chính tắc và dạng tổng quát. (Có nghĩa là A,
C, b và d có vai trò như nhau trong các dạng điển hình của bài toán tuyến
tính). Chú ý biểu diễn của tập ràng buộc của bài toán quy hoạch toàn phương
chính tắc khác với trong bài toán tuyến tính chính tắc. Định nghĩa bài toán


quy hoạch toàn phương ở trên được thông qua bởi mối liên kết chặt chẽ của
bài toán quy hoạch toàn phương với bài toán tuyến tính bù.
n
Định nghĩa 1.15. Một ma trận D

là được gọi là xác định dương nếu
n

□

> 0 (tương ứng, xác định âm nếu
0 (tương ứng,


< 0) với mọi

0) với mọi

. Nếu

thì D gọi là nửa xác định

dương (tương ứng, nửa xác định âm).
Mệnh đề 1.2. Cho f

=

trong đó D

n

n ,

và

□ s

□ . Nếu D là một ma trận nửa xác định dương thì f là một hàm lồi.
Nếu D là hàm nửa xác định âm, thì hàm f cho bởi (1.16) là hàm lõm,

với mọi x

,y


và

. Trong trường hợp đó cho rằng D không

là nửa xác định dương và cũng không là nửa xác định âm, ta nói
,

, là hàm toàn phương không xác định. Bài toán

toàn phương với hàm mục tiêu là hàm toàn phương không xác định gọi là bài
toán toàn phương không xác định.
Chú ý. Rõ ràng nếu f cho bởi (1.16), ở đó D

n

□ s , thì

với mọi

. Do đó, kết luận trong mệnh đề 1.2 là kết quả trực tiếp của định lý
sau: “Nếu f :

n

 □ là một và nếu ma trận Hessian
□
hàm

□


2

nửa xác định dương với mọi

, thì f là một hàm lồi”.

là


CHƯƠNG 2. CÁC ĐỊNH LÝ VỀ SỰ TỒN TẠI NGHIỆM
2.1 Định lý Frank – Wolfe
Xét bài toán quy hoạch toàn phương cho bởi dạng chuẩn sau

□n ,

min{
,
n

trong đó D

nn
□ s

,A

□

mn


,c

□ và b

},

(2.1)

m

□ . Ta sử dụng các kí hiệu tập

ràng buộc và giá trị tối ưu trong (2.1) như sau
,


Nếu quy ước
ra hai trường hợp:

thì

□,

. Nếu

thì có thể xảy

. Nếu (ii) xảy ra thì chắc chắn



(2.1) không có nghiệm. Câu hỏi đặt ra: Liệu bài toán trên luôn có nghiệm khi
(i) xảy ra không ?
Lưu ý rằng bài toán tối ưu với hàm mục tiêu không toàn phương có thể
không có nghiệm ngay cả trường hợp giá trị tối ưu là hữu hạn. Ví dụ, bài toán
min

không có nghiệm, trong khi giá trị tối ưu
là hữu hạn.

Định lý 2.1. (Định lý Frank và Wolfe) Nếu

là số

thực hữu hạn thì bài toán (2.1) có nghiệm.
Chứng minh
Giả sử

nghĩa là

. Lấy

khác rỗng. Chọn một điểm

tùy ý. Đặt
.

Lưu ý rằng

là tập lồi, khác rỗng và compact. Xét bài toán sau

min

.

Theo Định lý Weierstrass,

(2.2)

tồn tại y

sao cho

=

. Vì tập các nghiệm của bài toán (2.2) là khác rỗng và
compact, tồn tại

sao cho

Ta khẳng định rằng tồn tại

> 0 sao cho
.

(2.3)

Thật vậy, nếu khẳng định là sai thì ta tìm được một dãy
mọi k tồn tại

sao cho với


sao cho
=

,

.

(2.4)