Vì sao phương pháp chiếu gradient thông thường dễ phân kỳ trên bài toán điểm yên ngựa?

Khi toán tử chỉ mang tính đơn điệu thuần túy mà không có tính đơn điệu mạnh (như trong các trò chơi song tuyến tính), hướng dịch chuyển của gradient vuông góc với hướng hướng tâm về nghiệm, làm cho quỹ đạo lặp quay thành các vòng xoắn ốc mở rộng dần ra xa nghiệm với mọi bước lặp cố định.

Bước ngoại suy tại điểm trung gian trong phương pháp extragradient mang lại lợi ích gì?

Bước ngoại suy tính toán giá trị toán tử tại điểm dự báo trung gian giúp thu thập thông tin độ cong của quỹ đạo lặp, tạo ra một thành phần suy giảm tựa ma sát số học nhằm triệt tiêu dao động quay và kéo điểm lặp tiếp theo co dần về tập nghiệm.

Thuật toán tách thuận nghịch Tseng cải tiến phương pháp extragradient ở điểm nào?

Thuật toán của Tseng thay thế phép chiếu metric thứ hai bằng một phép cộng véc tơ đại số tuyến tính trực tiếp, nhờ đó chỉ đòi hỏi duy nhất một phép tính toán tử phân giải (hoặc một phép chiếu) trong mỗi bước lặp, giúp giảm một nửa chi phí hình học trên các mô hình quy mô lớn.

Phương pháp extragradient là gì? Cơ chế và ứng dụng

Phương pháp extragradient (extragradient method, hoặc phương pháp ngoại gradient) là thuật toán lặp hai bước dùng để giải bài toán bất đẳng thức biến phân, bài toán điểm yên ngựa lồi lõm và các bài toán cân bằng trò chơi phi hợp tác, trong đó mỗi bước lặp sử dụng giá trị gradient hoặc toán tử tại một điểm trung gian dự báo để cập nhật trạng thái tiếp theo nhằm dập tắt các dao động quay phân kỳ.

Trong giải tích lồi hiện đại và lý thuyết phương trình biến phân, nhiều bài toán kỹ thuật và kinh tế quan trọng không thể quy về dạng tối thiểu hóa một hàm mục tiêu duy nhất. Các mô hình cân bằng kinh tế, bài toán bất đẳng thức biến phân và các kiến trúc học máy đối kháng đòi hỏi việc tìm kiếm điểm cân bằng đồng thời cho nhiều phía tham gia. Phương pháp chiếu gradient thông thường thường xuyên thất bại và rơi vào trạng thái phân kỳ xoắn ốc khi áp dụng cho các hệ thống này do sự thiếu hụt tính đơn điệu mạnh. Phương pháp extragradient do nhà toán học Galina M. Korpelevich đề xuất lần đầu tiên vào năm 1976 (được hệ thống hóa toàn diện trong chuyên khảo của Facchinei và Pang năm 2004) đã khắc phục nhược điểm cốt tử đó bằng cách bổ sung một bước tính toán thăm dò tại điểm trung gian, tạo ra một cơ chế tiêu tán năng lượng số học giúp quỹ đạo lặp hội tụ ổn định về tập nghiệm.

Bài toán bất đẳng thức biến phân và điểm yên ngựa

Xét một tập hợp con $C$ lồi, đóng và khác rỗng trong không gian Euclid $\mathbb{R}^n$ hoặc không gian Hilbert thực $H$ . Cho toán tử $F: C \to H$ là một ánh xạ đơn trị phi tuyến. Bài toán bất đẳng thức biến phân kinh điển yêu cầu tìm kiếm một véc tơ nghiệm $x^{*} \in C$ sao cho bất đẳng thức sau đây được thỏa mãn với mọi phần tử thử nghiệm:

\langle F(x^{*}), x - x^{*} \\rangle \ge 0 \quad \text{với mọi } x \in C

Trong biểu thức trên, dấu ngoặc nhọn biểu thị tích vô hướng tiêu chuẩn giữa hai véc tơ trong không gian đang xét. Toán tử được gọi là toán tử đơn điệu nếu với hai điểm bất kỳ, tích vô hướng giữa hiệu giá trị toán tử và hiệu vị trí luôn không âm:

\langle F(u) - F(v), u - v \\rangle \ge 0 \quad \text{với mọi } u, v \in C

