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

NHỮ VĂN HUẤN

BẤT ĐẲNG THỨC BIẾN PHÂN
TRONG KHÔNG GIAN HỮU HẠN CHIỀU
VÀ BÀI TOÁN CỰC TRỊ LỒI

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

Thái Nguyên - 2015


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

NHỮ VĂN HUẤN

BẤT ĐẲNG THỨC BIẾN PHÂN
TRONG KHÔNG GIAN HỮU HẠN CHIỀU
VÀ BÀI TOÁN CỰC TRỊ LỒI

Chuyên ngành: Toán ứng dụng
Mã số:

60 46 01 12

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

NGƯỜI HƯỚNG DẪN KHOA HỌC

1.2.2. Định lý tồn tại duy nhất nghiệm . . . . . . . . .
2 Bất đẳng thức biến phân và bài toán cực trị lồi
2.1. Bất đẳng thức biến phân và bài toán cực trị . . . . . . .
2.1.1. Bài toán cực trị . . . . . . . . . . . . . . . . . . .

12
19
19
19

2.1.2. Mối liên hệ giữa bài toán cực trị và bất đẳng thức
biến phân . . . . . . . . . . . . . . . . . . . . . .
2.2. Bất đẳng thức biến phân với hệ phương trình, bài toán

22

bù và bài toán điểm bất động . . . . . . . . . . . . . . .
2.2.1. Hệ phương trình . . . . . . . . . . . . . . . . . .

24
24

2.2.2. Bài toán bù . . . . . . . . . . . . . . . . . . . . .
2.2.3. Bài toán điểm bất động . . . . . . . . . . . . . .

25
26

2.2.4. Bài toán cân bằng kinh tế dưới dạng bất đẳng
thức biến phân . . . . . . . . . . . . . . . . . . .

trọng trong thực tế được thiết lập và nghiên cứu dưới dạng bất đẳng
thức biến phân. Chẳng hạn, bài toán cân bằng mạng giao thông, bài
toán cân bằng thị trường độc quyền, bài toán cân bằng tài chính và bài
toán cân bằng di cư (xem [7]). Ngoài ra, bất đẳng thức biến phân còn là
một công cụ hữu hiệu để nghiên cứu và xây dựng các phương pháp giải
số cho nhiều lớp bài toán cân bằng trong kỹ thuật, vận tải, lý thuyết trò
chơi . . . Do vậy việc nghiên cứu sự tồn tại và duy nhất nghiệm, cũng
như xây dựng các phương pháp giải bất đẳng thức biến phân đã và đang
là một đề tài thời sự thu hút được sự quan tâm nghiên cứu của nhiều
nhà toán học.
Luận văn này nhằm trình bày tổng quan về bất đẳng thức biến phân
trong không gian hữu hạn chiều và bài toán cực trị lồi. Nội dung của
luận văn được trình bày trong hai chương. Chương 1 giới thiệu về bài


4

toán bất đẳng thức biến phân trong không gian hữu hạn chiều và nghiên
cứu điều kiện tồn tại và duy nhất nghiệm của bài toán. Chương 2 trình
bày mối quan hệ của bất đẳng thức biến phân hữu hạn chiều với bài
toán cực trị lồi.
Luận văn được hoàn thành tại Trường Đại học Khoa học – Đại học
Thái Nguyên. Tác giả xin cảm ơn sâu sắc tới người hướng dẫn luận văn
cao học của mình, TS. Nguyễn Thị Thu Thủy, giảng viên trường Đại
học Khoa học – Đại học Thái Nguyên, người đã dành nhiều thời gian
và tâm huyết để hướng dẫn và giải quyết những thắc mắc cho tôi trong
suốt quá trình tôi làm luận văn. Tôi cũng xin bày tỏ lời cảm ơn chân
thành tới các thầy cô trong hội đồng chấm luận văn thạc sĩ, các thầy cô
giảng dạy lớp Cao học toán K7D, gia đình, bạn bè, đồng nghiệp đã tạo
những điều kiện thuận lợi nhất để tôi có thể hoàn thiện khóa học cũng


