Gradient suy rộng và ứng dụng vào bài toán tối ưu không trơn

Gradient suy rộng và ứng dụng vào bài toán tối ưu không trơn

TRƯỜNG ĐẠI HỌC KHOA HỌC

ĐẶNG HIẾU TRỌNG

GRADIENT SUY RỘNG VÀ ỨNG DỤNG VÀO BÀI TOÁN

TỐI ƯU KHÔNG TRƠN

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

THÁI NGUYÊN - NĂM 2010

TRƯỜNG ĐẠI HỌC KHOA HỌC

ĐẶNG HIẾU TRỌNG

GRADIENT SUY RỘNG VÀ ỨNG DỤNG VÀO BÀI TOÁN

TỐI ƯU KHÔNG TRƠN

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

Mục lục

1.1 Định nghĩa và ký hiệu 3

1.2 Một số tính chất cơ bản của gradient suy rộng 8

2 Một số phương pháp giải bài toán tối ưu không trơn 11 2.1 Nội dung bài toán 11

2.2 Điều kiện tối ưu 14

2.3 Một số phương pháp giải bài toán tối ưu không trơn 18

2.3.1 Phương pháp dưới gradient 18

2.3.2 Phương pháp siêu phẳng cắt 25

2.3.3 Phương pháp bó 27

2.3.4 Phương pháp miền tin cậy đối với hàm hợp không trơn 30

2.3.5 Phương pháp Newton không trơn 38

Kết luận 46

Tài liệu tham khảo 47

Lời cảm ơn

Bản luận văn này được hoàn thành tại trường Đại học Khoa Học Đại học Thái Nguyên dưới sự hướng dẫn trực tiếp của GS.TS Trần VũThiệu Viện toán học - Viện KHCN Việt Nam Tác giả xin bày tỏ lòngkính trọng và biết ơn sâu sắc tới Thầy về sự hướng dẫn tận tình trongsuốt thời gian tác giả làm luận văn

-Tác giả xin bày tỏ lòng biết ơn tới các Thầy Cô ở Viện toán học - ViệnKHCN Việt Nam, Viện công nghệ thông tin, Khoa công nghệ thông tin,Khoa toán và Phòng đào tạo sau đại học trường Đại học Khoa Học -Đại học Thái Nguyên đã tận tình giảng dạy và tạo mọi điều kiện thuậnlợi cho tác giả trong quá trình học tập tại trường

Tác giả xin gửi lời cảm ơn tới Ban giám đốc trung tâm Giáo dụcthường xuyên Hưng Hà - Thái Bình và các Thầy Cô trong trung tâm đãtạo điều kiện giúp đỡ tác giả trong suốt thời gian học

Xin chân thành cảm ơn anh chị em học viên lớp cao học và các bạn

bè đồng nghiệp về những đóng góp quý báu, sự giúp đỡ tận tình và sự

cổ vũ hết sức to lớn trong suốt quá trình học tập, nghiên cứu và làmluận văn

được gọi là bài toán tối ưu không trơn nếu hàm mục tiêu f (x) hay một

Như chúng ta đã biết với bài toán tối ưu trơn, do các hàm khả vi córất nhiều tính chất đẹp, do đó các phương pháp giải đối với bài toánnày đã được xây dựng và phát triển khá hoàn thiện Nhưng với bài toántối ưu không trơn thì việc xây dựng các phương pháp giải gặp rất nhiều

giản Tuy nhiên, bài toán tối ưu không trơn có tính ứng dụng thực tiễnrất cao Vì vậy, xây dựng phương pháp giải cho bài toán tối ưu khôngtrơn thu hút rất nhiều người làm toán quan tâm Chính vì lẽ đó mà tácgiả đã chọn đề tài "Gradient suy rộng và ứng dụng vào bài toán tối ưukhông trơn"

Mục đích của luận văn này là trình bày những kiến thức ban đầu vềtối ưu không trơn, đề cập tới điều kiên tối ưu không trơn và giới thiệumột số phương pháp bằng số giải bài toán tối ưu không trơn