Đồng thời, bài toán bất đẳng thức biến phân có mối liên hệ trực tiếp với bài toán tìm điểm yên ngựa của một hàm lồi lõm hai biến số. Giả sử hàm số $\phi(x, y)$ là hàm lồi đối với biến thứ nhất và là hàm lõm đối với biến thứ hai. Điểm yên ngựa được định nghĩa là cặp véc tơ $(x^{*}, y^{*})$ thỏa mãn hệ bất đẳng thức kép:

\phi(x^{*}, y) \le \phi(x^{*}, y^{*}) \le \phi(x, y^{*}) \quad \text{với mọi } x \in X, y \in Y

Bằng cách ghép hai biến thành một véc tơ trạng thái chung và xây dựng toán tử gradient ghép gồm đạo hàm riêng thành phần thứ nhất và đạo hàm riêng đổi dấu của thành phần thứ hai, bài toán tìm điểm yên ngựa hoàn toàn tương đương với việc giải bài toán bất đẳng thức biến phân với toán tử đơn điệu.

Hiện tượng dao động xoay và giới hạn của phương pháp gradient thông thường

Để giải bài toán bất đẳng thức biến phân có ràng buộc, cách tiếp cận trực giác nhất là sử dụng phương pháp chiếu gradient. Tại mỗi bước lặp, trạng thái được cập nhật bằng cách dịch chuyển dọc theo hướng ngược chiều của toán tử và chiếu trực giao trở lại tập lồi:

x_{k+1} = P_{C}(x_{k} - \alpha F(x_{k}))

Trong công thức trên, ký hiệu $P_{C}$ đại diện cho toán tử chiếu metric lên tập lồi đóng $C$ , và $\alpha > 0$ là độ dài bước lặp dương. Khi bài toán có tính đơn điệu mạnh hoặc toán tử thỏa mãn điều kiện đồng cưỡng chế, phương pháp chiếu gradient bảo đảm tính co và hội tụ hình học. Tuy nhiên, khi toán tử chỉ đơn thuần là đơn điệu mà không có tính đơn điệu mạnh, phương pháp chiếu gradient bộc lộ khiếm khuyết cơ bản.

Điển hình là bài toán trò chơi đối kháng song tuyến tính không ràng buộc, trong đó toán tử có tính chất phản đối xứng thuần túy. Hướng di chuyển của thuật toán gradient luôn vuông góc với hướng hướng tâm về điểm yên ngựa, khiến quỹ đạo lặp tạo thành các đường xoắn ốc mở rộng dần ra xa nghiệm với mọi độ dài bước dương cố định. Hiện tượng phân kỳ quay tròn này giải thích vì sao các thuật toán giải bài toán minimax cơ bản thường rơi vào chu kỳ dao động vô hạn hoặc mất kiểm soát nếu thiếu tính đồng cưỡng chế.

Cơ chế lặp hai bước của phương pháp extragradient

Phương pháp extragradient do Korpelevich đề xuất năm 1976 giải quyết triệt để hiện tượng xoắn ốc phân kỳ bằng cách tách mỗi chu kỳ cập nhật thành hai pha tính toán độc lập gồm bước dự báo trung gian và bước hiệu chỉnh chính thức. Thuật toán hoạt động theo hai công thức truy hồi liên tiếp:

Bước một (bước dự báo ngoại suy): Từ vị trí hiện tại, thuật toán tính toán một bước dịch chuyển thăm dò dọc theo hướng toán tử tại vị trí đó và thực hiện phép chiếu lên tập ràng buộc để xác định điểm trung gian:

y_{k} = P_{C}(x_{k} - \alpha F(x_{k}))

Bước hai (bước hiệu chỉnh nghiệm): Thay vì dùng giá trị toán tử tại điểm trung gian để cập nhật từ điểm trung gian, thuật toán quay trở lại điểm xuất phát ban đầu và thực hiện bước dịch chuyển thực tế dựa trên thông tin ngoại gradient được đánh giá tại điểm trung gian:

x_{k+1} = P_{C}(x_{k} - \alpha F(y_{k}))

Bản chất hình học của bước hiệu chỉnh nằm ở chỗ véc tơ toán tử được tính tại điểm dự báo đã mang thông tin định hướng của độ cong quỹ đạo lặp. Việc lấy hiệu giữa hai bước tính toán tạo ra một số hạng gia số tỷ lệ với bình phương độ dài bước đóng vai trò như một lực cản ma sát số học. Lực cản nội tại này kéo quỹ đạo lặp hướng vào bên trong vòng xoắn, triệt tiêu động năng quay và bảo đảm dãy lặp co dần về nghiệm với điều kiện độ dài bước lặp nhỏ hơn nghịch đảo của hằng số Lipschitz của toán tử.