PC

phép chiếu mêtrix Rn lên tập con lồi đóng C của Rn

Fix(T )

tập điểm bất động của ánh xạ T


6

Chương 1
Bất đẳng thức biến phân trong
không gian hữu hạn chiều
Chương này trình bày một cách sơ lược về bất đẳng thức biến phân
trong không gian hữu hạn chiều và một số tính chất về sự tồn tại và
duy nhất nghiệm của bất đẳng thức biến phân. Mục 1.1 giới thiệu tổng
quan về bất đẳng thức biến phân trong không gian Euclid Rn và một số
tính chất của tập nghiệm của bài toán. Trong Mục 1.2 trình bày điều
kiện tồn tại và duy nhất nghiệm của bất đẳng thức biến phân. Các kiến
thức của chương được viết trên cơ sở các tài liệu [1]–[11].

1.1.
1.1.1.

Bất đẳng thức biến phân trong không gian Euclid
Định nghĩa và ví dụ

Trong mục này ta luôn giả thiết Rn là không gian Euclid với tích vô


Giả sử x0 là điểm cực tiểu cần tìm và x là phần tử tùy ý thuộc C. Vì C
là tập hợp lồi nên
(1 − t)x0 + tx = x0 + t(x − x0 ) ∈ C,

0 ≤ t ≤ 1.

Hàm
Φ(t) = f (x0 + t(x − x0 )),

0≤t≤1

đạt cực tiểu tại t = 0. Do đó, từ Ví dụ 1.1
Φ (0) = f (x0 )(x − x0 ) ≥ 0 ∀x ∈ C.
Như vậy điểm x0 thỏa mãn bất đẳng thức biến phân
x0 ∈ C :

f (x0 )(x − x0 ) ≥ 0 ∀x ∈ C.

Nếu tập C bị chặn thì điểm x0 tồn tại duy nhất.


8

1.1.2.

Tập nghiệm của bất đẳng thức biến phân

Cho C = ∅ là tập lồi đóng trong Rn và x∗ ∈ C. Nón chuẩn tắc tới C
tại x∗ là tập

thiết về tính đơn điệu cho ánh xạ F .


9

Định nghĩa 1.3 Cho C là một tập con lồi trong không gian Rn và F
là một ánh xạ từ C vào Rn . Ánh xạ F là:
(i) Ánh xạ η-đơn điệu mạnh trên C nếu tồn tại một hằng số η > 0 sao
cho
F (u) − F (v), u − v ≥ η u − v

2

∀u, v ∈ C;

(ii) Ánh xạ đơn điệu ngặt trên C nếu
F (u) − F (v), u − v > 0 ∀u, v ∈ C, u = v;
(iii) Ánh xạ đơn điệu trên C nếu
F (u) − F (v), u − v ≥ 0 ∀u, v ∈ C;
(iv) Ánh xạ giả đơn điệu trên C nếu
F (v), u − v ≥ 0 suy ra

F (u), u − v ≥ 0 ∀u, v ∈ C;

(v) Ánh xạ tựa đơn điệu trên C nếu
F (v), u − v > 0 suy ra

F (u), u − v ≥ 0 ∀u, v ∈ C.

Ví dụ 1.3 Xét các ánh xạ Ti : R → 2R (i = 1, 2) cho bởi các công thức:

xạ F = I − T , ta có:
F (x) − F (y), x − y = (I − T )(x) − (I − T )(y), x − y
= (x − y) − (T (x) − T (y)), x − y
= x−y

2

− T (x) − T (y), x − y

≥ x−y

2

− T (x) − T (y)

≥ x−y

2

− x−y

2

x−y

= 0.

Suy ra, ánh xạ F là ánh xạ đơn điệu.
✷
Mối quan hệ giữa tập nghiệm S của bài toán VI(F, C) và tập nghiệm


với mọi y ∈ C.

Định lý sau đây cho ta một tính chất quan trọng của phép chiếu
mêtric PC .
Định lý 1.1 [7] Cho C là một tập con lồi đóng của Rn . Khi đó, y = PC x
khi và chỉ khi
y − x, z − y ≥ 0 ∀z ∈ C.