Luận văn được chia làm hai chương

Chương 1: Gradient suy rộng

Trong chương này, tác giả trình bày một số khái niệm về hàm Lipschitz,đạo hàm theo hướng, đạo hàm theo hướng Dini trên, đạo hàm suy rộng

theo hướng và các tính chất, khái niệm vi phân suy rộng, gradient suyrộng Các tính chất cơ bản của gradient suy rộng, mối liên hệ giữa viphân suy rộng và dưới vi phân.

Chương 2: Một số phương pháp giải toán tối ưu không trơn.Trong chương này, tác giả trình bày một số ví dụ về bài toán tối ưukhông trơn và những khó khăn gặp phải khi giải bài toán này Xây dựngđiều kiện cần và đủ tối ưu cho bài toán tối ưu không trơn dựa trên tập

vi phân suy rộng Trình bày một số phương pháp giải bài toán như:phương pháp dưới gradient, phương pháp bó, phương pháp siêu phẳngcắt, phương pháp miền tin cậy đối với hàm hợp không trơn, phươngpháp Newton

Bản luận văn này được hoàn thành dưới sự hướng dẫn tận tình củaGS.TS Trần Vũ Thiệu Tác giả hi vọng rằng một phần kiến thức nhỏcủa luận văn sẽ là tài liệu tham khảo cho các bạn sinh viên, những ngườiquan tâm yêu thích đề tài này

Mặc dù tác giả đã cố gắng hết sức nhưng kết quả đạt được trong luậnvăn còn rất khiêm tốn, trong quá trình viết luận văn cũng như xử lývăn bản chắc chắn không tránh khỏi những sai sót nhất định, tác giả rấtmong nhận được những ý kiến đóng góp quý báu của các Thầy Cô vàcác bạn bè đồng nghiệp để luận văn được hoàn thiện hơn

Định nghĩa 1.2 Đạo hàm của hàm f theo phương d tại x ký hiệu là

f0(x, d) = lim

t↓0

f (x + td) − f (x)

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

Có thể thấy một hàm có tính Lipschitz ở gần một điểm không nhấtthiết khả vi tại điểm đó và có thể không có đạo hàm theo hướng theonghĩa cổ điển vừa nêu.

Định nghĩa 1.3 Đạo hàm theo hướng Dini trên của f tại x theo hướng

f(D)(x, d) = lim

t↓0 supf (x + td) − f (x)

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

Định nghĩa 1.4 Cho f là hàm Lipschitz ở gần x và d là một vecto bất

kì trong X Đạo hàm suy rộng theo hướng của f tại x theo hướng d, ký

f0(x, d) = limy→x

t↓0

ttrong đó y là vecto thuộc X và t là một số dương và t ↓ 0 được hiểu là tđơn điệu giảm tới 0

Vì đạo hàm suy rộng theo hướng do Clarke nêu ra nên đạo hàm

Nhận xét 1.1 i) Nếu f (x) là một hàm Lipschitz địa phương thì đạohàm theo hướng có thể không tồn tại nhưng đạo hàm theo hướng Dini vàđạo hàm theo hướng Clarke luôn tồn tại và ta có hệ thức

Bổ đề 1.1 Nếu f (x) là hàm Lipschitz ở gần x thì

mãn điều kiện

|f0(x, d)| ≤ K k d k

iii) f0(x, d) là nửa liên tục trên theo (x, d)

iv) f0(x, −d) = (−f )0(x, d)

Chứng minh i) Thật vậy, với λ > 0 ta có

f0(x, λd) = lim

y→x t↓0

t

= λ limy→x t↓0

λt

= λ limy→xη↓0

supf (y + t(d1 + d2)) − f (y)

t

≤ limy→x t↓0

supf (y + td1 + td2) − f (y + td2)

t

+ limy→x t↓0

t

≤ limt↓0

K k y + td − y k

t

= K k d k

