Luận văn Thạc sĩ Toán học: Một vài kết quả về sự tồn tại nghiệm của bài toán quy hoạch toàn phương

Mục lục

Mục lục ii

Danh sách ký hiệu iii

Mở đầu 1

1 Kiến thức chuẩn bị 3

1.1 Không gian Hilbert . . . . . . . . . . . . . . . . . . . . . . 3

1.1.1 Không gian tiền Hilbert . . . . . . . . . . . . . . . 3

1.1.2 Không gian Hilbert . . . . . . . . . . . . . . . . . . 4

1.1.3 Các ví dụ . . . . . . . . . . . . . . . . . . . . . . . 4

1.1.4 Một vài tính chất cơ bản . . . . . . . . . . . . . . . 5

1.2 Tập lồi và hàm lồi trong không gian Hilbert . . . . . . . . . 7

1.2.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . 11

. . . . 1.3 Hàm toàn phương . . . . . . . . . . . . . . . . . . . 17

2 Bài toán quy hoạch toàn phương 21

. . . . . . . . . . . . . . . . . . 2.1 Giới thiệu bài toán . . . . 21

. . . . . . . . . . . . . . . . . . 2.1.1 Phát biểu bài toán . 21

. . . . . . . . . . . . . . 2.2 Các định lí về sự tồn tại nghiệm . 23

2.2.1 Bài toán quy hoạch toàn phương với ràng buộc tuyến

tính . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.2.2 Bài toán quy hoạch toàn phương lồi với hữu hạn ràng

buộc toàn phương lồi trong không gian Hilbert thực . 37

Kết luận 60

Tài liệu tham khảo 61

iii

Danh sách ký hiệu

N Tập số tự nhiên

R Tập số thực

Rn Không gian các số thực n chiều

(cid:104)., .(cid:105) Tích vô hướng

(cid:107).(cid:107) Chuẩn

0+F Nón lùi xa của tập lồi F

∂f (x) Dưới vi phân của f tại x

∂εf (x0) ε−Dưới vi phân của f tại x0

∇f (x) Đạo hàm của f tại x

Rm×n Không gian ma trận cấp m × n

Không gian ma trận đối xứng cấp n × n

Rn×n S AT

B(x0, ρ) Ma trận chuyển vị của ma trận A Hình cầu đóng tâm x0 bán kính ρ

H Không gian Hilbert thực

Mở đầu

Quy hoạch toàn phương là một bộ phận đặc biệt của quy hoạch phi tuyến,

có nhiều ứng dụng trong lý thuyết và trong thực tế. Đây là vấn đề đã được

nhiều nhà Toán học nghiên cứu và xây dựng nên nhiều thuật toán để giải.

Sau khi học những kiến thức trong chuyên ngành Toán ứng dụng, với

mong muốn tìm 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 muốn tìm hiểu sâu hơn về kết quả tồn tại nghiệm

của bài toán quy hoạch toàn phương. Tác giả chọn đề tài nghiên cứu "Một vài

kết quả về sự tồn tại nghiệm của bài toán quy hoạch toàn phương".

Luận văn trình bày sự tồn tại nghiệm của bài toán quy hoạch toàn phương với ràng buộc tuyến tính trong Rn và bài toán quy hoạch toàn phương lồi với

những ràng buộc toàn phương lồi trong không gian Hilbert. Các kết quả và

thông tin trong luận văn được viết dựa vào bài báo "On the Solution Existence

of Convex Quadratic Programming Problems in Hilbert Spaces" của Vũ Văn

Đông và Nguyễn Năng Tâm, 2016.

Luận văn được chia thành hai chương với nội dung chính như sau:

Chương 1: "Kiến thức chuẩn bị", chương này trình bày một số kiến thức

cơ sở về không gian Hilbert, tập lồi và hàm lồi trong không gian Hilbert.

Chương 2: "Bài toán quy hoạch toàn phương", chương này trình bày

nội dung bài toán quy hoạch toàn phương và sự tồn tại nghiệm của bài toán quy hoạch toàn phương với ràng buộc tuyến tính trong không gian Rn và bài

toán quy hoạch toàn phương lồi với hữu hạn ràng buộc toàn phương lồi trong

không gian Hilbert thực.

Thái Nguyên, ngày 05 tháng 9 năm 2017

Tác giả luận văn

Đào Thị Thu

Chương 1

Kiến thức chuẩn bị

Chương này trình bày một số kiến thức cở bản về không gian Hilbert và

giải tích lồi. Đó là những kết quả sẽ được dùng cho chương sau. Nội dung

trong chương này được trích dẫn chủ yếu từ các tài liệu tham khảo [1], [2],

[3] và [4].

1.1 Không gian Hilbert

1.1.1 Không gian tiền Hilbert

Định nghĩa 1.1.1. Cho H là không gian trên trường K. Tích vô hướng trên H là một ánh xạ xác định như sau: (cid:104)., .(cid:105) : H × H → K, (x, y) (cid:55)→ (cid:104)x, y(cid:105), thỏa

mãn các điều kiện sau đây:

a) (cid:104)x, y(cid:105) = (cid:104)y, x(cid:105) với mọi x, y ∈ H;

b) (cid:104)x + y, z(cid:105) = (cid:104)x, z(cid:105) + (cid:104)y, z(cid:105) với mọi x, y, z ∈ H; c) (cid:104)λx, y(cid:105) = λ(cid:104)x, y(cid:105) với mọi x, y ∈ H; λ ∈ K;

d) (cid:104)x, x(cid:105) ≥ 0 với mọi x ∈ H và (cid:104)x, x(cid:105) = 0 khi và chỉ khi x = 0.

Số (cid:104)x, y(cid:105) được gọi là tích vô hướng của hai véctơ x và y. Cặp (H, (cid:104)., .(cid:105))

được gọi là không gian tiền Hilbert (hay còn gọi là không gian Unita).

Từ định nghĩa ta thấy rằng với trường R thì tích vô hướng (cid:104)., .(cid:105) là một dạng

song tuyến tính xác định dương trên H. Khi đó H được gọi là không gian tiền

Hilbert thực.

Định lí 1.1.2. Cho H là không gian tiền Hilbert với x, y ∈ H ta luôn có bất

đẳng thức sau

|(cid:104)x, y(cid:105)|2 ≤ (cid:104)x, x(cid:105).(cid:104)y, y(cid:105).

Dấu "=" xảy ra khi và chỉ khi x, y phụ thuộc tuyến tính.

Định lí 1.1.3. Cho H là không gian tiền Hilbert. Khi đó (cid:107)x(cid:107) = (cid:104)x, x(cid:105), x ∈ H

xác định một chuẩn trên H.

1.1.2 Không gian Hilbert

Một không gian tiền Hilbert xem như không gian định chuẩn có thể đầy

đủ hoặc không đầy đủ.

Định nghĩa 1.1.4. Nếu H là một không gian tiền Hilbert và đầy đủ với chuẩn

cảm sinh từ tích vô hướng thì được gọi là không gian Hilbert.

Cũng tương tự như trường hợp không gian tiền Hilbert, với trường R thì

ta có không gian Hilbert thực.

1.1.3 Các ví dụ

n (cid:88)

i) Rn là không gian Hilbert thực với tích vô hướng

i=1

(cid:104)x, y(cid:105) = xiyi, trong đó x = (x1, x2, . . . , xn), y = (y1, y2, . . . , yn) ∈ Rn.

∞ (cid:88)

ii) Xét không gian (cid:40) (cid:41)

i=1

l2 = . x = (xn)n ⊂ K |xn|2 < +∞ (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)

∞ (cid:88)

Ta đã biết l2 là không gian Banach với chuẩn

i=1

(cid:107)x(cid:107) = (1.1) |xn|2. (cid:118) (cid:117) (cid:117) (cid:116)

∞ (cid:88)

Với x = (xn)n∈N, y = (yn)n∈N ∈ l2, từ bất đẳng thức

i=1

≤ (cid:107)x(cid:107)2.(cid:107)y(cid:107)2 < +∞, xnyn (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)

∞ (cid:80) i=1

dễ kiểm tra rằng (cid:104)x, y(cid:105) = xnyn xác định một tích vô hướng trong l2 và nó

cảm sinh (1.1). Vậy l2 là không gian Hilbert.

1.1.4 Một vài tính chất cơ bản

Định lí 1.1.5. Cho H là không gian Hilbert. Khi đó (cid:104)., .(cid:105) : H × H → R là một hàm liên tục.

Định lí 1.1.6. Với mọi x, y thuộc không gian tiền Hilbert H ta luôn có đẳng

thức hình bình hành sau đây:

(cid:107)x + y(cid:107)2 + (cid:107)x − y(cid:107)2 = 2((cid:107)x(cid:107)2 + (cid:107)y(cid:107)2). (1.2)

Hệ quả 1.1.7. Cho H là không gian tiền Hilbert và x, y, z ∈ H. Khi đó, ta có

đẳng thức Apollonius:

y + z x − 2 (cid:0)(cid:107)x − y(cid:107)2 + (cid:107)x − z(cid:107)2(cid:1) = 4 + (cid:107)y − z(cid:107)2. 2 (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)

Định lí 1.1.8. Giả sử (H, (cid:107).(cid:107)) là một không gian định chuẩn trên trường R, trong đó bất đẳng thức hình bình hành nghiệm đúng với mọi x, y ∈ H:

(cid:107)x + y(cid:107)2 + (cid:107)x − y(cid:107)2 = 2((cid:107)x(cid:107)2 + (cid:107)y(cid:107)2).

Khi đó, với trường R ta đặt

(cid:104)x, y(cid:105) = p(x, y) = 1 ((cid:107)x + y(cid:107)2 − (cid:107)x − y(cid:107)2), 4

thì (cid:104)., .(cid:105) là một tích vô hướng trên H và ta có

(cid:104)x, x(cid:105) = (cid:107)x(cid:107)2, ∀x ∈ H.

Định lí 1.1.9. Với mọi không gian tiền Hilbert H đều tồn tại không gian

Hilbert chứa H sao cho H là một không gian con trù mật trong H.

Định nghĩa 1.1.10. Cho D (cid:54)= ∅ và y là một véctơ bất kỳ, đặt

(cid:107)x − y(cid:107). dD(y) := inf x∈D

Ta nói dD(y) là khoảng cách từ y tới D. Nếu tồn tại π ∈ D sao cho dD(y) :=

(cid:107)y − π(cid:107) thì ta nói π là hình chiếu (khoảng cách) của y trên D và kí hiệu là

π := pD(y).

Định lí 1.1.11. Cho M là một tập lồi, đóng và khác rỗng trong không gian

Hilbert H. Khi đó, với mỗi x ∈ H tồn tại duy nhất phần tử y ∈ M sao cho

(cid:107)x − y(cid:107) = d(x, M ).

Định nghĩa 1.1.12. Hai phần tử x, y trong không gian Hilbert H được gọi là

trực giao với nhau nếu (cid:104)x, y(cid:105) = 0 và kí hiệu là x ⊥ y.

Định lí 1.1.13. Giả sử M là không gian con đóng của không gian Hilbert.

Khi đó, mỗi phần tử x ∈ H được biểu diễn một cách duy nhất dưới dạng

x = y + z trong đó y ∈ M và z ∈ M ⊥ được gọi là hình chiếu trực giao của

x lên M .

Định nghĩa 1.1.14. Ánh xạ p : H → M xác định bởi p(x) = y trong đó x ∈ H được biểu diễn duy nhất: x = y + z mà y ∈ M và z ∈ M ⊥ của Định

lí 1.1.13 được gọi là phép chiếu trực giao từ H lên M .

Định lí 1.1.15. Phép chiếu trực giao p của không gian Hilbert H lên không

gian đóng M (cid:54)= {0} là một toán tử tuyến tính liên tục và có (cid:107)p(cid:107) = 1.

Định nghĩa 1.1.16. Cho H là không gian Hilbert. Dãy {xn} ⊂ H được gọi

(cid:104)xn, y(cid:105) = là hội tụ yếu đến phần tử x trong H, nếu với mọi y ∈ H ta có lim n→∞

(cid:104)x, y(cid:105). Kí hiệu xn (cid:42) x.

Định lí 1.1.17. Giả sử H là không gian Hilbert.

i) Nếu dãy {xn} hội tụ yếu đến x ∈ H và dãy {yn} hội tụ mạnh đến y ∈ H

thì dãy số {(cid:104)xn, yn(cid:105)} hội tụ đến (cid:104)x, y(cid:105).

ii) Nếu dãy {xn} hội tụ yếu đến x ∈ H và dãy {(cid:107)xn(cid:107)} hội tụ đến (cid:107)x(cid:107) thì

dãy {xn} hội tụ mạnh đến x ∈ H.

1.2 Tập lồi và hàm lồi trong không gian Hilbert

1.2.1 Tập lồi

Định nghĩa 1.2.1. Cho hai điểm a, b ∈ H.

i) Một đường thẳng đi qua a, b là tập hợp có dạng:

{x ∈ H : x = αa + βb, α, β ∈ R, α + β = 1}.

ii) Đoạn thẳng nối hai điểm a, b trong H có dạng:

{x ∈ H : x = αa + βb, α ≥ 0, β ≥ 0, α + β = 1}.

Định nghĩa 1.2.2. Một tập D được gọi là tập affin nếu D chứa mọi đường

thẳng đi qua hai điểm bất kì x, y ∈ D, tức là

∀x, y ∈ D, ∀λ ∈ R ⇒ λx + (1 − λ)y ∈ D.

Mệnh đề 1.2.3. Tập D (cid:54)= ∅ là tập affin khi và chỉ khi nó có dạng D = M +a với M là không gian con của H và a ∈ H. Không gian M được xác định duy

nhất và được gọi là không gian con song song của D.

Định nghĩa 1.2.4. Thứ nguyên (hay chiều) của một tập affin D là thứ nguyên

của không gian con song song với D và được kí hiệu là dim D.

Định nghĩa 1.2.5. Siêu phẳng trong không gian H là một tập hợp các điểm

có dạng

{x ∈ H : aT x = α},

trong đó a ∈ H là một véctơ khác 0 và α ∈ R.

Định nghĩa 1.2.6. Cho a ∈ H là một véctơ khác 0 và α ∈ R. Tập

{x : aT x ≥ α}

được gọi là nửa không gian đóng và tập {x : aT x > a} gọi là nửa không gian

mở.

Định nghĩa 1.2.7. Một tập D được gọi là tập lồi nếu với mọi a, b ∈ D và mọi

α ∈ [0; 1], ta có

λa + (1 − λ)b ∈ D.

Ví dụ 1.2.8. Tập rỗng là tập lồi.

+ Toàn bộ không gian là tập lồi.

+ Các không gian con là tập lồi.

+ Các tam giác, hình tròn trong mặt phẳng là các tập lồi. + Quả cầu C = {x (cid:12) (cid:12) (cid:107)x(cid:107) ≤ 1} là tập lồi.

Định lí 1.2.9. Tập lồi đóng với phép giao, phép cộng và phép nhân với một

số thực tức là, nếu C và D là hai tập lồi trong H thì C ∩ D, αC + βD cũng

là các tập lồi.

k (cid:88)

Định nghĩa 1.2.10. Ta nói x là tổ hợp lồi của các điểm (véctơ) x1, . . . , xk nếu

j=1

x = λjxj, λj ≥ 0 (j = 1, . . . , k), λj = 1.

Mệnh đề 1.2.11. Tập hợp D là lồi khi và chỉ khi nó chứa mọi tổ hợp lồi của

k (cid:88)

các điểm của nó. Tức là, tập D lồi khi và chỉ khi

j=1

∀k ∈ N∗, ∀λ1, . . . , λk, λj = 1, ∀x1, . . . , xk ∈ D ⇒ λjxj ∈ D.

Mệnh đề 1.2.12. Nếu A, B, C là các tập lồi đóng trong H, thì các tập sau là

lồi

A ∩ B := {x ∈ H| x ∈ A, x ∈ B};

αA + βB := {x ∈ H| x = αa + βb, a ∈ A, b ∈ B, α, β ∈ R};

A × C := {x ∈ H × H| x = (a, c); a ∈ A, c ∈ C}.

Định nghĩa 1.2.13. Một tập được gọi là tập lồi đa diện nếu nó là giao của

một số hữu hạn các nửa không gian đóng.

Như vậy, theo định nghĩa tập lồi đa diện là tập hợp nghiệm của một hệ

hữu hạn các bất phương trình tuyến tính. Dạng tường minh của tập lồi đa diện

được cho như sau:

C := {x ∈ H| (cid:104)aj, x(cid:105) ≤ bj, j ∈ I, |I| < +∞}.

Mệnh đề 1.2.14. Giao của một họ bất kỳ các tập lồi là một tập lồi.