Phương pháp chiếu siêu phẳng phân tách Solodov và Svaiter

Mặc dù phương pháp extragradient cổ điển bảo đảm tính hội tụ vững chắc, thuật toán đòi hỏi phải thực hiện hai phép chiếu metric lên tập lồi trong mỗi bước lặp. Khi tập ràng buộc có cấu trúc hình học phức tạp, chi phí tính toán của hai phép chiếu liên tiếp có thể trở thành điểm nghẽn nghiêm trọng.

Năm 1999 Solodov và Svaiter công bố phương pháp chiếu mới cho bài toán bất đẳng thức biến phân trên SIAM Journal on Control and Optimization. Solodov và Svaiter đã đề xuất một cơ chế chiếu siêu phẳng phân tách thông minh để khắc phục nhược điểm tính toán này. Thuật toán xây dựng một siêu phẳng phân tách nghiêm ngặt điểm lặp hiện tại khỏi tập nghiệm của bài toán biến phân.

Đóng góp cốt lõi của nghiên cứu của Solodov và Svaiter năm 1999 là việc chứng minh điểm lặp mới thu được bằng cách chiếu trực tiếp lên giao của tập lồi với siêu phẳng phân tách ( $C \cap H_{k}$ ). Bằng cách kết hợp phép tìm kiếm đường phù hợp, thuật toán Solodov Svaiter bảo đảm tính hội tụ toàn cục cho các bài toán giả đơn điệu mà chỉ cần một phép chiếu lên tập lồi kết hợp với phép chiếu lên siêu phẳng phụ trợ.

Phương pháp tách thuận nghịch cải tiến của Tseng

Song song với các bài toán có ràng buộc đơn giản, lớp bài toán bao gồm tổng của hai toán tử đơn điệu, trong đó một toán tử đơn giá trị trơn Lipschitz và một toán tử đa trị cực đại, đóng vai trò nền tảng trong tối ưu hóa và bao hàm vi phân. Năm 2000 Tseng đề xuất phương pháp tách thuận nghịch cải tiến cho các ánh xạ đơn điệu cực đại trên SIAM Journal on Control and Optimization.

Thuật toán của Tseng (thường được biết đến với tên gọi thuật toán tách Forward Backward Forward) cải tiến cấu trúc extragradient bằng cách kết hợp toán tử phân giải (resolvent operator). Quy trình lặp của Tseng gồm các thao tác liên tiếp:

y_{k} = J_{\alpha B}(x_{k} - \alpha A(x_{k}))

x_{k+1} = y_{k} - \alpha (A(y_{k}) - A(x_{k}))

Trong đó ký hiệu $J_{\alpha B} = (I + \alpha B)^{-1}$ đại diện cho toán tử phân giải của toán tử đa trị đơn điệu cực đại $B$ , và $A$ là toán tử đơn điệu liên tục Lipschitz. Đột phá quan trọng trong nghiên cứu của Tseng năm 2000 là việc chỉ yêu cầu duy nhất một lần tính toán tử phân giải (hoặc một phép chiếu metric khi xét bài toán ràng buộc) cùng hai lần đánh giá toán tử trơn trong mỗi bước lặp. Điểm cập nhật cuối cùng hoàn toàn là một phép cộng véc tơ đại số đơn giản mà không cần thực hiện thêm bất kỳ phép chiếu thứ hai nào, giúp thuật toán đạt hiệu năng tính toán xuất sắc trên các mô hình quy mô lớn.

Mở rộng Mirror Prox và tốc độ hội tụ tối ưu của Nemirovski

Đối với các bài toán trong không gian số chiều rất lớn hoặc trên các tập compact phi Euclid như đơn vị hình học đơn giản hoặc ma trận mật độ bán xác định dương, khoảng cách Euclid thông thường không phản ánh đúng hình học nội tại của bài toán. Năm 2004 Nemirovski công bố phương pháp Mirror Prox đạt tốc độ hội tụ $O(1/t)$ trên SIAM Journal on Optimization.

Nemirovski đã phát triển thuật toán Mirror Prox, một bước tổng quát hóa sâu sắc của phương pháp extragradient sang hình học phi Euclid bằng cách thay thế khoảng cách thông thường bằng hàm phân kỳ Bregman sinh bởi một hàm khoảng cách cơ sở lồi mạnh phù hợp. Thuật toán Mirror Prox thực hiện hai bước chiếu gương trong không gian đối ngẫu:

y_{k} = \text{argmin}_{z \in C} \{\alpha \langle F(x_{k}), z \\rangle + D_{\omega}(z, x_{k})\}