(1.4)

Chứng minh. Ta biết rằng y = PC x chính là cực tiểu của hàm g(z) =
z − x 2 trên tập C với g(z) = 2(z − x). Từ điều kiện tối ưu của bài
toán cực trị có ràng buộc ta có điều phải chứng minh.
✷
Hệ quả 1.1 [7] Cho C là tập con khác rỗng lồi đóng của Rn . Khi đó
phép chiếu mêtric PC là một ánh xạ không giãn, tức là
PC x − PC x

≤ x−x

∀x, x ∈ Rn .

(1.5)

Chứng minh. Lấy x, x ∈ Rn . Giả sử y = PC x và y = PC x . Khi đó
theo Định lý 1.1 ta có
với y ∈ C : y, z − y ≥ x, z − y

∀z ∈ C,

✷

1.2.2.

Định lý tồn tại duy nhất nghiệm

Định lý 1.2 [3] Giả sử C là tập con lồi và compact của không gian Rn
và F : C → Rn là một ánh xạ đơn điệu và liên tục trên C. Khi đó, tồn
tại ít nhất một điểm x∗ ∈ C thỏa mãn (1.1).
Để chứng minh Định lý 1.2 ta cần một số kết quả sau.
Bổ đề 1.1 [7] Cho C là tập con khác rỗng lồi đóng trong Rn . Khi đó
với mỗi x ∈ Rn , tồn tại duy nhất một điểm y ∈ C sao cho
x−y ≤ x−z

∀z ∈ C,

(1.8)

và điểm y được gọi là phép chiếu trực giao của x lên tập C với chuẩn
Euclid trong Rn , tức là
y = PC x = arg min x − z .
z∈C

Chứng minh. Giả sử x ∈ Rn là điểm cố định và z ∈ C bất kỳ. Xét
hàm g xác định bởi
g(z) = x − z 2 .
Ta thấy g là hàm liên tục. Khi đó, tồn tại điểm cực tiểu y của hàm g (vì
mọi hàm liên tục đều đạt được cực tiểu trên một tập compact), tức là
x−y



g(x) = x − [x∗ − tF (x∗ )], suy ra từ điều kiện tối

ưu cho bài toán cực trị có ràng buộc minx∈C g(x), nên
g(x∗ ), x − x∗ ≥ 0 ∀x ∈ C,
tức là
x∗ − [x∗ − tF (x∗ )], x − x∗ ≥ 0 ∀x ∈ C,
hay
F (x∗ ), x − x∗ ≥ 0 ∀x ∈ C.
✷
Định lý 1.2 đòi hỏi tập C phải là tập compact. Tuy nhiên khi C không
phải là tập compact thì bài toán (1.1) vẫn tồn tại nghiệm nếu điều kiện
trong định lý sau được thỏa mãn.
Định lý 1.4 [4] Cho C là một tập con khác rỗng lồi đóng trong không
gian Euclid Rn và F : C → Rn là ánh xạ liên tục trên C. Giả sử tồn tại


14

tập con compact U khác rỗng của C sao cho: với mọi u ∈ C \ U , tồn tại
v ∈ U thỏa mãn
F (u), u − v > 0.
Khi đó, bài toán (1.1) có ít nhất một nghiệm.
Khi C là tập không bị chặn thì sự tồn tại nghiệm của bất đẳng thức
biến phân VI(F, C) sẽ được đảm bảo nếu thêm điều kiện được chỉ ra
sau đây. Cho C là tập con khác rỗng lồi đóng trong Rn . Khi đó, CR =
C ∩ B(0, R) là một tập lồi compact, với B(0, R) := {u ∈ Rn : u ≤ R}
là hình cầu đóng tâm 0, bán kính R trong Rn . Tập CR là bị chặn và
theo Định lý 1.2, ta có
xR ∈ CR : F (xR ), x − xR ≥ 0 ∀x ∈ CR .