k tồn tại yk ∈ X và tk > 0 sao cho

limk→∞supf0(xk, dk) ≤ f0(x, d)

Vậy f0(x, d) là nửa liên tục trên.

iv) Ta có

f0(x, −d) = lim

y→x t↓0

t

= limu→x t↓0

t

= (−f )0(x, d)

cộng tính, vì thế theo định lý Han-Banach sẽ tồn tại phiếm hàm tuyến

X mà để cho tiện ta dùng các ký hiệu hξ, di hay hd, ξi thay cho ký hiệuξ(d) Ta nêu ra định nghĩa sau:

Định nghĩa 1.5 Cho f (x) Lipschitz gần x, vi phân suy rộng (hay viphân Clarke) của f tại x là tập

Ta nhắc lại khái niệm quan trọng sau đây về hàm tựa.

Hàm tựa của tập Ω 6= ∅ của X là hàm

được xác định theo công thức

σΩ(ξ) := sup

x∈Ω{hξ, xi}

1.2 Một số tính chất cơ bản của gradient suy rộngTính chất của gradient suy rộng và vi phân suy rộng được nêu trongcác bổ đề sau đây

Bổ đề 1.2 Cho f (x) Lipschitz gần x Khi đó,

ii) Là cách diễn đạt khác của sự kiện nói rằng ∂f (x) theo định nghĩa là

ξ∈∂f (x)

{hξ, di} với một d nào đó

Theo định lý Hahn-Banach tồn tại phiếm hàm tuyến tính ξ không vượt

chứng minh

Để ý rằng nếu f là hàm lồi thì các khái niệm đạo hàm suy rộng theohướng và gradient suy rộng trùng với khái niệm đạo hàm theo hướng vàdưới gradient đã được định nghĩa trong giải tích lồi

Bổ đề 1.3 Nếu f (x) là hàm lồi và Lipschitz gần x thì vi phân suyrộng ∂f (x) trùng với dưới vi phân tại x và đạo hàm suy rộng theo hướng

Chứng minh Theo giải tích lồi thì f0(x, d) tồn tại với mỗi d và f0(x, d) là

f (x0 + td) − f (x0)

ttrong đó δ > 0 là một số cho trước tùy ý Do f (x) là hàm lồi nên hàm

0 + td) − f (x0)t

f (x0 + εd) − f (x0)

ε

Do δ được chọn tùy ý nên f0(x, d) ≤ f0(x, d) Vậy, f0(x, d) = f0(x, d)

Bổ đề 1.4 Nếu f (x) Lipschitz gần x thì ξ ∈ ∂f (x) khi và chỉ khi

i=1

fi
(x) ⊂

mX

i=1

∂fi(x)

Lipschitz gần x và g(x) là Lipschitz gần h(x) thì f (x) là Lipschitz gần

x và

nX

Chương 2

Một số phương pháp giải bài toán tối ưu không trơn

2.1 Nội dung bài toán

Xét bài toán tối ưu không ràng buộc

min

trong đó f (x) là một hàm không khả vi xác định trong không gianBanach X và thỏa mãn điều kiện Lipschitz Với bài toán (2.1) có haikhó khăn chính trong việc tìm nghiệm

Thứ nhất, không thể dễ dàng đưa ra được tiêu chuẩn dừng quá trình

Khi đó, nếu x không phải là nghiệm cực tiểu của bài toán thì f (x) khả

Bài toán tối ưu có ràng buộc có dạng

min

trong đó Y ⊆ X là một tập hay miền chấp nhận được Ta định nghĩakhoảng cách từ điểm x đến Y là

trong đó f (x) + σdist(x, Y ) là hàm không khả vi Như vậy, bài toán tối

ưu có ràng buộc không trơn được đưa về bài toán tương đương khôngràng buộc không trơn Điều này giải thích tại sao người ta lại hay quantâm nghiên cứu các bài toán tối ưu không ràng buộc không trơn cụ thể

là bài toán (2.1)