Aα là một tập lồi. Chứng minh. Giả sử {Aα}α∈I là họ các tập lồi. Ta cần chứng minh A = (cid:84) α∈I + Với mọi x1, x2 ∈ A ⇒ x1, x2 ∈ Aα (∀α ∈ I).

+ Với mọi α ∈ I. Do Aα lồi nên ∀λ ∈ [0; 1] ta có

λx1 + (1 − λ)x2 ∈ A.

α∈I

Theo định nghĩa A = (cid:84) Aα là một tập lồi.

Định nghĩa 1.2.15. Một tập C ⊂ H đượ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.2.16. Cho C ⊆ H, x0 ∈ C. Nón pháp tuyến (ngoài) của tập C tại x0 là tập hợp

NC(x0) := {w | (cid:104)w, x − x0(cid:105) ≤ 0 ∀x ∈ C}.

Định nghĩa 1.2.17. Cho D ⊆ H là một tập lồi và x0 ∈ D. Tập

D(x0) := {w ∈ H | (cid:104)w, x − x0(cid:105) ≤ ε ∀x ∈ D}

N ε

được gọi là nón pháp tuyến ε của D tại x0.

Hiển nhiên 0 ∈ ND(x0) và từ định nghĩa ta có ND(x0) là một nón lồi

đóng.

Định nghĩa 1.2.18. Cho hai tập C và D, ta nói rằng siêu phẳng

H := {x : (cid:104)v, x(cid:105) = λ}

i) tách hai tập C và D nếu (cid:104)v, a(cid:105) ≤ λ ≤ (cid:104)v, b(cid:105) ∀a ∈ C, b ∈ D.

ii) tách chặt C và D nếu (cid:104)v, a(cid:105) < λ < (cid:104)v, b(cid:105) ∀a ∈ C, b ∈ D.

(cid:104)v, y(cid:105). (cid:104)v, x(cid:105) < λ < inf y∈D iii) tách mạnh C và D nếu sup x∈C

Định lí 1.2.19 (Định lí tách 1). Cho C và D là hai tập lồi khác rỗng trong H sao cho C ∩ D = ∅. Khi đó, có một siêu phẳng tách C và D.

Định lí 1.2.20 (Định lí tách 2). Cho C và D là hai tập lồi đóng khác rỗng trong H cho C ∩ D = ∅. Giả sử có ít nhất một tập compact. Khi đó, hai tập

C và D có thể tách mạnh được bởi một siêu phẳng.

Áp dụng định lí tách cho H là Rn ta được hệ quả sau:

Định lí 1.2.21 (Bổ đề Farkas). Cho a ∈ Rn và A là ma trận thực cấp m × n. Khi đó (cid:104)a, x(cid:105) ≥ 0 với mọi x thỏa mãn Ax ≥ 0 khi và chỉ khi tồn tại y ≥ 0 và y ∈ Rm sao cho a = AT y.

Ý nghĩa hình học của Bổ để Farkas: Siêu phẳng đi qua gốc tọa độ

(cid:104)a, x(cid:105) = 0 để nón Ax ≥ 0, về một phía của nó khi và chỉ khi véctơ pháp

tuyến a của siêu phẳng nằm trong nón sinh bởi các hàng của ma trận A.

Định nghĩa 1.2.22. Cho tập lồi khác rỗng F ⊂ H. Ta nói véctơ d là một

phương lùi xa của F nếu

x + λd ∈ F, ∀x ∈ F, ∀λ > 0.

Tập hợp tất cả các phương lùi xa của F được gọi là nón lùi xa của F và kí hiệu là 0+F . Vậy

0+F = {d ∈ H| x + λd ∈ F, ∀x ∈ F, ∀λ > 0.}

1.2.2 Hàm lồi

Định nghĩa 1.2.23. Cho D là một tập lồi và f : H → R ∪ {+∞}. Hàm f

được gọi là

i) lồi trên D nếu

f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀x, y ∈ D, 0 ≤ λ ≤ 1;

ii) lồi chặt trên D nếu

f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y), ∀x, y ∈ D, 0 < λ < 1.

Hàm f lõm (lõm chặt) nếu −f là lồi (lồi chặt).

Định nghĩa 1.2.24. Ta gọi miền hữu hạn (effective domain) của hàm f là tập

được cho bởi

dom(f ) = {x ∈ X|f (x) < ∞} .

Định nghĩa 1.2.25. Hàm f được gọi là chính thường (proper) nếu dom(f ) (cid:54)= ∅ và f (x) > −∞, ∀x ∈ X.

Định nghĩa 1.2.26. Ta nói hàm f : Rn → (−∞, ∞] là bức trên tập ∆ ⊂ Rn f (xk) = ∞. Trong nếu với mỗi dãy {xk} ⊂ ∆ sao cho (cid:107)xk(cid:107) → ∞ thì lim k→∞ trường hợp ∆ = Rn, ta nói f là bức.

Ví dụ 1.2.27. 1) Hàm a-phin. f (x) := aT x + α, trong đó a ∈ H, α ∈ R. Dễ dàng kiểm tra được f là một hàm vừa lồi vừa lõm trên toàn không gian. Khi

α = 0 thì hàm này được gọi là hàm tuyến tính.

Cho C (cid:54)= ∅ là một tập lồi.

2) Hàm tựa. Hàm dưới đây được gọi là hàm tựa của C:

(cid:104)y, x(cid:105). sC(y) := sup x∈C

3) Hàm khoảng cách. Cho C lồi đóng, hàm khoảng cách đến tập C được

định nghĩa bởi

(cid:107)x − y(cid:107). dC(x) := min y∈C

4) Hàm chuẩn. Giả sử x = (x1, . . . , xn).

f (x) := (cid:107)x(cid:107)i := max |xi|

hoặc

1 + · · · + x2

n)1/2.

f (x) := (cid:107)x(cid:107) := (x2

5) Hàm chỉ.

0   nếu x ∈ C δC(x) =  +∞ nếu x /∈ C

Định lí 1.2.28. Cho f và g là hai hàm lồi trên tập C và D tương ứng. Khi đó,

các hàm số αf + βg với mọi α, β ≥ 0; max{f, g} cũng lồi trên C ∩ D.

Một hàm lồi có thể không liên tục tại một số điểm trên biên miền xác định

của nó, tuy nhiên nó liên tục tại mọi điểm trong của tập đó theo định lí sau:

Định lí 1.2.29. Một hàm lồi f : H → R liên tục tại mọi điểm.

Tính chất sau đây đặc trưng cho một hàm lồi khả vi và thuận lợi để kiểm tra tính lồi của một hàm số. Ta kí hiệu f (cid:48)(a) hoặc ∇f (a) là đạo hàm của f tại

Định lí 1.2.30. Cho f : H → R là một hàm khả vi trên tập lồi mở D. Điều kiện cần và đủ để f lồi trên D là

f (x) + (cid:104)∇f (x), y − x(cid:105) ≤ f (y), ∀x, y ∈ D.

Nếu f khả vi hai lần thì điều kiện cần và đủ để f lồi trên D là với mọi

x ∈ D, ma trận Hessian H(x) của f tại x xác định không âm, tức là

yT H(x)y ≥ 0, ∀x ∈ D, y ∈ Rn.

Như vậy, hàm f (x) = xT Qx (Q là ma trận đối xứng) là hàm lồi khi và

chỉ khi Q xác định không âm. Hàm này là lồi chặt khi và chỉ khi ma trận của

nó xác định dương.

Tính khả vi của hàm lồi giữ vai trò quan trọng trong các phương pháp tối

ưu hóa. Lớp các hàm lồi có những tính chất khả vi rất đẹp mà các lớp khác không có. Giả sử f : H → R ∪ {+∞} là hàm lồi. Ta có các khái niệm sau:

Định nghĩa 1.2.31. Cho hàm f : H → R được gọi là nửa liên tục dưới đối với E tại một điểm x, nếu với mọi dãy {xk} ⊂ E, xk → x ta có lim inf f (xk) ≥

f (x). Hàm f được gọi là nửa liên tục trên, đối với E tại x nếu −f nửa liên

tục dưới, đối với E tại x.

Hàm f được gọi là liên tục đối với E tại x nếu nó vừa nửa liên tục trên và

nửa liên tục dưới đối với E tại x.

Hàm f được gọi là nửa liên tục dưới, đối với E trong A, nếu nó liên tục

dưới đối với E, tại mọi điểm thuộc A. Tương tự, ta cũng nói như vậy đối với

hàm nửa liên tục trên và hàm liên tục. Khi f liên tục (nửa liên tục) tại một

điểm x, đối với toàn không gian, thì ta nói đơn giản f liên tục (nửa liên tục)

tại x.

Định nghĩa 1.2.32. Cho ε > 0. Một véctơ w ∈ H được gọi là một ε− dưới gradient của f tại x0 ∈ H nếu

(cid:104)w, x − x0(cid:105) ≤ f (x) − f (x0) + ε ∀x ∈ H.

Tập tất cả các ε− dưới gradient gọi là ε− dưới vi phân của hàm f tại x0, được

kí hiệu là

∂εf (x0) := (cid:8)w ∈ H : (cid:104)w, x − x0(cid:105) ≤ f (x) − f (x0) + ε, ∀x ∈ H(cid:9) .

Nhận xét: Khi ε = 0 thì w được gọi là dưới gradient của f tại x ∈ H.

Tập tất cả các gradient của f tại x0, được kí hiệu là ∂f (x0)

Hàm f được gọi là khả dưới vi phân tại x0 nếu ∂f (x0) (cid:54)= ∅.

Ví dụ 1.2.33. Cho D là một tập lồi, khác rỗng của không gian H. Xét hàm

chỉ trên tập D

0   nếu x ∈ D δD(x) =  +∞ nếu x /∈ D.

Với mọi x0 ∈ D ta có w ∈ ∂δD(x0), suy ra

δD(x) − δD(x0) ≥ (cid:104)w, x − x0(cid:105), ∀x ∈ D.

Do đó (cid:104)w, x − x0(cid:105) ≤ 0, ∀x ∈ D, suy ra w ∈ ND(x). Điều này chứng tỏ ∂δD(x0) = ND(x0), ∀x0 ∈ D.

Cũng có trường hợp tồn tại những điểm x∗ tại đó f không có dưới vi phân, nghĩa là tập ∂f (x∗) có thể là tập rỗng. Tuy nhiên đối với hàm lồi ta có định lí

sau.

Định lí 1.2.34. Cho f là hàm lồi hữu hạn trên H. Lúc đó f có dưới vi phân

tại mọi điểm thuộc H.

Định nghĩa 1.2.35. Ta gọi đạo hàm theo hướng d của một hàm số f (không

nhất thiết là lồi) tại điểm x là đại lượng

f (x + λd) − f (x) , f (cid:48)(x, d) := lim λ→0+ λ

nếu giới hạn này tồn tại.

Định lí 1.2.36. Nếu f là một hàm lồi trên tập lồi D thì với mọi x ∈ D và

mọi d sao cho x + d ∈ D, đạo hàm theo hướng d của f tại x luôn tồn tại và

nghiệm đúng

f (cid:48)(x, d) ≤ f (x + d) − f (x).

Ngoài ra, với mỗi điểm x cố định thì f (cid:48)(x, .) là một hàm lồi trên tập lồi

{d : x + d ∈ D}.

Định nghĩa 1.2.37. Cho D ⊆ Rn là tập lồi, f : D → R là hàm lồi và ε ≥ 0.

Xét bài toán

f (x). (P (cid:48)) min x∈D

Mỗi điểm x ∈ D được gọi là ε− nghiệm của bài toán (P (cid:48)) nếu

f (x) + ε. f (x) ≤ min x∈D

Mệnh đề 1.2.38. Véctơ x ∈ D là ε− nghiệm của bài toán (P (cid:48)) khi và chỉ khi

0 ∈ ∂εf (x).

Chứng minh. Giả sử x ∈ D là ε− nghiệm của bài toán (P (cid:48)). Khi đó

f (x) ≤ f (x) + ε, ∀x ∈ D.

Suy ra

(cid:104)0; x − x(cid:105) ≤ f (x) − f (x) + ε, ∀x ∈ D ⇔ 0 ∈ ∂ε(f (x)).

Ngược lại, nếu 0 ∈ ∂εf (x) thì ta có

(cid:104)0; x − x(cid:105) ≤ f (x) − f (x) + ε, ∀x ∈ D.

Chứng tỏ x là ε− nghiệm của bài toán (P (cid:48)) .

Mệnh đề 1.2.39. Cho D là tập lồi đóng khác rỗng. Khi đó px là ε− chiếu

của x trên D khi và chỉ khi

(1.3) (cid:104)x − px, px − y(cid:105) ≥ −ε, ∀y ∈ D.

Chứng minh. Giả sử px là ε− chiếu của x trên D. Ta có bài toán

1     , (1.4) min y∈D 1 (cid:107)x − y(cid:107)2 hay min 2 (cid:107)x − y(cid:107) + δD(y) 2  

trong đó δD(y) là hàm chỉ của y trên tập D. Đặt

f (y) := 1 (cid:107)x − y(cid:107)2, x ∈ Rn. 2

Theo Định nghĩa 1.2.32, px là ε− nghiệm của bài toán (1.4). Từ Mệnh đề

1.2.38 ta được

(1.5) 0 ∈ ∂ε[f (px) + δD(px)] = ∂εf (px) + ∂εδD(px).

D(px) nên từ (1.5) ta được

Theo Ví dụ 1.2.33 ta có ∂εδD(px) = N ε

D(px).

0 ∈ {−x + px} + N ε

Suy ra

D(px) ⇔ (cid:104)x − px, ω − px(cid:105) ≤ ε, ∀ω ∈ D.

(x − px) ∈ N ε

Ngược lại, giả sử có (1.3). Ta có

(cid:107)x − y(cid:107)2 = (cid:107)x − px(cid:107)2 + 2(cid:104)x − px, px − y(cid:105) + (cid:107)px − y(cid:107)2

≥ (cid:107)x − px(cid:107)2 − 2(cid:104)x − px, y − px(cid:105).

Suy ra

(cid:107)x − y(cid:107)2 ≥ (cid:107)x − px(cid:107)2 − 2ε.

Chứng tỏ px là ε− chiếu của x trên D.

Nhận xét: Khi ε = 0, ta nói là hình chiếu chính xác.

1.3 Hàm toàn phương

Trong phần này ta xét H là không gian Hilbert thực.

Định nghĩa 1.3.1. Hàm toàn phương (hay còn gọi là hàm bậc hai) là hàm có

dạng

1 f (x) = (cid:104)x, T x(cid:105) + (cid:104)c, x(cid:105) + α, 2

với T là toán tử tuyến tính, tự liên hợp trong không gian Hilbert H và c ∈ H, α ∈ R.

Định nghĩa 1.3.2. (i) Toán tử tuyến tính, tự liên hợp T được gọi là xác định

dương nếu (cid:104)x, T x(cid:105) > 0, ∀x ∈ H\{0}. Nếu (cid:104)x, T x(cid:105) ≥ 0, ∀x ∈ H thì T được

gọi là nửa xác định dương.

(ii) Toán tử tuyến tính, tự liên hợp T được gọi là xác định âm (nửa xác

định âm) nếu −T là xác định dương (nửa xác định dương).

 1 −1 Ví dụ 1.3.3. Xét A =   và xT = (x1, x2) ∈ R2. Với mọi ∀xT ∈  −1 1

R2\{0}, ta có

    1 −1 x1 (cid:104)x, Ax(cid:105) = xT Ax = (x1, x2)     −1 1 x2

  x1 − x2 = (x1, x2)   −x1 + x2

= x2

1 − x1x2 − x1x2 + x2 2 1 − 2x1x2 + x2

2 ≥ 0.

= x2

Suy ra A là ma trận nửa xác định dương.

1 (cid:104)x, Dx(cid:105) + (cid:104)C, x(cid:105) + α với D ∈ Rn×n 2

, C ∈ Mệnh đề 1.3.4. Cho f (x) = Rn, α ∈ R. Nếu D là ma trận nửa xác định dương thì f (x) là hàm toàn

phương lồi.

Chứng minh. Ta có hàm x (cid:55)→ (cid:104)C, x(cid:105) + α là hàm lồi. Thật vậy, với mọi t ∈ [0; 1], x ∈ Rn

(cid:104)C, tx + (1 − t)y(cid:105) + α = t(cid:104)C, x(cid:105) + (1 − t)(cid:104)C, y(cid:105) + α

= tf (x) + (1 − t)f (y).

Tổng của hai hàm lồi là hàm lồi nên để chứng minh mệnh đề trên ta đi chứng

minh f (x) = (cid:104)x, Dx(cid:105) là hàm lồi khi D nửa xác định dương.

Thật vậy, do D là ma trận nửa xác định dương nên với mọi u, v ∈ Rn ta

có

0 ≤ (cid:104)u − v, D(u − v)(cid:105) = (cid:104)u, Du(cid:105) − 2(cid:104)v, Du(cid:105) + (cid:104)v, Dv(cid:105).

