LỜI CẢM ƠN
Luận văn được hoàn thành tại trường Đại học Sư phạm Hà Nội
2 dưới sự hướng dẫn của PGS.TS Nguyễn Năng Tâm. Thầy đã hướng
dẫn và truyền đạt cho tác giả những kinh nghiệm quý báu trong học tập
cũng như trong nghiên cứu khoa học. Thầy luôn động viên, khích lệ tác
giả vươn lên trong học tập, tự tin vượt qua khó khăn trong việc nghiên
cứu và hoàn thiện luận văn. Tác giả xin bày tỏ lòng biết ơn lớn lao, lòng
kính trọng sâu sắc nhất đối với Thầy.
Tác giả xin trân trọng cảm ơn Ban giám hiệu trường Đại học Sư
phạm Hà Nội 2, phòng Sau đại học, các thầy cô giáo trong nhà trường
và các thầy cô giáo dạy cao học chuyên ngành Toán giải tích đã giúp đỡ,
tạo điều kiện thuận lợi cho tác giả trong suốt quá trình học tập.
Tác giả xin chân thành cảm ơn Ban lãnh đạo tỉnh Lào Cai, Sở
GD-ĐT tỉnh Lào Cai, Ban giám hiệu, các thầy cô giáo, đồng nghiệp
trường Trung học phổ thông số III Bảo Yên cùng gia đình, người thân,
bạn bè đã giúp đỡ, động viên và tạo điều kiện thuận lợi để tác giả hoàn
thành khóa học Thạc sĩ và hoàn thành luận văn này.
Hà Nội, tháng 12 năm 2013
Tác giả
Phạm Trọng Dần
LỜI CAM ĐOAN
Luận văn được hoàn thành tại trường Đại Học Sư phạm Hà Nội 2
dưới sự hướng dẫn của PGS. TS Nguyễn Năng Tâm.
Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng tôi.
Trong quá trình nghiên cứu và hoàn thành luận văn tôi đã kế thừa
những thành quả khoa học của các nhà khoa học và đồng nghiệp với sự
trân trọng và biết ơn. Tôi xin cam đoan rằng các thông tin trích dẫn
trong luận văn đã được chỉ rõ nguồn gốc.
Hà Nội, tháng 12 năm 2013
Tác giả
Phạm Trọng Dần
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 KIẾN THỨC CHUẨN BỊ
3
1.1. Không gian Euclid Rn . . . . . . . . . . . . . . . . . . .
3
1.1.1. Tích vô hướng và chuẩn . . . . . . . . . . . . . .
4
1.1.2. Tập đóng và tập mở . . . . . . . . . . . . . . . .
4
1.1.3. Sự hội tụ
. . . . . . . . . . . . . . . . . . . . . .
5
1.1.4. Tập bị chặn, tập compact . . . . . . . . . . . . .
5
Tập lồi, hàm lồi, hàm lồi suy rộng . . . . . . . . . . . .
6
1.2.1. Tập lồi - tập affine . . . . . . . . . . . . . . . . .
6
1.2.2. Hàm lồi . . . . . . . . . . . . . . . . . . . . . . .
6
1.2.3. Hàm lồi suy rộng . . . . . . . . . . . . . . . . . .
7
1.3. Không gian tôpô lồi địa phương . . . . . . . . . . . . . .
9
1.3.1. Không gian tôpô . . . . . . . . . . . . . . . . . .
9
1.2.
iii
1.3.2. Không gian tôpô tuyến tính . . . . . . . . . . . .
10
1.3.3. Không gian tôpô lồi địa phương . . . . . . . . . .
11
1.3.4. Nón lồi và nón lùi xa của tập lồi . . . . . . . . . .
12
Hàm Lipschitz . . . . . . . . . . . . . . . . . . . . . . .
13
1.5. Ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.6.
14
1.4.
Hàm toàn phương và bài toán quy hoạch toàn phương .
1.6.1.
Hàm toàn phương . . . . . . . . . . . . . . . . .
14
1.6.2. Bài toán quy hoạch toàn phương . . . . . . . . .
16
2 DƯỚI VI PHÂN DƯỚI CỦA HÀM TOÀN PHƯƠNG
18
2.1. Khái niệm dưới vi phân dưới . . . . . . . . . . . . . . . .
18
2.2. Dưới vi phân dưới bị chặn của hàm toàn phương . . . . .
19
2.3. Dưới vi phân dưới của hàm toàn phương . . . . . . . . .
30
3 ỨNG DỤNG CỦA DƯỚI VI PHÂN DƯỚI VÀO BÀI
TOÁN TỐI ƯU TOÀN PHƯƠNG
46
3.1. Bài toán tối ưu toàn phương . . . . . . . . . . . . . . . .
46
3.2. Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . .
47
3.3. Thuật toán tìm nghiệm . . . . . . . . . . . . . . . . . . .
48
Kết luận
51
Tài liệu tham khảo
52
iv
BẢNG KÝ HIỆU
R
Tập số thực
R
R ∪ (−∞; +∞)
Rn
Không gian Euclide n - chiều
Rs n×n
Tập các ma trận thực đối xứng n × n
Rm×n
Tập các ma trận thực m × n
hx; yi
Tích vô hướng của x và y
kxk
Chuẩn của x
B x0 ; ε
Hình cầu mở tâm x0 bán kính ε
intK
Phần trong của tập K
K
Bao đóng của tập K
af f K
Bao afine của tập K
coK
Bao lồi của tập K
O+D
Nón lùi xa của tập D
N
Hằng số Lipschitz
ΠH
Phép chiếu lên siêu phẳng H
Q(x) = 12 xT Ax + bT x
Hàm toàn phương
∇Q(x0 )
Đạo hàm của Q(x) tại x0
∂ − f (x)
Dưới vi phân dưới của f tại x
Kết thúc chứng minh
1. Lý do chọn đề tài
Khái niệm dưới vi phân dưới được giới thiệu bởi Plastria [10] xem
như một sự nới lỏng khái niệm dưới vi phân trong giải tích lồi. Động cơ
thúc đẩy việc đưa ra khái niệm mới này là thuật toán, từ khi Plastria
chứng minh rằng, phương pháp mặt phẳng cắt cổ điển của Kelley cũng
dùng được cho bài toán tối ưu lồi, dưới một số giả thiết thích hợp sử
dụng dưới gradient dưới để sinh ra những mặt phẳng cắt. Plastria cũng
lưu ý rằng, tính dưới khả vi dưới của hàm số suy ra tính tựa lồi. Sau đó
mối liên quan giữa khái niệm dưới vi phân dưới với một số khái niệm
khác đã được nghiên cứu bởi Greenberg và Pierskalla [4]. Một số kết quả
của dưới vi phân dưới của hàm số được định nghĩa trong không gian lồi
và được ứng dụng vào các bài toán trong lĩnh vực quy hoạch phân thức.
Tính tựa lồi của hàm toàn phương được nghiên cứu bởi một số tác
giả [3]. Động cơ thúc đẩy họ là sự tin tưởng khái niệm dưới vi phân dưới
là điều kiện chắc chắn thích hợp mà ta đặt cho hàm tựa lồi để tạo nên
một lý thuyết, ở một mức độ nào đó, song song với giải tích lồi.
Sau khi học được các kiến thức về Toán giải tích, với mong muốn
tìm hiểu sâu hơn về các kiến thức đã học, mối quan hệ và ứng dụng của
chúng. Tôi đã chọn đề tài nghiên cứu:
“ Dưới vi phân dưới của hàm toàn phương và ứng dụng ”.
2. Mục đích nghiên cứu
Để hiểu sâu hơn về những kiến thức đã học, mối quan hệ và ứng
dụng của chúng. Đồng thời thu nhận được kiến thức về dưới vi phân
dưới của hàm toàn phương và ứng dụng.
2
3. Nhiệm vụ nghiên cứu
Dưới vi phân dưới của hàm toàn phương và ứng dụng.
4. Đối tượng và phạm vi nghiên cứu
Hàm toàn phương, dưới vi phân dưới của hàm toàn phương và bài
toán tối ưu với hàm mục tiêu là hàm toàn phương.
5. Phương pháp nghiên cứu
Nghiên cứu lý thuyết: Thu thập tài liệu, đọc và phân tích, tổng
hợp để được một nghiên cứu tổng quan về dưới vi phân dưới của hàm
toàn phương và bài toán tối ưu với hàm mục tiêu là hàm toàn phương.
6. Dự kiến đóng góp mới
Một tổng quan về dưới vi phân dưới của hàm toàn phương và ứng
dụng.
Chương 1
KIẾN THỨC CHUẨN BỊ
Chương này trình bày những khái niệm cơ bản dùng trong không
gian Euclid Rn và một số kiến thức có liên quan khác, xem như là công
cụ sẽ dùng đến trong các chương sau. Những điều không chứng minh sẽ
được tìm thấy trong [1] [2].
1.1.
Không gian Euclid Rn
Tập hợp
n
o
T
R = x = (x1 , x2 , ..., xn ) | x1 , x2 , ..., xn ∈ R
n
trong đó
x = (x1 , x2 , ..., xn )T
với hai phép toán
(x1 , ..., xn )T + (y1 , ..., yn )T = (x1 + y1 , ..., xn + yn )T
λ(x1 , ..., xn )T = (λx1 , ..., λxn )T , λ ∈ R
lập thành một không gian véc tơ thực n - chiều.
Nếu x = (x1 , ..., xn )T ∈ Rn thì xi gọi là thành phần tọa độ thứ i
của x. Véc tơ không của không gian này gọi là gốc của Rn và được kí
hiệu là 0, vậy 0 = (0, ..., 0)T .
3
4
Ta gọi hệ e1 = (1, 0, ..., 0)T ; e2 = (0, 1, 0, ..., 0)T ; ...; en = (0, ..., 0, 1)T
là cơ sở chính tắc của không gian Rn .
1.1.1.
Tích vô hướng và chuẩn
Trong không gian Rn ta định nghĩa tích vô hướng chính tắc h., .i
như sau: với x = (x1 , ..., xn )T , y = (y1 , ..., yn )T ∈ Rn ,
hx, yi =
n
X
xi yi
i=1
Khi đó với mọi x = x1 , ..., xn )T ∈ Rn ta định nghĩa
v
u n
p
uX
kxk = hx, xi = t
x2i
i=1
và gọi là chuẩn Euclid của véc tơ x.
1.1.2.
Tập đóng và tập mở
Định nghĩa 1.1.1. Cho x0 ∈ Rn ,ε > 0 ,ta gọi tập
B(x0 , ε) = x ∈ Rn |
x − x0
< ε
là hình cầu mở trong Rn có tâm tại x0 , bán kính ε.
Định nghĩa 1.1.2. Tập K ⊂ Rn được gọi là tập mở nếu với mọi x0 ∈ U
tồn tại ε > 0 sao cho B(x0 , ε) ⊂ K.
Tập L ⊂ Rn gọi là tập đóng nếu tập Rn \L là tập mở.
Định nghĩa 1.1.3. Cho K là tập con bất kì trong Rn . Kí hiệu {Ui (K)}i∈I
là họ tất cả các tập mở chứa trong K. {Fj (K)}j∈J là họ tất cả các tập
đóng chứa trong K. Ta có U = ∪ Ui (K) là tập mở và F = ∩ Fj (K) là
i∈I
j∈J
tập đóng.
Tập U gọi là phần trong của K và kí hiệu: intK. Tập F gọi là bao
đóng của K và kí hiệu: K
5
Ta có một số kết quả:
(i) K là tập mở khi và chỉ khi K = intK.
(ii) K là tập đóng khi và chỉ khi K = K.
1.1.3.
Sự hội tụ
Định nghĩa 1.1.4. Dãy điểm xk trong Rn gọi là hội tụ đến x0 ∈ Rn
khi k → ∞ nếu dãy số
xk − x0
hội tụ tới 0 ∈ R khi k → ∞. Khi đó
ta gọi x0 là giới hạn của dãy xk và kí hiệu xk → x0 . Ta nói x ∈ Rn
tiến đến x0 ∈ Rn . Kí hiệu x → x0 nếu
x − x0
→ 0.
Dễ dàng chứng minh được tính chất sau: Tập A ⊂ Rn được gọi là
tập đóng khi và chỉ khi với mọi dãy xk ⊂ A mà xk hội tụ đến x0 thì
x0 ∈ A.
1.1.4.
Tập bị chặn, tập compact
Định nghĩa 1.1.5. Tập K trong Rn được gọi là tập bị chặn nếu tồn tại
m > 0 sao cho kxk < m với mọi x ∈ K.
Định nghĩa 1.1.6. Tập K trong Rn được gọi là tập compact nếu mọi
dãy xk trong K đều có dãy con xkm hội tụ đến một điểm x∗ ∈ K.
Định lý 1.1.1. Tập K ⊂ Rn compact khi và chỉ khi K là tập đóng và
bị chặn.
6
1.2.
Tập lồi, hàm lồi, hàm lồi suy rộng
1.2.1.
Tập lồi - tập affine
Định nghĩa 1.2.1. Cho X là không gian véc tơ. Tập M ⊂ X được gọi
là đa tạp affine (tập affine) nếu với ∀x, y ∈ M , λ ∈ R ta có:
λx + (1 − λ) y ∈ M
Nếu K ⊂ X bất kì. Ta gọi bao affine của K, kí hiệu: af f K, là
giao của tất cả các tập affine chứa K.
Định nghĩa 1.2.2. Tập K ⊂ Rn được gọi là lồi nếu
λx + (1 − λ) y ∈ K ∀x, y ∈ K, ∀λ ∈ [0; 1]
Giả sử X ⊂ Rn . Giao của tất cả các tập lồi trong Rn chứa X được gọi
là bao lồi của tập X, kí hiệu là coX.
Theo định nghĩa tập rỗng được xem là tập lồi.
Ví dụ 1.2.1. Các tam giác và hình tròn trong mặt phẳng là tập lồi.
Hình cầu đơn vị trong không gian Rn là tập lồi.
1.2.2.
Hàm lồi
Định nghĩa 1.2.3. Cho K ⊂ Rn là một tập lồi và f : K → R là một
hàm số.
Hàm f được gọi là hàm lồi trên K nếu với mọi x, y ∈ K và với
mọi t ∈ [0, 1] ta có:
f (tx + (1 − t)y ≤ tf (x) + (1 − t)f (y)
Hàm f được gọi là hàm lồi chặt trên K nếu với mọi x, y ∈ K và
với mọi t ∈ [0, 1] ta có:
f (tx + (1 − t)y < tf (x) + (1 − t)f (y)
7
Hàm f được gọi là hàm lõm trên K nếu với mọi x, y ∈ K và với
mọi t ∈ [0, 1] ta có:
f (tx + (1 − t)y ≥ tf (x) + (1 − t)f (y)
Dễ nhận thấy, f là hàm lõm khi và chỉ khi (−f ) là hàm lồi trên
K, trong đó (−f ) được xác định bởi (−f )(x) = −f (x) với ∀x ∈ K.
Định nghĩa 1.2.4. Nếu f là một hàm lồi trên tập K ⊂ Rn thì tập
epi(f ) = {(x; α) ∈ X × R|f (x) ≤ α}
gọi là trên đồ thị của hàm f .
Ví dụ 1.2.2. Hàm hằng f : X → R; f (x) = a với ∀x ∈ X là một hàm
lồi.
Ví dụ 1.2.3. Hàm f : R → R; f (x) = x3 không phải là hàm lồi trên R.
Thật vậy với x = −1, y = 0, t =
1
2
ta có
1
1
f (tx + (1 − t) y) = − , tf (x) + (1 − t)f (y) = −
8
2
Chứng tỏ
f (tx + (1 − t) y) > tf (x) + (1 − t)f (y)
Vậy f (x) = x3 không phải là hàm lồi trên R
1.2.3.
Hàm lồi suy rộng
Định nghĩa 1.2.5. Cho K ⊂ Rn là một tập lồi và f : K → R là một
hàm số.
Hàm f được gọi là hàm giả lồi trên K nếu với mọi x, y ∈ K sao
cho f (x) ≤ f (y) và với mọi λ ∈ [0, 1], tồn tại một số β > 0 thỏa mãn
f (λx + (1 − λ)y) ≤ f (y) − λ(1 − λ)β
8
Hàm f được gọi là hàm giả lồi chặt trên K nếu với mọi x, y ∈ K
sao cho f (x) ≤ f (y) và với mọi λ ∈ [0, 1], tồn tại một số β > 0 thỏa
mãn
f (λx + (1 − λ)y) < f (y) − λ(1 − λ)β
Ta có một số tính chất sau:
(i)Hàm lồi là hàm giả lồi, hàm lồi chặt là hàm giả lồi chặt, nhưng
hàm giả lồi có thể không lồi.
(ii)Hàm lồi chưa chắc đã là hàm giả lồi chặt.
(iii)Hàm giả lồi chưa chắc đã là hàm giả lồi chặt.
Định nghĩa 1.2.6. Cho K ⊂ Rn là một tập lồi và f : K → R là một
hàm số.
Hàm f được gọi là hàm tựa lồi trên K nếu với mọi x, y ∈ K và
với mọi t ∈ [0, 1], ta có:
f (tx + (1 − t)y) ≤ max {f (x), f (y)}
Hàm f được gọi là hàm tựa lồi chặt trên K nếu với mọi x, y ∈ K
và với mọi t ∈ [0, 1], ta có:
f (tx + (1 − t)y) < max {f (x), f (y)}
Ta có một số tính chất sau:
(i)Hàm tựa lồi chặt là hàm tựa lồi.
(ii)Hàm tựa lồi thì chưa chắc tựa lồi chặt.
(iii)Nếu hàm f lồi thì nó là hàm tựa lồi. Điều ngược lại không
đúng.
(iv)Hàm lồi chưa chắc đã là hàm tựa lồi chặt.
9
1.3.
Không gian tôpô lồi địa phương
1.3.1.
Không gian tôpô
Cho X là tập hợp. Kí hiệu P(X) là họ các tập con của X. Họ
τ ⊂ P(X) được gọi là một tôpô trên X nếu nó thỏa mãn các tính chất
sau:
(i) ∅; X ∈ τ .
(ii) Giao của một số hữu hạn phần tử thuộc τ thì thuộc τ .
(iii) Hợp của một họ tùy ý các phần tử thuộc τ thì thuộc τ .
Khi đó X được gọi là không gian tôpô và mỗi phần tử U ∈ τ được
gọi là tập mở trong X.
Cho A ⊂ X, x0 ∈ X, ta nói x0 là:
- Điểm trong của A nếu tồn tại U ∈ τ sao cho x0 ∈ U ⊂ A.
- Điểm ngoài của A nếu tồn tại U ∈ τ sao cho x0 ∈ U và U ∩A = ∅.
- Điểm biên nếu cả hai mệnh đề trên đều sai.
Định nghĩa 1.3.1. Nếu x0 là điểm trong của A thì ta cũng nói A là lân
cận của x0 .
Cho không gian tôpô (X, τ ). Một họ B ⊂ τ được gọi là một cơ sở
lân cận của τ nếu mọi tập U ∈ τ đều được biểu diễn dưới dạng hợp của
các tập thuộc B. Một họ V ⊆ τ được gọi là một cơ sở lân cận của x0 ∈ X
nếu mọi lân cận U của x0 đều tồn tại V ∈ V sao cho x0 ∈ V ⊆ U .
10
1.3.2.
Không gian tôpô tuyến tính
Cho không gian véc tơ X. Khi đó một tôpô τ trên X được gọi là
tương đương với cấu trúc đại số trên X nếu dưới tôpô này các ánh xạ
sau lên tục:
+:X ×X →X
.:R×X →X
Tức là:
Với mọi x, y ∈ X và mọi lân cận W của x + y, tồn tại các lân cận
U của x, V của y sao cho U + V ⊂ W .
Với mọi λ ∈ R, x ∈ X và mọi lân cận W của λx, tồn tại ε > 0 và
lân cận V của x sao cho µV ⊂ W với mọi µ ∈ (λ − ε, λ + ε).
Khi đó, τ được gọi là tôpô tuyến tính trên X và X được gọi là
không gian tôpô tuyến tính.
Định nghĩa 1.3.2. Cho A là tập con của không gian véc tơ X trên
trường K
Tập A được gọi là cân đối nếu với mọi x ∈ A ta có λx ∈ A với
mọi |λ| ≤ 1.
Tập A được gọi là hấp thụ nếu với mọi x ∈ X đều tồn tại λ > 0
sao cho x ∈ µA với mọi µ thỏa mãn điều kiện |µ| ≥ λ.
Định lý 1.3.1. Cho X là một không gian véc tơ
(a) Nếu τ là một tôpô tuyến tính, thì tồn tại cơ sở lân cận gốc V ⊂ τ
thỏa mãn:
(i) V cân đối, hấp thụ với mọi V ∈ V,
(ii) αV ⊂ V với mọi α 6= 0 và V ∈ V,
(iii) Với mọi V ∈ V tồn tại U ∈ V sao cho U + U ⊂ V,
(iv) Với mọi V1 , V2 ∈ V sao cho U ⊂ V1 ∩ V2 .
11
(b) Ngược lại nếu V ⊂ P(X) là họ các tập thỏa mãn các điều kiện (i iv), thì tồn tại tôpô tuyến tính τ trên X nhận V làm cơ sở lân cận gốc.
1.3.3.
Không gian tôpô lồi địa phương
Từ kết quả trên ta thấy cấu trúc tôpô tuyến tính hoàn toàn được
xác định bởi hệ cơ sở lân cận gốc. Nếu tồn tại một hệ cơ sở lân cận gốc
gồm toàn các tập lồi thì τ được gọi là tôpô lồi địa phương và X được
gọi là không gian tô pô lồi địa phương.
Định lý 1.3.2. Cho X là một không gian véc tơ.
(i) Nếu τ là một tôpô lồi địa phương trên X, thì tồn tại một cơ sở
lân cận gốc gồm các tập lồi, cân đối và hấp thụ.
(ii) Ngược lại, nếu V0 là họ gồm các tập lồi, cân đối và hấp thụ thì
họ sau
o
n
m
V = ε ∩ Vi | ε > 0; m ∈ N; Vi ∈ V0
1
là cơ sở lân cận gốc của một tôpô lồi địa phương nào đó. Hơn nữa, tôpô
là Hausdorff khi và chỉ khi
∩
V ∈V0 ,ε>0
εV = {0}
Trong phần này ta định nghĩa phần trong tương đối của K (Với K
là tập lồi trong X) là phần trong của tập này theo tôpô cảm sinh trong
af f (K). Cụ thể:
riK = {x ∈ K |
∃V : (x + V ) ∩ aff(K) ⊂ K}
(Với V là lân cận gốc)
Ví dụ 1.3.1. Không gian định chuẩn là không gian tôpô lồi địa phương
sinh bởi họ gồm một tập: V0 = {B(0, 1)}. Khi đó, cơ sở lân cận gốc
tương ứng
V = {εB(0, 1) | ε > 0} = {B(0, ε)|ε > 0}
12
1.3.4.
Nón lồi và nón lùi xa của tập lồi
Định nghĩa 1.3.3. Tập K ⊂ Rn được gọi là một nón nếu với mọi
x ∈ K, với mọi λ ≥ 0 ta có: tx ∈ K.
Định nghĩa 1.3.4. Tập K ⊂ Rn được gọi là một nón lồi nếu K vừa là
nón vừa là một tập lồi, tức là: với mọi x, y ∈ K và với mọi λ, µ ≥ 0, ta
có
λx + µy ∈ K
Định lý 1.3.3. Tập K ⊂ Rn được gọi là một nón lồi khi và chỉ khi
∀x; y ∈ K, ∀λ ≥ 0 ⇒ x + y ∈ K; λx ∈ K
Chứng minh. ⇒ Giả sử K là hình nón lồi. Khi đó do K là tập lồi, ta có:
z = 12 (x + y) ∈ K.
Do K là nón nên ta có:x + y = 2z ∈ K.
⇐ Ngược lại, với ∀x; y ∈ K, ∀λ ≥ 0 ta có λx ∈ K , vậy K là hình
nón.
Với 0 < λ < 1; x, y ∈ K ta có (1 − λ)x ∈ K; λy ∈ K và (1 − λ)x +
λy ∈ K
Chú ý với λ = 0 ta vẫn có (1 − λ)x + λy ∈ K. Vậy K là tập lồi.
Từ đó ta suy ra K là nón lồi.
Định nghĩa 1.3.5. Cho D là tập lồi khác rỗng trong Rn .
Véc tơ v ∈ Rn khác 0 được gọi là phương lùi xa của D nếu với mọi
x ∈ D, với mọi t ≥ 0 ta có x + tv ∈ D.
Tập tất cả các phương lùi xa của D cùng véc tơ 0 của Rn lập thành
một nón lồi. Ta gọi nón đó là nón lùi xa của D và kí hiệu là 0+ D.
13
1.4.
Hàm Lipschitz
Định nghĩa 1.4.1. Giả sử X là không gian Banach, f : X → R
Hàm f được gọi là Lipschitz địa phương tại x0 ∈ X hay Lipschitz
địa phương gần x0 , nếu tồn tại lân cận U của x0 số K > 0 sao cho với
mọi x, x0 ∈ X ta có
|f (x) − f (x0 )| ≤ K kx − x0 k
Hàm f được gọi là Lipschitz địa phương trên tập Y ⊂ X, nếu f là
Lipschitz địa phương tại mọi x ∈ Y .
Hàm f được gọi là Lipschitz địa phương với hằng số Lipschitz K
trên tập Y ⊂ X, nếu biểu thức trên đúng với mọi x, x0 ∈ Y
1.5.
Ma trận
Định nghĩa 1.5.1. Gọi Rs n×n là tập hợp các ma trận thực đối xứng
n × n Giả sử A là ma trận thuộc Rs n×n ta có:
(i) A được gọi là nửa xác định dương nếu xT Ax ≥ 0; ∀x ∈ Rn .
(ii) A được gọi là xác định dương nếu A là nửa xác định dương
trên Rs n×n và xT Ax = 0 ⇔ x = 0.
(iii) A được gọi là nửa xác định âm (xác định âm) nếu −A là nửa
xác định dương (xác định dương) .
Ta kí hiệu:
a1
diag(a1 , ..., an ) =
0
...
0
an
14
1.6.
Hàm toàn phương và bài toán quy hoạch toàn
phương
1.6.1.
Hàm toàn phương
Trong luận văn này ta xét hàm toàn phương Q : Rn → R được cho
1
dưới dạng: Q(x) = xT Ax + bT x , trong đó A là ma trận thực đối xứng
2
n
cấp n × n và b ∈ R . Ta có định lý sau:
Định lý 1.6.1. Nếu A là ma trận vuông cấp n × n, đối xứng, nửa xác
1
định dương, b ∈ Rn thì hàm toàn phương Q(x) = xT Ax + bT x là một
2
hàm lồi.
Chứng minh. Vì A là nửa xác định dương nên với x, y ∈ Rn ta có
(x − y)T A(x − y) ≥ 0
suy ra
1
1 T
x Ax + y T Ay ≥ xT Ay
2
2
Do đó với mọi x, y ∈ Rn và với mọi t ∈ (0, 1) ta có:
t2 T
1 − t2 T
x Ax + tbT x +
y Ay
2
2
+ (1 − t) bT x + t (1 − t) xT Ay
Q [tx + (1 − t) y] =
t2 T
≤ x Ax + tbT x
2
1 − t2 T
+
y Ay + (1 − t) bT y
2
1 T
1 T
+ t (1 − t) x Ax y Ay
2
2
≤ tQ(x) + (1 − t)Q(y)
Vậy Q lồi.
15
Áp dụng. Trường hợp n = 1 ta thấy hàm toàn phương như trên có
dạng hàm bậc hai f (x) = ax2 + bx
Theo định lý trên ta thấy hàm bậc hai là hàm lồi khi a > 0.
Dựa vào các kết quả của S.Schaible [12], các tính chất của hàm
toàn phương, tựa lồi, ta có các kết quả sau:
1
Định lý 1.6.2. Cho K ⊂ Rn là thể lồi và Q(x) = xT Ax + bT x.
2
Khi đó Q là tựa lồi, nhưng không lồi trên K khi và chỉ khi rankA =
rank(A; b) và tồn tại ma trận không suy biến P sao cho với mọi véc tơ
v thỏa mãn Av + b = 0 ta có:
(i) Hàm số hợp G(y) = G(P v + b) có thể viết lại là:
1
G(y) = y T Λy + δ
2
trong đó
Λ = diag(−1, 1, ..., 1, 0, ..., 0)
(ii) Tập hợp D = {y ∈ Rn | x = P y + v ∈ K} thỏa mãn một trong
hai điều sau:
D ⊂ {y = (y1 , y2 , ..., yn ) ∈ Rn | G(y) ≤ δ, y1 ≥ 0}
hoặc
D ⊂ {y = (y1 , y2 , ..., yn ) ∈ Rn | G(y) ≤ δ, y1 ≤ 0}
1
trong trường hợp này hàm số h(x) = −(δ − Q(x)) 2 là hàm lồi trên K.
Hệ quả 1.6.1. Cho K ⊂ Rn là tập lồi, mở.
Khi đó
1
Q(x) = xT Ax + bT x
2
gọi là tựa lồi trên clK khi và chỉ khi nó là hàm giả lồi trên K.
Định lý 1.6.3. K ⊂ Rn là tập lồi, mở.
Khi đó
1
Q(x) = xT Ax + bT x
2
- Xem thêm -