Có nhiều ví dụ về bài toán tối ưu không trơn chẳng hạn bài toánminimax: min

x∈X max1≤i≤mfi(x.)Hơn nữa, để giải hệ phương trình phi tuyến

Ví dụ 2.3 (Bài toán đối ngẫu) Xét bài toán

λigi(x) +

pP

∀x ∈ C, ∀(λ, µ), λ ≥ 0, inf

Do đó, khi ta lấy supremum với (λ, µ), λ ≥ 0 và sau đó lấy infimum với

x ∈ C ta thu được các kết quả

và

supλ≥0,µ

inf

x∈C supλ≥0,µL(x, λ, µ)

i=1

λigi(x) +

pX

2.2 Điều kiện tối ưu

Mục này đề cập tới điều kiện tối ưu đối với cực tiểu của hàm Lipschitz.Cho X là một không gian Banach với chuẩn k k được định nghĩatrên X Xét hàm f : X → R

Định nghĩa 2.1 i) Ta nói x∗ ∈ X là điểm cực tiểu (cực tiểu chặt) của

f trên X nếu f (x∗) ≤ f (x), ∀x ∈ X (f (x∗) < f (x), ∀x ∈ X, x 6= x∗)

Bài toán tìm cực đại của một hàm trên tập đã cho được phát biểumột cách tương tự nhưng để ý

min

Từ bổ đề 1.4 trực tiếp suy ra điều kiện cần cấp 1 sau đây

0 ∈ ∂f (x∗)

nghĩa 1.5 thì với mọi d ∈ X ta có

f0(x∗, d) ≥ 0

f0(x∗, d) ≥ 0

f(D)(x∗, d) ≥ 0

Điểm x∗ gọi là điểm dừng Clarke của hàm f nếu với mọi d ta có

f0(x∗, d) ≥ 0 tức là 0 ∈ ∂f (x∗)

địa phương f luôn là điểm dừng Dini của hàm f Nếu f khả vi theo

điểm dừng Clarke, nhưng không có điều ngược lại

phương của hàm f

{ξ ∈ X∗|f (z) − f (x∗) ≥ hξ, z − x∗i, ∀z ∈ X}

= {ξ ∈ X∗|f0(x∗, d) ≥ hξ, di, ∀z ∈ X}

f (z) − f (x∗) ≥ h0, z − x∗i = 0, ∀z ∈ X

tương đương với

f0(x, d) ≥ 0, ∀d ∈ X

Định lí 2.3 Cho f (x) là hàm lồi và Lipschitz gần x∗ Nếu f0(x, d) >

và f0(x∗, d) liên tục (thực ra, f0(x∗, d) là hàm lồi thuần nhất dương theod) nên tồn tại δ > 0 sao cho

Ta thấy f (−x) = f (x), ∀x ∈ [−1; 0] Rõ ràng f (x) Lipschitz trên đoạn

cực trị của hàm f

2.3 Một số phương pháp giải bài toán tối ưu không

trơn

Phương pháp dưới gradient được suy rộng trực tiếp từ phương pháp

Phương pháp dưới gradient được mô tả như sau

Thuật toán 2.1 (Phương pháp dưới gradient.)

Bước 2 Tính f (xk), gk ∈ ∂f (xk)

k gk k2.Đặt k := k + 1 và quay lại bước 2

Như đã nêu ở mục trước phương pháp dưới gradient với thủ tục tìm

Trong tối ưu không trơn thủ tục tìm gần đúng theo tia được hiểu là

Để ý là độ dài bước hằng số là không thích hợp, bởi vì hàm cần tìm

Mặc dầu thủ tục tìm chính xác và gần đúng theo tia dùng trong tối

ưu trơn không thể mở rộng một cách đơn giản cho trường hợp khôngtrơn, nhưng hướng đối dưới gradient vẫn là hướng tốt để cho điểm lặpmới gần hơn với nghiệm cực tiểu cần tìm Ta cần bổ đề sau

Bằng cách sử dụng tính chất trên đây của hướng dưới gradient ta có