✷
Chú ý 1.1 Mặc dù, điều kiện xR < R là khó kiểm tra nhưng người
ta có thể xác định giá trị của R một cách thích hợp trong các bài toán
cụ thể.
Sự tồn tại nghiệm của bài toán VI(F, C) còn được thiết lập với điều
kiện bức đặt lên ánh xạ F như nội dung của hệ quả sau đây.
Hệ quả 1.2 [3] Cho C là một tập con lồi và compact của không gian
Euclid Rn và F : C → Rn là một ánh xạ đơn điệu và liên tục trên C và
thỏa mãn điều kiện
lim

x →∞

F (x) − F (x), x − x
= +∞
x−x

∀x ∈ C,

(1.10)

với x ∈ C. Khi đó bài toán VI(F, C) luôn có nghiệm.
Chứng minh. Theo giả thiết (1.10), ta có thể chọn hằng số c > 0 và
R > 0 sao cho 0 < F (x) < c và 0 < x < R thỏa mãn
F (x) − F (x), x − x ≥ c x − x

∀x ∈ C

và


tính chất kiểu đơn điệu của ánh xạ F .
Định lý 1.6 [3] Nghiệm của bất đẳng thức biến phân VI(F, C) là duy
nhất nếu F : C → Rn là ánh xạ đơn điệu ngặt.
Chứng minh. Thật vậy, giả sử x1 ∈ C và x2 ∈ C là hai nghiệm khác
nhau của VI(F, C). Khi đó,
F (x1 ), x − x1 ≥ 0 ∀x ∈ C

(1.13)

F (x2 ), x − x2 ≥ 0 ∀x ∈ C.

(1.14)

và
Lần lượt thay x = x2 trong (1.13) và x = x1 trong (1.14), sau đó cộng
hai vế tương ứng của hai bất đẳng thức thu được ta có:
F (x1 ) − F (x2 ), x1 − x2 ≤ 0.
Điều này vô lý vì giả thiết F là đơn điệu ngặt. Suy ra x1 = x2 .
✷
Cho C ⊂ Rn và F : C → Rn . Ma trận Jacobian của hàm F , ký hiệu
là F (x) xác định bởi

 ∂F
∂F1
1
.
.
.
∂x
∂xn

F (x)y ≥ α y

2

với α > 0 và y ∈ Rn thì F là ánh xạ đơn điệu mạnh.
Ta có hệ quả sau đây về tính đơn điệu của ánh xạ F khi F là ánh xạ
affine.
Hệ quả 1.3 [8] Cho F là ánh xạ affine, tức là F = q + M x, M ∈ Rn×n
và q ∈ Rn . Khi đó,
(i) F là đơn điệu khi và chỉ khi M là nửa xác định dương.
(ii) F đơn điệu mạnh khi và chỉ khi M là xác định dương.
Định lý sau đây cho ta một điều kiện để đảm bảo cho sự tồn tại và
duy nhất nghiệm của bất đẳng thức biến phân VI(F, C) mà không cần
đến tính compact của tập C.
Định lý 1.8 [3] Giả sử F là đơn điệu mạnh. Khi đó tồn tại duy nhất
nghiệm x∗ thỏa mãn bất đẳng thức biến phân VI(F, C).
Chứng minh. Thật vậy, do F đơn điệu mạnh nên F thỏa mãn điều
kiện bức và đơn điệu ngặt. Tính bức của ánh xạ F bảo đảm cho cho sự
tồn tại nghiệm của VI(F, C) và tính đơn điệu ngặt của F bảo đảm cho
tính duy nhất nghiệm của VI(F, C).
✷
Nhận xét 1.1 Như vậy,


18

(i) khi C là tập không bị chặn, tính đơn điệu mạnh của F bảo đảm
cho sự tồn tại và duy nhất nghiệm của bất đẳng thức biến phân.
(ii) khi C là tập compact, sự tồn tại nghiệm của bất đẳng thức biến
phân được bảo đảm với điều kiện F là liên tục và tính duy nhất

có ràng buộc đều có thể biểu diễn được dưới dạng bất đẳng thức biến
phân.


20