x_{k+1} = \text{argmin}_{z \in C} \{\alpha \langle F(y_{k}), z \\rangle + D_{\omega}(z, x_{k})\}

Trong các biểu thức trên, ký hiệu $D_{\omega}(z, x_{k})$ đại diện cho khoảng cách Bregman giữa hai điểm được xác định thông qua hàm khoảng cách cơ sở. Đóng góp mang tính cột mốc của Nemirovski năm 2004 là việc chứng minh toán học chặt chẽ rằng thuật toán Mirror Prox đạt tốc độ hội tụ tiệm cận ở mức tối ưu $O(1/t)$ đối với bài toán bất đẳng thức biến phân và bài toán điểm yên ngựa lồi lõm trơn có toán tử liên tục Lipschitz. Đây là tốc độ hội tụ không thể cải thiện thêm đối với lớp bài toán này theo lý thuyết độ phức tạp tính toán thông tin.

Phương pháp ngoại gradient dưới đạo hàm của Censor, Gibali và Reich

Nhằm giải quyết rào cản chi phí tính toán của hai phép chiếu metric trong không gian vô hạn chiều, các nhà toán học đã tìm kiếm cách thức thay thế phép chiếu thứ hai bằng các phép toán hình học đơn giản hơn. Năm 2011 Censor cùng Gibali và Reich công bố phương pháp ngoại gradient dưới đạo hàm trong không gian Hilbert trên Journal of Optimization Theory and Applications.

Nhóm tác giả Censor, Gibali và Reich đã giới thiệu thuật toán ngoại gradient dưới đạo hàm (subgradient extragradient method). Điểm khác biệt mấu chốt của thuật toán là bước thứ nhất vẫn giữ nguyên phép chiếu lên tập lồi ban đầu để sinh điểm trung gian, nhưng bước thứ hai thay thế phép chiếu phức tạp lên tập lồi bằng một phép chiếu trực giao lên một nửa không gian dưới đạo hàm được xác định bởi điểm trung gian:

T_{k} = \{x \in H : \langle (x_{k} - \alpha F(x_{k})) - y_{k}, x - y_{k} \\rangle \le 0\}

x_{k+1} = P_{T_{k}}(x_{k} - \alpha F(y_{k}))

Công trình của Censor và các cộng sự năm 2011 đã chứng minh rằng phép chiếu lên nửa không gian có nghiệm giải tích tường minh dạng đóng cực kỳ đơn giản, không yêu cầu giải bài toán tối ưu con lặp. Nhờ đó, thuật toán bảo toàn đầy đủ các tính chất hội tụ yếu của phương pháp extragradient gốc trong không gian Hilbert nhưng cắt giảm được một nửa độ phức tạp hình học ở mỗi vòng lặp.

Góc nhìn hiện đại từ học máy và trò chơi đối kháng

Kể từ năm 2014, sự phát triển của trí tuệ nhân tạo và mạng nơ-ron đối kháng tạo sinh (GAN) đã đưa phương pháp extragradient trở thành tâm điểm nghiên cứu của lý thuyết học sâu. Trong huấn luyện đối kháng, mô hình sinh và mô hình phân biệt cạnh tranh trực tiếp dưới dạng một trò chơi đối kháng, tạo thành bài toán điểm yên ngựa có độ phức tạp cao.

Năm 2020 Mokhtari cùng Ozdaglar và Pattathil công bố phân tích thống nhất về tốc độ hội tụ của phương pháp extragradient và phương pháp gradient lạc quan trên SIAM Journal on Optimization. Nhóm tác giả đã cung cấp một khung lý thuyết thống nhất dựa trên nguyên lý xấp xỉ thuật toán điểm tiệm cận gần kề (proximal point method).

Nghiên cứu của Mokhtari và cộng sự năm 2020 chứng minh rằng cả hai phương pháp extragradient và gradient lạc quan đều đóng vai trò xấp xỉ cấp một của toán tử điểm tiệm cận gần kề ẩn, thiết lập tốc độ hội tụ tiệm cận $O(1/k)$ của bình phương chuẩn gradient cho bài toán điểm yên ngựa lồi lõm trơn không ràng buộc. Trong thực hành huấn luyện mạng đối kháng (GAN), bước lặp ngoại gradient đóng vai trò phương pháp tính toán thực nghiệm hữu hiệu giúp ổn định hóa dao động xoay giữa hai mạng nơ-ron, dù việc bảo đảm hội tụ toàn cục cho các cảnh quan phi lồi phi lõm tổng quát vẫn là một bài toán mở của ngành.