Suy ra

(cid:104)v, Dv(cid:105) ≤ (cid:104)u, Du(cid:105) − 2(cid:104)v, D(u − v)(cid:105). (1.6)

Cho x, y ∈ Rn, ∀t ∈ [0; 1]. Đặt z = tx + (1 − t)y. Trong (1.6) thay v bởi z

ta có

(cid:104)z, Dz(cid:105) ≤ (cid:104)y, Dy(cid:105) − 2(cid:104)z, D(y − z)(cid:105);

(cid:104)z, Dz(cid:105) ≤ (cid:104)x, Dx(cid:105) − 2(cid:104)z, D(x − z)(cid:105).

Vì z = tx + (1 − t)y nên y − t = t(y − x), x − t = −(1 − t)(y − x). Suy ra

(cid:104)z, Dz(cid:105) ≤ (cid:104)y, Dy(cid:105) − 2t(cid:104)z, D(y − x)(cid:105);

(cid:104)z, Dz(cid:105) ≤ (cid:104)x, Dx(cid:105) − 2(1 − t)(cid:104)z, D(y − x)(cid:105).

Vì t ∈ (0; 1) nên 1 − t > 0; t > 0. Suy ra

t(cid:104)z, Dz(cid:105) + (1 − t)(cid:104)z, Dz(cid:105) ≤ (1 − t)(cid:104)y, Dy(cid:105) + t(cid:104)x, Dx(cid:105)

hay

(cid:104)z, Dz(cid:105) ≤ t(cid:104)x, Dx(cid:105) + (1 − t)(cid:104)y, Dy(cid:105)

hay

f1(tx + (1 − t)y) ≤ tf1(x) + (1 − t)f1(y).

Suy ra f1(x) = (cid:104)x, Dx(cid:105) là hàm lồi. Do vậy f (x) = (cid:104)x, Dx(cid:105) + (cid:104)C, x(cid:105) + α là

hàm toàn phương lồi.

Nhận xét: Nếu D nửa xác định âm thì f là hàm lõm, tức là ∀x, y ∈ Rn, t ∈ (0; 1) thì

f (tx + (1 − t)y) ≥ tf (x) + (1 − t)f (y).

Ví dụ 1.3.5. Cho hàm toàn phương

1 − 4x1x2 + 4x2

2) + 4x1 − 3x2 − 9.

1 f (x) = (3x2 2

   3; −2 Ta có D =   , C =  , α = −9. Do ma trận D là xác định −2; 4  4  3

dương (dùng quy tắc Jacobi) nên f là hàm lồi ngặt trên R2.

Mệnh đề 1.3.6 (Định lí Weierstrass). Xét hàm lồi chính thường đóng f : Rn → (−∞, +∞] và giả sử một trong ba điều kiện sau đây thỏa mãn

(i) dom(f ) là bị chặn;

(ii) tồn tại số thực γ sao cho tập mức {x| f (x) ≤ γ} khác rỗng và bị

chặn;

(iii) f là hàm bức.

Khi đó, tập cực tiểu Sol(P ) của f trên Rn khác rỗng và compact.

f (x). f (x) = inf x∈Rn Chứng minh. • Giả sử điều kiện (i) đúng. Vì f là hàm chính thường đóng nên dom(f ) (cid:54)= ∅. Xét dãy {xk} ⊂ dom(f ) sao cho lim k→∞

Vì dom(f ) bị chặn nên dãy có ít nhất một điểm giới hạn yếu x∗. Vì f

f (x) = lồi, đóng nên f là nửa liên tục dưới yếu tại x∗. Do vậy f (x∗) ≤ lim k→∞

inf x∈Rn

f (x), suy ra x∗ là điểm cực tiểu của f (x). Như vậy Sol(P ) (cid:54)= ∅; vì Sol(P ) ⊂ dom(f ) và dom(f ) bị chặn nên

suy ra Sol(P ) bị chặn. Tuy nhiên Sol(P ) là giao của tất cả các tập mức

f (x). Vì f đóng nên các tập mức là {x| f (x) ≤ γ} trong đó γ > inf x∈Rn

đóng, bởi vậy Sol(P ) là đóng, suy ra Sol(P ) compact yếu.

f (x) • Giả sử điều kiện (ii) đúng, ta chỉ việc thay f bởi hàm   khi f (x) ≤ γ (cid:101)f (x) = ∞  khi f (x) > γ

Miền xác định của (cid:101)f là tập mức {x| f (x) ≤ γ}. Nó bị chặn bởi giả thiết và

đóng vì f đóng.

Tập cực tiểu của (cid:101)f bằng tập cực tiểu của f . Áp dụng điều kiện (i) suy ra

điều phải chứng minh.

• Giả sử điều kiện (iii) đúng. Vì f chính thường nên sẽ có một tập mức

khác tập rỗng. Vì f là bức nên tập mức khác rỗng, bị chặn hay {x| f (x) ≤ γ} (cid:54)= ∅ và bị chặn, suy ra (ii) đóng, suy ra điều phải chứng minh.

Chương 2

Bài toán quy hoạch toàn phương

Trong chương này luận văn trình bày một vài kết quả về sự tồn tại nghiệm

của bài toán quy hoạch toàn phương với ràng buộc tuyến tính trong không

gian Hilbert thực hữu hạn chiều và bài toán quy hoạch toàn phương lồi với

hữu hạn ràng buộc toàn phương lồi trong không gian Hilbert thực. Nội dung

trong chương này được trích dẫn chủ yếu từ các tài liệu tham khảo [5], [6] và

[7].

2.1 Giới thiệu bài toán

2.1.1 Phát biểu bài toán

Ta xét bài toán quy hoạch toàn phương với ràng buộc tuyến tính trong Rn:

Định nghĩa 2.1.1. Bài toán

    min f (x) = 1 (cid:104)x, Dx(cid:105) + (cid:104)c, x(cid:105) + α 2 (2.1)  

   x ∈ Rn, Ax ≥ b

, A ∈ Rm×n, c ∈ Rn, b ∈ Rm, α ∈ R được gọi là bài toán

trong đó D ∈ Rn×n quy hoạch toàn phương với ràng buộc tuyến tính trong Rn.

Nếu D là ma trận 0 và α = 0 thì f là hàm tuyến tính. Do đó, lớp các bài

toán quy hoạch tuyến tính là lớp con của các bài toán quy hoạch toàn phương

với ràng buộc tuyến tính.

Nếu hàm mục tiêu f là hàm lồi thì bài toán (2.1) được gọi là bài toán quy

hoạch toàn phương lồi. Nếu f không lồi thì (2.1) là bài toán quy hoạch toàn

phương không lồi.

Nếu ta bỏ hằng số α trong công thức của hàm mục tiêu f thì không làm

thay đổi tập nghiệm của bài toán quy hoạch toàn phương ban đầu. Do đó, ta

chỉ cần xét bài toán

1     min f (x) = (cid:104)x, Dx(cid:105) + (cid:104)c, x(cid:105) 2 (P ) :  

   x ∈ Rn, Ax ≥ b

trong đó D ∈ Rn×n , A ∈ Rm×n, c ∈ Rn, b ∈ Rm.

Trong không gian Hilbert thực H nói chung ta xét bài toán quy hoạch toàn

phương lồi sau:

Định nghĩa 2.1.2.

 1     min f (x) = (cid:104)x, T x(cid:105) + (cid:104)c, x(cid:105) 2   (CQP ) :

x ∈ H, gi(x) =   1 (cid:104)x, Tix(cid:105) + (cid:104)ci, x(cid:105) + αi ≤ 0, i = 1, 2, . . . , m 2

trong đó T, Ti : H → H là toán tử tuyến tính tự liên hợp, nửa xác định dương và c, ci ∈ H, αi ∈ R, i = 1, 2, . . . , m.

Nhận xét: Nếu với mọi i = 1, 2, . . . , m mà Ti là các toán tử không thì bài

toán (CQP ) là bài toán quy hoạch toàn phương lồi trên tập ràng buộc tuyến

tính (QP L) .

Nếu T, Ti là toán tử không với mọi i = 1, 2, . . . , m thì bài toán (CQP )

trở thành bài toán quy hoạch tuyến tính và những lớp con của những lớp bài

toán quy hoạch tuyến tính lồi và ràng buộc là có dạng toàn phương lồi.

2(cid:104)x, Tix(cid:105) + αi ≤ 0, ∀i = 1, 2, . . . , m} là tập ràng

F = {x ∈ H| gi(x) = 1

buộc của bài toán (CQP ), F là lồi đóng và bị chặn dưới.

2.2 Các định lí về sự tồn tại nghiệm

2.2.1 Bài toán quy hoạch toàn phương với ràng buộc tuyến tính

Định lí 2.2.1 (Định lí Frank - Wolfe). Nếu θ = inf{f (x) : x ∈ ∆} là một số thực hữu hạn thì bài toán (P ) có nghiệm, trong đó ∆ = {x ∈ Rn : Ax ≥

b} = ∆(A, b).

Chứng minh. Dùng tính chất compact của mặt cầu đơn vị. Giả sử θ ∈ R. Ta cần chứng minh bài toán (P ) có nghiệm. Do θ ∈ R nên ∆ (cid:54)= ∅. Lấy x0 ∈ ∆, với ρ > 0 tùy ý. Đặt ∆ρ = ∆ ∩ B(x0, ρ). Suy ra ∆ρ là

tập lồi, khác rỗng và compact.

Xét bài toán

(2.2) min{f (x) : x ∈ ∆ρ}

Theo định lí Weierstrass, tồn tại y ∈ ∆ρ sao cho

f (y) = qρ := min{f (x) : x ∈ ∆ρ}.

Vì tập nghiệm của (2.2) là khác rỗng và compact nên tồn tại yρ ∈ ∆ρ sao cho

(cid:107)y − x0(cid:107) = min{(cid:107)y − x0(cid:107) : y ∈ ∆ρ, f (y) = qρ}.

Khi đó, tồn tại (cid:98)ρ > 0 sao cho

(2.3) (cid:107)yρ − x0(cid:107) < ρ, ∀ρ ≥ (cid:98)ρ.

Thật vậy, giả sử trái lại ta tìm được dãy tăng {ρk} và ρk → +∞ sao cho với mỗi k tồn tại yρk ∈ ∆ρk sao cho f (yρk) = qρk; (cid:107)yρk − x0(cid:107) = ρk.

Để đơn giản cho kí hiệu ta viết yk thay cho yρk. Vì yk ∈ ∆ nên Aiyk ≥

bi, ∀i = 1, 2, . . . , m.

k(cid:48)→+∞

A1yk(cid:48)

Với i = 1 ta có dãy {A1yk} bị chặn dưới nên tồn tại dãy {k(cid:48)} ⊂ {k} sao A1yk(cid:48) = +∞). Không mất tính tổng A1yk tồn tại.

cho lim tồn tại (có thể lim k(cid:48)→+∞ quát ta giả sử {k(cid:48)} ≡ {k}, khi đó lim k→∞ Tương tự, với i = 2 ta cũng có lim k→∞

A2yk tồn tại. Tiếp tục quá trình trên Amyk tồn tại. Khi đó, với mỗi i ∈ {1, 2, . . . , m} ta luôn với i = m ta có lim k→∞

Aiyk đều tồn tại.

Aiyk = bi}, I1 = I\I0 = {i ∈ có lim k→∞ Đặt I = {1, 2, . . . , m}, I0 = {i ∈ I : lim k→∞

I : Aiyk > bi}.

Aiyk ≥ bi + ε, ∀i ∈ I1. Mặt khác lim k→∞ Khi đó, tồn tại ε > 0 sao cho lim k→∞

yk − x0 (cid:107) = 1, ∀k. (cid:107)yk − x0(cid:107) = ρk, suy ra (cid:107) ρk

Vì mặt cầu đơn vị trong Rn là compact nên không mất tính tổng quát ta

yk − x0     có thể giả sử dãy hội tụ về v ∈ Rn khi k → ∞ và (cid:107)v(cid:107) = 1. Vì ρk 

 ρk → +∞ nên với mỗi i ∈ I0 ta có

 

  0 = lim k→∞ (Aiyk − bi) = lim k→∞ Aiyk − bi ρk

   

  Ai = lim k→∞  + lim k→∞ yk − x0 ρk Aix0 − bi ρk

= Aiv.

Tương tự, với mỗi i ∈ I1 ta có

   

inf inf +    0 ≤ lim k→∞  = lim k→∞ Aiyk − bi ρk Aiyk − Aix0 ρk Aix0 − bi ρk

   

 Ai  = Aiv.  + lim k→∞ = lim k→∞ yk − x0 ρk Aix0 − bi ρk

Khi đó Aiv = 0, ∀i ∈ I0 và Aiv ≥, ∀i ∈ I1. Suy ra v là phương lùi xa của tập

lồi đa diện ∆. Do đó

y + tv ∈ ∆ ∀t ≥ 0 và y ∈ ∆ (2.4)

V f (yk) = f (yρk) = qρk = min{f (x) : x ∈ ∆ρk}

= min{f (x) : x ∈ ∆ ∩ B(x0, ρk)}.

Vì dãy ρk là dãy tăng ρk → +∞ nên ta có {f (yk)} là dãy giảm và f (yk) → θ với k đủ lớn. Ta có θ − 1 ≥ f (yk) ≥ θ + 1. Sử dụng công thức của hàm f ta

có thể viết dưới dạng

1 θ − 1 ≤ (cid:104)yk − x0, D(yk − x0)(cid:105) + (cid:104)C, yk − x0(cid:105) + (cid:104)x,D(yk − x0)(cid:105) 2

+ 1 (cid:104)x0, Dx0(cid:105) + (cid:104)C, x0(cid:105) < θ + 1. 2

k và cho k → +∞ ta được

Chia các vế của bất đẳng thức trên cho ρ2

0 ≤ 1 (cid:104)v, Dv(cid:105) ≤ 0 ⇒ (cid:104)v, Dv(cid:105) = 0. 2

Từ (2.4) suy ra y + tv ∈ ∆, ∀t ≥ 0 và k ∈ N. Kết hợp với điều kiện

(cid:104)v, Dv(cid:105) = 0 ta có

f (yk + tv) = 1 (cid:104)yk + tv, D(yk + tv)(cid:105) + (cid:104)c, yk + tv(cid:105) 2

= 1 (cid:104)yk, Dyk(cid:105) + (cid:104)c, yk(cid:105) + t(cid:104)yk, Dv(cid:105) + (cid:104)c, v(cid:105). 2

Suy ra

(cid:104)yk, Dv(cid:105) + (cid:104)c, v(cid:105) ≥ 0, ∀k ∈ N. (2.5)

Giả sử ngược lại (cid:104)yk, Dv(cid:105)+(cid:104)c, v(cid:105) < 0 với k ∈ N nào đó thì f (yk+tv) → −∞ khi t → +∞. Điều này trái với giả thiết θ ∈ R. Do đó có (2.5).

yk − x0 Mặt khác (cid:104)v, v(cid:105) = 1 và → v nên ∃k1 ∈ N sao cho ρk

(cid:43)

, v > 0, ∀k > k1. (cid:42)yk − x0 ρk

Cố định k ≥ k1 ta có (cid:104)yk − x0, v(cid:105) > 0. Suy ra

(cid:107)yk − x0 − tv(cid:107)2 = (cid:107)yk − x0(cid:107)2 − 2t(cid:104)yk − x0, v(cid:105) + t2(cid:107)v(cid:107)2 ≤ (cid:107)yk − x0(cid:107)2. (2.6)

Với t > 0 đủ nhỏ. Ta lại có Ai(yk − tv) = Aiyk ≥ bi, ∀i ∈ I0 (do với i ∈ Ik ta có Aiv = 0). Mặt khác lim Aiyk ≥ bi + ε, ∀i ∈ I1 nên ∃k2 ∈ N, k2 ≥ k1

sao cho

ε Aiyk ≥ bi , ∀k ≥ k2, i ∈ I1. 2

ε Cố định chỉ số k ≥ k2 và chọn δk > 0 sao cho tAiv ≤ , ∀i ∈ I1, t ∈ (0, δk). 2

Khi đó

ε Ai(yk − tv) ≥ bi + − tAiv ≥ bi, ∀i ∈ I1, t ∈∈ (0, δk). 2

Suy ra yk − tv ∈ ∆, ∀t ∈ (0, δk). Kết hợp với (2.6) ta có yk − tv ∈ ∆ và

(cid:107)(yk − tv) − x0(cid:107) = (cid:107)yk − x0 − tv(cid:107) ≤ (cid:107)yk − x0(cid:107) = ρk

với mọi t ∈ (0, δk) đủ nhỏ. Từ (2.5) ta có

1 f (yk − tv) = (cid:104)yk, Dyk(cid:105) + (cid:104)c, yk(cid:105) + (cid:104)yk, Dv + (cid:104)c, v(cid:105)(cid:105)

2 = f (yk) − t(cid:104)yk, Dv + (cid:104)c, v(cid:105)(cid:105)

≤ f (yk).

Do đó yk − tv là nghiệm của bài toán min{f (x) : x ∈ ∆ρk}. Từ bất đẳng thức (cid:107)(yk − tv) − x0(cid:107) < (cid:107)yk − x0(cid:107) suy ra yk không phải là nghiệm của bài toán trên với khoảng cách tới x0 là nhỏ nhất. Điều này trái với giả thiết

(cid:107)yk − x0(cid:107) = min{(cid:107)y − x0(cid:107) : ∈ ∆ρk, f (y) = qρk}.

Vậy ta chứng minh được tồn tại (cid:98)ρ > 0 sao cho (2.3) được thỏa mãn. Tiếp tục, quá trình chứng minh ta chỉ ra tồn tại ρ > (cid:98)ρ sao cho

(2.7) qρ = θ.

Vì qρ = min{f (x) : ρx ∈ ∆ρ} nên kết quả (2.7) suy ra định lí được chứng

minh.

Ta chứng minh khẳng định (2.7) bằng phản chứng. Giả sử ngược lại

(2.8) qρ (cid:54)= θ, ∀ρ > (cid:98)ρ.

ρ với mọi ρ(cid:48) ≥ ρ và qρ → θ khi ρ → +∞. Từ (2.8) suy ra tồn tại ρi ∈ ((cid:98)ρ, +∞), (i = 1, 2) sao cho ρ1 < ρ2 và

Chú ý rằng qρ ≥ ρ(cid:48)

qρ1 > qρ2. Vì ρ2 > ρ1 nên kết quả (2.3) ta có (cid:107)yρ2 − x0(cid:107) < ρ2.

Ta có qρ1 > qρ2 nên ρ1 < (cid:107)yρ2(cid:107). Thật vậy nếu ρ1 ≥ (cid:107)yρ2 − x0(cid:107) thì yρ2 ∈ ∆ρ2 và f (yρ2) = qρ2 < qρ1 = f (yρ1). Điều này mâu thuẫn với cách chọn qρ1. Đặt ρ3 = (cid:107)yρ2 − x0(cid:107) ta có ρ1 < ρ3 < ρ2. Vì ρ3 < (cid:98)ρ và ρ2 > (cid:98)ρ nên từ khẳng định (2.3) ta có

(2.9) (cid:107)yρ3 − x0(cid:107) < ρ3 = (cid:107)yρ2 − x0(cid:107) < ρ2.

Vì ρ2 > ρ3 nên qρ3 = f (yρ3) ≥ f (yρ2) = qρ2.

Nếu f (yρ3) = f (yρ2) thì từ (2.9) suy ra yρ3 là véctơ chấp nhận được của

bài toán

(2.10) min{f (x) : x ∈ ∆ρ2}.

Với hàm mục tiêu có giá trị tối ưu qρ2 = f (yρ2) mà f (yρ3) = f (yρ2) nên yρ3

cũng là nghiệm của bài toán (2.10).

Mặt khác (cid:107)yρ3 − x0(cid:107) < (cid:107)yρ2 − x0(cid:107). Suy ra yρ2 không phải là nghiệm của bài toán (2.10) với khoảng cách tới x0 đủ nhỏ. Điều này trái với sự tồn tại yρ2. Do đó f (yρ3) > f (yρ2). Ta lại có (cid:107)yρ2 − x0(cid:107) = ρ3 nên yρ3 là điểm chấp nhận được của bài toán min{f (x) : x ∈ ∆ρ3}. Từ bất đẳng thức f (yρ3) > f (yρ2)

dẫn đến mâu thuẫn với điều kiện yρ3 là nghiệm tối ưu của bài toán. Suy ra

khẳng định (2.7) được chứng minh. Vậy bài toán (P) có nghiệm.

Nhận xét: Định lý Frank - Wolfe còn được phát biểu như sau: Nếu hàm toàn

phương f bị chặn dưới trên tập lồi đa diện khác rỗng thì f đạt giá trị nhỏ nhất

trên tập đó.

Ví dụ 2.2.2. Xét bài toán quy hoạch toàn phương hai biến

1 − 4x1x2 + 5x2

2; x1 − 2x2 ≥ 1, x2 ≥ 0}.

