Luận văn thạc sĩ khoa học phương pháp điểm gần kề để giải bài toán tối ưu

Luận văn thạc sĩ nghiên cứu phương pháp điểm gần kề để giải bài toán tối ưu, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện trong lĩnh vực toán học.

• Đề tài: Luận Văn Thạc Sĩ Khoa Học Phương Pháp Điểm Gần Kề Để Giải Bài Toán Tối Ưu
• Loại tài liệu: thesis

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• DANH MỤC CÁC KÝ HIỆU
• DANH MỤC CÁC BẢNG
• MỞ ĐẦU
• 1. CHƯƠNG 1: MỘT SỐ KIẾN THỨC CƠ SỞ
• 1.1. Chuẩn
• 1.2. Hàm số và vi phân
• 1.3. Tập lồi
• 1.4. Hàm lồi
• 1.5. Một số lệnh cơ bản trong Matlab
• 1.5.1. Các toán tử cơ bản của Matlab
• 1.5.2. Định nghĩa một hàm trong Matlab
• 2. CHƯƠNG 2: BÀI TOÁN TỐI ƯU KHÔNG RÀNG BUỘC VÀ PHƯƠNG PHÁP ĐIỂM GẦN KỀ
• 2.1. Bài toán tối ưu không ràng buộc
• 2.2. Phương pháp điểm gần kề
• 2.2.1. Định nghĩa hàm điều chỉnh Moreau - Yosida
• 2.2.2. Một vài tính chất cơ bản của hàm điều chỉnh
• 2.2.3. Thuật toán điểm gần kề cho bài toán tối ưu
• 3. CHƯƠNG 3: CÁC VÍ DỤ VÀ CHƯƠNG TRÌNH MÁY TÍNH
• 3.1. Các ví dụ
• 3.2. Chương trình máy tính
• KẾT LUẬN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan phương pháp điểm gần kề giải bài toán tối ưu

Phương pháp điểm gần kề là một công cụ mạnh mẽ trong lĩnh vực lý thuyết tối ưu (optimization theory), đặc biệt hiệu quả cho các bài toán tối ưu hóa lồi (convex optimization), kể cả trơn và không trơn. Được đề xuất lần đầu bởi Martinet và phát triển bởi Rockafellar vào năm 1976, phương pháp này đã trở thành nền tảng cho nhiều thuật toán lặp (iterative algorithm) hiện đại. Cốt lõi của phương pháp nằm ở việc thay thế bài toán tối ưu ban đầu bằng một chuỗi các bài toán con dễ giải hơn. Mỗi bài toán con này được xây dựng dựa trên việc thêm một số hạng điều chỉnh bậc hai vào hàm mục tiêu, giúp làm "trơn" hóa và tạo ra tính lồi mạnh. Nghiệm của bài toán con tại mỗi bước lặp được gọi là điểm gần kề, và chuỗi các điểm này được chứng minh sẽ hội tụ về nghiệm của bài toán gốc. Luận văn này tập trung nghiên cứu sâu về cơ sở lý thuyết của thuật toán điểm gần kề (proximal point algorithm), từ việc định nghĩa hàm điều chỉnh Moreau-Yosida, phân tích các tính chất cơ bản của nó, đến chứng minh chi tiết sự hội tụ của thuật toán (convergence of algorithm). Các khái niệm nền tảng như không gian Hilbert (Hilbert space), tập lồi, hàm lồi và dưới vi phân được hệ thống hóa để cung cấp một cái nhìn toàn diện. Phương pháp này đặc biệt hữu ích khi đối mặt với các bài toán tối ưu hóa phi trơn (nonsmooth optimization), nơi mà các phương pháp dựa trên gradient truyền thống không thể áp dụng trực tiếp. Bằng cách sử dụng toán tử gần kề (proximal operator), thuật toán có khả năng xử lý các thành phần không khả vi một cách hiệu quả, mở ra ứng dụng rộng rãi trong các lĩnh vực tiên tiến như học máy (machine learning) và xử lý tín hiệu (signal processing).

1.1. Lịch sử và tầm quan trọng của lý thuyết tối ưu hóa

Lý thuyết tối ưu hóa là một nhánh toán học ứng dụng tập trung vào việc tìm kiếm giá trị tốt nhất (cực đại hoặc cực tiểu) của một hàm số trong một tập hợp các lựa chọn cho trước. Các bài toán này xuất hiện trong hầu hết mọi lĩnh vực, từ kinh tế, kỹ thuật đến khoa học máy tính. Sự phát triển của các phương pháp tối ưu hóa, đặc biệt là tối ưu hóa lồi, đã tạo ra một cuộc cách mạng trong việc giải quyết các vấn đề phức tạp. Trước khi các phương pháp hiện đại ra đời, việc tìm nghiệm tối ưu cho các hàm phức tạp, đặc biệt là các hàm không trơn, là một thách thức lớn. Các phương pháp cổ điển thường yêu cầu hàm mục tiêu phải khả vi, điều này giới hạn phạm vi ứng dụng của chúng. Sự ra đời của các kỹ thuật như phương pháp điểm gần kề đã khắc phục những hạn chế này, cung cấp một khuôn khổ lý thuyết vững chắc và các công cụ tính toán hiệu quả cho một lớp bài toán rộng lớn hơn.

