Hiệu chỉnh bài toán bù tổng quát

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM

KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM

HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ

NGUYỄN THỊ THÚY HOA

HIỆU CHỈNH BÀI TOÁN BÙ TỔNG QUÁT

Chuyên ngành: Toán ứng dụng

Mã số: 62460112

LUẬN ÁN TIẾN SĨ TOÁN HỌC

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

1. GS.TS Nguyễn Bường

2. TS. Nguyễn Công Điều

HÀ NỘI - NĂM 2016

ii

LỜI CAM ĐOAN

Các kết quả trình bày trong luận án là công trình nghiên cứu của tôi,

được hoàn thành dưới sự hướng dẫn của GS.TS. Nguyễn Bường và TS.

Nguyễn Công Điều. Các kết quả trình bày trong luận án là mới và chưa

từng được công bố trong các công trình của người khác.

Tôi xin chịu trách nhiệm về những lời cam đoan của mình.

Tác giả

Nguyễn Thị Thúy Hoa

iii

LỜI CẢM ƠN

Luận án này được hoàn thành tại Viện Công nghệ thông tin, Học viện

Khoa học và Công nghệ thuộc Viện Hàn lâm Khoa học và Công nghệ

Việt Nam dưới sự hướng dẫn tận tình của GS.TS. Nguyễn Bường và TS.

Nguyễn Công Điều. Tác giả xin bày tỏ sự kính trọng và lòng biết ơn sâu

sắc nhất tới hai thầy.

Tác giả cũng xin bày tỏ lòng biết ơn tới các thầy, cô giáo thuộc Viện

Công nghệ thông tin, Viện Toán học, Học viện Khoa học và Công nghệ

đã tạo điều kiện, giúp đỡ tác giả trong quá trình học tập và nghiên cứu.

Tác giả xin chân thành cảm ơn Ban Giám hiệu trường Đại học Nội vụ

Hà Nội, Trung tâm Tin học, nơi tác giả đang công tác, đã tạo điều kiện

thuận lợi để tác giả hoàn thành luận án.

Cảm ơn các anh chị em nghiên cứu sinh, bạn bè đồng nghiệp đã trao

đổi những kiến thức và kinh nghiệm trong thời gian tác giả học tập, nghiên

cứu tại Viện Công nghệ Thông tin.

Cuối cùng, tác giả xin bày tỏ lòng biết ơn sâu sắc tới những người thân

trong gia đình đã luôn động viên, chia sẻ và khích lệ tác giả trong quá

trình nghiên cứu.

Tác giả

Nguyễn Thị Thúy Hoa

Mục lục

Trang bìa phụ i

Lời cam đoan ii

Lời cảm ơn iii

Mục lục iv

Một số ký hiệu và viết tắt vi

Mở đầu 1

Chương 1. Một số kiến thức chuẩn bị 7

1.1. Một số khái niệm . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2. Bài toán đặt không chỉnh và phương pháp hiệu chỉnh . . . . 8

1.2.1. Khái niệm bài toán đặt không chỉnh . . . . . . . . . 8

1.2.2. Phương pháp hiệu chỉnh Tikhonov . . . . . . . . . . 9

1.2.3. Phương pháp hiệu chỉnh Tikhonov cho bài toán cực

trị tổng quát . . . . . . . . . . . . . . . . . . . . . . 10

1.3. Bài toán bù . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3.1. Bài toán bù tuyến tính . . . . . . . . . . . . . . . . . 12

1.3.2. Bài toán bù phi tuyến . . . . . . . . . . . . . . . . . 18

Chương 2. Bài toán bù tổng quát và phương pháp hiệu chỉnh 39

2.1. Vấn đề tồn tại nghiệm của bài toán bù tổng quát . . . . . . 39

2.2. Hiệu chỉnh bài toán bù tổng quát . . . . . . . . . . . . . . . 40

2.2.1. Hiệu chỉnh bài toán bù tổng quát dựa trên phiếm

hàm Tikhonov . . . . . . . . . . . . . . . . . . . . . . 40

2.2.2. Hiệu chỉnh bài toán bù tổng quát có ràng buộc . . . 49

2.3. Một số bài toán dẫn tới bài toán bù . . . . . . . . . . . . . . 52

v

Chương 3. Bài toán cực trị với ràng buộc là bài toán bù tổng

quát 62

3.1. Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . 62

3.2. Phương pháp hiệu chỉnh Tikhonov cho bài toán đặt ra . . . 67

3.3. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . . 72

Kết luận chung 79

Kiến nghị hướng nghiên cứu tiếp theo 80

Danh mục các công trình đã công bố liên quan đến luận án 81

Tài liệu tham khảo 82

Một số ký hiệu và viết tắt

R