cực tiểu cần tìm Từ bổ đề trên ta có thể dễ dàng suy ra kết luận sauđây của Shor

Với mỗi δ > 0 tìm được số r > 0 sao cho nếu áp dụng Thuật toán 2.1

toán 2.1 không hội tụ Vì vậy, để khắc phục ta nên chọn αk thỏa mãnđiều kiện

αk > 0, lim

∞X

k=1

Thuật toán 2.1 sẽ thỏa mãn điều kiện

limk→∞dist(xk, S∗) = 0

trong đó dist(xk, S∗) = min

Nếu đặt δ(0) = 0, thì biểu thức trên đúng với mọi k Cộng hai vế của(2.8) ta nhận được

lim inf

Vậy

lim infk→∞ dist(xk, S∗) = 0

Bây giờ ta giả sử ngược lại rằng định lý không đúng, nghĩa là lim dist(xk, S∗) >

0 Khi đó, tồn tại số δ0 > 0 và vô số giá trị k sao cho

tụ chậm bởi vì

k xk − x∗ k + k xk+1− x∗ k≥k xk − xk+1 k= αknên

bất kỳ α0 và g cho trước, nếu dist(x1, S∗) > α0

(2.12) kết quả hội tụ của Thuật toán như sau

Định lí 2.6 Giả sử f (x) là một hàm lồi và tồn tại hằng số δ1 > 0 saocho

(x − x∗)Tg ≥ δ1 k g kk x − x∗ k, ∀g ∈ ∂f (x), ∀x ∈ X

Thuật toán 2.1 thỏa mãn

trong đó x∗ ∈ S∗, q và α là các hằng số k x1 − x∗ k và δ1, M (δ1, α0) >

k g k≤ bc, ∀g ∈ ∂f (x),

f (x) − f∗ ≥ cdist(x; S∗),

k xk − x∗ k≤ M qk,

trong đó q = (1 − λ(2 − λ)bc2

c2)1

Thảo luận trên cho thấy rằng nếu chỉ cải tiến quy tắc xác định độdài bước thí nói chung không thể làm tăng đáng kể được tốc độ hội tụ.Trên thực tế sự hội tụ chậm là do gradient gần như trực giao với hướngnhằm tới điểm cực tiểu Cách đơn giản là thay đổi góc giữa gradient vàhướng hướng tới điểm cực tiểu Thay đổi đó có thể thực hiện bằng kỹthuật mở rộng không gian mà thực chất nó chính là một dạng tổng quátcủa phương pháp metric biến thiên.

Phương pháp này được mô tả như sau

Thuật toán 2.2 (Phương pháp mở rộng không gian.)

xk+1 = xk − αkHk

gk(gTk.Hk.gk)12Bước 3 Chọn rk > 0 và βk < 1 Đặt

Đặt k:=k+1 và quay lại bước 2

thì dãy {xk} sinh bởi Thuật toán 2.2 với cách chọn tham số theo (2.15)thỏa mãn

lim infk→∞

Rõ ràng với hàm lồi f (x) ta có

f (x) = sup

y

supg∈∂f (y)

Phương pháp siêu phẳng cắt chính là ở mỗi phép lặp giải một bài

hiện có Mỗi vòng lặp ta giải bài toán phụ

Rõ ràng bài toán quy hoạch tuyến tính (2.19)-(2.20) là xấp xỉ của bàitoán (2.17)-(2.18)

Phương pháp siêu phẳng cắt được mô tả như sau

Thuật toán 2.3 (Phương pháp siêu phẳng cắt)

trước

và quay trở lại bước 2

Như trên đã nói, ở mỗi vòng lặp thuật toán thêm vào một ràng buộcmới mà về mặt hình học một phần của tập S không chứa nghiệm sẽ bịcắt bỏ bởi siêu phẳng mới đưa vào này

Sự hội tụ của phương pháp siêu phẳng cắt được nêu trong định lý sau