1.2. Giới thiệu thuật toán điểm gần kề Proximal Point Algorithm

Về bản chất, thuật toán điểm gần kề (Proximal Point Algorithm - PPA) là một phương pháp lặp để tìm điểm bất động (fixed point) của một toán tử. Trong bối cảnh tối ưu hóa, nó được áp dụng để tìm điểm cực tiểu của một hàm lồi. Ý tưởng chính là tại mỗi bước lặp thứ k, thay vì tối thiểu hóa trực tiếp hàm mục tiêu F(y), thuật toán sẽ giải một bài toán con đơn giản hơn: min {F(y) + (1/2c_k) * ||y - x_k||^2}. Ở đây, x_k là điểm lặp hiện tại và c_k là một tham số dương. Nghiệm của bài toán con này, ký hiệu là x_{k+1}, chính là điểm gần kề của x_k. Điểm này sau đó được sử dụng làm điểm bắt đầu cho vòng lặp tiếp theo. Quá trình này được lặp lại cho đến khi đạt được sự hội tụ. Ưu điểm lớn của PPA là tính ổn định và đảm bảo hội tụ dưới các điều kiện rất tổng quát, ngay cả khi hàm mục tiêu không trơn.

II. Thách thức trong bài toán tối ưu hóa lồi và phi trơn

Các bài toán tối ưu hóa lồi chiếm một vị trí trung tâm trong toán học ứng dụng do chúng sở hữu nhiều tính chất lý thuyết đẹp và các thuật toán hiệu quả. Một trong những đặc điểm quan trọng nhất là mọi điểm cực tiểu địa phương cũng chính là cực tiểu toàn cục. Tuy nhiên, việc giải quyết các bài toán này không phải lúc nào cũng đơn giản. Một thách thức lớn phát sinh khi hàm mục tiêu là phi trơn, tức là không khả vi tại một số điểm. Các phương pháp hạ gradient gần kề (proximal gradient method) truyền thống và các biến thể của nó thường dựa vào thông tin của đạo hàm để xác định hướng giảm. Khi gặp phải các điểm không khả vi, chẳng hạn như trong các bài toán có thành phần chính quy hóa L1 như hồi quy LASSO (LASSO regression), các phương pháp này không thể áp dụng trực tiếp. Đây là lúc các kỹ thuật trong tối ưu hóa phi trơn (nonsmooth optimization) trở nên cần thiết. Một khó khăn khác là tốc độ hội tụ. Ngay cả với các hàm lồi trơn, các thuật toán lặp có thể hội tụ rất chậm, đòi hỏi số lượng lớn các bước lặp để đạt được độ chính xác mong muốn. Việc cải thiện sự hội tụ của thuật toán là một hướng nghiên cứu không ngừng. Phương pháp điểm gần kề, mặc dù đảm bảo hội tụ, nhưng bản thân nó có thể chậm. Tuy nhiên, nó lại là nền tảng để xây dựng các thuật toán phức tạp hơn và nhanh hơn như thuật toán ADMM (Alternating Direction Method of Multipliers), giúp giải quyết các bài toán có cấu trúc phức tạp một cách hiệu quả.

2.1. Khó khăn của các bài toán tối ưu không ràng buộc

Bài toán tối ưu không ràng buộc, min F(x), là dạng bài toán cơ bản nhất. Mặc dù trông có vẻ đơn giản, chúng vẫn tiềm ẩn nhiều thách thức. Thứ nhất, nếu hàm F(x) không lồi, bài toán có thể có nhiều điểm cực tiểu địa phương. Hầu hết các thuật toán chỉ có thể đảm bảo tìm thấy một cực tiểu địa phương, không đảm bảo đó là cực tiểu toàn cục. Thứ hai, ngay cả khi F(x) là lồi, nếu nó không trơn (ví dụ F(x) = |x|), việc tính toán gradient là không thể. Các khái niệm tổng quát hơn như dưới vi phân (subgradient) phải được sử dụng, nhưng các thuật toán dựa trên dưới vi phân thường có tốc độ hội tụ chậm và không ổn định. Cuối cùng, đối với các bài toán có số chiều lớn, việc lưu trữ và tính toán với các ma trận như ma trận Hessian (trong các phương pháp bậc hai) trở nên rất tốn kém, đòi hỏi các phương pháp chỉ sử dụng thông tin bậc nhất.

2.2. Hạn chế của các phương pháp dựa trên Gradient truyền thống

