ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THANH HẰNG
MỘT SỐ PHƯƠNG PHÁP CHIẾU GIẢI BÀI TOÁN TỐI
ƯU VÀ BẤT ĐẲNG THỨC BIẾN PHÂN
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số: 60.46.36
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học:
GS.TSKH. LÊ DŨNG MƯU
THÁI NGUYÊN - NĂM 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
i
Mục lục
Mục lục i
Lời cảm ơn iii
Mở đầu 1
1 Toán tử chiếu lên tập lồi đóng 3
1.1 Một số khái niệm và tính chất cơ bản . . . . . . . . . . . . 3
1.1.1 Tập lồi và hàm lồi . . . . . . . . . . . . . . . . . . 3
1.1.2 Dưới vi phân . . . . . . . . . . . . . . . . . . . . . . 6
1.1.3 Tính đơn điệu. . . . . . . . . . . . . . . . . . . . . . 7
1.2 Phép chiếu lên tập lồi . . . . . . . . . . . . . . . . . . . . . 8
2 Phương pháp chiếu
giải quy hoạch lồi. 14
2.1 Bài toán quy hoạch lồi. . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Mô tả bài toán . . . . . . . . . . . . . . . . . . . . . 14
2.1.2 Sự tồn tại nghiệm tối ưu . . . . . . . . . . . . . . . 16
2.1.3 Điều kiện tối ưu. . . . . . . . . . . . . . . . . . . . . 17
2.2 Phương pháp chiếu dưới gradient xấp xỉ. . . . . . . . . . . 26
3 Phương pháp chiếu giải bài toán bất đẳng thức biến phân

Giải tích lồi là bộ môn cơ bản của giải tích hiện đại, nghiên cứu về tập
lồi và hàm lồi cùng những vấn đề liên quan. Bộ môn này có vai trò quan
trọng trong nhiều lĩnh vực khác nhau của toán học ứng dụng, đặc biệt là
trong tối ưu hoá, bất đẳng thức biến phân, các bài toán cân bằng. Một
trong những vấn đề quan trọng của giải tích lồi đó là phép chiếu. Đây là
một công cụ sắc bén và khá đơn giản để chứng minh nhiều định lý quan
trọng như Định lý tách, Định lý xấp xỉ tập lồi, Định lý về tồn tại nghiệm
của Bất đẳng thức biến phân. Hơn nữa phép chiếu còn được dùng để xây
dựng các phương pháp giải nhiều lớp bài toán quan trọng như bài toán
quy hoạch lồi, bất đẳng thức biến phân.
Bài toán bất đẳng thức biến phân được ứng dụng rộng rãi trong nhiều
lĩnh vực khác nhau như kinh tế, kỹ thuật, vật lý toán, vận trù học. Bài
toán bất đẳng thức biến phân được giới thiệu bởi Hartman và Stampacchia
vào năm 1966. Những nghiên cứu đầu tiên về bài toán này liên quan tới
việc giải các bài toán điều khiển tối ưu và các bài toán biên của phương
trình đạo hàm riêng. Bài toán bất đẳng thức biến phân trong không gian
vô hạn chiều và các ứng dụng của nó được giới thiệu trong cuốn sách
"An Introduction to Variational Inequalities and Their Applications" của
D. Kinderlehrer và G. Stampacchia , xuất bản năm 1980 và trong cuốn
sách "Variational and Quasivariational Inequalities: Application to Free
Boundary Problems" của C. Baiocci và A. Capelo , xuất bản năm 1984.
Bài toán bất đẳng thức biến phân trong không gian hữu hạn chiều được giới
thiệu khá đầy đủ trong cuốn Finite-Dimensional Variational-Inequalities
and Complementarity Problems của S. Facchinei and J. Pang (2003).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2
Những năm gần đây, bài toán bất đẳng thức biến phân đã có những
bước phát triển rất mạnh và thu hút được sự quan tâm của nhiều nhà
nghiên cứu. Một trong các hướng nghiên cứu quan trọng của bài toán bất
đẳng thức biến phân là việc xây dựng các phương pháp giải. Có rất nhiều