min{f (x) = 3x2

Trong bài toán này ta có

1 − 4x1x2 + 5x2

2 = 2x2

1 + (x1 − 2x2)2 + x2

2 ≥ 0

f (x) = 3x2

với mọi x ∈ R2 và ∆ = {xT = (x1, x2) ∈ R2 sao cho x1 − 2x2 ≥ 1, x2 ≥ 0}

là tập lồi đa diện, khác rỗng. Theo định lí Frank - Wolfe bài toán đã cho có nghiệm. Có thể thấy nghiệm cực tiểu của bài toán là x∗ = (1, 0) với fmin = f (x∗) = 3.

Ví dụ 2.2.3. Xét bài toán quy hoạch toàn phương hai biến

1 +16x1x2 +30x2

2)−2x2 −6; x1 +5x2 ≥ 3, x1 +3x2 ≥ 4}.

min{f (x) = (2x2 1 2

Bài toán này ta có

1 + 8x1x2 + 15x2

2 − 2x2 − 6

f (x) = x2

1 + 8x1x2 + 16x2

2 − x2

2 − 2x2 − 1

= x2

= (x1 + 4x2)2 − (x2 + 1)2 − 5

≥ (3 + 1)(4 − 1) − 5 = 7; ∀(x1, x2)T ∈ ∆.

Ta có f bị chặn dưới trên miền ràng buộc

∆ = {xT = (x1, x2) ∈ R2 : x1 + 5x2 ≥ 3, x1 + 3x2 ≥ 4}.

Ta có (1; 1)T ∈ ∆, suy ra ∆ (cid:54)= ∅. Theo định lí Frank - Wolfe bài toán có  11 ; − nghiệm. Rõ ràng x∗ = là nghiệm và fmin = f (x∗) = 7.  2  1  2

Ví dụ 2.2.4. Xét bài toán

min{f (x) = 2x2 + 1; x1x2 − x2 ≥ 1, x2 ≥ 0, x1 ≥ 1},

trong đó f (x) = 2x2 + 1 là hàm toàn phương.

Tập ràng buộc

∆ = {xT = (x1, x2) ∈ R2 : (x1 − 1)x2 ≥ 1, x1 ≥ 1, x2 ≥ 0}

không phải là tập lồi đa diện.

Ta có f (x) = 2x2 + 1 ≥ 1, ∀(x1, x2) ∈ ∆, suy ra f (x) bị chặn dưới trên

tập ∆ (cid:54)= ∅.  2 1 = Lấy {xk} =   ∈ ∆, k ∈ N, f (xk) = 1 + k, + 1, suy ra lim k→+∞ k k

  2 + 1  = 1, suy ra θ = inf{f (x) : x ∈ ∆} = 1.  lim k→+∞ k

Mặt khác f (x) = 2x2 + 1 = 1 khi và chỉ khi x2 = 0 mà (x1, 0) /∈ ∆. Vậy

bài toán vô nghiệm.

x + 1   Ví dụ 2.2.5. Xét bài toán   . f (x) = : x ∈ R, x ≥ 3 min x − 2  

Ta có f không là hàm toàn phương. Miền ràng buộc ∆ = {x ∈ R : x ≥ 3} là tập lồi đa diện và ∆ (cid:54)= ∅.

x + 1     : x ∈ R, x ≥ 3 = 1, f (x) = Ta có θ = inf f (x) = 1 . lim x→+∞ x − 2  

Rõ ràng bài toán min{f (x)| x ∈ ∆} trong trường hợp này không có nghiệm.

Qua Ví dụ 2.2.4 và Ví dụ 2.2.5 ta thấy rằng định lí Frank - Wolfe nếu

thiếu hai giả thiết đó là hàm toàn phương và miền ràng buộc là tập lồi đa diện

thì định lí không còn đúng nữa.

Định lí 2.2.6 (Định lí Eaves). Bài toán (P) có nghiệm khi và chỉ khi ba điều

kiện sau được thỏa mãn:

(i) ∆ (cid:54)= ∅; (ii) Nếu v ∈ Rn và Av ≥ 0 thì (cid:104)v, Dv(cid:105) ≥ 0; (iii) Nếu v ∈ Rn sao cho Av ≥ 0, (cid:104)v, Dv(cid:105) = 0 và Ax ≥ b thì (cid:104)Dx +

c, v(cid:105) ≥ 0.

Chứng minh. Giả sử bài toán (P ) có nghiệm x, ta cần chứng minh điều kiện

(i), (ii), (iii) thỏa mãn. Thật vậy, vì x là nghiệm của bài toán (P ) nên x ∈ ∆, suy ra ∆ (cid:54)= ∅ tức là (i) thỏa mãn.

Giả sử v ∈ Rn và Av ≥ 0. Ta có

A(x + tv) = Ax + tAv ≥ b + 0 = b, ∀t ≥ 0

nên x + tv ∈ ∆, ∀t ≥ 0. Suy ra f (x + tv) ≥ f (x), ∀t ≥ 0 hay

1 (cid:104)x, Dx(cid:105) + (cid:104)c, x(cid:105) 1 (cid:104)x + tv, D(x + tv)(cid:105) + (cid:104)C, t + tv(cid:105) ≥ 2 2

1 ⇒ t2(cid:104)v, Dv(cid:105) + t(cid:104)Dx + c, v(cid:105) ≥ 0, ∀t ≥ 0. 2

Suy ra (cid:104)v, Dv(cid:105) ≥ 0 (vì nếu ngược lại (cid:104)v, Dv(cid:105) < 0 thì ta cho t → +∞ vế trái

của bất đẳng thức tiến tới −∞, điều này vô lý). Do đó, điều kiện (ii) được

thỏa mãn.

Giả sử v ∈ Rn và x ∈ Rn sao cho Av ≥ 0, (cid:104)v, Dv(cid:105) ≥ 0 và Ax ≥ b.

x + tv ∈ ∆, ∀t ≥ 0 và x là nghiệm của bài toán (P ) nên f (x + tv) ≥

f (x), ∀t ≥ 0. Từ điều kiện (cid:104)v, Dv(cid:105) = 0 suy ra

t(cid:104)Dx + c, v(cid:105) + 1 (cid:104)x, Dx(cid:105) + (cid:104)c, x(cid:105) ≥ f (x), ∀t ≥ 0. 2

Nếu (cid:104)Dx + c, v(cid:105) < 0 thì ta cho t → +∞ ở bất đẳng thức trên sẽ dẫn đến điều

vô lý. Suy ra, điều kiện (iii) được thỏa mãn.

Ngược lại, giả sử ba điều kiện (i), (ii), (iii) được thỏa mãn. Ta chứng minh bài toán (P ) có nghiệm. Đặt θ = inf{f (x) : x ∈ Rn, Ax ≥ b}. Vì ∆ (cid:54)= ∅ nên θ (cid:54)= +∞. Nếu θ ∈ R thì theo định lí Frank - Wolfe bài toán (P ) có

nghiệm. Ta sẽ chứng minh θ = −∞ không xảy ra.

Thật vậy, giả sử θ = −∞. Cố định x0 ∈ ∆, với mọi ρ > 0 ta định nghĩa ∆ρ = ∆ ∩ B(x0, ρ). Ta xét bài toán min{f (x) : x ∈ ∆ρ}. Gọi

qρ là giá trị tối ưu của bài toán này. Lấy yρ ∈ ∆ρ sao cho f (yρ) = qρ và (cid:107)yρ − x0(cid:107) = min{(cid:107)y − x0(cid:107) : y ∈ ∆ρ, f (yρ) = qρ}.

Khi đó, luôn tồn tại (cid:98)ρ > 0 sao cho (cid:107)yρ − x0(cid:107) < ρ, ∀ρ ≥ (cid:98)ρ. Thật vậy, giả sử ngược lại ta tìm được dãy tăng {ρk} : ρk → +∞ sao cho

mỗi k tồn tại yρk ∈ ∆yρk sao cho f (ρk) = qρk, (cid:107)yρk − x0(cid:107) = ρk.

Để đơn giản cho kí hiệu ta viết yk thay cho yρk. Vì yk ∈ ∆ nên Aiyk ≥

bi, ∀i = 1, 2, . . . , m.

Với i = 1 ta có dãy A1yk bị chặn dưới nên tồn tại dãy {k(cid:48)} ⊂ {k} sao cho

1 = 1). Không mất tính

A1yk = y(cid:48) tồn tại (có thể xảy ra trường hợp Ak lim k(cid:48)→∞

A1yk tồn tại.

Tương tự, với i = 2 ta cũng có lim k→∞

tổng quát ta giả sử {k(cid:48)} = {k}. Khi đó lim k→∞ A2yk tồn tại. Tiếp tục quá trình trên Amyk tồn tại. Khi đó, với mỗi i ∈ {1, 2, . . . , m} với i = m ta có k → ∞, lim k→∞

Aiyk tồn tại. ta có lim k→∞

Aiyk = b}; I1 = I\I0 = {i ∈ Đặt I = {1, 2, . . . , m}; I0 = {i ∈ I : lim k→∞

Aiyk > b}.

Aiyk ≥ bi + δ, ∀i ∈ I1. Mặt khác I : lim k→∞ Khi đó, tồn tại δ > 0 sao cho lim k→∞

yk − x0 = 1, ∀k. Vì mặt cầu đơn vị trong Rn là (cid:107)y − x0(cid:107) = ρk, suy ra ρk (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13)

yk − x0     hội compact nên không mất tính tổng quát ta có thể giả sử dãy ρ  

tụ về v ∈ R khi k → ∞ và (cid:107)v(cid:107) = 1. Vì ρk → +∞ nên với mỗi i ∈ I0 ta có

 

  0 = lim k→∞ (Aiyk − bi) = lim k→∞ Aiyk − bi ρk

yk − x0 . Ai = lim k→∞ + lim k→∞ ρk Aix0 − bi ρk

Tương tự, với mỗi i ∈ I1 ta có

 

inf   0 ≤ lim k→∞ Aiyk − b ρk

 

inf +   = lim k→∞ Aiyk − b ρk Aix0 − bi ρk

  yk − x0 = Aiv. Ai  + lim k→∞ = lim k→∞ ρk Aix0 − bi ρk

Khi đó Aiv = 0, ∀i ∈ I0 và Aiv ≥ 0, ∀i ∈ I1. Suy ra v là phương lùi xa của

tập lồi đa diện ∆. Do đó

y + tv ∈ ∆, ∀t ≥ 0 và y ∈ ∆. (2.11)

Vì

f (yk) = f (yρk) = qρk

= min{f (x) : x ∈ ∆ρk}

= min{f (x) : x ∈ ∆ ∩ B(x0, ρk)}

và dãy {ρk} là dãy tăng ρk → +∞ nên có {f (yk)} là dãy giảm và f (yk) → −∞. Suy ra f (yk) < 0, ∀k đủ lớn. Sử dụng công thức của f ta được

1 1 (cid:104)yk−x0, D(yk−x0)(cid:105)+(cid:104)c, yk−x0(cid:105)+(cid:104)x0, D(yk−x0)(cid:105)+ (cid:104)x0, Dx0(cid:105)+(cid:104)c, x0(cid:105) < 0. 2 2

k và cho k → +∞ ta được (cid:104)v, Dv(cid:105) ≥ 0. Vì Av ≥ 0 nên từ điều kiện (ii) suy ra (cid:104)v, Dv(cid:105) ≥ 0. Do đó (cid:104)v, Dv(cid:105) = 0. Từ (2.11) suy ra yk + tv ∈ ∆ với mọi t ≥ 0 và k ∈ N. Kết hợp với điều kiện

Chia các vế của bất đẳng thức trên cho ρ2

(cid:104)v, Dv(cid:105) = 0 ta có

f (yk + tv) = 1 (yk + tv).D(yk + tv) + (cid:104)c, yk + tv(cid:105) 2

= 1 (cid:104)yk, Dyk(cid:105) + (cid:104)c, yk(cid:105) + t(cid:104)yk, Dv + (cid:104)c, v(cid:105)(cid:105). 2

Vì yk ∈ ∆, Av ≥ 0, (cid:104)v, Dv(cid:105) = 0 nên từ điều kiện (iii) suy ra

(cid:104)yk, Dv(cid:105) + (cid:104)c, v(cid:105) = (cid:104)Dyk + c, v(cid:105) ≥ 0, ∀k ∈ N. (2.12)

ykx0 Mặt khác (cid:104)v, v(cid:105) = 1 và → v nên tồn tại k1 ∈ N sao cho ρk

(cid:43)

, v ≥ 0, ∀k ≥ k1. (cid:42)yk − x0 ρk

Cố định k ≥ k1 ta có (cid:104)yk − x0, v(cid:105) > 0. Suy ra

(cid:107)yk − x0 − tv(cid:107)2 = (cid:107)yk − x0(cid:107)2 − 2t(cid:104)yk − x0, v(cid:105) + t2(cid:107)v(cid:107)2 < (cid:107)yk − x0(cid:107)2 (2.13)

với t > 0 đủ nhỏ. Ta lại có Ai(yk −tv) = Aiyk ≥ bi, ∀i ∈ I0 (do với i ∈ I0) ta Aiyk ≥ bi + ε, ∀i ∈ I1 nên tồn tại k2 ∈ N, k2 ≥ k1 có Aiv = 0. Mặt khác lim k→∞

sao cho

ε , ∀ ≥ k2, i ∈ I1. Aiyk ≥ bi + 2

ε Cố định chỉ số k ≥ k2 và chọn δk ≥ 0 sao cho tAiv ≤ , ∀i ∈ I1, t ∈ (0, δk). 2

Khi đó Ai(yk − tv) ≥ bi + − tAiv ≥ bi, ∀i ∈ I1, t ∈ (0, δk). Suy ra yk−tv ∈ ∆ với mọi t ∈ (0, δk). Kết hợp với điều kiện (2.13) ta có yk−tv ∈ ∆

và

(cid:107)(yk − tv) − x0(cid:107) = (cid:107)yk − x0 − tv(cid:107) < (cid:107)yk − x0(cid:107) = ρk,

với mọi t ∈ (o, δk) đủ nhỏ. Từ (2.12) ta có

f (yk − tv) = 1 (cid:104)yk, Dyk(cid:105) + (cid:104)c, yk(cid:105) − t(cid:104)yk, Dv(cid:105) + (cid:104)c, v(cid:105) 2

= f (yk) − t(cid:104)Dyk + c, v(cid:105) ≤ f (yk).

(cid:107)yk − x0(cid:107) = min{(cid:107)y − x0(cid:107) : y ∈ ∆ρk, f (y) = qρk}.

Vậy ta đã chứng minh được tồn tại ρ > 0 sao cho

(2.14) (cid:107)yρ − x0(cid:107) < ρ, ∀ρ ≥ ˆρ

Chú ý rằng qρ ≥ qρ(cid:48) với mọi ρ(cid:48) ≥ ρ và qρ → θ = −∞ khi ρ → +∞. Suy ra tồn tại ρi ∈ ((cid:98)ρ, +∞), (i = 1, 2) sao cho ρ1 < ρ2 và qρ1 > qρ2. Vì qρ1 > qρ2 nên ρ1 < (cid:107)yρ2 − x0(cid:107) (vì nếu ρ1 ≥ (cid:107)yρ2 − x0(cid:107) thì yρ2 ∈ ∆ρ1 và f (yρ2) = qρ2 < qρ1 = f (yρ1), điều này mâu thuẫn với cách chọn yρ1). Đặt

ρ3 = (cid:107)yρ2 − x0(cid:107) ta có, ρ1 < ρ3 < ρ2. Vì ρ3 < (cid:98)ρ và ρ2 > (cid:98)ρ nên khẳng định (2.14) ta có

(2.15) (cid:107)yρ3 − x3(cid:107) < ρ3 = (cid:107)yρ2 − x0(cid:107) < ρ2.

Vì ρ2 > ρ3 nên qρ3 = f (yρ3) ≥ f (yρ2) = qρ2.

Nếu f (yρ3) = f (yρ2) thì từ (2.15) suy ra yρ3 là véctơ chấp nhận được của

bài toán

(2.16) min{f (x : x ∈ ∆ρ2)}

với hàm mục tiêu có giá trị tối ưu qρ2 = f (yρ) mà f (yρ3) = f (yρ2) nên yρ3

cũng là nghiệm của bài toán (2.16).

Mặt khác (cid:107)yρ3 − x0(cid:107) < (cid:107)yρ2 − x0(cid:107). Suy ra yρ2 không phải là nghiệm của bài toán (2.16) với khoảng cách tới x0 nhỏ nhất, điều này mâu thuẫn với sự tồn tại của yρ2. Do đó f (yρ3) > f (yρ2). Ta lại có (cid:107)yρ2 − x0(cid:107) = ρ3 nên yρ2 là vectơ chấp nhận được của bài toán min{f (x) : x ∈ ∆ρ3}. Từ bất đẳng

thức f (yρ3) > f (yρ2) dẫn đến mâu thuẫn với sự kiện yρ3 là nghiệm tối ưu

của bài toán. Do đó trường hợp θ = −∞ không xảy ra. Vậy bài toán (P) có

nghiệm.

Hệ quả 2.2.7. Giả sử D là ma trận xác định dương. Khi đó, bài toán (P ) có

nghiệm khi và chỉ khi ∆ khác rỗng và điều kiện sau thỏa mãn:

(∀v ∈ Rn, x ∈ Rn : Av ≥ 0, vT Dv = 0, Ax ≥ b) ⇒ (cid:104)Dx + c, v(cid:105) ≥ 0.

Hệ quả 2.2.8. Giả sử D là ma trận xác định âm. Khi đó, bài toán (P ) có nghiệm nếu và chỉ nếu ∆ (cid:54)= ∅ và các điều kiện sau được thỏa mãn:

(i) (v ∈ Rn, Av ≥ 0) ⇒ (cid:104)v, Dv(cid:105) = 0; (ii) (∀v ∈ Rn, x ∈ Rn, Av ≥ 0, Ax ≥ b) ⇒ (cid:104)Dx + c, v(cid:105) ≥ 0.

, A ∈ Rm×n, c ∈ Rn và b ∈ Rm. Bài toán Hệ quả 2.2.9. Lấy D ∈ Rn×n

    min f (x) = (2.17) 1 (cid:104)x, Dx(cid:105) + (cid:104)c, x(cid:105) : x ∈ Rn, Ax ≥ b, x ≥ 0 2  

có nghiệm khi và chỉ khi ba điều kiện sau thỏa mãn (i) Tập {x ∈ Rn : Ax ≥ b, x ≥ 0} khác rỗng; (ii) Nếu v ∈ Rn, Av ≥ 0 và v ≥ 0 thì (cid:104)v, Dv(cid:105) ≥ 0; (iii) Nếu v ∈ Rn và x ∈ Rn sao cho Av ≥ 0, v ≥ 0, (cid:104)v, Dv(cid:105) ≥ 0, Ax ≥ 0,

x ≥ 0 thì (cid:104)Dx + c, v(cid:105) ≥ 0.

Chứng minh. Cho (cid:101)A ∈ Rm+n × n,(cid:101)b ∈ Rm+n bởi     b A (cid:101)A =    ,(cid:101)b =  0 E

Trong đó E là kí hiệu ma trận đơn vị trong Rn×n, (2.17) có thể được viết dưới

dạng

    f (x) = min . 1 (cid:104)x, Dx(cid:105) + (cid:104)c, x(cid:105) : x ∈ Rn, (cid:101)Ax ≥ (cid:101)b 2  

Áp dụng định lí Eaves, suy ra điều phải chứng minh.

, A ∈ Rm×n, C ∈ Rs×n, c ∈ Rn, b ∈ Rm và

Hệ quả 2.2.10. Cho D ∈ Rn×n d ∈ Rs. Bài toán

1     min (cid:104)x, Dx(cid:105) + (cid:104)c, x(cid:105) : x ∈ Rn, Ax ≥ b, Cx = d f (x) = (2.18) 2  

có nghiệm khi và chỉ khi ba điều kiện sau đâ được thỏa mãn:

(i) Tập {x ∈ Rn : Ax ≥ b, Cx = d} (cid:54)= ∅; (ii) Nếu v ∈ Rn, Av ≥ 0 và Cv = 0 thì (cid:104)v, Dv(cid:105) ≥ 0; (iii) Nếu v ∈ Rn và x ∈ Rn sao cho Av ≥ 0, Cv = 0, (cid:104)v, Dv(cid:105) = 0,

Ax ≥ b và Cx = d thì (cid:104)Dx + c, v(cid:105) ≥ 0.

Chứng minh. Cho (cid:101)A ∈ Rm+2s × n,(cid:101)b ∈ Rm+2s bởi   b   A d (cid:101)A =  ,(cid:101)b =  −C         −d

(2.18) có thể viết dưới dạng

1     min f (x) = . (cid:104)x, Dx(cid:105) + (cid:104)c, x(cid:105) : x ∈ Rn, (cid:101)Ax ≥ (cid:101)b 2  

Sử dụng định lí Eaves ta được điều phải chứng minh.

2.2.2 Bài toán quy hoạch toàn phương lồi với hữu hạn ràng buộc

toàn phương lồi trong không gian Hilbert thực

Định nghĩa 2.2.11. Dạng toàn phương Q được gọi là

(i) Không âm nếu Q(x) ≥ 0 với mọi x ∈ H;

(ii) Dương nếu Q(x) > 0 với mọi x ∈ H\{0}.

Toán tử T được gọi là nửa xác định dương (dương) nếu dạng toàn phương

Q(x) = (cid:104)x, T x(cid:105) không âm (dương).

Mệnh đề 2.2.12. Dạng toàn phương Q(x) = (cid:104)x, T x(cid:105) trên không gian Hilbert

H là lồi nếu và chỉ nếu nó không âm.

Mệnh đề 2.2.13. Dạng toàn phương không âm, liên tục trên không gian

Hilbert H là nửa liên tục dưới yếu.

Định nghĩa 2.2.14. Dạng toàn phương Q trên không gian Hilbert H được gọi

thỏa mãn điều kiện Legrendre nếu nó thỏa mãn các điều kiện sau:

(i) Q là nửa liên tục dưới yếu; (ii) xk → x0 khi xk (cid:42) x0 thì Q(xk) → Q(x0).

Rõ ràng nếu H hữu hạn chiều thì mọi dạng toàn phương Q(x) trên H đều

thỏa mãn điều kiện Legrendre.

Định nghĩa 2.2.15. Toán tử T : H → H được gọi là toán tử hữu hạn chiều

(hay toán tử có hạng hữu hạn) nếu tập giá trị của nó là hữu hạn chiều.

Toán tử T trong không gian Hilbert được gọi là toán tử compact nếu với

mỗi dãy bị chặn {xn} trong H, thì dãy {T xn} có một dãy con hội tụ.

Nhận xét 2.2.16. Mọi toán tử T hữu hạn chiều, bị chặn trên H đều là toán tử

compact và toán tử compact là toán tử hữu hạn chiều.

Bổ đề 2.2.17. Nếu F khác rỗng thì

(2.19) 0+F = {v ∈ H| Tiv = 0, (cid:104)ci, v(cid:105) ≤ 0, ∀i = 1, 2, . . . , m}.

Chứng minh. Ta có 0+F = {v ∈ H| ∃x ∈ F với x + tv ∈ F, ∀t ≥ 0}.

Đặt E = {v ∈ H| Tiv = 0, (cid:104)ci, v(cid:105) ≤ 0, ∀i = 1, 2, . . . , m}. Ta chứng minh E = 0+F .

Lấy x ∈ E, suy ra Tix = 0, suy ra (cid:104)x, Tix(cid:105) = 0, ∀i = 1, 2, . . . , m.

(cid:104)ci, x(cid:105) ≤ 0, ∀i = 1, 2, . . . , m.

Vì F (cid:54)= ∅ nên tồn tại x∗ ∈ F, x∗ ∈ H thỏa mãn

g(x∗) ≤ 0, ∀i = 1, 2, . . . , m.

Vì x, x∗ ∈ H, H là toàn không gian Hilbert, suy ra x∗ + tx ∈ H, ∀t ≥ 0.

1 (cid:104)x∗ + tx, Ti(x∗ + tx)(cid:105) + (cid:104)ci, x∗ + tx(cid:105) + αi gi(x∗ + tx) = 2

1 = (cid:104)x∗, Tix∗(cid:105) + (cid:104)ci, x∗(cid:105) + αi 2

+ t(cid:104)x∗, Tix(cid:105) + t2(cid:104)x, Tix(cid:105) + t(cid:104)ci, x(cid:105)

= gi(x∗) ≤ 0 ∀i = 1, 2, . . . , m.

Do đó x∗ + tx ∈ F suy ra x ∈ 0+F nên F ⊂ 0+F .

Ngược lại, với mọi v ∈ 0+F ta sẽ chứng minh v ∈ E. Thật vậy v ∈ 0+F ,

suy ra tồn tại x ∈ F với mọi x + tv ∈ F, ∀t ≥ 0. Tức là gi(x + tv) ≤ 0, ∀t ≥

0, ∀i hay

(cid:104)x, Tix(cid:105) + (cid:104)ci, x(cid:105) + αi + t(cid:104)x, Tiv(cid:105) + t2(cid:104)v, Tiv(cid:105) + t(cid:104)ci, v(cid:105) ≤ 0, ∀t ≥ 0. 2

Do (cid:104)v, Tiv(cid:105) ≥ 0, ∀i nên nếu Tiv (cid:54)= 0 thì tồn tại (cid:104)v, Tiv(cid:105) > 0 hoặc (cid:104)ci, v(cid:105) > 0.

gi(x + tv) = +∞ điều này dẫn đến vô lý. Khi đó lim t→+∞

Vậy Tiv = 0, (cid:104)ci, v(cid:105) ≤ 0, suy ra v ∈ E hay 0+F ⊂ E. Điều phải chứng

minh.

Nhận xét 2.2.18. Giả sử xk ∈ F \{0} với mọi k, (cid:107)xk(cid:107) → ∞ khi k → ∞ và (cid:107)xk(cid:107)−1xk (cid:42) v. Khi đó v ∈ 0+F .

1 (cid:104)x, T x(cid:105) + (cid:104)c, x(cid:105) với T : H → H là toán tử tuyến Bổ đề 2.2.19. Cho f (x) = 2

tính, tự liên hợp và nửa xác định dương và c ∈ H. Giả sử f bị chặn dưới trên

H và một trong các điều kiện sau xảy ra:

(i) (cid:104)x, T x(cid:105) thỏa mãn điều kiện Legrendre,

(ii) T là toán tử có hạng hữu hạn.

Khi đó, tồn tại x ∈ H sao cho f (x) ≤ f (x) với mọi x ∈ H.

1 Chứng minh. Đặt f ∗ = inf{f (x)| x ∈ H} > −∞. Với mỗi k, xét tập Sk =   x ∈ H| f (x) ≤ f ∗ + k    . 

Vì f ∗ > −∞ nên tồn tại xk ∈ H sao cho

1 1 (cid:104)xk, T xk(cid:105) + (cid:104)c, xk(cid:105) ≤ f ∗ + . f (xk) = (2.20) k 2

Do đó Sk khác rỗng. Vì f liên tục và lồi nên mỗi tập Sk là lồi đóng. Do đó,

trong Sk tồn tại phần tử có chuẩn nhỏ nhất. Không mất tính tổng quát ta giả sử xk trong (2.20) là phần tử có chuẩn nhỏ nhất trong Sk.

Xét dãy {xk}. Ta sẽ chứng minh {xk} bị chặn. Giả sử ngược lại {xk} không bị chặn. Không mất tính tổng quát ta giả sử (cid:107)xk(cid:107) → ∞ khi k → ∞,

xk (cid:107)xk(cid:107) (cid:54)= 0 với mọi k. Đặt vk := , ta có (cid:107)vk(cid:107) = 1. Khi đó, tồn tại một dãy (cid:107)xk(cid:107)

con của {vk} hội tụ yếu tới v. Không mất tính tổng quát ta giả sử vk (cid:42) v khi

k → ∞.

Ta sẽ chứng minh

T v = 0, (cid:104)c, v(cid:105) = 0. (2.21)

Vì T nửa xác định dương nên Mệnh đề 2.2.13, suy ra (cid:104)x, T x(cid:105) là liên tục dưới yếu. Chia cả hai vế của (2.20) cho (cid:107)xk(cid:107)2 và cho k → ∞ ta có

1 1 0 ≤ (cid:104)v, T v(cid:105) ≤ (cid:104)vk, T vk(cid:105) lim inf k→∞ 2 2

1 ≤ (cid:104)vk, T vk(cid:105) ≤ 0. 2 lim sup k→∞

Từ đó, suy ra

(2.22) (cid:104)vk, T vk(cid:105) = 0. (cid:104)v, T v(cid:105) = lim k→∞

Vì T là nửa xác định dương nên từ trên ta suy ra

T v = 0. (2.23)

Theo tính nửa xác định dương của T , từ (2.20) suy ra

1 (cid:104)c, xk(cid:105) ≤ f ∗ + . (2.24) k

Chia cả hai vế của (2.24) cho (cid:107)xk(cid:107) và cho k → ∞ ta có

 (cid:42) (cid:43) xk 1 1 c,  f ∗ +  ⇒ (cid:104)c, v(cid:105) ≤ 0. lim k→∞ ≤ lim k→∞ (cid:107)xk(cid:107) (cid:107)xk(cid:107) k

Ta cần chứng minh (cid:104)c, v(cid:105) = 0. Rõ ràng, nếu (cid:104)c, v(cid:105) < 0 thì với mỗi k và với mọi t > 0 ta có xk + tv ∈ H và

t2 f (xk + tv) = f (xk) + (cid:104)v, T v(cid:105) + t(cid:104)xk, T v(cid:105) + t(cid:104)c, v(cid:105) 2

= f (xk) + t(cid:104)c, v(cid:105) (do T v = 0).

Vì f bị chặn trên H, khi cho t → +∞ thì

f (xk + tv) = f (xk) + t(cid:104)c, v(cid:105) → −∞.

Điều này mâu thuẫn với f bị chặn dưới trên H. Do vậy (cid:104)c, v(cid:105) < 0 không thể

xảy ra. Do đó

(cid:104)c, v(cid:105) = 0. (2.25)

Từ (2.23) và (2.25) ta thu được (2.21).

Xét trường hợp (cid:104)x, T x(cid:105) thỏa mãn điều kiện Legrendre. Vì (cid:104)x, T x(cid:105) thỏa mãn điều kiện Legrendre và vk (cid:42) v khi k → ∞. Từ (2.22), suy ra vk hội tụ đến v. Do đó, ta có v (cid:54)= 0 và (cid:107)v(cid:107) = 1. Đặt yk(t) := xk − tv, t ∈ R, theo

(2.21) ta có

f (yk(t)) = f (xk − tv)

t2 = (cid:104)v, T v(cid:105) − t(cid:104)xk, T v(cid:105) − t(cid:104)c, v(cid:105) 1 (cid:104)xk, T xk(cid:105) + (cid:104)x, xk(cid:105) + 2 2

1 = f (xk) ≤ f ∗ + . k

Điều này chứng tỏ rằng yk(t) ∈ Sk với mọi số thực t. Mặt khác, ta có

(cid:107)yk(t)(cid:107)2 = (cid:107)xk − tv(cid:107)2 = (cid:107)xk(cid:107)2 − t (cid:0)2(cid:104)xk, v(cid:105) − t(cid:104)v, v(cid:105)(cid:1) . (2.26)

Suy ra (cid:107)yk(t)(cid:107)2 − (cid:107)xk(cid:107)2 = t2 − 2t(cid:104)xk, v(cid:105).

Vì (cid:104)v, v(cid:105) = 1 và (cid:104)xk/(cid:107)xk(cid:107), v(cid:105) → (cid:104)v, v(cid:105) nên tồn tại k1 sao cho

(cid:104)xk, v(cid:105) > 0, ∀k ≥ k1.

Do đó, với k ≥ k1, theo (2.26) thì tồn tại γ > 0 sao cho

t2 − 2t.(cid:104)xk, v(cid:105) < 0, ∀t ∈ (0, γ). (2.27)

Từ (2.27) suy ra (cid:107)xk − tv(cid:107) < (cid:107)xk(cid:107) với k đủ lớn. Điều này mâu thuẫn với giả thiết xk là phần tử có chuẩn nhỏ nhất trong Sk. Do đó {xk} bị chặn.

Xét trường hợp T là toán tử có hạng hữu hạn. Đặt L = H ⊕ R, ở đây ⊕ là

tổng trực tiếp của các không gian Hilbert và (cid:104)., .(cid:105)L và (cid:107).(cid:107)L là tích vô hướng và chuẩn trên L. Cho A : H → H ⊕ R được định nghĩa bởi Ax = (T x, (cid:104)c, x(cid:105)).

Vì T là toán tử có hạng hữu hạn nên nó compact với miền đóng, do đó A

compact với miền đóng. Với mỗi k, xét hệ phương trình tuyến tính

Ax = Axk. (2.28)

Vì A là compact nên tồn tại A+ liên tục giả đảo của A và một nghiệm xk của (2.28) sao cho xk = A+Axk. Do đó, tồn tại ρ > 0 chỉ phụ thuộc vào A sao cho (cid:107)xk(cid:107) ≤ ρ((cid:107)Axk(cid:107)L). Điều này cho ta (cid:107)xk(cid:107) ≤ ρk((cid:107)T xk(cid:107) + |(cid:104)c, xk(cid:105)|). Vì

T xk = T xk   Axk = Axk nên (T xk, (cid:104)c, xk(cid:105)) = (T xk, (cid:104)c, xk(cid:105)), suy ra (cid:104)c, xk(cid:105) = (cid:104)c, xk(cid:105) 

nên T (xk − xk) = 0.

1 1 f (xk) − f (xk) = (cid:104)xk, T xk(cid:105) + (cid:104)c, xk(cid:105) − (cid:104)xk, T xk(cid:105) − (cid:104)c, xk(cid:105) 2 2

1 1 1 = (cid:104)xk, T xk(cid:105) − (cid:104)xk, T xk(cid:105) = (cid:104)xk − xk, T xk(cid:105) = 0. 2 2 2

1 nên f (xk) = f (xk) ≤ f ∗ + . k

Vì xk là chuẩn nhỏ nhất trong Sk nên

(cid:107)xk(cid:107) ≤ (cid:107)xk(cid:107) ≤ ρ (cid:0)(cid:107)T xk(cid:107) + |(cid:104)c, xk(cid:105)|(cid:1) ∀k.

Chia cả hai vế của bất đẳng thức trên cho (cid:107)xk(cid:107), cho k → ∞ và theo tính

compact của T , ta có

1 ≤ ρ((cid:107)T v(cid:107) + |(cid:104)c, v(cid:105)|).

Điều này mâu thuẫn với T v = 0 và (cid:104)c, v(cid:105) = 0. Do đó dãy {xk} bị chặn.

Vì dãy {xk} bị chặn nên nó có một dãy con hội tụ yếu. Không mất tính tổng quát ta giả sử xk (cid:42) x khi k → ∞. Vì T là nửa xác định dương nên

(cid:104)x, T x(cid:105) là nửa liên tục yếu, bị chặn dưới. Do đó

1 1 inf (cid:104)xk, T xk(cid:105). (cid:104)x, T x(cid:105) ≤ lim k→∞ 2 2

Do đó, theo (2.20) ta có

 

f (x) =   1 (cid:104)x, T x(cid:105) + (cid:104)c, x(cid:105) ≤ lim inf 2 k→∞ 1 (cid:104)xk, T xk(cid:105) + (cid:104)c, xk(cid:105) 2

  = f ∗.  f ∗ + ≤ lim inf k→∞ k

Điều này chứng tỏ rằng tồn tại x ∈ H sao cho f (x) ≤ f (x) với mọi x ∈

Bây giờ chúng ta sẽ chứng minh sự tồn tại nghiệm của bài toán (CQP )

bằng cách sử dụng tính chất Legrendre của bài toán quy hoạch toàn phương.

Trong định lý sau đây chúng ta mở rộng kết quả trong không gian Hilbert.

Định lí 2.2.20 (Định lí Frank - Wolfe 1). Xét bài toán quy hoạch toàn phương

lồi (CQP ) . Giả sử (cid:104)x, T x(cid:105) thỏa mãn điều kiện Legrendre và hàm mục tiêu

f là bị chặn dưới trên tập ràng buộc khác rỗng F . Khi đó, bài toán (CQP )

có nghiệm.

Chứng minh. Đặt f ∗ = inf{f (x)| x ∈ F } > −∞. Với mỗi k xét tập Sk =

1 {c ∈ F |f (x) ≤ f ∗ + }. Theo giả thiết f ∗ > −∞, nên tồn tại xk ∈ H sao k

cho

1 1 f (xk) = (cid:104)xk, T xk(cid:105) + (cid:104)c, xk(cid:105) ≤ f ∗ + , (2.29) 2 k

1 i = 1, 2, . . . , m. (2.30) gi(xk) = (cid:104)xk, Tixk(cid:105) + (cid:104)ci, xk(cid:105) + αi ≤ 0, 2

Suy ra xk ∈ Sk. Vì thế Sk khác rỗng. Vì f, gi là lồi và liên tục nên mỗi tập Sk

là lồi và đóng. Do đó trong Sk tồn tại phần tử có chuẩn nhỏ nhất. Không mất tính tổng quát, ta giả sử xk trong (2.29) và (2.30) là phần tử có chuẩn nhỏ

nhất trong Sk.

Ta xét dãy {xk}. Nếu {xk} bị chặn thì tồn tại một dãy con hội tụ yếu. Không mất tính tổng quát ta giả sử xk (cid:42) x khi k → ∞. Từ (2.30) ta suy ra xk ∈ F . Theo tính hội tụ yếu của F , ta có x ∈ F . Vì (cid:104)x, T x(cid:105) thỏa mãn điều

kiện Legrendre nên (cid:104)x, T x(cid:105) nửa liên tục yếu bị chặn dưới. Suy ra

1 1 inf (cid:104)xk, T xk(cid:105). (cid:104)x, T x(cid:105) ≤ lim k→∞ 2 2

Từ điều này và (2.29) suy ra

 

f (x) =   1 (cid:104)x, T x(cid:105) + (cid:104)c, x(cid:105) ≤ lim inf 2 k→∞ 1 (cid:104)xk, T xk(cid:105) + (cid:104)c, xk(cid:105) 2

1 inf   = f ∗.  f ∗ + ≤ lim k→∞ k

Do đó x là một nghiệm của bài toán (CQP ) .

Xét trường hợp {xk} không bị chặn. Không mất tính tổng quát ta giả sử

xk rằng (cid:107)xk(cid:107) → ∞ khi k → ∞, (cid:107)xk(cid:107) (cid:54)= 0 với mọi k. Đặt vk := thì (cid:107)xk(cid:107)

(cid:107)vk(cid:107) = 1. Vì (cid:107)vk(cid:107) bị chặn nên tồn tại một dãy con hội tụ yếu. Không mất tính tổng quát ta giả sử rằng vk (cid:42) v khi k → ∞. Theo Nhận xét 2.2.18 ta có v ∈ 0+F . Lập luận tương tự như trong chứng minh Bổ đề 2.2.19 ta có

v (cid:54)= 0 và T v = 0, (cid:104)c, v(cid:105) = 0. (2.31)

Do (cid:104)ci, v(cid:105) ≤ 0 ta có ba khả năng sau:

+ Khả năng 1: (cid:104)ci, v(cid:105) = 0 với mọi i = 1, 2, . . . , m. Khi đó

T v = 0, (cid:104)c, v(cid:105) = 0, Tiv = 0, ∀i = 1, 2, . . . , m.

Đặt yk(t) = xk − tv, t > 0. Ta dễ dàng kiểm tra rằng yk(t) = xk − tv ∈ F

với mọi t > 0. Vì T v = 0, (cid:104)c, v(cid:105) = 0 nên ta có

f (yk(t)) = f (xk − tv)

1 t2 = (cid:104)xk, T xk(cid:105) + (cid:104)c, xk(cid:105) + (cid:104)v, T v(cid:105) − t(cid:104)xk, T v(cid:105) − t(cid:104)c, v(cid:105) 2 2

1 = f (xk) ≤ f ∗ + . k

Do đó yk(t) ∈ Sk, ∀t > 0. Mặt khác, ta có

(cid:107)yk(t)(cid:107)2 = (cid:107)xk − tv(cid:107)2 (2.32)

(cid:43)

, v Vì (cid:104)v, v(cid:105) = (cid:107)v(cid:107) = 1 và → (cid:104)v, v(cid:105) nên tồn tại k1 sao cho = (cid:107)xk(cid:107)2 + t2(cid:107)v(cid:107)2 − 2t(cid:104)xk, v(cid:105). (cid:42) xk (cid:107)xk(cid:107)

(cid:104)xk, v(cid:105) > 0, ∀k ≥ k1.

Do đó, với k ≥ k1, theo (2.32) tồn tại γ > 0 sao cho

(cid:107)xk − tv(cid:107)2 < (cid:107)xk(cid:107)2, ∀t ∈ (0, γ). (2.33)

Từ (2.33) suy ra (cid:107)xk − tv(cid:107) < (cid:107)xk(cid:107). Điều này mâu thuẫn với xk là phần tử có

chuẩn nhỏ nhất trong Sk và vì thế khả năng 1 không thể xảy ra.

+ Khả năng 2: (cid:104)ci, v(cid:105) > 0 với mọi i = 1, 2, . . . , m.

Xét bài toán quy hoạch toàn phương

1     min f (x) := (cid:104)x, T x(cid:105) + (cid:104)c, x(cid:105)| x ∈ H . 2  

Nếu f (x) bị chặn dưới trên không gian Hilbert thì theo Bổ đề 2.2.19 tồn tại x ∈ H sao cho f (x) ≤ f ∗. Nnếu f (x) không bị chặn dưới trên không gian Hilbert H thì tồn tại ˆx ∈ H sao cho f (ˆx) ≤ f ∗. Vì thế trong cả hai trường hợp ta đều tồn tại x∗ ∈ H sao cho f (x∗) ≤ f ∗.

Theo Nhận xét 2.10 ta có v ∈ 0+F , suy ra Tiv = 0, ∀i = 1, 2, . . . , m, ∀t ≥

t∗ và t∗ = max{−gi(x∗)/(cid:104)ci, v(cid:105); i = 1, 2, . . . , m}.

1 gi(x∗ + tv) = (cid:104)x∗ + tv, T (x∗ + tv)(cid:105) + (cid:104)ci, x∗ + tv(cid:105) + αi 2

t2 1 = (cid:104)x∗, Tix∗(cid:105) + t(cid:104)x∗, Tiv(cid:105) + (cid:104)v, Tiv(cid:105) + (cid:104)ci, x∗(cid:105) + t(cid:104)ci, v(cid:105) + α 2 2

1 = (cid:104)x∗, Tix∗(cid:105) + (cid:104)ci, x∗(cid:105) + αi + t(cid:104)ci, v(cid:105) 2  

+ t = g(x∗) + t(cid:104)ci, v(cid:105) = −(cid:104)ci, v(cid:105)   ≤ 0 − gi(x∗) (cid:104)ci, v(cid:105)

với mọi i = 1, 2, . . . , m. Khi đó, ta có x∗ + tv ∈ F , với mọi t ≥ t∗ nên

1 f (x∗ + t∗v) = (cid:104)x∗, T x∗(cid:105) + (cid:104)c, x∗(cid:105) ≤ f ∗ 2

hay f (x∗ + t∗v) ≤ f (x), ∀x ∈ H hay x∗ + t là nghiệm của bài toán (CQP ) .

+ Khả năng 3: Tồn tại i và j sao cho (cid:104)ci, v(cid:105) = 0 và (cid:104)cj, v(cid:105) < 0. Đặt

I = {1, 2, . . . , m}, I1 = {i ∈ I| (cid:104)ci, v(cid:105) = 0} và F1 = {x ∈ H| gi(x) ≤

0, ∀i ∈ I1}. Xét bài toán

1     . min f (x) = (cid:104)x, T x(cid:105) + (cid:104)c, x(cid:105)| x ∈ F1 2  

1 ∈ F1 sao 1)/(cid:104)cj, x(cid:105), j ∈ I\I1}. Dễ dàng kiểm