Các phương pháp dựa trên gradient, như phương pháp hạ gradient (gradient descent), là một trong những thuật toán tối ưu hóa phổ biến nhất. Chúng hoạt động bằng cách di chuyển lặp đi lặp lại theo hướng ngược lại với gradient của hàm mục tiêu. Tuy nhiên, chúng có những hạn chế cố hữu. Rõ ràng nhất là chúng yêu cầu hàm mục tiêu phải khả vi. Đối với các bài toán tối ưu hóa phi trơn, các phương pháp này thất bại. Hơn nữa, hiệu suất của chúng rất nhạy cảm với việc lựa chọn kích thước bước (learning rate). Một kích thước bước quá lớn có thể khiến thuật toán phân kỳ, trong khi một kích thước bước quá nhỏ có thể dẫn đến sự hội tụ của thuật toán cực kỳ chậm. Các phương pháp này cũng gặp khó khăn với các bài toán có điều kiện xấu (ill-conditioned), nơi các đường đồng mức của hàm mục tiêu có dạng elip rất dẹt, khiến quá trình hội tụ đi theo đường ziczac.

III. Khám phá toán tử gần kề và hàm điều chỉnh Moreau Yosida

Nền tảng của phương pháp điểm gần kề chính là hai khái niệm toán học then chốt: hàm điều chỉnh Moreau-Yosida và toán tử gần kề (proximal operator). Hàm điều chỉnh Moreau-Yosida, ký hiệu là J(x), của một hàm F được định nghĩa là giá trị cực tiểu của một bài toán phụ: J(x) = min {F(y) + (1/2c) * ||y - x||^2}. Hàm J(x) này có nhiều tính chất tốt. Quan trọng nhất, J(x) luôn là một hàm lồi và khả vi liên tục (trơn), ngay cả khi hàm F ban đầu là phi trơn. Đạo hàm của J(x) có dạng Lipschitz, một tính chất đảm bảo sự ổn định trong tính toán. Hơn nữa, điểm cực tiểu của hàm F và hàm J(x) là trùng nhau. Điều này cho phép chuyển đổi một bài toán tối ưu hóa phi trơn thành một bài toán tối ưu hóa trơn tương đương mà ta có thể áp dụng các phương pháp dựa trên gradient. Toán tử tương ứng tìm ra nghiệm duy nhất của bài toán con này chính là toán tử gần kề, ký hiệu là prox_F(x). Toán tử này lấy một điểm x và trả về một điểm y gần x mà vẫn tối thiểu hóa F. Nó có thể được xem là một sự tổng quát hóa của phép chiếu lên một tập lồi. Việc tính toán hiệu quả toán tử gần kề là chìa khóa để triển khai thành công các thuật toán điểm gần kề và các biến thể của nó.

3.1. Định nghĩa và vai trò của toán tử gần kề Proximal Operator

Toán tử gần kề của một hàm lồi F với tham số c > 0, ký hiệu là prox_{cF}(x), được định nghĩa là: prox_{cF}(x) = argmin_y {F(y) + (1/2c) * ||y - x||^2}. Về mặt hình học, toán tử này tìm một điểm y cân bằng giữa hai mục tiêu: làm cho giá trị F(y) nhỏ và giữ cho y gần với điểm ban đầu x. Vai trò của nó trong lý thuyết tối ưu là cực kỳ quan trọng. Nó cho phép tách rời các phần phức tạp của hàm mục tiêu. Ví dụ, nếu hàm mục tiêu là tổng của một hàm trơn và một hàm phi trơn, ta có thể áp dụng các bước gradient cho phần trơn và toán tử gần kề cho phần phi trơn. Đây chính là cơ sở của phương pháp hạ gradient gần kề (proximal gradient method), một thuật toán rất phổ biến trong học máy.

3.2. Phân tích tính chất của hàm hiệu chỉnh Moreau Yosida

Hàm hiệu chỉnh Moreau-Yosida J(x) là một công cụ làm trơn hóa mạnh mẽ. Một số tính chất cơ bản của nó bao gồm: (1) J(x) luôn hữu hạn, lồi và khả vi trên toàn bộ không gian, bất kể hàm gốc F có những tính chất đó hay không. (2) Đạo hàm của J(x) có thể được tính toán thông qua toán tử gần kề: ∇J(x) = (1/c) * (x - prox_{cF}(x)). Công thức này rất quan trọng vì nó liên kết trực tiếp việc tối ưu hóa hàm trơn J(x) với việc tính toán toán tử gần kề. (3) Tập hợp các điểm cực tiểu của F và J là giống hệt nhau. Do đó, việc tìm cực tiểu cho F tương đương với việc tìm cực tiểu cho J, tức là tìm x sao cho ∇J(x) = 0, hay x = prox_{cF}(x). Điều này cho thấy điểm cực tiểu chính là một điểm bất động của toán tử gần kề.

IV. Hướng dẫn thuật toán điểm gần kề và sự hội tụ của nó