1.1 Một số khái niệm và tính chất cơ bản
1.1.1 Tập lồi và hàm lồi
Đoạn thẳng nối hai điểm a, b ∈ R
n
là tập các véc tơ x có dạng
{x ∈ R
n
: x = αa + βb; α ≥ 0; β ≥ 0; α + β = 1}.
Tập lồi là một khái niệm cơ bản nhất của giải tích lồi nó được định nghĩa
như sau.
Định nghĩa 1.1. Một tập C ⊂ R
n
được gọi là một tập lồi, nếu C chứa
mọi đoạn thẳng đi qua hai điểm bất kỳ của nó. Tức là C lồi khi và chỉ khi
∀x, y ∈ C; ∀λ ∈ [0, 1] ⇒ λx + (1 −λ) y ∈ C.
Ví dụ 1.1. • Hình cầu đóng B(a, r) = {x ∈ R
n
: x −a ≤ r}.
• Toàn không gian, siêu phẳng, hình tam giác, hình vuông,
hình tròn, mặt phẳng, nửa mặt phẳng trong R
2
.
Mệnh đề 1.1. Giao của một họ bất kỳ các tập lồi là một tập lồi.
Chứng minh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
4
Giả sử {A
α
}
α∈I

α
là một tập lồi. ✷
Mệnh đề 1.2. (Tính chất tập lồi)
(i) Nếu C, D ⊂ R
n
là các tập lồi thì
C + D = {x + y : x ∈ C, y ∈ D};
αC = {αx : x ∈ C, α ∈ R}.
cũng là các tập lồi trong R
n
, do đó C −D = C + (−1) D là tập lồi trong
R
n
.
(ii) Nếu C ⊂ R
n
, D ⊂ R
m
là tập lồi thì C ×D = {(x, y) : x ∈ C, y ∈ D}
cũng là tập lồi trong R
n+m
.
Định nghĩa 1.2. Một tập C ⊂ R
n
được gọi là nón nếu
∀x ∈ C, ∀λ > 0 ⇒ λx ∈ C.
Một nón được gọi là nón lồi nếu nó là nón và là một tập lồi.
Định nghĩa 1.3. Cho C ⊆ R
n
là một tập lồi và x

ε
C

x
0

:=

w : w
t
(x −x
0
) ≤ ε; ∀x ∈ C

được gọi là nón ε -
pháp tuyến ngoài của C tại x
0
.
Định nghĩa 1.4. Cho hàm f : C → (−∞; +∞], C lồi là tập con của R
n
.
Khi đó:
(a) f được gọi là hàm lồi trên C nếu
f(λx + (1 −λ)y) ≤ λf(x) + (1 − λ)f(y), ∀x, y ∈ C, λ ∈ [0, 1].
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
5
(b) f được gọi là lồi chặt trên C nếu với mọi x, y ∈ C sao cho x = y với
mọi λ ∈ (0, 1), ta có
f(λx + (1 −λ)y) < λf(x) + (1 − λ)f(y).
(c) f được gọi là tựa lồi tại y ∈ C nếu với mọi x ∈ C sao cho f (x) ≤ f (y)

(x) là hàm lồi khi và chỉ khi C là tập lồi.
• Hàm chuẩn f (x) = x =

x, x, x ∈ R
n
là lồi ✷
Định nghĩa 1.5. Cho hàm f : C → (−∞; +∞], C lồi là tập con của R
n
.
Khi đó, miền hữu hiệu của f, kí hiệu là domf, được xác định bởi
domf := {x ∈ C : f(x) < +∞}.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
6
Hàm f được gọi là chính thường nếu:
domf = ∅ và f(x) > −∞, ∀x ∈ domf.
Mệnh đề 1.3. Cho hàm f : C → R với C ⊆ R
n
.
Nếu f là hàm số khả vi và ∇f liên tục. Khi đó, f là hàm lồi khi và chỉ
khi
f(y) −f(x) ≥ ∇f(x), y − x, ∀x, y ∈ C.
Định nghĩa 1.6. Hàm f : C → R ∪ {+∞} được gọi là liên tục Lipchits
quanh x
0
nếu có L > 0 và lân cận U của x
0
sao cho
f (x) −f (x

) ≤ L x − x