Bảng đối chiếu các biến thể của phương pháp extragradient

Bảng dưới đây tổng hợp và so sánh các đặc tính thuật toán, chi phí tính toán trên mỗi bước lặp và phạm vi không gian áp dụng của các biến thể chính thuộc họ phương pháp ngoại gradient:

Biến thể thuật toán	Số phép chiếu lên tập lồi	Số lần đánh giá toán tử	Dạng không gian áp dụng	Đặc điểm nổi bật
Phương pháp extragradient cổ điển (1976)	Hai phép chiếu metric lên tập ràng buộc lồi	Hai lần tính toán tử tại điểm hiện tại và trung gian	Không gian Euclid hữu hạn chiều	Thiết kế nguyên bản của Korpelevich với hai bước chiếu trực giao bảo đảm hội tụ toán tử đơn điệu
Phương pháp Solodov Svaiter (1999)	Một phép chiếu lên tập lồi và một phép chiếu lên giao của tập lồi với siêu phẳng	Một hoặc nhiều lần đánh giá tùy thuộc phép tìm kiếm đường	Không gian Euclid và không gian Hilbert	Sử dụng siêu phẳng phân tách giúp mở rộng điều kiện hội tụ cho toán tử giả đơn điệu
Phương pháp tách thuận nghịch Tseng (2000)	Một phép tính toán tử phân giải (hoặc một phép chiếu)	Hai lần tính toán tử trơn liên tục Lipschitz	Không gian Hilbert thực	Loại bỏ hoàn toàn phép chiếu thứ hai bằng tổ hợp đại số tuyến tính trực tiếp
Phương pháp Mirror Prox Nemirovski (2004)	Hai bước chiếu gương qua phân kỳ Bregman	Hai lần tính toán tử tại điểm hiện tại và trung gian	Không gian Banach và tập compact phi Euclid	Đạt tốc độ hội tụ tối ưu cho bài toán điểm yên ngựa lồi lõm trơn
Ngoại gradient dưới đạo hàm Censor (2011)	Một phép chiếu lên tập lồi và một chiếu lên nửa không gian	Hai lần tính toán tử tại điểm hiện tại và trung gian	Không gian Hilbert thực	Phép chiếu thứ hai có công thức tường minh dạng đóng giúp tối ưu hóa chi phí

Phạm vi ứng dụng và ranh giới kỹ thuật

Phương pháp extragradient và các phiên bản mở rộng được ứng dụng rộng rãi trong nhiều lĩnh vực toán học và kỹ thuật hiện đại:

Bài toán cân bằng kinh tế và quy hoạch giao thông: Mô hình hóa cân bằng cung cầu thị trường, cân bằng Wardrop trong mạng lưới giao thông đô thị và bài toán bù phi tuyến.
Huấn luyện mạng đối kháng tạo sinh: Ổn định hóa động lực học huấn luyện giữa bộ sinh và bộ phân biệt, giảm thiểu hiện tượng sụp đổ mốt và triệt tiêu chu kỳ phân kỳ.
Lý thuyết trò chơi nhiều người chơi: Tìm kiếm điểm cân bằng Nash trong các trò chơi đơn điệu liên tục và bài toán tối ưu hóa phân tán trên mạng truyền thông.

Mặc dù sở hữu những ưu thế toán học vượt trội, phương pháp extragradient đòi hỏi người thực hành phải lưu ý các ranh giới kỹ thuật cốt tử:

Độ phức tạp tính toán tăng gấp đôi: Mỗi bước lặp đòi hỏi hai lần đánh giá toán tử và hai lần cập nhật trạng thái. Đối với các mạng nơ-ron có nhiều tham số, việc tính toán hai lần lan truyền xuôi và lan truyền ngược có thể làm tăng đáng kể thời gian xử lý và dung lượng bộ nhớ.
Phụ thuộc vào hằng số Lipschitz: Tính hội tụ của thuật toán yêu cầu độ dài bước lặp phải nhỏ hơn nghịch đảo của hằng số Lipschitz của toán tử. Khi hằng số này quá lớn hoặc không xác định trước, thuật toán đòi hỏi kỹ thuật tìm kiếm đường bước lặp phức tạp.
Giới hạn đối với bài toán phi lồi phi lõm: Các kết quả hội tụ lý thuyết vững chắc chủ yếu được thiết lập cho các bài toán đơn điệu hoặc lồi lõm trơn. Với các cảnh quan phi lồi phi lõm tổng quát, phương pháp vẫn có thể gặp khó khăn trong việc hội tụ về các điểm cân bằng cục bộ.