Thuật toán điểm gần kề (proximal point algorithm) là một thuật toán lặp đơn giản nhưng hiệu quả để giải bài toán tối ưu hóa lồi. Quy trình thuật toán được thực hiện theo các bước tuần tự. Đầu tiên, khởi tạo một điểm xuất phát bất kỳ x_0 và một dãy tham số dương {c_k}. Tại mỗi bước lặp k, bước tiếp theo x_{k+1} được tính bằng cách áp dụng toán tử gần kề vào điểm hiện tại: x_{k+1} = prox_{c_k F}(x_k). Quá trình này được lặp lại cho đến khi một điều kiện dừng được thỏa mãn, ví dụ như ||x_{k+1} - x_k|| đủ nhỏ. Về mặt lý thuyết, một trong những kết quả quan trọng nhất là chứng minh sự hội tụ của thuật toán. Dưới các điều kiện rất tổng quát, chẳng hạn như hàm F là lồi, đóng và chính thường trong một không gian Hilbert (Hilbert space), và dãy tham số {c_k} thỏa mãn một số điều kiện nhất định (ví dụ, tổng của chúng phân kỳ), thì dãy {x_k} được tạo ra bởi thuật toán sẽ hội tụ đến một điểm cực tiểu của F. Việc chứng minh thường dựa trên việc cho thấy khoảng cách từ các điểm lặp đến tập nghiệm giảm dần và dãy {x_k} là một dãy Cauchy. Sự đảm bảo hội tụ này làm cho phương pháp điểm gần kề trở thành một công cụ đáng tin cậy, đặc biệt trong các bối cảnh lý thuyết và là nền tảng cho việc phát triển các thuật toán phức tạp hơn.

4.1. Các bước triển khai một thuật toán lặp Iterative Algorithm

Để triển khai thuật toán điểm gần kề, cần thực hiện các bước sau: (1) Bước 0: Khởi tạo: Chọn một điểm bắt đầu x_0 trong không gian R^n. Chọn một dãy tham số điều chỉnh dương {c_k} (ví dụ, c_k = 1 cho mọi k). (2) Bước 1: Vòng lặp chính: Tại bước lặp thứ k, giải bài toán con để tìm x_{k+1}: x_{k+1} = argmin_y {F(y) + (1/2c_k) * ||y - x_k||^2}. Đây là bước tính toán cốt lõi và có thể đòi hỏi một thuật toán con riêng để giải quyết, tùy thuộc vào dạng của hàm F. (3) Bước 2: Kiểm tra điều kiện dừng: So sánh x_{k+1} và x_k. Nếu ||x_{k+1} - x_k|| nhỏ hơn một ngưỡng epsilon cho trước, thuật toán dừng lại và trả về x_{k+1} làm nghiệm. Ngược lại, gán k := k + 1 và quay lại Bước 1. Việc lựa chọn dãy {c_k} có thể ảnh hưởng đến tốc độ hội tụ, nhưng không ảnh hưởng đến tính hội tụ của thuật toán.

4.2. Chứng minh sự hội tụ của thuật toán trong không gian Hilbert

Việc chứng minh sự hội tụ của thuật toán điểm gần kề thường được thực hiện trong bối cảnh tổng quát của không gian Hilbert. Giả sử S là tập các điểm cực tiểu của hàm F (giả sử không rỗng). Với một điểm z bất kỳ trong S, ta có thể chứng minh được rằng bất đẳng thức sau luôn đúng: ||x_{k+1} - z||^2 <= ||x_k - z||^2 - ||x_{k+1} - x_k||^2. Bất đẳng thức này cho thấy hai điều: thứ nhất, dãy khoảng cách ||x_k - z|| là một dãy số không tăng và do đó hội tụ; thứ hai, hiệu ||x_{k+1} - x_k|| tiến về 0. Điều này chứng tỏ dãy {x_k} là một dãy Cauchy. Vì không gian Hilbert là đầy đủ, mọi dãy Cauchy đều hội tụ. Do đó, dãy {x_k} hội tụ đến một điểm x*. Bằng cách sử dụng tính nửa liên tục dưới của hàm F, có thể chỉ ra rằng điểm giới hạn x* này phải thuộc tập nghiệm S. Đây là sườn chính của chứng minh, đảm bảo tính đúng đắn của phương pháp.

V. Ứng dụng PPA giải bài toán tối ưu trong học máy và xử lý tín hiệu

Phương pháp điểm gần kề và các thuật toán liên quan như phương pháp hạ gradient gần kề (proximal gradient method) có ứng dụng vô cùng rộng rãi trong các lĩnh vực hiện đại, đặc biệt là học máy (machine learning) và xử lý tín hiệu (signal processing). Trong học máy, nhiều bài toán có thể được xây dựng dưới dạng tối ưu hóa một hàm mục tiêu bao gồm một thành phần tổn thất (loss term) và một thành phần điều chuẩn (regularization term). Thành phần điều chuẩn thường là phi trơn, ví dụ như chuẩn L1 trong hồi quy LASSO (LASSO regression) để thúc đẩy tính thưa của nghiệm (sparse solution). Phương pháp hạ gradient gần kề là công cụ lý tưởng để giải quyết loại bài toán này. Nó cho phép xử lý phần tổn thất (thường là trơn) bằng một bước hạ gradient và xử lý phần điều chuẩn L1 (phi trơn) bằng toán tử gần kề, hay còn gọi là toán tử co mềm (soft-thresholding operator). Tương tự, trong xử lý tín hiệu và hình ảnh, các bài toán như khôi phục tín hiệu, khử nhiễu, hay nén ảnh thường liên quan đến việc tối thiểu hóa các hàm mục tiêu phức tạp. Ví dụ, trong bài toán Compressed Sensing, mục tiêu là khôi phục một tín hiệu thưa từ một số lượng nhỏ các phép đo. Bài toán này cũng dẫn đến một vấn đề tối ưu hóa với điều chuẩn L1. Các thuật toán điểm gần kề và đặc biệt là các biến thể hiệu quả hơn như thuật toán ADMM đã trở thành công cụ tiêu chuẩn để giải quyết các vấn đề này một cách nhanh chóng và đáng tin cậy.