0
được gọi là dưới vi
phân của f tại x
0
và kí hiệu là ∂f(x
0
). Vậy
∂f(x
0
) := {w ∈ R
n
: w, x − x
0
 ≤ f(x) − f(x
0
), ∀x ∈ R
n
}.
• Hàm f được gọi là khả dưới vi phân tại x
0
nếu ∂f(x
0
) = ∅.
Ví dụ 1.3. Cho C là một tập lồi, khác rỗng của không gian R
n
. Xét hàm
chỉ trên tập lồi C có dạng
δ
C
(x) :=

: δ
C
(x) ≥ w, x − x
0
, ∀x ∈ C}.
Hay ∂δ
C
(x
0
) = {w ∈ R
n
: 0 ≥ w, x −x
0
, ∀x ∈ C} = N
C
(x
0
). ✷
1.1.3 Tính đơn điệu.
Trong mục này ta luôn giả sử C là tập lồi trong R
n
Định nghĩa 1.8. (xem[5]) Giả sử C ⊆ R
n
và F : R
n
→ R
n
. Toán tử F
được gọi là:
(a) Đơn điệu mạnh trên C với hằng số δ > 0 nếu

tơ bất kỳ, đặt
d
C
:= inf
x∈C
x −y.
Ta nói d
C
(y) là khoảng cách từ y đến C. Nếu tồn tại π ∈ C sao cho
d
C
(y) = π −y, thì ta nói π là hình chiếu (khoảng cách) của y trên C.
Ký hiệu: π = p
C
(y) là hình chiếu của y trên C.
Theo định nghĩa, ta thấy rằng hình chiếu p
C
(y) của y trên C sẽ là nghiệm
của bài toán tối ưu
min

1
2
x −y
2
|x ∈ C

.
Nói cách khác việc tìm hình chiếu của y trên C có thể đưa về việc tìm cực
tiểu của hàm toàn phương x − y

(y) = 0 là siêu phẳng tựa của C
tại p
C
(y) và tách hẳn y khỏi C, tức là
p
C
(y) −y, x −p
C
(y) ≥ 0, ∀x ∈ C,
và
p
C
(y) −y, y −p
C
(y) < 0.
(iv) Ánh xạ y → p
C
(y) có các tính chất sau:
a) p
C
(x) −p
C
(y) ≤ x −y, ∀x, ∀y. (tính không giãn),
b) p
C
(x) −p
C
(y) , x −y ≥ p
C
(x) −p

≤ y − (λx + (1 − λ) π)
2
⇔ π − y
2
≤ λ (π − x) + (y −π)
2
⇔ π − y
2
≤ λ
2
π − x
2
+ y −π
2
+ 2λ π −x, y − π
⇔ λ
2
π − x
2
+ 2λ π −x, y − π ≥ 0.
Do λ > 0 nên λπ − x
2
+ 2 π −x, y − π ≥ 0 đúng với mọi x ∈ C và
λ ∈ (0; 1).
Do đó λ → 0 thì π − y, x −π ≥ 0 với mọi x ∈ C.
Suy ra y − π ∈ N
C
(π) .
• Có y − π ∈ N
C

p (y) = y
d
C
(y) = 0.
Nếu y /∈ C, ta có d
C
(y) = π −y nên theo định nghĩa cận dưới đúng,
tồn tại một dãy x
k
∈ C sao cho
lim
k→∞


x
k
− y


= d
C
(y) < +∞.
Vì dãy

x
k

bị chặn nên tồn tại một dãy con

x

là hình
chiếu của y trên C thì y −π
1
∈ N
C

π
1

; y − π
2
∈ N
C

π
2

.
⇒




π
1
− y, π
1
− π
2