n

không gian Ơclit n - chiều

R

n×m không gian các ma trận cấp n × m

R tập hợp các số thực

R+ tập hợp các số thực không âm

R++ tập hợp các số thực dương

x

T

chuyển vị của véctơ x

{x

k

} dãy các véctơ x

1

, x2

, x3

, . . .

k.k chuẩn trong không gian R

n

hx, yi tích vô hướng của x và y trong R

n

y ≤ 0 các thành phần yi ≤ 0, i = 1, 2, . . . , n

∇θ



∂θ

∂xj



− gradient của hàm θ : R

n → R

A

T

chuyển vị của ma trận A

PC(x) phép chiếu mêtric phần tử x lên tập đóng lồi C

V I(., .) bài toán bất đẳng thức biến phân

LCP(., .) bài toán bù tuyến tính

NCP(.) bài toán bù phi tuyến

P NCP(., .) bài toán bù phi tuyến nhiễu

GCP(., .) bài toán bù tổng quát

CGCP bài toán bù tổng quát có ràng buộc là tập C đóng, lồi

MP EC bài toán cực trị với ràng buộc là bài toán bù tổng quát

R(., .) toán tử hiệu chỉnh

H(., .) khoảng cách Hausdorff

x

∗ − MNS x∗

- chuẩn nhỏ nhất

x

∗ − CMNS x∗

- C chuẩn nhỏ nhất

Mở đầu

Trong các ấn phẩm về toán, có thể tìm thấy các trường hợp riêng của

bài toán bù rất sớm vào những năm 1940, tuy nhiên bài toán bù chỉ thực

sự thu hút các nhà toán học từ đầu năm 1960 [10], khi bài toán trở thành

một chủ đề nghiên cứu riêng.

Bài toán bù có nguồn gốc từ bài toán bất đẳng thức biến phân, bài toán

quy hoạch toàn phương, bài toán cân bằng thị trường, bài toán điểm dừng

tối ưu, trò chơi song ma trận,...[10] và nó có nhiều ứng dụng trong các lĩnh

vực như: kinh tế, tài chính, kỹ thuật, vật lý, sinh thái và điều khiển tối

ưu,... Chính vì vậy, việc nghiên cứu bài toán bù hiện nay vẫn đang là vấn

đề thời sự [15], [20], [24], [25], đặc biệt là việc nghiên cứu tìm ra phương

pháp giải bài toán bù sao cho hiệu quả.

Trong bối cảnh đó, luận án này đề cập tới phương pháp hiệu chỉnh

Tikhonov cho bài toán bù tổng quát, đó là bài toán: tìm x˜ ∈ R

n

sao cho

g(˜x) ≤ 0, h(˜x) ≤ 0,hg(˜x), h(˜x)iRm = 0, (0.1)

ở đây g(x), h(x) là hai hàm liên tục từ không gian R

n

tới không gian R

m,

h., .i, k.kRn lần lượt là tích vô hướng và chuẩn trong R

n

; và phương pháp

hiệu chỉnh bài toán cực trị với ràng buộc là bài toán bù tổng quát, được

phát biểu như sau: tìm một phần tử x˜ ∈ C ∩ S˜, thỏa mãn điều kiện

ϕ(˜x) = min

y∈C˜

ϕ(y), C˜ = C ∩ S, ˜ (0.2)

ở đây C là tập đóng, lồi trong không gian Ơclit R

n

, S˜ = S˜

1 ∩ S˜

2, trong đó

S˜

1 = {x ∈ R

n

: ˜g(x) ≤ 0, h˜(x) = 0},

S˜

2 = {x ∈ R

n

: g(x) ≤ 0, h(x) ≤ 0,hg(x), h(x)iRq = 0},

(0.3)

các hàm thực ϕ : R

n −→ R, g˜ : R

n −→ R

m, h˜ : R

n −→ R

p

, g và h : R

n −→

R

q

là liên tục, ký hiệu y = (y1, y2, ..., ym) ≤ 0 có nghĩa là yi ≤ 0 với mọi

2

i = 1, 2, ..., m. Ta giả thiết tập nghiệm của các bài toán (0.1), (0.2) và (0.3)

khác rỗng.

Những bài toán có dạng (0.2)-(0.3) được biết đến như những bài toán

với ràng buộc bù, ký hiệu là MPEC. Thông thường, một bài toán MPEC

là bài toán tối ưu với ràng buộc là bất đẳng thức biến phân. Tuy nhiên,

trong một số trường hợp MPEC có thể viết dưới dạng (0.2)-(0.3) [38].

Trong trường hợp đặc biệt, khi m = n, g(x) = −x và h(x) = −F(x),

trong đó F : R

n −→ R

n

