مسح خوارزميات الأولي-المزدوج: من نقاط السرج المحدبة-المقعرة إلى المسائل غير المحدبة وغير المقعرة
A Survey of Primal–Dual Algorithms: From Convex–Concave Saddle Points to Nonconvex–Nonconcave Problems
| المؤلف |
Iyad WALWIL* |
| محكمة |
نعم |
| الدولة |
اليمن |
| سنة النشر |
2026 |
| الشهر |
July |
| المجلد |
13 |
| العدد |
22 |
| DOI |
https://aust.uni.ye/article/22/1437
|
| ISSN |
2410-1818 |
| نوع المحتوى |
بحوث ومقالات |
| اللغة |
العربية |
| قواعد المعلومات |
HumanIndex |
| رابط المحتوى |
تحميل PDF
|
الملخص
البحث
أصبحت خوارزميات الأولي-المزدوج ركيزةً أساسيةً في التحسين الحديث، إذ تُقدّم إطاراً موحداً لمعالجة المسائل المنظّمة التي تتضمّن في آنٍ واحد متغيرات أولية ومضاعفات مزدوجة. يعود نطاق تطبيقها الواسع إلى الملاحظة القائلة بأن طيفاً عريضاً من نماذج التحسين يمكن صياغته على شكل مسائل نقطة السرج، حيث يتجلّى التفاعل بين الجدوى الأولية والمثالية المزدوجة بصورة صريحة.
يُقدّم هذا المسح مراجعةً منهجيةً لخوارزميات الأولي-المزدوج عبر أربع فئات من المسائل تتصاعد تدريجياً في عموميّتها: (أ) مسائل نقطة السرج المحدبة-المقعرة، (ب) المسائل غير المحدبة ذات القيود الاشتراطية التآلفية، (ج) مسائل نقطة السرج غير المحدبة-المقعرة، و(د) الفئة الأعمّ والأكثر تحدياً وهي المسائل غير المحدبة وغير المقعرة. ولكل فئة، نتتبع التطور التاريخي للخوارزميات الرئيسية، ونناقش الرؤى النظرية الكامنة التي تُمكّن التقارب، ونسلّط الضوء على أوجه الترابط بين المنهجيات المختلفة.
يبدأ عرضنا بطريقة Arrow-Hurwicz-Uzawa الكلاسيكية من خمسينيات القرن الماضي، ثم ينتقل عبر طريقة النقطة القريبة، وتشعيب الأمام-الخلف، والمتغيرات ذات الأساس الإضافي، وطريقة ADMM، وطريقة PDHG، قبل الانتقال إلى مسائل التحسين الحديثة غير المحدبة. وفي النطاق غير المحدب، نستعرض طرق لاغرانج المعزّزة، ومتغيرات ADMM غير المحدبة، وتحليل نزول-صعود التدرج، وإطار متباينات Minty الضعيفة الحديثة الذي يُشكّل الأساس لخوارزميات متطورة كـEG+ وBC-SEG+ لمعالجة مسائل نقطة السرج غير المحدبة-غير المقعرة. يهدف هذا المسح إلى تقديم منظور تاريخي ودليل عملي للباحثين والمختصين العاملين في تقاطع التحسين والتعلم الآلي ومعالجة الإشارات.
الكلمات المفتاحية: خوارزميات الأولي-المزدوج، مسائل نقطة السرج، التحسين المحدب-المقعر، التحسين غير المحدب، ADMM، PDHG، التدرج الإضافي، متباينات التغيّر، تحسين الحد الأدنى-الأقصى، العوامل الرتيبة.
Abstract
ABSTRACT
Primal–dual algorithms have become a cornerstone of modern optimization, offering a unified framework for tackling structured problems that involve both primal variables and dual multipliers simultaneously. Their broad applicability stems from the observation that a wide variety of optimization models can be cast as saddle point problems, in which the interplay between primal feasibility and dual optimality is made explicit.
This survey provides a structured review of primal–dual algorithms across four progressively general problem classes: (i) convex–concave saddle point problems, (ii) nonconvex problems with affine equality constraints, (iii) nonconvex–concave saddle point problems, and (iv) the most general class of nonconvex–nonconcave problems. For each setting, we trace the historical development of key algorithms, discuss the underlying theoretical insights that enable convergence, and highlight the connections between methods.
Our exposition begins with the classical Arrow–Hurwicz–Uzawa method of the 1950s and proceeds through the proximal point method, forward–backward splitting, extra-gradient variants, ADMM, and PDHG, before moving into modern nonconvex territory. In the nonconvex regime, we survey augmented Lagrangian methods, nonconvex ADMM variants, gradient descent–ascent analysis, and the recent weak Minty variational inequality framework that underlies state-of-the-art algorithms for nonconvex–nonconcave saddle points. The goal of this survey is to offer both a historical perspective and a practical guide to researchers and practitioners working at the intersection of optimization, machine learning, and signal processing.
Keywords: primal–dual algorithms, saddle point problems, convex–concave optimization, nonconvex optimization, ADMM, PDHG, extra-gradient, variational inequalities, min–max optimization, monotone operators.
أبحاث أخرى
لا توجد أبحاث أخرى حالياً لنفس الباحث
أبحاث مشابهة
لا توجد أبحاث مشابهة حالياً