π − y, x −π ≥ 0, ∀x ∈ C.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
11
Vậy π −y, x = π − y, π là một siêu phẳng tựa của C tại π. Siêu phẳng
này tách hẳn khỏi y vì y = π nên
π − y, x −π = −π − y
2
< 0.
(iv)
a) Theo (ii) Ánh xạ x → p (x) xác định khắp nơi. Do
z −p (z) ∈ N
C
(p (z)) , ∀z.
Áp dụng với z = y và z = x , ta có
x −p (x) , p (y) −p (x) ≤ 0,
y − p (y) , p (x) −p (y) ≤ 0.
Cộng vế hai bất đẳng thức được
p (y) −p (x) , p (y) −p (x) + x −y ≤ 0.
Theo bất đẳng thức Cauchy-Schwarz ta có: p (x) − p (y) ≤ x − y.
b) Theo tính chất (ii) áp dụng lần lượt với p(x) và p(y), ta có:
p (x) −x, p (x) − p (y) ≤ 0,
y − p (y) , p (x) −p (y) ≤ 0.
Cộng hai bất đẳng thức này ta được
p (x) −p (y) + y −x, p (x) − p (y) ≤ 0
⇔ p (x) − p (y)
2
+ p (x) −p (y) , y −x ≤ 0
⇔ p (x) − p (y) , x − y ≥ p (x) − p (y)
2
.

2
− p (x) −p (y)
2
− y −x
2
+ 2 p (x) −p (y) , x −y
= 2 p (x) −p (y) , x −y −p (x) −p (y)
2
≥ 2p (x) − p (y)
2
− p (x) −p (y)
2
= p (x) −p (y)
2
⇒ x −y
2
− p (x) −p (y) −x + y
2
≥ p (x) − p (y)
2
.
✷
Trong chương 2 ta sẽ sử dụng kiến thức sau
Định nghĩa 1.10. Cho C ⊆ R
n
là tập lồi và f : C → R
n
là hàm lồi và
ε ≥ 0. Xét bài toán
min

Nghĩa là
1
2
x −p
x

2
≤
1
2
x −p
C
(x)
2
+ ε. Trong đó p
C
(x) là hình chiếu
của x trên C.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
13
Mệnh đề 1.6. Cho C là tập lồi đóng khác rỗng. Khi đó p
x
là ε - chiếu
của x trên C khi và chỉ khi
x −p
x
, p
x
− y ≥ −ε, ∀y ∈ C. (1.2)
Chứng minh

, x ∈ R
n
.
Theo định nghĩa 1.11 p
x
là ε- nghiệm của bài toán (1.3). Từ mệnh đề 1.5
ta được
0 ∈ ∂
ε
[f (p
x
) + δ
C
(p
x
)] = ∂
ε
f (p
x
) + ∂
ε
δ
C
(p
x
) . (1.4)
Theo ví dụ 1.3 ∂
ε
δ
C

x −p
C
(x)
2
= x −p
x

2
+ 2 x − p
x
, p
x
− p
C
(x) + p
x
− p
C
(x)
2
≥ x − p
x

2
+ 2 x − p
x
, p
x
− p
C

∗
) := min {f (x) : x ∈ C } (P ).
Bài toán này được hiểu là hãy tìm x
∗
∈ C sao cho f (x
∗
) ≤ f (x) với
mọi x ∈ C. Mỗi điểm x ∈ C được gọi là một phương án chấp nhận được
của bài toán (P ). Tập C được gọi là miền (tập) chấp nhận được, f gọi là
hàm mục tiêu của bài toán (P). Thông thường tập C được cho như tập
nghiệm của một hệ bất đẳng thức và đẳng thức có dạng:
C := {x ∈ X : g
j
(x) ≤ 0, h
i
(x) = 0, j = 1 , m; i = 1 , k}. (2.1)
Trong đó X là tập lồi khác rỗng trong R
n
và g
j
, h
i
: R
n
→ R, g
j
lồi, h
i
là
hàm affine. Bài toán (P) cho bởi (2.1) gọi là trơn trên hàm mục tiêu và