1) ≤ f ∗. Đặt t∗

Đây là bài toán được xác định bằng cách xóa bớt điều kiện ràng buộc của bài

1 + tv ∈ F, ∀t ≥ max{0, t∗

1}. Khi đó, ta có

toán (CQP ) chỉ giữ lại các điều kiện gi(x) ≤ 0 với i ∈ I1. Theo cách chứng minh của khả năng 1 ta suy ra {xk} phải bị chặn. Suy ra tồn tại x∗ 1 = max{−gi(x∗ cho f (x∗ tra được x∗

1 + t∗v) =

1, T x∗

1(cid:105) + (cid:104)c, x∗

1(cid:105) = f (x∗

1) ≤ f ∗.

1 f (x∗ (cid:104)x∗ 2

1 +t∗

1v là nghiệm của bài toán (CQP ) . Định lí được

Điều này chứng tỏ rằng x∗

chứng minh.

Nhận xét 2.2.21. Định lí Frank - Wolfe đối với bài toán (P ) trong không gian Rn thì điều kiện đủ để (P ) có nghiệm là hàm mục tiêu f bị chặn dưới trên

∆. Tuy nhiên trong không gian Hilbert với bài toán (CQP ) thì tính bị chặn

dưới của hàm mục tiêu thường không xảy ra, điều kiện đủ ở đây là Tính chất

Legrendre của (cid:104)x, T x(cid:105).

Ví dụ 2.2.22. Kí hiệu l2 là không gian Hilbert bình phương các dãy số thực

khả tổng

∞ (cid:88)

(cid:40) (cid:41)

i=1

l2 = . x = (x1, x2, . . . , xn, . . . )| xi < ∞, xn ∈ R, n = 1, 2, . . .

Tích vô hướng và chuẩn trong l2 được định nghĩa

∞ (cid:88)

i=1

(cid:33) 1 (cid:32) ∞ (cid:88) (cid:104)x, y(cid:105) = . xnyn, (cid:107)x(cid:107) = x2 n

Với mỗi x = (x1, x2, . . . , xn, . . . ) ∈ l2 ta định nghĩa T : l2 → l2 bởi

  x2 , . . . , T x =  . x1, 2 xn nn, . . .

∞ (cid:80) i=1

Ta có (cid:104)x, T x(cid:105) = x2 n nn ≥ 0, ∀x. Suy ra T là toán tử tuyến tính liên tục nửa

xác định dương và (cid:107)T (cid:107) = 1.

∞ (cid:88)

Dạng toàn phương liên kết với T cho bởi

i=1

n, . . . ) thỏa mãn

2, . . . , ek

Q(x) = (cid:104)x, T x(cid:105) = x2 n nn.

Ta sẽ chứng tỏ Q(x) không thỏa mãn điều kiện Legrendre. Thật vậy, lấy {ek} 1, ek là một dãy trong l2, trong đó ek = (ek

  1 nếu n = k ek n =  0 nếu n (cid:54)= k

kk → 0 = (cid:104)0, T 0(cid:105) khi k → ∞. Do đó Q(x) = (cid:104)x, T x(cid:105) không thỏa mãn điều kiện Legrendre. Từ

Ta thấy ek (cid:42) 0 nhưng ek (cid:57) 0 trên l2, ta có (cid:104)ek, T ek(cid:105) = 1

∞ (cid:80) i=1

Q(x) = (cid:104)x, T x(cid:105) = x2 n nn ≥ 0, ∀x ∈ l2 nên theo Mệnh đề 2.2.12 và 2.2.13

suy ra (cid:104)x, T x(cid:105) lồi, nửa liên tục yếu bị chặn dưới.

Bây giờ ta xét bài toán

    (CQP ) : min f (x) := , (2.34) 1 (cid:104)x, T x(cid:105)| x ∈ l2 và (cid:104)c1, x(cid:105) + α1 ≤ 0 2  

trong đó

∞ (cid:88)

i=1

 1 , . . . (cid:104)x, T x(cid:105) = −1; −   ∈ l2. x2 n nn, C1 = 1 , . . . , − 2 n

Suy ra, miền ràng buộc

∞ (cid:88)

i=1

    . x ∈ l2| − + 1 ≤ 0 F = (cid:8)x ∈ l2| (cid:104)c1, x(cid:105) + α1 ≤ 0(cid:9) = xn n  

Ta có F (cid:54)= ∅. Thật vậy, với mỗi số nguyên dương k, đặt xk = k.ek ∈ l2, trong đó ek là vectơ được nói đến ở trên. Dễ kiểm tra được rằng (cid:104)c1, xk(cid:105) + 1 = −1 + 1 = 0, suy ra xk ∈ F, ∀k.

∞ (cid:80) i=1

Vì (cid:104)x, T x(cid:105) = x2 n nn nên (cid:104)x, T x(cid:105) = 0 nếu và chỉ nếu x = 0. Dễ thấy rằng

0 /∈ F , ta có

∞ (cid:88)

i=1

1 1 (cid:104)x, T x(cid:105) = f (x) = (2.35) 2 2 x2 n nn > 0, ∀x ∈ F.

Mặt khác ta có

1 f (xk) = (cid:104)xk, T xk(cid:105) = 2 1 . 2 1 kk−2 → 0 khi k → ∞.

Điều này cùng với (2.35), suy ra rằng cận dưới của f trên F là 0. Vì 0 /∈ F

nên bất đẳng thức (2.35) chứng tỏ rằng bài toán (CQP ) không có nghiệm.

Nhận xét 2.2.23. Định lí trên cho ta điều kiện đủ để bài toán (CQP ) có

nghiệm. Ta có kết quả sau là điều kiện cần và điều kiện đủ để bài toán (CQP )

có nghiệm.

Định lí 2.2.24 (Định lí Eaves). Xét bài toán (CQP ) trong đó F khác rỗng và

(cid:104)x, T x(cid:105) thỏa mãn điều kiện Legrendre. Khi đó, các phát biểu sau là đúng:

(a) Nếu bài toán (CQP ) có nghiệm thì

(v ∈ 0+F, T v = 0) ⇒ (cid:104)c, v(cid:105) ≥ 0. (2.36)

(b) Bài toán (CQP ) có nghiệm nếu một trong các điều kiện sau thỏa mãn:

c = 0, (2.37)

(v ∈ (0+F )\{0}, T v = 0) ⇒ (cid:104)c, v(cid:105) > 0, (2.38)

(2.39) (v ∈ (0+F ), T v = 0) ⇒ ((cid:104)c, v(cid:105) ≥ 0, (cid:104)ci, v(cid:105) = 0, ∀i ∈ I1),

trong đó I = {1, 2, . . . , m} và I1 = {i ∈ I| Ti (cid:54)= 0}.

Chứng minh. (a) Giả sử bài toán (CQP ) có nghiệm x. Để thu được (2.36), ta giả sử v ∈ 0+F sao cho T v = 0. Vì x + v ∈ F và T v = nên ta có

0 ≤ f (x + v) − f (x)

= 1 (cid:104)x + v, T (x + v)(cid:105) + (cid:104)c, x + v(cid:105) − 2 1 (cid:104)x, T x(cid:105) − (cid:104)c, x(cid:105) 2

= 1 (cid:104)x, T x(cid:105) + 2 1 (cid:104)x + v, T v(cid:105) + (cid:104)c, x(cid:105) + (cid:104)c, v(cid:105) − 2 1 (cid:104)x, T v(cid:105) − (cid:104)c, x(cid:105) 2

= (cid:104)c, v(cid:105)

Điều này có nghĩa là (cid:104)c, v(cid:105) ≥ 0 với mọi v ∈ 0+F và thỏa mãn T v = 0.

(b) Giả sử c = 0, ta chứng minh bài toán (CQP ) có nghiệm. Theo Định

lý 2.2.20 thì f bị chặn trên F . Vì (cid:104)x, T x(cid:105) ≥ 0 với mọi x ∈ H, ta có

1 f (x) = 1 (cid:104)x, T x(cid:105) + (cid:104)c, x(cid:105) = (cid:104)x, T x(cid:105) ≥ 0, ∀x ∈ H. 2 2

Suy ra f (x) bị chặn dưới trên F , suy ra bài toán (CQP) có nghiệm.

Tiếp tục, giả sử rằng (2.38) xảy ra. Ta sẽ chứng minh f là hàm bức trên

F . Giả sử ngược lại f không là hàm bức trên F . Khi đó, có thể tìm được một vài a ∈ R và một dãy {xk} ⊂ F với (cid:107)xk(cid:107) → ∞ khi k → ∞ và

1 (cid:104)xk, T xk(cid:105) + (cid:104)c, xk(cid:105) ≤ a, ∀k. f (xk) = (2.40) 2

Ta có thể giả sử rằng (cid:107)xk(cid:107) (cid:54)= 0 với mọi k, vk := (cid:107)xk(cid:107)−1xk (cid:42) v. Theo Nhận xét 2.2.18, ta có v ∈ 0+F .

Chia hai vế của (2.40) với (cid:107)xk(cid:107)2 và lấy giới hạn khi k → ∞, ta có

k→∞

(cid:104)vk, T vk(cid:105) ≤ lim sup (cid:104)vk, T vk(cid:105) ≤ 0. (2.41) (cid:104)v, T v(cid:105) ≤ lim inf k→∞

Vì T là nửa xác định dương của T nên

(cid:104)vk, T vk(cid:105) = (cid:104)v, T v(cid:105) = 0. (2.42) lim k→∞

T v = 0. (2.43)

Vì (cid:104)x, T x(cid:105) thỏa mãn điều kiện Legrendre và vk (cid:42) v khi k → ∞, theo (2.42), vk hội tụ tới v. Do đó, ta có v (cid:54)= 0.

Vì (cid:104)xk, T xk(cid:105) ≥ 0 nên từ (2.40) suy ra

(cid:104)c, xk(cid:105) ≤ f (xk) ≤ a. (2.44)

Chia cả hai vế của (2.44) cho (cid:107)xk(cid:107) và cho k → ∞, ta có

(cid:104)c, v(cid:105) ≤ 0. (2.45)

Điều này mâu thuẫn với (2.38). Suy ra f là hàm bức trên F , suy ra bài toán

(CQP ) có nghiệm.

Cuối cùng giả sử (2.39) thỏa mãn. Khi đó, theo định lí Frank - Wolfe, suy

ra bài toán (CQP ) có nghiệm. Định lí được chứng minh hoàn toàn.

Nhận xét 2.2.25. Điều kiện (2.36) trong Định lí Eaves chỉ là điều kiện cần

chứ không phải là điều kiện đủ (điều ngược lại không đúng). Thật vậy, ta xét

ví dụ sau đây.

Ví dụ 2.2.26. Xét không gian Hilbert H = l2, T x = (0, 0, x3, . . . , xn, . . . ), T1x = (0, x2, 0, 0, . . . ) với x = (x1, x2, . . . , xn, . . . ) ∈ l2 và cho c = (0, −1, 0, 0, . . . ), c1 = (1, 0, 0, . . . ) ∈ l2, α1 = −1. Khi đó, bài toán (CQP ) trở thành

4 + . . . ) − x2| x ∈ F )

3 + x2

2 + x2

1 + 0x2

    , min f (x) = (2.46) 1 (0x2 2  

1 trong đó F = {x = (x1, x2, . . . , xn, . . . ) ∈ l2| x2 2 + x1 − 1 ≤ 0}. 2

∞ (cid:88)

Vì (cid:104)x, T x(cid:105) ≥ 0, với mọi x ∈ F nên f (x) là lồi. Ta có

3 + x2

4 + · · · =

n − (x2 x2

1 + x2

2) = (cid:107)x(cid:107)2 − (x2

1 + x2

2).

i=1

(cid:104)x, T x(cid:105) = x2

Suy ra, dạng toàn phương (cid:104)x, T x(cid:105) là tổng của dạng toàn phương elliptic và

dạng toàn phương có hạng hữu hạn nên (cid:104)x, T x(cid:105) thỏa mãn điều kiện Legren-

dre. Ta có

0+F = {v ∈ F | T1v = 0, (cid:104)c1, v(cid:105) ≤ 0}

= {(v1, 0, v3, v4, . . . ) ∈ l2| v1 ≤ 0}.

Ta thấy rằng nếu v = (v1, 0, v3, v4, . . . ) ∈ 0+F và T v = 0 thì (cid:104)c, v(cid:105) = −v2 = 0, tức là (2.36) được thỏa mãn. Vì xk := (− 1 2k2, k, 0, . . . ) ∈ F với mỗi k ≥ 1 và f (xk) = −k nên f không bị chặn dưới trên F . Do đó, bài toán (2.46)

không có nghiệm.

Trong định lí trên các điều kiện (2.37), (2.38) và (2.39) chỉ là điều kiện

đủ chứ không là điều kiện cần để tồn tại nghiệm của bài toán (CQP ). Ta xét

các ví dụ sau đây:

Ví dụ 2.2.27. Xét bài toán

1     min f (x) := (cid:104)x, T x(cid:105) + (cid:104)c, x(cid:105)| x ∈ F (2.47) 2  

trong đó, miền ràng buộc

1     i = 1, 2 , F = (x1, x2, . . . ) ∈ l2, (cid:104)x, Tix(cid:105) + (cid:104)ci, x(cid:105) + αi ≤ 0, 2  

trong đó T x = (0, x2, x3, x4, . . . ), c = (0, 1, 0, 0, . . . ), T1x = (0, x2, x3, . . . ),

c1 = (0, 0, . . . ), α1 = 0, T2x = (0, 0, x3, 0, 0, . . . ), c2 = (1, 0, 0, . . . ), α2 =

∞ (cid:80) n=2

Khi đó, ta có F = {(x1, 0, 0, . . . ) ∈ l2| x1 ≤ 0}. Vì (cid:104)x, T x(cid:105) = x2 n ≥ 0

với mọi x ∈ l2 nên (cid:104)x, T x(cid:105) lồi.

n − x2 x2

1 = (cid:107)x(cid:107)2 − x2

1 và vì thế (cid:104)x, T x(cid:105) là tổng

∞ (cid:80) n=1

Ta có (cid:104)x, T x(cid:105) =

của dạng toàn phương elliptic và dạng toàn phương có hạng hữu hạn. Do đó

(cid:104)x, T x(cid:105) thỏa mãn điều kiện Legrendre. Từ Bổ đề 2.2.17, ta có

0+F = {v ∈ l2|Tiv = 0, (cid:104)ci, v(cid:105) = 0, i = 1, 2}

= {v ∈ (v1, v2, . . . ) ∈ l2| (0, v2, v3, . . . ) = (0, 0, 0, . . . ), v1 ≤ 0}.

Suy ra 0+F = {(v1, 0, 0, . . . ) ∈ l2| v1 ≤ 0} = F . Với mọi x ∈ F ta có

f (x) = 0, suy ra tập nghiệm của bài toán (2.47) là tập ràng buộc F .

Ta thấy rằng bài toán (2.47) có nghiệm trong khi c = (0, 1, 0, 0, . . . ) (cid:54)=

0, (cid:104)c, v(cid:105) = 0 và (cid:104)c2, v(cid:105) (cid:54)= 0, trong đó v := (−1, 0, 0, 0, . . . ). Vậy các điều

kiện (2.37), (2.38) và (2.39) là những điều kiện đủ nhưng không là điều kiện

cần cho sự tồn tại nghiệm của bài toán (CQP ).

Trong các kết quả của sự tồn tại nghiệm của bài toán (CQP )nói trên thì

ta chỉ xét đến các trường hợp mà dạng toàn phương (cid:104)x, T x(cid:105) thỏa mãn điều

kiện Legrendre. Một câu hỏi đặt ra là nếu bỏ giả thiết (cid:104)x, T x(cid:105) thỏa mãn điều

kiện Legrendre thì kết quả tồn tại nghiệm của bài toán (CQP ) sẽ như thế

nào? Vấn đề còn lại chúng ta chứng minh kết quả của sự tồn tại nghiệm của

bài toán (CQP ) dưới đây. Với giả thiết rằng tất cả các dạng toàn phương mà

toán tử tương ứng của nó là có hạng hữu hạn. Như vậy, giả thiết đã rất thu hẹp

nhưng chúng ta có thể sử dụng giả thiết này để nghiên cứu sự tồn tại nghiệm

của lớp các bài toán (CQP ) mà dạng toàn phương của hàm mục tiêu không

cần thỏa mãn điều kiện Legrendre.

Định lí 2.2.28 (Định lí Frank - Wolfe 2). Xét bài toán (CQP ), trong đó T và

Ti, (i = 1, 2, . . . , m) là các toán tử có hạng hữu hạn và nửa các định dương.

Giả sử hàm mục tiêu f bị chặn dưới trên tập ràng buộc F khác rỗng. Khi đó,

bài toán (CQP ) có nghiệm.

Chứng minh. Ta chứng minh định lý bằng quy nạp trên m là số các hàm toàn

phương được xác định trong tập ràng buộc F của bài toán (CQP ).

1     x ∈ F | f (x) ≤ f ∗ + . Vì Với m = 1: Với mỗi k, xét tập Sk = k  

f ∗ > −∞ nên tồn tại {xk} ⊂ H sao cho

1 1 f (xk) = (cid:104)xk, T xk(cid:105) + (cid:104)c, xk(cid:105) ≤ f ∗ + , (2.48) 2 k

g1(xk) = 1 (cid:104)xk, T1xk(cid:105) + (cid:104)c1, xk(cid:105) + α1 ≤ 0. 2

Vì vậy xk ∈ Sk nên Sk khác rỗng, lồi và đóng. Do đó Sk chứa phần tử có

chuẩn nhỏ nhất.

Giả sử xk là phần tử có chuẩn nhỏ nhất trong Sk. Nếu {xk} bị chặn thì {xk} có dãy con hội tụ yếu. Không mất tính tổng quát, ta giả sử xk hội tụ yếu

đến x. Vì T và T1 là các toán tử có hạng hữu hạn nên chúng là compact. Do

đó f (x) và g1(x) là những hàm liên tục yếu. Do đó, lấy giới hạn trong (2.48) khi xk (cid:42) x ta thấy rằng f (x) ≤ f ∗; g1(x) ≤ 0. Suy ra x là nghiệm của bài

toán (CQP ).

Xét trường hợp {xk} không bị chặn, không mất tính tổng quát ta giả sử

xk xk → −∞ khi k → ∞ và (cid:107)xk(cid:107) (cid:54)= 0, ∀k. Đặt vk := , ta có (cid:107)vk(cid:107) = 1, (cid:107)xk(cid:107)

suy ra {vk} bị chặn nên tồn tại một dãy con hội tụ yếu đến v. Không mất tính tổng quát ta giả sử vk (cid:42) v khi k → ∞. Vì T và T1 nửa xác định dương,

chứng minh tương tự như Định lý 2.2.20, ta có

T v = 0, (cid:104)c, v(cid:105) = 0, T1v = 0, (cid:104)c1, v(cid:105) ≤ 0.

Ta sẽ chứng minh (cid:104)c1, v(cid:105) < 0. Giả sử ngược lại (cid:104)c1, v(cid:105) = 0. Thì T v =

0, (cid:104)c, v(cid:105) = 0, T1v = 0, (cid:104)c1, v(cid:105) = 0.

Xét L1 = H ⊕ H ⊕ R2, trong đó ⊕ là tổng trực tiếp trong không gian

Hilbert và xét (cid:104)., .(cid:105) và (cid:107).(cid:107)L là tích vô hướng và chuẩn trong L.

Xét A : H → L1 được định nghĩa bởi

Ax = (T x, T1x, (cid:104)c, x(cid:105), (cid:104)c1, x(cid:105)).

Vì T và T1 là các toán tử có hạng hữu hạn nên A cũng là toán tử có hạng hữu

hạn. Với mỗi k, xét hệ phương trình tuyến tính

Ax = Axk. (2.49)

Vì A là toán tử có hạng hữu hạn nên A là toán tử compact với miền đóng (theo Nhận xét 2.2.16 ). Do đó, tồn tại toán tử liên tục giả đảo A+ của A và xk là nghiệm của (2.49) sao cho xk = A+Axk. Do đó, tồn tại ρ > 0 phụ thuộc vào

A sao cho

(cid:1) . (cid:107)xk(cid:107) < ρ (cid:0)(cid:107)Axk(cid:107)L

Suy ra

(cid:107)xk(cid:107) ≤ ρ (cid:0)(cid:107)T xk(cid:107) + (cid:107)T1xk(cid:107) + |(cid:104)c, xk(cid:105)| + |(cid:104)c1, xk(cid:105)|(cid:1) .

Từ (2.49) và Axk = Axk suy ra

1 f (xk) = f (xk) ≤ f ∗ + . k

Vì xk là phần tử có chuẩn nhỏ nhất trong Sk nên

(cid:107)xk(cid:107) ≤ (cid:107)xk(cid:107) ≤ ρ (cid:0)(cid:107)T xk(cid:107) + (cid:107)T1xk(cid:107) + |(cid:104)c, xk(cid:105)| + |(cid:104)c1, xk(cid:105)|(cid:1) , ∀k.

Theo giả thiết T và T1 là các toán tử có hạng hữu hạn nên T và T1 là compact với miền đóng. Chia các vế của bất đẳng thức trên cho (cid:107)xk(cid:107), cho k → ∞ và

theo tính compact của T, T1 ta có

1 ≤ ρ ((cid:107)T v(cid:107) + (cid:107)T1v(cid:107) + |(cid:104)c, v(cid:105)| + |(cid:104)c1, v(cid:105)|) .

Điều này mâu thuẫn với T v = 0, (cid:104)c, v(cid:105) = 0, T1v = 0, (cid:104)c1, v(cid:105) = 0. Do đó

(cid:104)c1, v(cid:105) < 0.

Xét bài toán quy hoạch toàn phương

1     min f (x) := (cid:104)x, T x(cid:105) + (cid:104)c, x(cid:105)| x ∈ H . 2  

Nếu f bị chặn dưới trên không gian Hilbert H thì theo Bổ đề 2.2.19, tồn tại x ∈ H sao cho f (x) ≤ f ∗. Nếu f không bị chặn dưới trên H thì tồn tại ˆx ∈ H sao cho f (ˆx) ≤ f ∗. Do đó, trong cả hai trường hợp ta đều suy ra tồn tại x∗ ∈ H sao cho f (x∗) ≤ f ∗.

Vì (cid:104)c1, v(cid:105) < 0 và t > 0 nên

g1(x∗ + tv) = 1 (cid:104)x∗ + tv, T1(x∗ + tv)(cid:105) + (cid:104)g, x∗ + tv(cid:105) + α1 2

1 t = (cid:104)x∗, T1x∗(cid:105) + (cid:104)x∗ + tv, T v(cid:105) + (cid:104)c1, x∗(cid:105) + α1 + t(cid:104)c1, v(cid:105) 2 2

= g1(x∗) + t(cid:104)c1, v(cid:105) → −∞ khi t → +∞

Suy ra x∗ + tv ∈ F với t > 0 đủ lớn. Chọn t∗ > 0 sao cho x∗ + t∗v ∈ F , theo

(2.48) ta có

1 f (x∗ + t∗v) = (cid:104)x∗ + t∗v, T (x∗ + t∗v)(cid:105) + (cid:104)c, x∗ + t∗v(cid:105) 2

t∗ t∗ 1 = (cid:104)x∗, T x∗(cid:105) + (cid:104)c, x∗(cid:105) + (cid:104)x∗ + t∗v, T v(cid:105) + (cid:104)x∗, T v(cid:105) + t∗(cid:104)c, v(cid:105) 2 2 2

1 = (cid:104)x∗, T x∗(cid:105) + (cid:104)c, x∗(cid:105) ≤ f ∗. 2

Điều này chứng tỏ rằng x∗ + t∗v là nghiệm của bài toán (CQP ) trong trường

hợp m = 1.

Giả sử rằng khẳng định đúng cho tất cả các tập ràng buộc F xác định bởi

m − 1 hàm toàn phương và xét F được xác định bởi m hàm toàn phương. Đặt 1   x ∈ F | f (x) ≤ f ∗ + f ∗ = inf{f (x)| x ∈ F } > −∞. Ta định nghĩa Sk = k    . 

Vì f ∗ > −∞ nên Sk khác rỗng, lồi và đóng. Do đó Sk chứa phần tử có chuẩn nhỏ nhất. Gọi xk là phần tử có chuẩn nhỏ nhất trong Sk, ta có

1 1 f (xk) = (cid:104)xk, T xk(cid:105) + (cid:104)c, xk(cid:105) ≤ f ∗ + , k 2

1 i = 1, 2, . . . , m. (cid:104)xk, T xk(cid:105) + (cid:104)ci, xk(cid:105) + αi ≤ 0, gi(xk) = 2

Nếu {xk} bị chặn thì nó có dãy con hội tụ yếu. Không mất tính tổng quát, ta giả sử xk (cid:42) x. Khi đó, dễ dàng kiểm tra được x là nghiệm của bài toán

(CQP ) (từ các đẳng thức trên ta cho k → ∞).

Xét trường hợp {xk} không bị chặn. Không mất tính tổng quát ta giả sử

xk xk → +∞ khi k → +∞ và (cid:107)xk(cid:107) (cid:54)= 0. Đặt vk = , có (cid:107)vk(cid:107) = 1. Suy ra (cid:107)xk(cid:107)

{vk} bị chặn, suy ra tồn tại dãy con hội tụ yếu. Không mất tính tổng quát ta giả sử vk (cid:42) v khi k → ∞. Vì T và Ti là nửa xác định dương, chứng minh

tương tự trường hợp m = 1 ta có

i = 1, 2, . . . , m, T v = 0, (cid:104)c, v(cid:105) = 0, Tiv = 0, (cid:104)ci, v(cid:105) ≤ 0,

và tồn tại j = {1, 2, . . . , m} sao cho (cid:104)cj, v(cid:105) < 0. Không mất tính tổng quát,

ta giả sử (cid:104)cm, v(cid:105) < 0.

Xét bài toán

1     , min f (x) = (cid:104)x, T x(cid:105) + (cid:104)c, x(cid:105)| x ∈ F1 (P1) 2  

trong đó F1 := {x ∈ H : gi(x) ≤ 0, i = 1, 2, . . . , m − 1}.

Với bài toán này, f bị chặn dưới trên F1 hoặc không bị chặn dưới trên

F1. Nếu f bị chặn dưới trên F1 thì theo giả thiết quy nạp, suy ra bài toán

(P1) có nghiệm. Còn nếu f không bị chặn dưới trên F1 thì ∃ˆx ∈ F1 sao cho f (ˆx) ≤ f ∗. Như vậy f bị chặn dưới trên F1 hoặc không bị chặn dưới trên F1 đều tồn tại x ∈ F1 sao cho f (x) ≤ f ∗.

Xét vectơ x(t) := x + tv, t ≥ 0. Ta có (cid:104)c, v(cid:105) = 0,

f (x(t)) = f (x) + t(cid:104)c, v(cid:105) = f (x) ≤ f ∗, ∀t > 0.

Vì

gm(x(t)) = gm(x) + t(cid:104)cm, v(cid:105),

và (cid:104)cm, v(cid:105) < 0 nên ta có thể chọn t∗ > 0 đủ lớn sao cho gm(x(t))+t∗(cid:104)cm, v(cid:105) ≤ 0 hay x(t∗) ∈ F và f (x(t∗)) ≤ f ∗. Điều này chứng tỏ rằng x(t∗) là nghiệm

của bài toán (CQP ). Định lí được chứng minh hoàn toàn.

Nhận xét 2.2.29. Trong Ví dụ 2.2.22, T là toán tử compact trên miền không

đóng, do vậy T là toán tử có hạng không hữu hạn, suy ra bài toán (CQP )

không có nghiệm. Điều này chứng tỏ rằng Định lí 2.2.28 sẽ không còn đúng

nữa nếu ta thay giả thiết T và Ti là những toán tử có hạng hữu hạn bởi giả

thiết T và Ti là compact, i = 1, 2, . . . , m.

Trong trường hợp T = 0 và Ti = 0 (i = 1, 2, . . . , m), ta được kết quả của

sự tồn tại nghiệm của bài toán quy hoạch tuyến tính (LP )trong không gian

Hilbert.

Hệ quả 2.2.30. Xét bài toán quy hoạch tuyến tính (LP ) (là bài toán (CQP )

trong trường hợp T = 0 và Ti = 0 i = 1, 2, . . . , m). Giả sử f (x) bị chặn dưới

trên tập F khác rỗng. Khi đó, bài toán (CQP ) có nghiệm.

Nhận xét 2.2.31. Nếu H là không gian Hilbert hữu hạn chiều thì mọi toán tử

liên tục T trên H đều hữu hạn chiều và (cid:104)x, T x(cid:105) thỏa mãn điều kiện Legrendre.

Vì thế nên nếu H là hữu hạn chiều thì Định lí 2.2.20 và Định lý 2.2.28 là trùng

nhau.

Kết luận

Trong luận văn tôi đã trình bày được các kết quả sau:

(1) Trình bày một số kiến thức cơ bản về không gian Hilbert; tập lồi và

hàm lồi trong không gian Hilbert; hàm toàn phương.

(2) Trình bày và chứng minh các định lí Frank - Wolfe, định lí Eaves về sự

tồn tại nghiệm của bài toán quy hoạch toàn phương với ràng buộc tuyến tính.

(3) Trình bày và chứng minh các định lí Frank - Wolfe 1, định lí Eaves,

định lí Frank - Wolfe 2 về sự tồn tại nghiệm của bài toán quy hoạch toàn

phương lồi với hữu hạn ràng buộc toàn phương lồi trong không gian Hilbert

thực.

Tài liệu tham khảo

Tiếng Việt

[1] Nguyễn Văn Hiền, Lê Dũng Mưu và Nguyễn Hữu Điển (2014), Giải tích

lồi ứng dụng, Nhà xuất bản Đại học Quốc gia Hà Nội.

[2] Nguyễn Thị Bạch Kim (2008), Giáo trình các phương pháp tối ưu - Lý

thuyết và thuật toán, Nhà xuất bản Bách khoa và Kỹ thuật.

[3] Lê Dũng Mưu (1998), Giáo trình các phương pháp tối ưu, Nhà xuất bản

Khoa học và Kỹ thuật Hà Nội.

[4] Trần Vũ Thiệu, Nguyễn Thị Thu Thủy (2011), Nhập môn tối ưu phi

tuyến, Nhà xuất bản Đại học Quốc gia Hà Nội.

Tiếng Anh

[5] Bertsekas D. P. (2003), Convex Analysis and Optimization, Springer.

[6] Dong V. V. and Tam N. N. (2016), "On the Solution Existence of Con-

vex Quadratic Programming Problems in Hilbert Spaces", Taiwanese

Journal Of Mathematics, Vol. 20, No. 6, pp. 1417-1436.

[7] Heinz H. B. and Patrick L. C. (2011), Convex Analysis and Monotone

Opetator Theory in Hilbert Spaces, Springer.

Luận văn Thạc sĩ Toán học: Một vài kết quả về sự tồn tại nghiệm của bài toán quy hoạch toàn phương

Mục lục

Danh sách ký hiệu

Mở đầu

Chương 1

Kiến thức chuẩn bị

1.1 Không gian Hilbert

1.1.1 Không gian tiền Hilbert

1.1.2 Không gian Hilbert

1.1.3 Các ví dụ

1.1.4 Một vài tính chất cơ bản

1.2 Tập lồi và hàm lồi trong không gian Hilbert

1.2.1 Tập lồi

1.2.2 Hàm lồi

1.3 Hàm toàn phương

Chương 2

Bài toán quy hoạch toàn phương

2.1 Giới thiệu bài toán

2.1.1 Phát biểu bài toán

2.2 Các định lí về sự tồn tại nghiệm

2.2.1 Bài toán quy hoạch toàn phương với ràng buộc tuyến tính

2.2.2 Bài toán quy hoạch toàn phương lồi với hữu hạn ràng buộc

toàn phương lồi trong không gian Hilbert thực

Kết luận

Tài liệu tham khảo

Tiếng Việt

Tiếng Anh

Có thể bạn quan tâm

Luận văn Thạc sĩ: Quản lý hoạt động phát triển nhận thức cho trẻ mẫu giáo ở các trường mầm non, huyện Hoàng Su Phì, tỉnh Hà Giang

Bài giảng điện tử Phương pháp tính: Số gần đúng và sai số

Bài giảng điện tử Phương pháp tính: Phương trình phi tuyến

Bài giảng điện tử Phương pháp tính: Hệ phương trình tuyến tính

Bài giảng điện tử Phương pháp tính: Đạo hàm và tích phân

Bài giảng điện tử Phương pháp tính: Nội suy và xấp xỉ hàm

Bài giảng điện tử Phương pháp tính: Phương trình vi phân thường

Bài giảng Nhóm phương pháp tính: Chương 1 - Đại học Bách khoa Hà Nội

Bài giảng Nhóm phương pháp tính: Chương 2 - Đại học Bách khoa Hà Nội

Bài giảng Nhóm phương pháp tính: Chương 3 - Đại học Bách khoa Hà Nội

Bài giảng Nhóm phương pháp tính: Chương 4 - Đại học Bách khoa Hà Nội

Bài giảng Nhóm phương pháp tính: Chương 5 - Đại học Bách khoa Hà Nội

Bài giảng Nhóm phương pháp tính: Chương 6 - Đại học Bách khoa Hà Nội

Luận văn Thạc sĩ tóm tắt: Pháp luật về điều kiện đầu tư kinh doanh trong lĩnh vực giáo dục, đào tạo ở Việt Nam

Luận văn Thạc sĩ: Sự nghiệp nghiên cứu phê bình văn học của Hoài Thanh

Luận văn Thạc sĩ: Tiểu thuyết của Đỗ Phấn từ góc nhìn sinh thái

Luận văn Thạc sĩ: Giải pháp ứng phó với nhập cư ở Liên minh Châu Âu

Luận văn Thạc sĩ: Diễn ngôn về giới nữ trong văn xuôi nữ Việt Nam đương đại (khảo sát sáng tác của Dạ Ngân, Y Ban, Lý Lan, Nguyễn Thị Thu Huệ)

Luận văn Thạc sĩ: Xây dựng mức phát thải tham chiếu rừng khu vực huyện Bảo Lâm tỉnh Lâm Đồng

Luận văn Thạc sĩ: Đặc điểm nhân vật chính trong ba tác phẩm của Franz Kafka: Lâu đài, Vụ án, Hóa thân

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS

Luận án Tiến sĩ: Ứng dụng phản ứng Domino vào tổng hợp các dẫn xuất Podophyllotoxin, Pyrimidine và đánh giá hoạt tính sinh học của các chất tổng hợp được

Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và một số hoạt tính sinh học của cây chùm ngây (Moringa oleifera)

Tóm tắt Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và ứng dụng ức chế ăn mòn cho thép của cao chiết xuất từ cây Lộc vừng thuộc họ Lecythidaceae

Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