Gradient Suy Rộng và Ứng Dụng Vào Bài Toán Tối Ưu Không Trơn

Hàm f : Y → R được gọi là Lipschitz trên Y nếu tồn tại một hằng số K sao cho |f(x) - f(y)| ≤ K ||x - y|| với mọi x, y ∈ Y ⊆ X. Hằng số K được gọi là hằng số Lipschitz. Điều kiện Lipschitz đảm bảo rằng hàm không thay đổi quá nhanh, giúp cho việc xây dựng các thuật toán tối ưu trở nên khả thi. Tính Lipschitz là một điều kiện quan trọng trong lý thuyết tối ưu hóa không trơn vì nó cho phép chúng ta kiểm soát sự thay đổi của hàm và đảm bảo sự hội tụ của các thuật toán.

Đạo hàm theo hướng d tại x, ký hiệu là f'(x, d), được định nghĩa là giới hạn lim (t↓0) (f(x + td) - f(x))/t, nế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ất thiết khả vi tại điểm đó và có thể không có đạo hàm theo hướng theo nghĩa cổ điển vừa nêu. Đạo hàm theo hướng Dini trên của f tại x theo hướng d, ký hiệu là f (D) (x, d) được định nghĩa là giới hạn f (x + td) − f (x) f (D) (x, d) = lim sup t↓0 t nếu giới hạn này tồn tại.

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ý hiệu là f'(x, d) được định nghĩa là giới hạn. Vi phân suy rộng (hay vi phân Clarke) của f tại x là tập ∂f (x) = {ξ ∈ X ∗ |f 0 (x, d) ≥ hξ, di, ∀d ∈ X} trong đó X ∗ là không gian liên hợp của X, ξ gọi là gradient suy rộng của f tại x.

Nếu f(x) là hàm lồi và Lipschitz gần x, thì vi phân suy rộng ∂f(x) trùng với dưới vi phân tại x. Theo giải tích lồi thì f'(x, d) tồn tại với mỗi d và f'(x, d) là hàm tựa của dưới vi phân tại x. Do đó, ta chỉ cần chứng minh f'(x, d) = f'(x, d). Ta có f (x0 + td) − f (x0 ) f 0 (x, d) = lim sup sup ε↓0 kx0 −xk<εδ 0<t<ε t trong đó δ > 0 là một số cho trước tùy ý.

Nếu f(x) = g(h(x)) và h(x) = (h1(x), ..., hn(x))T với mỗi hi(x) là Lipschitz gần x và g(x) là Lipschitz gần h(x) thì f(x) là Lipschitz gần x và ∂f(x) ⊂ CO {∑αi ξi : ξi ∈ ∂hi(x), α ∈ ∂g(h)} trong đó CO là bao lồi compact yếu∗.

Nếu f(x) Lipschitz gần x thì ξ ∈ ∂f(x) khi và chỉ khi f'(x, d) ≥ <ξ, d> với mọi d ∈ X. Nếu X hữu hạn chiều thì ∂f nửa liên tục trên.

Với bài toán tối ưu trơn thì với x đủ gần điểm cực tiểu x∗ thì k ∇f (x) k rất nhỏ.2) thường được sử dụng làm tiêu chuẩn dừng. Tuy nhiên, với hàm không trơn thì không có kết quả tương tự. Xét bài toán tối ưu đơn giản với hàm f : R1 → R1 và f (x) = |x|. 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ả vi và ta có |∂f (x)| = |∇f (x)| = 1.

Nếu f(x) không khả vi mà ta sử dụng phương pháp hướng giảm nhanh nhất với thủ tục tìm chính xác theo tia để giải (2.1) có thể nhận được dãy {xk } hội tụ về điểm không dừng. Xét hàm f : R2 → R, x = (u, v)T và 1 1 f (x) = max[ u2 + (v − 1)2 ; u2 + (v − 1)2 ] 2 2