đó tồn tại lân cận U của x
∗
sao cho
f (x
∗
) ≤ f (x) , ∀x ∈ U ∩ C.
Với mọi x ∈ C và 0 < λ < 1. Do tập C là tập lồi và U là lân cận của
x
∗
∈ C nên
x
λ
:= (1 −λ) x
∗
+ λx ∈ U ∩ C.
Do f (x
∗
) ≤ f (x
λ
) và f lồi, ta có
f (x
∗
) ≤ f (x
λ
) ≤ (1 − λ) f (x
∗
) + λf (x) , ∀x ∈ C.
Vậy x
∗
là nghiệm tối ưu toàn cục của f trên C .

∗
) ≤ f (x) , ∀x ∈ C.
Vậy z
∗
là điểm tối ưu của f trên C hay tập nghiệm tối ưu của f trên C
là lồi. ✷
2.1.2 Sự tồn tại nghiệm tối ưu
Xét bài toán tối ưu toàn cục (P ). Có 4 trường hợp:
• C = ∅ (không có nghiệm).
• f không bị chặn dưới trên C (inf
x∈C
f (x) = −∞).
• inf
x∈C
f (x) < ∞ nhưng giá trị cực tiểu không đạt được trên C.
• Tồn tại x
∗
∈ C sao cho f (x
∗
) = min
x∈C
f (x).
Định lí 2.1. Điều kiện cần và đủ để tồn tại nghiệm tối ưu toàn cục của
bài toán (P ) là
F
+
(C) := {t ∈ R
n
: f (x) ≤ t, x ∈ C},
đóng và bị chặn dưới.

là một điểm cực tiểu của f trên C. ✷
Định lí 2.2. (Weierstrass) Nếu C là tập compact và f là nửa liên tục
dưới trên C thì bài toán (P ) có nghiệm tối ưu.
Chứng minh. Đặt α := inf
x∈C
f (x). Theo định nghĩa có một dãy

x
k

⊂ C
sao cho lim
k→+∞
f

x
k

= α. Do C là compact nên có một dãy con hội tụ về
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
17
x
0
∈ C, không giảm tính tổng quát có thể coi x
k
→ x
0
.
Vì f là nửa liên tục dưới nên α > −∞. Nhưng x
0

a
T
x ≤ α ≤ a
T
y, ∀x ∈ C, ∀y ∈ D.
Ta nói siêu phẳng a
T
x = α tách chặt C và D nếu
a
T
x < α < a
T
y, ∀x ∈ C, ∀y ∈ D.
Ta nói siêu phẳng a
T
x = α tách mạnh C và D nếu
sup
x∈C
a
T
x < α < inf
y∈D
a
T
y.
Bổ đề 2.2. (Bổ đề liên thuộc) Cho C ⊂ R
n
là một tập lồi khác rỗng. Giả
sử x
0

Định lí 2.3. (Định lý Tách 1) Cho C và D là hai tập lồi khác rỗng trong
R
n
sao cho C ∩ D = ∅. Khi đó có một siêu phẳng tách C và D.
Định lý tách 1 có thể suy ra ngay từ bổ đề trên, chính là định lý tách
một tập lồi và một phần tử không thuộc nó.
Chứng minh.
Do C và D là lồi, nên C −D cũng lồi. Hơn nữa 0 /∈ (C − D), vì C ∩D = ∅.
Theo bổ đề trên áp dụng với x
0
= 0, tồn tại véc-tơ t ∈ R
n
, t = 0 với mọi
z ∈ C − D. Vì z = x −y với x ∈ C, y ∈ D, nên ta có
t, x ≥ t, y ∀x ∈ C, y ∈ D.
Lấy α : = sup
y∈D
t, y, khi đó siêu phẳng t, x = α tách C và D. ✷
Định lí 2.4. (Định lý tách 2 - Định lý nói về việc tách mạnh hai tập lồi).
Cho C và D là hai tập lồi đóng khác rỗng sao cho C ∩D = ∅. Giả sử có ít
nhất một tập com-pắc. Khi đó hai tập này có thể tách mạnh được bởi một
siêu phẳng.
Bổ đề 2.3. Cho C ⊂ R
n
là một tập lồi đóng khác rỗng sao cho 0 /∈ C.
Khi đó tồn tại một véc-tơ t ∈ R
n
, t = 0 và α > 0 sao cho
t, x ≥ α > 0, ∀x ∈ C.
Theo bổ đề này, thì C và điểm gốc tọa độ có thể tách mạnh, ví dụ bởi siêu