là ánh xạ affin, nghĩa là

F(x) = Mx + q, M ∈ R

n×n

, q ∈ R

n

,

bài toán (0.1) được gọi là bài toán bù tuyến tính, ký hiệu bởi LCP(q, M).

Tìm hiểu nghiệm của bài toán này, Olsson D. [44] đã thu được các kết quả

sau.

Định lí 0.1 Khi M ∈ R

n×n

là P - ma trận với tất cả các định thức con

chính của M dương thì LCP(q, M) có một nghiệm với q ∈ R

n

.

Định lí 0.2 Nếu q không âm thì bài toán bù tuyến tính LCP(q, M) luôn

giải được và x = 0 là một nghiệm tầm thường của nó.

Nghiên cứu mối quan hệ giữa bài toán bù tuyến tính và bài toán bất

đẳng thức biến phân, ký hiệu bởi V I(K, F), là bài toán tìm một vectơ

x ∈ K ⊂ R

n

sao cho

hy − x, F(x)i ≥ 0, ∀y ∈ K,

ở đây F : K −→ R

n

là hàm liên tục và K là tập đóng, lồi, Olsson D. [44]

đã chứng minh tiếp được kết quả dưới đây.

Định lí 0.3 Nếu F = Mx + q, M ∈ R

n×n

, q ∈ R

n

, x ∈ R

n

+ thì V I(F, R

n

+)

và bài toán bù tuyến tính LCP(q, M) có nghiệm hoàn toàn trùng nhau.

Khi n = m, g(x) = −x và h(x) = −F(x) trong đó F là ánh xạ phi

tuyến từ R

n vào R

n

, bài toán (0.1) được gọi là bài toán bù phi tuyến, ký

hiệu bởi NCP(F), đó là bài toán tìm vectơ x ∈ R

n

sao cho

x ≥ 0, F(x) ≥ 0,hx, F(x)i = 0, (0.4)

các nhà khoa học cũng đã tìm ra rất nhiều phương pháp giải cho loại bài

toán này [13], [17], [18], [23], [33]-[35]. Tất cả các phương pháp đưa ra đều

3

dẫn tới giải một bài toán cực tiểu hoặc một hệ phương trình tương đương.

Có thể chia thành lớp các phương pháp sau:

• Phương pháp sử dụng hàm khoảng

Trong phương pháp này, họ đã biến đổi bài toán NCP(F) thành bài

toán tương đương nhờ một hàm được gọi là hàm khoảng (merit function)

để đưa về bài toán tìm cực tiểu có ràng buộc của một phiếm hàm. Công cụ

thuận tiện để thiết lập hàm khoảng là C - hàm [12], đó là hàm φ : R

2 −→ R

thỏa mãn tính chất:

φ(a, b) = 0 ⇐⇒ ab = 0, a ≥ 0, b ≥ 0.

Có một số C - hàm sau:

φNR(a, b) = min{a, b};

φMS(a, b) = ab +

1

2α

￾

max{0, a − αb}

2 − a

2 + max{0, b − αa}

2 − b

2

, α > 1;

φF B(a, b) = p

a

2 + b

2 − a − b.

Hàm khoảng được xây dựng trên hàm φNR được gọi là hàm số dư tự

nhiên. Hàm φMS không âm trên R

2 và hàm khoảng được xây dựng trên nó

gọi là hàm Lagrange ẩn được giới thiệu bởi Mangasarian và Solodov [41].

Hàm φF B được gọi là hàm Fischer [16]. Gần đây, dựa trên hàm φF B nhiều

nhà khoa học đã mở rộng nghiên cứu và đưa ra một số hàm mới có tính

chất tốt hơn. Luo và Tseng [39] đã đưa ra một lớp các hàm khoảng mới

˜f : R

n −→ R xác định bởi

˜f(x) = ψ0(hx, F(x)iRn ) +Xn

i=1

ψi(−xi

, −Fi),

ở đây ψ0 : R −→ [0,∞) và ψi

: R

2 −→ [0,∞), i = 1, 2, ..., n là các hàm liên

tục. Ý tưởng mới này cũng được Kanzow C., Yamashita N. và Fukushima

M. [32] sử dụng để xây dựng hàm khoảng mới.

• Phương pháp hiệu chỉnh

Thay vì tìm nghiệm trực tiếp, phương pháp này tìm nghiệm của dãy

các bài toán đặt chỉnh mà những nghiệm của chúng sẽ hội tụ tới nghiệm

của bài toán ban đầu. Lược đồ hiệu chỉnh Tikhonov trong [11], [22] đối với

bài toán bù bao gồm việc giải dãy các bài toán:

x ≥ 0, Fε(x) ≥ 0,hx, Fε(x)iRn = 0, (0.5