Có nhiều ví dụ về bài toán tối ưu không trơn chẳng hạn bài toán minimax: min max fi (x.) x∈X 1≤i≤m Hơn nữa, để giải hệ phương trình phi tuyến fi (x) = 0, i = 1, ., m ta thường tìm nghiệm của bài toán cực tiểu min f (x) = min k f (x) k (2.5) x∈X x∈X với chuẩn nào đó, trong đó f (x) =k f (x) k, f (x) = (f1 (x), ., fm (x)) là một hàm vecto từ X vào Rn . Rõ ràng bài toán (2.5) là bài toán tối ưu không trơn.

Nếu f (x) đạt cực tiểu (hay cực đại) địa phương tại x∗ và f (x) Lipschitz gần x∗ thì 0 ∈ ∂f (x∗ ) Chứng minh. Do x∗ là điểm cực tiểu địa phương của f (x) nên theo định nghĩa 1.5 thì với mọi d ∈ X ta có f 0 (x∗ , d) ≥ 0.

Cho f (x) là hàm lồi và Lipschitz gần x∗ . Do f (x) là hàm lồi và Lipschitz gần x∗ nên theo bổ đề 1.3 vi phân suy rộng và dưới vi phân của f tại x∗ là trùng nhau, tức là {ξ ∈ X ∗ |f (z) − f (x∗ ) ≥ hξ, z − x∗ i, ∀z ∈ X} = {ξ ∈ X ∗ |f 0 (x∗ , d) ≥ hξ, di, ∀z ∈ X}. Vậy x∗ là điểm cực tiểu của f (x).

Cho f (x) là hàm lồi và Lipschitz gần x∗ . Nếu f 0 (x, d) > 0, ∀d 6= 0, d ∈ X thì x∗ là điểm cực tiểu chặt của f (x), nghĩa là tồn tại số δ > 0 sao cho f (x) − f (x∗ ) > δ k x − x∗ k với mọi x đủ gần x∗ .

Phương pháp dưới gradient được suy rộng trực tiếp từ phương pháp hướng giảm nhanh nhất bằng cách sử dụng hướng −gk trong đó gk ∈ ∂f (xk ) để sinh ra dãy {xk }. Ta đã biết hàm lồi và Lipschitz gần x thì khả vi hầu x∈R khắp nơi và ∂f (x) = convΩ(x) trong đó convΩ là bao lồi của Ω và Ω(x) = {g|g = lim ∇f (xi ), xi → x, ∃∇f (xi )}.

Việc lựa chọn bước là rất quan trọng trong phương pháp dưới gradient. Bước quá lớn có thể dẫn đến việc thuật toán dao động và không hội tụ. Bước quá nhỏ có thể làm cho thuật toán hội tụ rất chậm. Có nhiều chiến lược lựa chọn bước khác nhau, chẳng hạn như bước giảm dần, bước tỉ lệ với độ lớn của dưới gradient, hoặc bước được xác định thông qua tìm kiếm đường thẳng.

Phương pháp dưới gradient có ưu điểm là đơn giản và dễ cài đặt. Nó cũng có thể được áp dụng cho các bài toán có hàm mục tiêu rất phức tạp. Tuy nhiên, phương pháp này có nhược điểm là hội tụ chậm và không đảm bảo hội tụ về điểm tối ưu. Nó cũng nhạy cảm với việc lựa chọn bước.

Phương pháp bó là một phương pháp tối ưu không trơn sử dụng thông tin từ nhiều dưới gradient để xây dựng một mô hình xấp xỉ của hàm mục tiêu. Mô hình này được sử dụng để xác định hướng tìm kiếm. Phương pháp bó thường có tốc độ hội tụ nhanh hơn so với phương pháp dưới gradient vì nó sử dụng nhiều thông tin hơn.

Phương pháp siêu phẳng cắt là một phương pháp tối ưu không trơn sử dụng các siêu phẳng để xấp xỉ hàm mục tiêu. Các siêu phẳng được tạo ra từ các dưới gradient. Phương pháp này thường được sử dụng để giải các bài toán có hàm mục tiêu lồi và Lipschitz.

Phương pháp Newton không trơn là một phương pháp tối ưu không trơn sử dụng thông tin từ vi phân cấp hai của hàm mục tiêu để xác định hướng tìm kiếm. Phương pháp này thường có tốc độ hội tụ rất nhanh, nhưng nó cũng đòi hỏi nhiều tính toán hơn so với các phương pháp khác.