DOI: https://doi.org/10.1007/s10957-025-02885-0
تاريخ النشر: 2026-03-11
المؤلف: Mitsuaki Obara وآخرون
الموضوع الرئيسي: أبحاث خوارزميات التحسين المتقدمة
نظرة عامة
تستكشف هذه الورقة البحثية مشاكل تحسين ريمان مع قيود عدم المساواة والمساواة، مع التركيز على فئة من طرق النقاط الداخلية ريمان (IPMs). تتميز الخوارزمية المقترحة بتكرارات خارجية وداخلية، مما يظهر تقاربًا فائقًا محليًا من خلال حل نظام خطي في كل تكرار خارجي، مما يبسط التكرارات الداخلية. تم تقديم تحديث محدد لمعلمة الحاجز، مما يحقق تقاربًا قريبًا من التربيعي محليًا. يتم تطبيق النتائج على الطريقة التي قدمها أوبارا، وأوكونو، وتاكيدا (2026)، مما يؤكد تقاربها الفائق المحلي والقريب من التربيعي جنبًا إلى جنب مع تحليل الاستقرار من الدرجة الثانية. من الجدير بالذكر أن هذا العمل يقدم أول خوارزمية لتحسين مقيد على مانيفولدات ريمان تضمن كل من التقارب المحلي والعالمي إلى نقطة مستقرة من الدرجة الثانية، مدعومة بالنتائج العددية.
في الختام، تسلط الورقة الضوء على التقدم النظري في IPMs ريمان، خاصة من خلال الخوارزمية 1، وتناقش اتجاهات البحث المستقبلية. تشمل هذه الاتجاهات تحسين تحديثات معلمة الحاجز، وتطوير التكرارات الداخلية مع التقارب العالمي، وتحسين حسابات اتجاه البحث، ومعالجة المشاكل المتدهورة، واستكشاف التقارب المحلي إلى الحد الأدنى المحلي غير الصارم. يؤكد المؤلفون على الحاجة إلى تحسينات عملية وإمكانية توسيع الطرق الحالية لتحقيق التقارب العالمي في إعدادات أكثر شمولاً، مما يعزز مجال تحسين ريمان.
مقدمة
في هذه الورقة، يتناول المؤلفون مشكلة تحسين ريمان غير الخطية (RNLO)، المعرفة بتقليل دالة \( f(x) \) على مانيفولد ريمان متصل وكامل \( M \) مع مراعاة قيود عدم المساواة \( g_i(x) \geq 0 \) وقيود المساواة \( h_j(x) = 0 \). تكمن أهمية تحسين ريمان في قدرته على الحفاظ على هياكل المانيفولد وضمان القابلية، والتي غالبًا ما تتعرض للخطر في تحسين إقليدي. يبرز المؤلفون أن طرق ريمان يمكن أن تحقق حلولًا أكثر دقة، خاصة في التطبيقات التي تتضمن هياكل هندسية محددة، مثل المصفوفات المحددة الإيجابية ومانيفولدات غراسمن.
تستعرض الورقة التقدمات الأخيرة في تحسين ريمان المقيد، بما في ذلك شروط الأمثلية وطرق مختلفة مثل عقوبة دقيقة وطرق لاغرانج المعززة، التي أظهرت خصائص تقارب عالمي. من الجدير بالذكر أن المؤلفين يركزون على طرق النقاط الداخلية (IPMs) لتحسين ريمان، والتي لا تزال غير مستكشفة مقارنة بنظيراتها الإقليدية. يشيرون إلى الأعمال السابقة التي قدمت IPMs ريمان مع ضمانات تقارب عالمي ومحلي. يجادل المؤلفون بأن تطوير هذه الطرق أمر حاسم لتحقيق دقة عالية في حل مشاكل التحسين مع قيود غير خطية، خاصة في مجالات مثل نظرية التحكم، حيث تشمل التطبيقات تحديد الأنظمة المستقرة وتقليل النموذج الأمثل H2.
طرق
في هذا القسم، يوضح المؤلفون البيئة التجريبية والمنهجيات المستخدمة لمقارنة ثلاثة خوارزميات: RIPME (طريقة النقاط الداخلية ريمان مع خطوات الاستقراء)، RIPTRM (طريقة النقاط الداخلية ريمان في منطقة الثقة)، وGlobalRIPM (طريقة النقاط الداخلية ريمان المتقاربة عالميًا). تستخدم تنفيذ RIPME طريقة الباقي المترافق لحل الأنظمة الخطية، كما هو مذكور في الأعمال السابقة. يتبع تحديث معلمة الحاجز معادلة محددة (35). يعتمد تنفيذ RIPTRM على ورقة رفيقة، مع إجراء تعديلات على المعلمة \( r \) في المعادلة (35). يتم تنفيذ الخوارزميات GlobalRIPM وLocalRIPM وRALM وRSQO باستخدام أكواد MATLAB من المؤلفين الأصليين، باستثناء أن RALM تستخدم الانحدار التدرجي بدلاً من طريقة BFGS ذات الذاكرة المحدودة بسبب مشاكل التوافق مع إطار Pymanopt 2.2.1.
لتقييم أداء هذه الخوارزميات، يقدم المؤلفون مقياسًا للباقي لتقييم انحراف تكرار عن مجموعة نقاط كاروش-كون-تاكر (KKT). يتم تعريف هذا الباقي في المعادلة (49)، ويشمل مصطلحات تعكس شروط KKT وانتهاك قيود المانيفولد. بشكل محدد، تتناول المصطلحان الأولان شروط KKT، بينما تقوم الدالة \( \text{Manvio}(X) \) بتحديد انتهاك قيود المانيفولد، حيث تعيد \( +\infty \) إذا كانت المصفوفة \( X \) تحتوي على قيمة ذاتية سالبة و\( 0 \) بخلاف ذلك. تتيح هذه المقاربة الشاملة مقارنة قوية لفعالية الخوارزميات في تلبية شروط KKT والحفاظ على قيود المانيفولد.
نتائج
في هذا القسم، يقدم المؤلفون نتائج طرقهم المقترحة، RIPME وRIPTRM، المطبقة على حالة تم إنشاؤها عشوائيًا مع قيم مختلفة لمعامل الحاجز \( r \in \{0.01, 0.1, 0.25, 0.5, 0.75, 0.99\} \). تشير النتائج إلى أن RIPME حققت تقاربًا محليًا سريعًا إلى حل بمجرد أن انخفض معامل الحاجز إلى عتبة الخطأ العددي \( 10^{-16} \). بالمقابل، أظهرت RIPTRM انتقالًا سلسًا من التقارب العالمي إلى المحلي، مع سلوك مستقر يتماشى مع التوقعات النظرية. بشكل محدد، بالنسبة لـ \( r \leq 0.25 \)، استخدمت RIPTRM تكرارًا داخليًا واحدًا تلاه تحديث لـ \( \mu_k \)، بينما بالنسبة لـ \( r \geq 0.5 \)، ت alternated بين تكرارين داخليين وتحديث، مما أدى إلى تقليل تدريجي للبقايا، على الرغم من بعض الانحرافات عن التوقعات النظرية.
بالإضافة إلى ذلك، أجرى المؤلفون تحليلًا مقارنًا لطرقهم مقابل الطرق الموجودة من خلال إنشاء حالة أخرى \( A \) مع 20 نقطة أولية، مع تعيين \( r = 0.25 \) لكل من RIPME وRIPTRM. تشير النتائج، الموضحة في مخططات الصندوق للبقايا من 20 تجربة، إلى أن كل من RIPME وRIPTRM حلا الحالات بفعالية بدقة عالية، مما يظهر قوتهما وموثوقيتهما في تحقيق الحلول المثلى.
نقاش
في هذا القسم، يقدم المؤلفون مساهماتهم في تحليل طرق النقاط الداخلية ريمان (IPMs) لحل مشاكل تحسين ريمان غير الخطية (RNLO). يقدمون هيكل خوارزمية مزدوجة الحلقة تتكون من تكرار خارجي يختار النقاط الأولية وظروف التوقف، وتكرار داخلي يحسب التكرارات اللاحقة. يثبت المؤلفون تقاربًا فائقًا محليًا وقريبًا من التربيعي لخوارزميتهم المقترحة، موسعين المنهجيات السابقة إلى سياق RNLO. من الجدير بالذكر أنهم يظهرون أن الخوارزمية يمكن أن تحقق التقارب المحلي دون الحاجة إلى تكرارات داخلية، وهو تقدم كبير مقارنة بالطرق الحالية.
بالإضافة إلى ذلك، يحلل المؤلفون التقارب المحلي لطريقة النقاط الداخلية ريمان في منطقة الثقة (RIP-TRM) تحت ظروف معينة، مما يجعلها أول خوارزمية لتحسين مقيد على مانيفولدات ريمان تحقق كل من التقارب المحلي والعالمي إلى نقاط مستقرة من الدرجة الثانية (SOSP). تؤكد تجاربهم العددية النتائج النظرية، حيث تظهر باستمرار الخصائص المرغوبة للتقارب وتحقق حلولًا عالية الدقة. يختتم القسم بتنظيم مفصل للورقة، موضحًا الأقسام التالية التي تتناول مفاهيم هندسة ريمان، وإثباتات التقارب، والتطبيقات العددية.
DOI: https://doi.org/10.1007/s10957-025-02885-0
Publication Date: 2026-03-11
Author(s): Mitsuaki Obara et al.
Primary Topic: Advanced Optimization Algorithms Research
Overview
This research paper investigates Riemannian optimization problems with both inequality and equality constraints, focusing on a class of Riemannian interior point methods (IPMs). The proposed algorithm features outer and inner iterations, demonstrating local superlinear convergence by solving a linear system at each outer iteration, which simplifies the inner iterations. A specific update for the barrier parameter is introduced, achieving local near-quadratic convergence. The findings are applied to the method by Obara, Okuno, and Takeda (2026), confirming its local superlinear and near-quadratic convergence alongside an analysis of second-order stationarity. Notably, this work presents the first algorithm for constrained optimization on Riemannian manifolds that guarantees both local and global convergence to a second-order stationary point, supported by numerical results.
In conclusion, the paper highlights the theoretical advancements in Riemannian IPMs, particularly through Algorithm 1, and discusses future research directions. These include enhancing barrier parameter updates, developing inner iterations with global convergence, improving search direction computations, addressing degenerate problems, and exploring local convergence to non-strict local minima. The authors emphasize the need for practical improvements and the potential for extending existing methods to achieve global convergence in more comprehensive settings, thereby advancing the field of Riemannian optimization.
Introduction
In this paper, the authors address the Riemannian nonlinear optimization problem (RNLO), defined as minimizing a function \( f(x) \) over a connected, complete Riemannian manifold \( M \) while satisfying inequality constraints \( g_i(x) \geq 0 \) and equality constraints \( h_j(x) = 0 \). The significance of Riemannian optimization lies in its ability to preserve manifold structures and ensure feasibility, which is often compromised in Euclidean optimization. The authors highlight that Riemannian methods can yield more accurate solutions, particularly in applications involving specific geometrical structures, such as positive definite matrices and Grassmann manifolds.
The paper reviews recent advancements in constrained Riemannian optimization, including optimality conditions and various methods such as exact penalty and augmented Lagrangian approaches, which have demonstrated global convergence properties. Notably, the authors focus on interior point methods (IPMs) for Riemannian optimization, which remain underexplored compared to their Euclidean counterparts. They reference previous work that has introduced Riemannian IPMs with global and local convergence guarantees. The authors argue that developing these methods is crucial for achieving high accuracy in solving optimization problems with nonlinear constraints, particularly in fields like control theory, where applications include stable system identification and H2 optimal model reduction.
Methods
In this section, the authors detail the experimental environment and methodologies employed to compare three algorithms: RIPME (Riemannian interior point method with extrapolation steps), RIPTRM (Riemannian interior point trust region method), and GlobalRIPM (a globally convergent Riemannian interior point method). The implementation of RIPME utilizes the conjugate residual method for solving linear systems, as referenced in prior work. The barrier parameter update follows a specified equation (35). The RIPTRM implementation is based on a companion paper, with adjustments made to the parameter \( r \) in equation (35). The algorithms GlobalRIPM, LocalRIPM, RALM, and RSQO are executed using MATLAB codes from the original authors, with the exception that RALM employs gradient descent instead of the limited-memory BFGS method due to compatibility issues with the Pymanopt 2.2.1 framework.
To evaluate the performance of these algorithms, the authors introduce a residual measure for assessing the deviation of an iterate from the set of Karush-Kuhn-Tucker (KKT) points. This residual, defined in equation (49), incorporates terms that reflect the KKT conditions and the violation of manifold constraints. Specifically, the first two terms address the KKT conditions, while the function \( \text{Manvio}(X) \) quantifies the violation of the manifold constraints, returning \( +\infty \) if the matrix \( X \) has a negative eigenvalue and \( 0 \) otherwise. This comprehensive approach allows for a robust comparison of the algorithms’ effectiveness in meeting the KKT conditions and maintaining manifold constraints.
Results
In this section, the authors present the results of their proposed methods, RIPME and RIPTRM, applied to a randomly generated instance with varying barrier parameter values \( r \in \{0.01, 0.1, 0.25, 0.5, 0.75, 0.99\} \). The findings indicate that RIPME achieved rapid local convergence to a solution once the barrier parameter decreased to the numerical error threshold of \( 10^{-16} \). In contrast, RIPTRM demonstrated a smooth transition from global to local convergence, exhibiting stable behavior consistent with theoretical expectations. Specifically, for \( r \leq 0.25 \), RIPTRM utilized one inner iteration followed by an update of \( \mu_k \), while for \( r \geq 0.5 \), it alternated between two inner iterations and an update, resulting in a stepwise reduction of residuals, albeit with some deviations from theoretical predictions.
Additionally, the authors conducted a comparative analysis of their methods against existing ones by generating another instance \( A \) with 20 initial points, setting \( r = 0.25 \) for both RIPME and RIPTRM. The results, illustrated in box plots of the residuals from 20 runs, indicate that both RIPME and RIPTRM effectively solved the instances with high accuracy, demonstrating their robustness and reliability in achieving optimal solutions.
Discussion
In this section, the authors present their contributions to the analysis of Riemannian Interior Point Methods (IPMs) for solving Riemannian Nonlinear Optimization Problems (RNLO). They introduce a double-loop algorithm structure comprising an outer iteration that selects initial points and stopping conditions, and an inner iteration that computes subsequent iterates. The authors establish local superlinear and near-quadratic convergence for their proposed algorithm, extending previous methodologies to the RNLO context. Notably, they demonstrate that the algorithm can achieve local convergence without requiring inner iterations, which is a significant advancement over existing methods.
Additionally, the authors analyze the local convergence of the Riemannian Interior Point Trust Region Method (RIP-TRM) under specific conditions, marking it as the first algorithm for constrained optimization on Riemannian manifolds to achieve both local and global convergence to second-order stationary points (SOSP). Their numerical experiments corroborate the theoretical findings, consistently exhibiting the desired convergence properties and yielding high-accuracy solutions. The section concludes with a detailed organization of the paper, outlining subsequent sections that delve into Riemannian geometry concepts, convergence proofs, and numerical applications.