5.1. Giải quyết bài toán hồi quy LASSO LASSO Regression

Bài toán hồi quy LASSO là một ví dụ điển hình về ứng dụng của các phương pháp gần kề. Bài toán có dạng: min_w { ||Xw - y||^2_2 + λ||w||_1 }. Ở đây, ||Xw - y||^2_2 là hàm tổn thất bình phương nhỏ nhất, là một hàm lồi và trơn. Thành phần λ||w||_1 là số hạng điều chuẩn L1, là một hàm lồi nhưng phi trơn tại gốc tọa độ. Áp dụng phương pháp hạ gradient gần kề, tại mỗi bước lặp, ta thực hiện hai bước: (1) Cập nhật theo hướng gradient của phần trơn: z_k = w_k - α∇(||Xw_k - y||^2_2). (2) Áp dụng toán tử gần kề của hàm chuẩn L1 lên z_k để có được w_{k+1}: w_{k+1} = prox_{αλ||.||_1}(z_k). Toán tử gần kề này có dạng công thức đóng gọi là toán tử co mềm, rất dễ tính toán. Sự kết hợp này tạo ra một thuật toán lặp hiệu quả, được gọi là ISTA (Iterative Shrinkage-Thresholding Algorithm).

5.2. Mối liên hệ với thuật toán ADMM và xử lý tín hiệu

Thuật toán ADMM (Alternating Direction Method of Multipliers) có thể được xem như một biến thể của phương pháp điểm gần kề áp dụng cho bài toán đối ngẫu của một bài toán tối ưu có ràng buộc. ADMM đặc biệt hiệu quả cho các bài toán có dạng min { f(x) + g(z) } với ràng buộc Ax + Bz = c. Thuật toán này phân rã bài toán lớn thành các bài toán con nhỏ hơn liên quan đến x và z, sau đó giải chúng một cách xen kẽ. Mỗi bài toán con này thường có thể được giải quyết hiệu quả bằng cách sử dụng toán tử gần kề của f và g. Nhờ khả năng phân rã này, ADMM rất phù hợp cho các bài toán quy mô lớn trong xử lý tín hiệu và tính toán phân tán. Nhiều bài toán như lọc ảnh, tái tạo Tomography, hay phân tích thành phần chính mạnh mẽ (Robust PCA) đều có thể được giải quyết hiệu quả bằng ADMM, biến nó thành một trong những công cụ tối ưu hóa hàng đầu trong lĩnh vực này.

VI. Tương lai và hướng phát triển của phương pháp điểm gần kề

Phương pháp điểm gần kề, dù đã có lịch sử phát triển lâu dài, vẫn là một lĩnh vực nghiên cứu sôi động với nhiều tiềm năng trong tương lai. Các kết quả nghiên cứu trong luận văn này đã hệ thống hóa một cách đầy đủ và chi tiết các kiến thức nền tảng, từ định nghĩa, tính chất của hàm điều chỉnh đến chứng minh sự hội tụ của thuật toán. Đây là một tài liệu tham khảo có giá trị cho sinh viên và nhà nghiên cứu quan tâm đến lý thuyết tối ưu. Tuy nhiên, lý thuyết này vẫn còn nhiều không gian để mở rộng và cải tiến. Một trong những hướng nghiên cứu chính là phát triển các thuật toán mới dựa trên nền tảng của thuật toán điểm gần kề để tăng tốc độ hội tụ. Các phiên bản gia tốc, như thuật toán của Nesterov, đã được áp dụng thành công cho phương pháp hạ gradient gần kề, mang lại sự cải thiện đáng kể về hiệu suất. Việc tìm ra các phương pháp gia tốc tương tự cho thuật toán điểm gần kề tổng quát vẫn là một thách thức mở. Một hướng khác là mở rộng phương pháp này để giải quyết các lớp bài toán phức tạp hơn, chẳng hạn như bài toán cân bằng, bài toán tìm điểm bất động cho các toán tử phi giãn, hoặc các bài toán tối ưu ngẫu nhiên (stochastic optimization) trong bối cảnh dữ liệu lớn của học máy. Việc kết hợp các ý tưởng từ phương pháp điểm gần kề với các kỹ thuật tối ưu hóa ngẫu nhiên và phân tán hứa hẹn sẽ tạo ra những thuật toán mạnh mẽ, có khả năng xử lý các bài toán quy mô rất lớn một cách hiệu quả.