k
∈ D. Vì C compact, nên có một dãy con x
k
j
→ x khi
j → + ∞. Vậy z = x −y ∈ C −D. Chứng tỏ C − D là tập đóng.
Do 0 /∈ C−D, nên theo bổ đề trên, tồn tại t = 0, sao cho t, x −y ≥ α > 0
với mọi x ∈ C, y ∈ D. Vậy
inf
x∈C
t, x −
α
2
≥ sup
y∈D
t, y +
α
2
.
Chứng tỏ C và D có thể tách mạnh. ✷
Chú ý. Điều kiện một trong hai tập là compact trong định lý là không
thể bỏ được. Hãy xét ví dụ trong đó
C :=

(x, t) ∈ R
2


x ≥ 0, t = 0


Farkas là: Nửa không gian

x


a
T
x ≥ 0

chứa nón {x |Ax ≥ 0} khi và chỉ
khi vectơ a nằm trong nón sinh bởi các hàng của ma trận A. Tức là
A
T
x ≥ 0 ⇒ a
T
x ≥ 0 khi và chỉ khi A
T
y = a, y ≥ 0.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
20
Chứng minh. Giả sử A
T
y = a, y ≥ 0 với một y ∈ R
m
có một nghiệm y
nào đó. Nếu như Ax ≥ 0, thì từ A
T
y = a, nhân tích vô hướng với x, và
do Ax ≥ 0, y ≥ 0, ta có a
T

với mọi x ∈ C. Do 0 ∈ C nên α < 0. Thay x = A
T
y, với y ≥ 0, ta viết
được α ≤ p
T
A
T
y = y
T
Ap.
Chú ý rằng nếu x ∈ C thì ζx ∈ C với mọi ζ ≥ 0, vì từ x = A
T
y có
ζx = A
T
ζy. Vậy các tọa độ của y có thể lớn tùy ý, nên từ bất đẳng thức
α ≤ p
T
A
T
y = y
T
Ap, suy ra Ap ≥ 0. Vậy ta đã chỉ ra sự tồn tại của một
véc-tơ p sao cho Ap ≥ 0 và a
T
p < 0. Chứng tỏ hệ Ax ≥ 0, a
T
x < 0 với
một x ∈ R
n

n
.
Cả E và G đều là tập lồi (Do C và f lồi). Hơn nữa E ∩G = ∅, vì trái lại
thì tồn tại (
¯
t, ¯x) ∈ E và (
¯
t, ¯x) ∈ G
⇒ (
¯
t, ¯x) = (0, ¯x) với ¯x ∈ C ⇒
¯
t = 0.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
21
Kết hợp với (
¯
t, ¯x) ∈ E ⇒ t > f (x) −f (x
∗
) . Nên
0 > f (x) − f (x
∗
) ⇒ f (x
∗
) > f (x) .
Mâu thuẫn với giả thiết x
∗
là nghiệm tối ưu, vậy E ∩ G = ∅.
Áp dụng định lý siêu phẳng tách tồn tại a = (u
0

, u) = 0. Do đó
u
0
< 0. Chia cả hai vế của (2.4) cho −u
0
> 0, ta có
−t +

u
−u
0
, x

≤

u
−u
0
, v

, ∀x, v ∈ C; ∀t > f (x) −f (x
∗
) .
Cho t → f (x) −f (x
∗
), ta được
−f (x) + f (x
∗
) +