Cho C là tập con lồi đóng trong Rn và hàm f là khả vi liên tục trên
một tập mở U ⊂ Rn chứa C. Bài toán cực trị, ký hiệu là OP(f, C)
(optimization problem), được phát biểu như sau:
Tìm điểm x∗ ∈ C thỏa mãn f (x∗ ) ≤ f (x) ∀x ∈ C,
hay dưới dạng ngắn gọn hơn
min → {f (x) | x ∈ C}.

(2.1)

Kí hiệu S † là tập nghiệm của bài toán (2.1). Tính lồi của hàm f trong
(2.1) đóng vai trò quan trọng trong việc nghiên cứu tính chất của tập
S † . Điều này cũng tương tự như tính đơn điệu khi ta xét đến tính chất
tập nghiệm của bài toán bất đẳng thức biến phân. Ta nhắc lại một số
định nghĩa về tính chất lồi của hàm số như sau.
Định nghĩa 2.1 Cho W và V là các tập con lồi trong Rn , W ⊆ V và
cho hàm f : V → R là hàm khả vi. Hàm f được gọi là
(a) lồi mạnh trên W nếu với hằng số τ > 0, với mỗi cặp u, v ∈ W và
α ∈ [0, 1] ta có
f (αu + (1 − α)v) ≤ αf (u) + (1 − α)ϕ(v) − 0.5α(1 − α)τ u − v 2 ;
(b) lồi chặt trên W nếu với mỗi u, v ∈ W, u = v và α ∈ (0, 1), thì
f (αu + (1 − α)v) < αf (u) + (1 − α)ϕ(v);
(c) lồi trên W nếu với mỗi cặp u, v ∈ W và α ∈ [0, 1] ta có
f (αu + (1 − α)v) ≤ αf (u) + (1 − α)ϕ(v).
Khẳng định sau được suy ra trực tiếp từ định nghĩa trên:

ϕ (0) ≥ 0 ⇔

f (x∗ ), x − x∗ ≥ 0.

Do đó, x∗ thỏa mãn điều kiện (2.2).
✷
Chú ý 2.1 Nếu f là hàm lồi thì cực tiểu địa phương x∗ sẽ trở thành
cực tiểu toàn cục của f trên C.
Chứng minh. Thật vậy, do f là hàm lồi nên ta có
f (x) ≥ f (x∗ ) +
Mà

f (x∗ ), x − x∗

∀x ∈ C.

f (x∗ ), x − x∗ ≥ 0 do x∗ là nghiệm địa phương của OP(f, C).

Suy ra: f (x) ≥ f (x∗ ) ∀x ∈ C. Vậy x∗ là cực tiểu toàn cục của hàm f
trên C.
✷
Mệnh đề sau đây, còn được gọi là nguyên lý cực tiểu, cho ta một điều
kiện để x∗ là cực tiểu địa phương của hàm f .


22

Mệnh đề 2.4 Nếu x∗ là cực tiểu địa phương của hàm f trên tập C thì
f (x∗ ), x − x∗ ≥ 0 ∀x ∈ C.
2.1.2.

Chứng minh. Do f (x) là hàm lồi nên ta có
f (x) ≥ f (x∗ ) +

f (x∗ ), x − x∗

∀x ∈ C.

(2.5)

Mặt khác
f (x∗ ), x − x∗ ≥ 0 vì x∗ là nghiệm của VI( f, C). Do đó,
từ (2.5) ta suy ra
f (x) ≥ f (x∗ ) ∀x ∈ C,
hay x∗ chính là nghiệm của bài toán (2.1).
✷


23

Trong trường hợp C = Rn thì bài toán (2.1) trở thành bài toán không
ràng buộc và ta vẫn đưa được bài toán đó về bất đẳng thức biến phân.
Khi đó, ta có định lý sau về mối quan hệ của bài toán OP(f, C) và
VI(F, C).
Định lý 2.1 [5] Giả sử hàm f : C → R là hàm khả vi. Khi đó:
(i) S † ⊆ S tức là, mỗi nghiệm của bài toán (2.1) là nghiệm của bài
toán (1.1) với
F (x) =

f (x);