6.1. Tóm tắt kết quả nghiên cứu và đóng góp chính của luận văn

Luận văn đã thành công trong việc tổng hợp và trình bày một cách hệ thống, mạch lạc về phương pháp điểm gần kề để giải bài toán tối ưu. Đóng góp chính của công trình là cung cấp một tài liệu tổng quan bằng tiếng Việt, chi tiết và dễ tiếp cận. Luận văn đã làm rõ các khái niệm cốt lõi như hàm hiệu chỉnh Moreau-Yosida, toán tử gần kề, và chứng minh một cách chặt chẽ sự hội tụ của thuật toán. Bên cạnh đó, các ví dụ minh họa cụ thể cùng với chương trình máy tính viết bằng Matlab đã giúp kết nối giữa lý thuyết và thực hành, cho thấy cách áp dụng thuật toán để giải các bài toán cực tiểu hàm lồi cụ thể. Những kết quả này không chỉ có ý nghĩa khoa học mà còn có tính thực tiễn cao, làm tài liệu tham khảo hữu ích cho cộng đồng học thuật.

6.2. Hướng nghiên cứu cải tiến tốc độ hội tụ của thuật toán

Một hạn chế của thuật toán điểm gần kề cơ bản là tốc độ hội tụ có thể chậm (hội tụ tuyến tính dưới một số giả định). Do đó, một hướng nghiên cứu quan trọng trong tương lai là cải tiến tốc độ hội tụ. Các kỹ thuật có thể được xem xét bao gồm: (1) Phương pháp gia tốc: Áp dụng các kỹ thuật ngoại suy như của Nesterov để kết hợp thông tin từ các bước lặp trước đó nhằm tạo ra các bước nhảy lớn hơn và hội tụ nhanh hơn. (2) Phương pháp gần-Newton (Quasi-Newton): Kết hợp thông tin xấp xỉ bậc hai để định hướng các bước lặp một cách thông minh hơn, giúp cải thiện tốc độ hội tụ từ tuyến tính lên siêu tuyến tính. (3) Lựa chọn tham số thích ứng: Phát triển các chiến lược để tự động điều chỉnh tham số c_k tại mỗi bước lặp nhằm tối ưu hóa tiến trình hội tụ, thay vì sử dụng một giá trị cố định hoặc một dãy định trước.

Trích đoạn nội dung tài liệu

CHƯƠNG 1 MỘT SỐ KIÊN THỨC CƠ SỞ “Trong luận văn này, chúng ta sẽ làm việc với không gian Euclide n-chiéu trên trường số thực I8. Không gian này sẽ được ký hiệu là R". Như vậy mỗi vecto x € R" sé gdm n toa do là các số thực. Thông thường khi viết một vectơ #, nếu không có quy ước gì thêm, ta luôn h đó là vectơ cột.

Chương, này nhắc lại một số khái niệm, tính chất cơ bản trong không gian R" , ham nhiều biến, khả vi,tập lồi và hàm lồi. Đồng thời nhắc lại một số lệnh cơ bản trong Matlab. Do chương này chỉ mang tính chất bổ trợ nên ta không chứng, mình các kết quả nêu ở đây. Nội dung của chương được trích dẫn chủ yếu từ tài liệu tham khảo [2],(3},[4].CHUẨN Định nghĩa 1.

Ánh xạ | : ||: R" —> R được gọi là chuẩn khi nó thỏa mãn các tính chất sau: 6) llzll> 0,Vz € R°;llz|| =0 khi và chỉ khi x @) llazll = la| llr||,Va € R,Vz € R"; (iii) lla + ø|| < llz|| + llw||. Các ví dụ thường gặp về chuẩn vectơ : lzllx = max lzi, (chuẩn 1,).#„)T € IR", 4 Các ví dụ trên là trường hợp cụ thể của chuẩn !„ được định nghĩa như sau: i,= (Š lá) (chun |). h với p là một số không nhỏ hơn 1 bất kỳ. Cho | : Ja va ||: ||z là các chuẩn trên RR".

Nếu tồn tại M1, He > 0, Mllella < llrlls < ø2||z|la.Ye 8° thì ta nói rằng | - ||a và ||- ||¿ là hai chuẩn tương đương. Đặc biệt, ta có lzllz < llzlli < vnllzlls. Izll« < llzla < vnllzl-. lzllx < llzll: < nlzll<.

IIzll« < Ilzll < llzlh. “Ta sử dụng các chuẩn để giới thiệu khoảng cách. Cho z, € R" và một hàm chuẩn. Khi đó, khoảng cách giữa 2 điểm z và được xác định bởi ||z — ||: Cụ thể, nếu # = (#ạ,.a)7, thì lz — 9lls = Vi — 9)Ê +.

