DOI: https://doi.org/10.1007/s11075-026-02360-5
تاريخ النشر: 2026-04-01
المؤلف: Andrea Brilli وآخرون
الموضوع الرئيسي: أبحاث خوارزميات التحسين المتقدمة
نظرة عامة
في هذا البحث، يقدم المؤلفون نهجًا جديدًا لحل مشاكل تحسين غير خطية مقيدة بدون اشتقاقات من خلال دمج طريقة عقوبة مختلطة-نقطة داخلية مع تقنيات البحث المباشر. تستخدم الطريقة المقترحة دالة جدارة تصنف القيود غير الخطية إلى مجموعتين: واحدة تُدار من خلال نهج حاجز لوغاريتمي، بينما يتم التعامل مع الأخرى، جنبًا إلى جنب مع القيود المتساوية، عبر مصطلح عقوبة. تم تكييف هذا الإطار إلى طريقة بحث مباشر، مما يسهل الإدارة الفعالة للقيود غير الخطية العامة. يثبت المؤلفون التقارب إلى نقاط كروش-كون-تاكر (KKT) الثابتة تحت فرضية التفاضل المستمر، دون الحاجة إلى تقعر الدوال المعنية.
تقوم الدراسة أيضًا بتوسيع خوارزمية SID-PSM، وهي طريقة بحث نمطية عامة، من خلال دمج نماذج متعددة الحدود لتعزيز الأداء العددي خلال خطوات البحث والاستطلاع. تحتفظ الخوارزمية المقترحة حديثًا، LOG-DS، بالميزات الأساسية لـ SID-PSM بينما تستخدم دالة جدارة مختلطة-حاجز لوغاريتمي للتعامل مع القيود غير الخطية والعامة. تظهر التجارب العددية الواسعة التي أجريت على مشاكل اختبار CUTEst أن LOG-DS تظهر قوة وكفاءة وفعالية عامة عند مقارنتها بعدد من الحلول الرائدة في هذا المجال.
مقدمة
في هذا القسم، يتناول المؤلفون مشكلة تحسين بدون اشتقاقات تتميز بقيود عامة، سواء كانت خطية أو غير خطية، تم صياغتها على النحو التالي:
\[
\min f(x) \quad \text{s.t.} \quad g_\ell(x) \leq 0, \quad \ell = 1, \ldots, m, \quad h_j(x) = 0, \quad j = 1, \ldots, p, \quad x \in X,
\]
حيث \( f: X \to \mathbb{R} \)، \( g_\ell: X \to \mathbb{R} \)، و \( h_j: X \to \mathbb{R} \) هي دوال قابلة للاشتقاق بشكل مستمر، و \( X = \{ x \in \mathbb{R}^n \mid Ax \leq b \} \) مع \( A \in \mathbb{R}^{q \times n} \) و \( b \in \mathbb{R}^q \). يبرز المؤلفون التحدي المتمثل في تحسين السياقات التي لا يمكن فيها حساب المشتقات، وهو سيناريو شائع في تحسينات قائمة على المحاكاة.
تستعرض الورقة تطور طرق تحسين مقيدة بدون اشتقاقات، بدءًا من تقنيات البحث النمطية المبكرة التي طورها لويس وتورزون، والتي تناولت كل من القيود الخطية وغير الخطية. تناقش استراتيجيات متنوعة، بما في ذلك استخدام طرق لاغرانج المعززة وإطار البحث المباشر التكيفي (MADS)، الذي يستخدم نهج حاجز متطرف لإدارة القيود. كما يذكر المؤلفون التقدم مثل تقنية الحاجز التقدمي ودمج دوال الجدارة التي تسهل التعامل مع كل من القيود غير المتساوية والمتساوية، مما يحسن كفاءة وموثوقية عمليات التحسين في غياب معلومات المشتقات.
النتائج
في هذا القسم، يقدم المؤلفون نتائج أولية لطريقتهم المقترحة، والتي تتضمن الحد الأدنى المتسلسل لدالة الجدارة \( Z(\cdot; \rho_k) \) عبر تسلسل متناقص من معلمات حاجز العقوبة \( \{\rho_k\} \). فرضية حاسمة لفعالية الطريقة هي وجود حل أمثل لكل مشكلة تقليل \( (P_{\rho_k}) \). لضمان ذلك، يؤكد المؤلفون على ضرورة كون مجموعات المستوى الأدنى للدالة الهدف مضغوطة، تحديدًا \( L_{\rho}(\alpha) = \{x \in X \mid Z(x; \rho) \leq \alpha\} \) لكل \( \rho > 0 \). يشيرون إلى اللمحة 2.5 لدعم هذه الفرضية.
تسلط قسم النتائج والتحليل الضوء على الأداء العددي لخوارزمية LOG-DS، موضحة فعاليتها مقارنة بـ SID-PSM وغيرها من الحلول الرائدة في هذا المجال. يهدف المؤلفون إلى إثبات أن طريقتهم لا تلبي فقط المتطلبات النظرية ولكنها تتفوق أيضًا في التطبيقات العملية.
مناقشة
في هذا القسم، يقدم المؤلفون مساهماتهم في مجال تحسين القيود غير الخطية من خلال تطوير خوارزمية LOG-DS، التي تدمج نهج البحث النمطي العام (GPS) مع طريقة حاجز عقوبة مختلطة-لوغاريتمية. تم تصميم هذه الخوارزمية للتعامل بفعالية مع القيود غير الخطية من خلال تقسيم مجموعة القيود إلى مجموعتين فرعيتين بناءً على تخمين أولي، مما يضمن بقاء دالة الجدارة محددة بشكل جيد. تتضمن دالة الجدارة، التي تُرمز بـ \( Z(x; \rho) \)، مصطلحات حاجز لوغاريتمي للقيود غير المتساوية ومصطلحات عقوبة خارجية للقيود المتساوية، مما يسهل عملية التحسين.
تم تحديد هيكل الخوارزمية في عملية تكرارية من ثلاث خطوات: خطوة بحث، خطوة استطلاع، وخطوة تحديث حاجز العقوبة. تتيح خطوة البحث استكشافًا هيكليًا لمساحة الحل، بينما تقوم خطوة الاستطلاع بتقييم الاتجاهات الطبيعية لتحديد التحسينات المحتملة. تعدل خطوة تحديث حاجز العقوبة معلمات العقوبة بناءً على نجاح التكرارات السابقة، مما يضمن التقارب نحو حل المشكلة الأصلية. يثبت المؤلفون خصائص التقارب لخوارزمية LOG-DS، موضحين أن تسلسل معلمات العقوبة يتقارب إلى الصفر، وهو أمر ضروري لتحقيق الأمثلية في سياق المشكلة المحددة. يدعم الإطار النظري افتراضات تتعلق بكثافة المنطقة القابلة للحل وسلوك الخوارزمية بالقرب من الحل، مما يؤدي إلى نظرية تقارب تضمن نقاط ثابتة تحت ظروف معينة.
DOI: https://doi.org/10.1007/s11075-026-02360-5
Publication Date: 2026-04-01
Author(s): Andrea Brilli et al.
Primary Topic: Advanced Optimization Algorithms Research
Overview
In this research, the authors introduce a novel approach for solving nonlinearly constrained derivative-free optimization problems by integrating a mixed penalty-interior point method with direct search techniques. The proposed method employs a merit function that categorizes nonlinear inequality constraints into two groups: one is managed through a logarithmic barrier approach, while the other, along with equality constraints, is addressed via a penalization term. This framework is adapted into a direct search method, facilitating the effective management of general nonlinear constraints. The authors establish convergence to Karush-Kuhn-Tucker (KKT) stationary points under the assumption of continuous differentiability, without necessitating convexity of the involved functions.
The study further extends the SID-PSM algorithm, a generalized pattern search method, by incorporating polynomial models to enhance numerical performance during both search and poll steps. The newly proposed algorithm, LOG-DS, retains the fundamental features of SID-PSM while utilizing a mixed penalty-logarithmic barrier merit function to tackle both general nonlinear and linear constraints. Extensive numerical experiments conducted on CUTEst test problems demonstrate that LOG-DS exhibits robustness, efficiency, and overall effectiveness when compared to several leading solvers in the field.
Introduction
In this section, the authors address a derivative-free optimization problem characterized by general constraints, both linear and nonlinear, formulated as:
\[
\min f(x) \quad \text{s.t.} \quad g_\ell(x) \leq 0, \quad \ell = 1, \ldots, m, \quad h_j(x) = 0, \quad j = 1, \ldots, p, \quad x \in X,
\]
where \( f: X \to \mathbb{R} \), \( g_\ell: X \to \mathbb{R} \), and \( h_j: X \to \mathbb{R} \) are continuously differentiable functions, and \( X = \{ x \in \mathbb{R}^n \mid Ax \leq b \} \) with \( A \in \mathbb{R}^{q \times n} \) and \( b \in \mathbb{R}^q \). The authors highlight the challenge of optimizing in contexts where derivatives cannot be computed, a common scenario in simulation-based optimization.
The paper reviews the evolution of constrained derivative-free optimization methods, starting from early pattern search techniques developed by Lewis and Torczon, which addressed both linear and nonlinear constraints. It discusses various strategies, including the use of augmented Lagrangian methods and the Mesh Adaptive Direct Search (MADS) framework, which employs an extreme barrier approach to manage constraints. The authors also mention advancements such as the progressive barrier technique and the incorporation of merit functions that facilitate the handling of both inequality and equality constraints, thereby improving the efficiency and robustness of optimization processes in the absence of derivative information.
Results
In this section, the authors present preliminary results for their proposed method, which involves the sequential minimization of the merit function \( Z(\cdot; \rho_k) \) across a decreasing sequence of penalty-barrier parameters \( \{\rho_k\} \). A critical assumption for the method’s efficacy is the existence of an optimal solution for each minimization problem \( (P_{\rho_k}) \). To ensure this, the authors assert the necessity of the compactness of the lower-level sets of the objective function, specifically \( L_{\rho}(\alpha) = \{x \in X \mid Z(x; \rho) \leq \alpha\} \) for all \( \rho > 0 \). They reference Lemma 2.5 to substantiate this assumption.
The results and analysis section highlights the numerical performance of the LOG-DS algorithm, showcasing its effectiveness in comparison to the SID-PSM and other leading solvers in the field. The authors aim to demonstrate that their method not only meets theoretical requirements but also excels in practical applications.
Discussion
In this section, the authors present their contributions to the field of nonlinear constrained optimization through the development of the LOG-DS algorithm, which integrates a generalized pattern search (GPS) approach with a mixed penalty-logarithmic barrier method. This algorithm is designed to effectively handle nonlinear constraints by partitioning the set of constraints into two subsets based on an initial guess, ensuring that the merit function remains well-defined. The merit function, denoted as \( Z(x; \rho) \), incorporates logarithmic barrier terms for inequality constraints and exterior penalty terms for equality constraints, facilitating the optimization process.
The algorithm’s structure is outlined in a three-step iterative process: a search step, a poll step, and a penalty-barrier update step. The search step allows for heuristic exploration of the solution space, while the poll step evaluates normalized directions to identify potential improvements. The penalty-barrier update step adjusts the penalty parameters based on the success of the previous iterations, ensuring convergence towards a solution of the original problem. The authors establish convergence properties of the LOG-DS algorithm, demonstrating that the sequence of penalty parameters converges to zero, which is essential for achieving optimality in the context of the defined problem. The theoretical framework is supported by assumptions regarding the compactness of the feasible region and the behavior of the algorithm near the solution, culminating in a convergence theorem that guarantees stationary points under certain conditions.