i) v2 ≤ v3 ≤ · · · ≤ vk → f∗

Giả sử rằng hàm f (x) khả vi và thuật toán hội tụ tới nghiệm Khi

(2.20) trở thành điều kiện xấu Một nhược điểm nữa của phương phápsiêu phẳng cắt là khi k đủ lớn sẽ có quá nhiều ràng buộc trong bài toán(2.19)-(2.20) do đó chi phí tính toán khá cao, bởi vì các ràng buộc siêuphẳng cắt luôn được thêm vào tập ràng buộc hiện có mà không baogiờ bị loại đi Vì những nhược điểm nêu trên nên các phương pháp siêuphẳng cắt ít được chú ý tới, mặc dầu nó là một trong những phương

pháp sớm nhất để giải quy hoạch lồi tổng quát Vì thế, cần có những cảibiên nhất định cho phương pháp siêu phẳng cắt.

Phương pháp bó được thác triển từ phương pháp dưới gradient liên

Phương pháp dưới gradient liên hợp do Wolfe nêu ra Tại bước lặp thứ

xác theo tia thì hướng xác định bởi (2.21)-(2.23) trùng với hướng củaphương pháp gradient liên hợp Phương pháp được mô tả như sau:Thuật toán 2.4 (Phương pháp dưới gradient liên hợp)

Chọn 0 < m2 < m1 < 1

2; 0 < m3 < 1, 0 < ε, η > 0, k := 1,

I = {1}

hoặc

Bước 4 Nếu có gk+1 ∈ ∂f (xk) thỏa mãn

thì xk+1 := yk Trái lại, đặt xk+1 := xk

Tk = {i| k xi − xi+1 k> ε}

Bước 6 Đặt k := k + 1 và quay trở lại Bước 2

Thuật toán trên hội tụ theo định lý sau:

Định lí 2.10 Giả sử f (x) là một hàm lồi Nếu k ∂f (x) k bị chặn trong

lặp

Chúng ta xét một trường hợp mở rộng của phương pháp dưới gradientliên hợp

Giả sử rằng chúng ta đã thực hiện được một số bước của phương phápdưới gradient liên hợp Khi đó, một số điểm nào đó đã được sinh ra vàtại các điểm đó giá trị của hàm f cùng với các dưới gradient đã được tínhtoán Ta kí hiệu các thông tin trên bằng bó x1, , xk; f1, , fk; g1, , gk,trong đó fi = f (xi) và gi ∈ ∂f (xi)

Giả sử tại bước lặp thứ k ta có các giá trị trọng số t(i)k ≥ 0(i = 1, , k).Xét bài toán phụ sau

min k

kX

i=1

với điều kiện

kX

i=1

kX

i=1

trong đó, ε > 0 là một hằng số cho trước Gọi nghiệm của (2.27)-(2.29)

kX

i=1

Dễ kiểm tra lại rằng nếu t(k)i = 0 (i ∈ Ik) và t(k)i = +∞ (i 6∈ Ik) thì bàitoán (2.27)-(2.29) sẽ hoàn toàn tương đương với bài toán (2.22)-(2.23).Thuật toán 2.5 (Phương pháp bó)

Đặt k := k + 1 quay lại Bước 2

Thuật toán bó hội tụ theo định lý sau

trơn< /h3>

Phương pháp gradient suy rộng trực tiếp từ phương pháp

Phương pháp gradient mô tả sau

Thuật toán 2.1 (Phương pháp gradient. )... σdist(x, Y ) hàm không khả vi Như vậy, tốn tối

ưu có ràng buộc khơng trơn đưa tốn tương đương khơngràng buộc khơng trơn Điều giải thích người ta lại hay quantâm nghiên cứu tốn tối ưu khơng ràng... cần tìm

Mặc dầu thủ tục tìm xác gần theo tia dùng tối

ưu trơn mở rộng cách đơn giản cho trường hợp khôngtrơn, hướng đối gradient hướng tốt điểm lặpmới gần với nghiệm cực tiểu cần