+ (Ea — n)® Rõ ràng, theo Định nghĩa 1.1, khoảng cách cũng có các tính chất sau: 1.|lz—w||[0 khi và chỉ khi z =ÿ. |lz — z|| < llr — w|| + lu - z||- 3. lla — || = llw = #|- Một đãy {z¿} được gọi là hội £ự đến z* nếu jim |lz¿ — #'|| = 0.HÀM SỐ VÀ VI PHAN Cho điểm z € R* và ổ > Ú. Lân cận ổ của # được định nghĩa Bo(x) = {y € R"||ly — z|| < 6}.

Điểm z được gọi là điểm trong của D nếu tồn tại 6 > 0 sao cho Bs(x) C D. Tap hợp tất cả các điểm như vậy được gọi là phần trong của D và được ký hiệu là int(D) hose J. Chắc chấn là int(D) C D. Hơn nữa, nếu int(D) = D,tức là mọi điểm của D là điểm trong của D thì D là một tập mở.

Tập D C R" đóng khi và chỉ khi phần bù của nó mở.z € R" duge goi là điểm tu nếu với méi 6 > 0,D 1 Ns(x) # Ø. Có nghĩa là tồn tại một dãy {#„} CD sao cho x, — z.Tập hợp tất cả cá điểm như vậy được gọi là bao đóng của D và được ký hiệu là D. Hơn nữa, nếu D = D, tức là mỗi điểm tụ của D đều thuộc D thì D là tập đóng. Tập D C R”" được gọi là compact nếu nó bị chặn và đóng.

Với mỗi dãy {z,} trong tập eompaet_D, tồn tại một dãy con hội tụ tới một điểm trong D. Hàm f : R" —> R được gọi là liên tục tại # € R" nếu với bất ky € > 0, tồn tại 6 > 0 sao cho Vz € R",||x — Z|] < 6 ,ta c6 |f(x) — ƒ(Œ)| < e. Ta cũng có thể viết lại như sau: Ve > 0,35 > 0 sao cho Vz € N¿(Œ), ta có f(x) € Ä,(ƒ(Œ)). Nếu ƒ liên tục tại mọi điểm trong tập mở D C R" thì ƒ liên tục trên 72.

Hàm liên tục ƒ : JR" => R được gọi là khả mỉ liên tục tại z € R" nếu 9, () (x) tồn tại và liên tục, = 1,. Gradient của ƒ tại z được định nghĩa như sau r Vi (a) = FEC), of Ox, (|. Nếu ƒ khả vi liên tục tại mỗi diém trong tap mé DC R" thì ƒ khả 0i liên tục trên D và được ký ula fe CD). Hàm ƒ : R" —> R kha vi liên tục được gọi là kha vi lién tuc hai lan tai 2 reR"néu (x) ton tai va liên tuc,i, j = 1,.

Ma trận Hessian của Ørôz, ƒ được định nghĩa là ma trận đối xứng m x m với các phần tử 2ƒ VION, = quán, (œ),L<¡. Nếu ƒ là hàm khả vi liên tục hai lần tại mỗi điểm trong tập mở D C R" thì ƒ khả ơi liên tục hai lần trên D và được ký hiệu là ƒ Œ®(D). Khi dé, « € D vad € R", đạo hàm theo hướng của f tai x theo hướng d được định nghĩa như sau f'(x;d) = jim Œ +99) = ƒ@) = Vƒ()Td. 650 9 trong dé V f(x) la gradient cia ƒ tại z.

Với bất kỳ z,z + d€ D, nếu ƒ € C!(D) thì f(atd) = a) + [vse + eaFaa = see) Ƒ ` v9@ ue. “Tương tự, với mọi x,y € D, ta có L(y) = f(a) + Vƒ (ø + tíy — z))” (y — ø),t € (0,1).1) thi (f(y) - f(@)| Sly] sup › I/@)lI- €€L(z,w) trong dé L(x, y) la ký hiệu đoạn thẳng với điểm cuối z và 1. Véi bat ky « € Dd € R", dao hàm theo hướng lần hai của ƒ tại z theo hướng d được định nghĩa như sau f"(e;d) = lim LO Od) Prd) = dV? f(x)d. trong d6 V?f(x) la ma tran Hessian cita f tai x.

Với bất kỳ z,z + đ € D, tồn tai € € (z,z + đ) sao cho. TAP LOI Định nghĩa 1. (¡) Dường thẳng di qua hai điểm (hai vecta)a,b trong TR" là tập hợp tất cả các vectơ z € R” có dang {x € R"|x = aa + b;a,8 € R,a+ 8 = 1}. (ii) Doan thang néi hai diém a va b trong R" 1A tap hợp tất cả các vectơ # có dạng {z €R"lz = aa+ đb;a >0, > 0,a + đ = 1}.

Mot tap C C R” được gọi là một ứập lô nếu Œ chứa mọi đoạn thẳng đi qua hai điểm bất kỳ của nó. Tức là Œ lồi khi và chỉ khi Vz,u€ Œ;VA €[0,1] thì Az+(1—À)y€Œ., 2" nếu (ii) Tập hợp các tổ hợp afne của z1, z2,. zẺ thường được gọi là bao affine của các điểm này. Tập hợp Ở là lồi khi uà chỉ khi nó chứa mọi tổ hợp lồi của các điểm của nó.

Tức là, Œ lồi khi va chi khi a = 8 Vi du 1. Siéu phing H = {x € R"\p™x = a} la mot tập lồi, trong đó p€R" là một vectơ khác vectơ không, còn gọi là vectơ pháp tuyến và œ là một vô hướng. That vay, Văi,za € H và 9 € [0,1], p™ [6x1 + (1 — )x2] = a, thi Ox; + (1— 6)+a € H. Trong siêu phẳng H = {z € R"|pfz = a} , nếu œ = 0, nó trở thành một không gian con gồm các vectơ trực giao với ?.

“Tương tự, nửa không gian đóng H~ = {z € R"|pFz < 8} va Ht = {z € R"|pFz > đ} là các tập lồi đóng. Nửa không gian mở (ïJ)~ = {z € R"|pTx < B} va (H)* = {z € R"|pFz > đ} là các tập lồi mở. Tia C = {x € R"|x = xo + Ad, \ > 0} 1a mot tap lồi, trong đó đ€ R*" là một vectơ khác không, x € R" la diém c6 dinh. ‘That vay, Vari, 22 € C và À € |0, 1], ta có 2 = 29 + Aid, x2 = 29 + And, trong đó À¡, À; € [0, 1].

Giao hữu hạn các nửa không gian đóng, C=f{z€R"lpfz < 6, i=1,. được gọi là mnột tập đa điện, trong đó mỗi p; 1a một vectơ khác không, mỗi đ¡ là một số vô hướng (1 < ¡ < m). Chi ý rằng, các tập đa di: là các tập lồi. Vì một đẳng thức có thể được biểu diễn bằng hai bất đẳng thức, nên dưới đây là các ví dụ của tập đa diện: Œ=f{z€R"|Az=b,z > 0}, Œ=f{z€R"|Az >0,z > 0}.

Cho C nà C¿ là các tập lồi trên RR". (ii) Cy & Cy = {21 + x92, € Cl, x2 € Cy} Loi. Một tập C dude goi la nén néu: VÀ >0,Vz € Œ Àz € C. (ï) Một nón được gọi là nón lôi nếu nó đồng thời là một tập lồi.

() Một nón lồi được gọi là nón nhọn nếu nó không chứa đường thẳng, khi đó ta nói O là đỉnh của nón. Nếu nón lồi này là một tập lồi đa diện thì ta nói nó là nón lôi đa điện. Cho Œ C 8" là một tập lồi và z € C. được gọi là nón pháp tuyến ngodi cia C tai x.

được gọi là nón pháp tuyến trong của Ở tại #.HÀM LỒI Định nghĩa 1. Cho là một tập con, lồi và khác rỗng trong không.2) 10 Nếu —ƒ là một hàm lồi (lồi chặt, lồi mạnh) trên C thi f được gọi là hàm lõm ( lõm chặt, lõm mạnh) trên Ơ. Cho C C R" la mét tap lồi mnở, khác rỗng tà ƒ : Ở C Rầ" —› IR là hàm khé vi. Khi do, (i) f Udi khi va chi khi L(y) 2 fe) + VF(@)"(y—2),We,y EC.

trong đó, e > () là một hằng số. Cho Ở C R" là một tập lồi mỏ, khác rỗng tà hàm ƒ : Ơ C R" SR kha vi lién tuc hai lan. Khi đó, (i) ƒ lồi khi va chỉ khi ma trận Hessian của nó nửa xác định dương tại mỗi điểm trên C. (ii) ƒ lồi chặt khi uà chỉ khi ma trận Hessian của nó xác định dương tại mỗi điểm trên C.

Cho ánh xạ #': DCR" + R" (i) F la đơn điệu trên Dụ C D nếu (F(x) — F(w),+ — ) > 0,Yz,ụ € Dạ.+ — 0) > c|lz — w|Š,Yz,u € Do. Nếu ta cho £ = Vƒ theo định nghĩa trên, ta có thể nhận được định lý nói rằng, với hàm lồi ƒ, gradient Vƒ là một ánh xạ đơn diệu. Gid sit ham f : D CR" + R" khd vi trên tập mở D, tà ỚC D là một tập con lồi. Khi đó, (0) ƒ lồi trên Ở khi uà chỉ khi gradient W ƒ là đơn điệu, tức là (V/(œ)— Vƒf(w),z—) >0, Va,ye C.# — u) >0, Va,ye Ca Ay.

trong đó e > 0 là một hằng số của (1. (¡) Cho Ở là một tập con, lồi, khác rỗng của R" và hàm f:C + RU {+00, —oo}. Khi do, cde tập hợp: domf := {x €C: f(x) < +00}, epif = {(x,a) €C xR: f(x) <a}.