البرمجة التربيعية المتسلسلة

إذا لم تتضمن المسألة قيودًا على عدم المساواة (أي،${\displaystyle m_{I}=0}$) شروط الأمثلية من الدرجة الأولى (المعروفة أيضًا باسم شروط KKT )${\displaystyle \nabla {\mathcal {L}}(x,\sigma )=0}$هي مجموعة من المعادلات غير الخطية التي يمكن حلها بشكل تكراري باستخدام طريقة نيوتن . تعمل طريقة نيوتن على تحويل شروط كاروش-كون-تاكر إلى شروط خطية عند التكرار الحالي.${\displaystyle \left[x_{k},\sigma _{k}\right]^{T}}$، مما يوفر التعبير التالي لخطوة نيوتن${\displaystyle \left[d_{x},d_{\sigma }\right]^{T}}$:

${\displaystyle {\begin{bmatrix}d_{x}\\d_{\sigma }\end{bmatrix}}=-[\nabla _{xx}^{2}{\mathcal {L}}(x_{k},\sigma _{k})]^{-1}\nabla _{x}{\mathcal {L}}(x_{k},\sigma _{k})=-{\begin{bmatrix}\nabla _{xx}^{2}{\mathcal {L}}(x_{k},\sigma _{k})&\nabla g(x_{k},\sigma _{k})\\\nabla g^{T}(x_{k},\sigma _{k})&0\end{bmatrix}}^{-1}{\begin{bmatrix}\nabla f(x_{k})+\sigma _{k}\nabla g(x_{k})\\g(x_{k})\end{bmatrix}}}$،

أين${\displaystyle \nabla _{xx}^{2}{\mathcal {L}}(x_{k},\sigma _{k})}$يرمز إلى مصفوفة هيسيان لدالة لاغرانج، و${\displaystyle d_{x}}$و${\displaystyle d_{\sigma }}$يمثلان الإزاحتين الأولية والثنائية على التوالي. تجدر الإشارة إلى أنه لا يتم عكس مصفوفة لاغرانج الهيسية بشكل صريح، ويتم حل نظام خطي بدلاً من ذلك.

عندما يكون الهيسي اللاغرانجي${\displaystyle \nabla ^{2}{\mathcal {L}}(x_{k},\sigma _{k})}$إذا لم تكن المصفوفة موجبة تمامًا ، فقد لا توجد خطوة نيوتن، أو قد تُشير إلى نقطة ثابتة ليست صغرى محلية (بل كبرى محلية أو نقطة سرجية). في هذه الحالة، يجب تنظيم مصفوفة هيسيان لاغرانج، على سبيل المثال، يمكن إضافة مضاعف لمصفوفة الوحدة إليها بحيث تصبح المصفوفة الناتجة موجبة تمامًا.

تتمثل إحدى وجهات النظر البديلة للحصول على الإزاحات الثنائية الأولية في بناء وحل نموذج تربيعي محلي للمسألة الأصلية عند التكرار الحالي:

${\displaystyle {\begin{array}{rl}\min \limits _{d_{x}}&f(x_{k})+\nabla f(x_{k})^{T}d_{x}+{\frac {1}{2}}d_{x}^{T}\nabla _{xx}^{2}{\mathcal {L}}(x_{k},\sigma _{k})d_{x}\\\mathrm {s.t.} &g(x_{k})+\nabla g(x_{k})^{T}d_{x}=0.\end{array}}}$

تتوافق شروط الأمثلية لهذه المسألة التربيعية مع شروط كاروش-كون-تاكر الخطية للمسألة الأصلية. لاحظ أن الحد${\displaystyle f(x_{k})}$يمكن حذف في التعبير أعلاه، لأنه ثابت تحت${\displaystyle \min \limits _{d}}$المشغل.

في ظل وجود قيود عدم المساواة (${\displaystyle m_{I}>0}$), يمكننا بشكل طبيعي توسيع تعريف النموذج التربيعي المحلي الذي تم تقديمه في القسم السابق:

${\displaystyle {\begin{array}{rl}\min \limits _{d}&f(x_{k})+\nabla f(x_{k})^{T}d+{\frac {1}{2}}d^{T}\nabla _{xx}^{2}{\mathcal {L}}(x_{k},\lambda _{k},\sigma _{k})d\\\mathrm {s.t.} &h(x_{k})+\nabla h(x_{k})^{T}d\geq 0\\&g(x_{k})+\nabla g(x_{k})^{T}d=0.\end{array}}}$

تبدأ خوارزمية SQP من التكرار الأولي${\displaystyle (x_{0},\lambda _{0},\sigma _{0})}$في كل تكرار، يتم بناء وحل المسألة الفرعية QP؛ واتجاه خطوة نيوتن الناتج${\displaystyle [d_{x},d_{\lambda },d_{\sigma }]^{T}}$تُستخدم لتحديث التكرار الحالي:

${\displaystyle \left[x_{k+1},\lambda _{k+1},\sigma _{k+1}\right]^{T}=\left[x_{k},\lambda _{k},\sigma _{k}\right]^{T}+[d_{x},d_{\lambda },d_{\sigma }]^{T}.}$

تُكرر هذه العملية لـ${\displaystyle k=0,1,2,\ldots }$إلى أن يتم استيفاء معيار التقارب.