2025-11-18T17:07:13.972479

An Augmented Lagrangian Method on GPU for Security-Constrained AC Optimal Power Flow

Pacaud, Nurkanović, Pozharskiy et al.
We present a new algorithm for solving large-scale security-constrained optimal power flow in polar form (AC-SCOPF). The method builds on Nonlinearly Constrained augmented Lagrangian (NCL), an augmented Lagrangian method in which the subproblems are solved using an interior-point method. NCL has two key advantages for large-scale SC-OPF. First, NCL handles difficult problems such as infeasible ones or models with complementarity constraints. Second, the augmented Lagrangian term naturally regularizes the Newton linear systems within the interior-point method, enabling to solve the Newton systems with a pivoting-free factorization that can be efficiently parallelized on GPUs. We assess the performance of our implementation, called MadNCL, on large-scale corrective AC-SCOPFs, with complementarity constraints modeling the corrective actions. Numerical results show that MadNCL can solve AC-SCOPF with 500 buses and 256 contingencies fully on the GPU in less than 3 minutes, whereas Knitro takes more than 3 hours to find an equivalent solution.
academic

طريقة لاغرانج المعززة على وحدة معالجة الرسومات لتدفق الطاقة الأمثل المقيد بالأمان في التيار المتردد

المعلومات الأساسية

  • معرّف الورقة: 2510.13333
  • العنوان: An Augmented Lagrangian Method on GPU for Security-Constrained AC Optimal Power Flow
  • المؤلفون: François Pacaud, Armin Nurkanović, Anton Pozharskiy, Alexis Montoison, Sungho Shin
  • التصنيف: math.OC (التحسين والتحكم)
  • تاريخ النشر: 15 أكتوبر 2025
  • رابط الورقة: https://arxiv.org/abs/2510.13333

الملخص

تقدم هذه الورقة خوارزمية جديدة لحل مشاكل تدفق الطاقة الأمثل المقيد بالأمان في التيار المتردد (AC-SCOPF) على نطاق واسع. تعتمد الطريقة على طريقة لاغرانج المعززة للقيود غير الخطية (NCL)، باستخدام طريقة النقطة الداخلية لحل المسائل الفرعية. تتمتع طريقة NCL بميزتين رئيسيتين للمسائل الكبيرة SC-OPF: أولاً، يمكن لـ NCL التعامل مع المسائل الصعبة مثل المسائل غير الممكنة أو النماذج ذات القيود التكاملية؛ ثانياً، يوفر حد لاغرانج المعزز تنظيماً طبيعياً لنظام نيوتن الخطي في طريقة النقطة الداخلية، مما يسمح بحل نظام نيوتن باستخدام التحليل الخالي من المحور، والذي يمكن موازاته بكفاءة على وحدة معالجة الرسومات. تُظهر النتائج العددية أن MadNCL يمكنه حل AC-SCOPF بالكامل مع 500 عقدة و256 عطلاً على وحدة معالجة الرسومات في أقل من 3 دقائق، بينما يحتاج Knitro إلى أكثر من 3 ساعات للعثور على حل معادل.

الخلفية البحثية والدافع

وصف المشكلة

في شبكات النقل الكهربائي، يتم حساب الجدولة المثلى عادة بحل مشكلة تدفق الطاقة الأمثل المقيد بالأمان (SCOPF). تقلل هذه الجدولة معياراً معيناً (التكلفة أو خسائر الشبكة) مع الأخذ في الاعتبار القيود الفيزيائية (تدفق الطاقة وحدود تدفق الخطوط) وقدرات المولدات. بالإضافة إلى ذلك، يجب أن تظل الجدولة ممكنة في سلسلة من حالات الطوارئ المقابلة لأعطال الخطوط أو المولدات (معيار الأمان N-1).

أهمية المشكلة

عادة ما يتم صياغة SCOPF كمشكلة برمجة خطية كبيرة الحجم تسمى DC-SCOPF، حيث يزداد حجمها خطياً مع عدد الأعطال. لكن هذا يأتي على حساب خطية القيود الفيزيائية غير الخطية، مما يؤثر على دقة الحل. ومع ذلك، فإن حل AC-SCOPF باستخدام الصيغة غير الخطية الأصلية لا يزال تحدياً مفتوحاً.

قيود الطرق الموجودة

تواجه الصيغة غير الخطية مشكلتين:

  1. AC-SCOPF هي مشكلة برمجة غير خطية ضخمة الحجم، يتجاوز حجمها قدرات أحدث محللات التحسين غير الخطي مثل Ipopt أو Knitro
  2. القيود التكاملية في نموذج AC-SCOPF يصعب التعامل معها عددياً، وتتطلب خوارزميات متخصصة

الدافع البحثي

تدفع خصائص AC-SCOPF على نطاق واسع الخوارزمية إلى الحدود، لأن عدد القيود التكاملية يزداد خطياً مع عدد الأعطال. للتعامل مع هذا التحدي، يقترح المؤلفون استخدام طريقة لاغرانج المعززة بناءً على طريقة لاغرانج المعززة للقيود غير الخطية (NCL) لحل AC-SCOPF.

المساهمات الأساسية

  1. التطبيق الأول لطريقة لاغرانج المعززة: التطبيق الأول للخوارزميات القائمة على لاغرانج المعزز لحل SCOPF التصحيحي مع القيود التكاملية
  2. التسريع على وحدة معالجة الرسومات: تطوير MadNCL، وهو تطبيق NCL يدعم التسريع على وحدة معالجة الرسومات، باستخدام NVIDIA cuDSS لحل المعادلات الخطية
  3. معالجة القيود التكاملية: إظهار أن MadNCL يتعامل بشكل جيد مع القيود التكاملية في AC-SCOPF ويكتشف بفعالية المسائل غير الممكنة
  4. تحسن الأداء الكبير: تحقيق تسريع كبير مقارنة بالطرق التقليدية على الحالات الكبيرة، مع إصدار GPU أسرع من إصدار CPU بأكثر من 6 مرات

شرح الطريقة

تعريف المهمة

يتم تعريف مشكلة تدفق الطاقة الأمثل المقيد بالأمان في التيار المتردد (AC-SCOPF) على النحو التالي:

min⁡x,uf(x0,u0)\min_{x,u} f(x^0, u^0)

تخضع للقيود:

  • الحالة الأساسية: g0(x0,u0)=0g^0(x^0, u^0) = 0, h0(x0,u0)≤0h^0(x^0, u^0) \leq 0
  • لكل عطل k∈{1,⋯ ,K}k \in \{1, \cdots, K\}:
    • gk(u0,xk,uk)=0g^k(u^0, x^k, u^k) = 0
    • hk(xk,uk)≤0h^k(x^k, u^k) \leq 0
    • 0≤G(xk,uk)⊥H(xk,uk)≥00 \leq G(x^k, u^k) \perp H(x^k, u^k) \geq 0

حيث تنشأ القيود التكاملية من:

  1. التحكم التلقائي بتوليد الطاقة (AGC): تنظيم القدرة الفعالة للتردد
  2. تبديل PV/PQ: التحكم في الجهد وحدود القدرة التفاعلية

معمارية النموذج

إعادة بناء MPCC

إعادة بناء AC-SCOPF كبرمجة رياضية مع قيود تكاملية (MPCC):

c(w) = 0, \quad w_0 \geq 0 \\ 0 \leq w_1 \perp w_2 \geq 0 \end{cases}$$ #### خوارزمية NCL تعمل NCL على مستويين: - **التكرار الخارجي**: تحديث معامل العقوبة $\rho^{(n)}$ وتقديرات المضروبات $(λ^{(n)}, ν_0^{(n)})$ - **التكرار الداخلي**: حل المسألة الفرعية غير الخطية المقيدة: $$\min_{w,r,t} L_ρ(w, r, t, λ^{(n)}, ν_0^{(n)})$$ تخضع للقيود: $$c(w) - r = 0, \quad W_1W_2e \leq t, \quad (w_0, w_1, w_2) \geq 0$$ #### هيكل نظام نيوتن يتمتع نظام نيوتن للمسألة الفرعية بالهيكل التالي: $$\begin{bmatrix} A & B^⊤ \\ B & -C \end{bmatrix} \begin{bmatrix} Δw \\ Δy \end{bmatrix} = \begin{bmatrix} r_1 \\ r_2 \end{bmatrix}$$ حيث يوفر التنظيم من حد لاغرانج المعزز تنظيماً طبيعياً يسمح باستخدام التحليل الخالي من المحور. ### نقاط الابتكار التقني 1. **التنظيم الطبيعي**: يوفر حد لاغرانج المعزز تنظيماً طبيعياً لنظام نيوتن الخطي، مما يحافظ على عدم تفرد النظام حتى عندما لا تكون التكاملية الصارمة قائمة 2. **التحليل الخالي من المحور**: يسمح التنظيم باستخدام طرق خالية من المحور مثل تحليل Cholesky الرمزي، والتي يمكن موازاتها بكفاءة على وحدة معالجة الرسومات 3. **كشف عدم الإمكانية**: عندما تكون المشكلة غير ممكنة، تعود NCL تلقائياً إلى مشكلة الجدوى، بزيادة معامل العقوبة $ρ^{(n)}$ إلى اللانهاية ## إعداد التجربة ### مجموعات البيانات استخدام الحالات من مكتبة MATPOWER: - 118ieee, ACTIVSg200, 300ieee, ACTIVSg500 - 1354pegase, ACTIVSg2000, 2869pegase - عدد الأعطال يتراوح من 2 إلى 256 ### مؤشرات التقييم - **وقت الحل**: إجمالي وقت الحل ووقت كل تكرار - **عدد التكرارات**: عدد تكرارات طريقة النقطة الداخلية - **القيمة الموضوعية**: قيمة دالة الهدف للحل الأمثل - **الجدوى**: القدرة على كشف الأعطال غير الممكنة ### طرق المقارنة - **Knitro**: محلل التحسين المتقدم الذي يدعم MPCC، باستخدام طريقة العقوبة الدقيقة $\ell_1$ - **MadNCL-CPU**: إصدار CPU باستخدام HSL MA57 - **MadNCL-GPU**: إصدار GPU باستخدام NVIDIA cuDSS ### تفاصيل التنفيذ - **لغة البرمجة**: Julia 1.11 - **تفاوت التقارب**: 1e-6 - **الحد الأدنى لمعامل الحاجز**: $μ_{min} = 10^{-7}$ - **الأجهزة**: معالج AMD EPYC 7430، وحدة معالجة رسومات NVIDIA A30 (24GB ذاكرة) ## نتائج التجربة ### النتائج الرئيسية #### أداء فحص الأعطال في مهمة فحص الأعطال، يتفوق MadNCL بشكل كبير على Knitro: | الحالة | Knitro (ثانية) | MadNCL-CPU (ثانية) | |------|------------|----------------| | 118ieee | 0.5 | 0.01 | | ACTIVSg500 | 5.4 | 0.3 | | 2869pegase | 238.4 | 14.1 | يكون MadNCL أسرع بما لا يقل عن 10 مرات على الحالات التي تزيد عن 300 عقدة. #### حل AC-SCOPF على نطاق واسع لحالة ACTIVSg500، مع زيادة عدد الأعطال: | K | عدد المتغيرات | وقت Knitro (ثانية) | وقت MadNCL-GPU (ثانية) | نسبة التسريع | |---|--------|---------------|-------------------|--------| | 64 | 241,900 | 2159.59 | 27.96 | 77.2× | | 128 | 480,300 | 4852.33 | 46.40 | 104.6× | | 256 | 957,100 | 11136.08 | 170.75 | 65.2× | ### تجارب الاستئصال #### أداء GPU مقابل CPU تحسن أداء MadNCL-GPU مقارنة بـ MadNCL-CPU: - بالنسبة لـ K≥64، يكون إصدار GPU أسرع بحوالي 6 مرات من إصدار CPU - بالنسبة لـ K≥64، يكون إصدار GPU أسرع بأكثر من 20 مرة من Knitro #### تحليل وقت كل تكرار مع زيادة عدد الأعطال، يزداد وقت كل تكرار لـ MadNCL-GPU بأبطأ معدل، مما يُظهر قابلية توسع جيدة. ### نتائج التجربة 1. **قابلية التوسع**: يُظهر MadNCL قابلية توسع ممتازة، مع القدرة على التعامل مع مشاكل تقترب من مليون متغير 2. **الاستتباب**: يمكن لـ NCL اكتشاف والتعامل تلقائياً مع المشاكل غير الممكنة 3. **كفاءة التوازي**: يستفيد التطبيق على GPU بشكل كامل من مزايا الحوسبة المتوازية 4. **الاستقرار العددي**: يحسن التنظيم من لاغرانج المعزز الاستقرار العددي ## الأعمال ذات الصلة ### الاتجاهات البحثية الرئيسية 1. **طرق حل MPCC**: تشمل الطرق المباشرة وطرق التنظيم وطرق العقوبة 2. **تحسين الأنظمة الكهربائية**: استراتيجيات حل مختلفة لـ DC-SCOPF و AC-SCOPF 3. **تسريع التحسين على GPU**: نقل خوارزميات التحسين إلى منصة GPU ### مساهمة هذه الورقة مقارنة بالأعمال الموجودة، تطبق هذه الورقة لأول مرة طريقة لاغرانج المعززة على AC-SCOPF مع قيود تكاملية، وتحقق تسريعاً فعالاً على GPU. ## الخلاصة والمناقشة ### الاستنتاجات الرئيسية 1. يمكن لـ MadNCL حل مشاكل AC-SCOPF الكبيرة بفعالية، مع التعامل مع ما يقرب من مليون متغير 2. يحقق إصدار التسريع على GPU تحسناً في الأداء بعشرات المرات مقارنة بمحللات CPU التقليدية 3. توفر طريقة لاغرانج المعززة حلاً قوياً للتعامل مع القيود التكاملية ### القيود 1. **مشكلة رقم الشرط**: يتدهور رقم شرط النظام الخطي مع زيادة حجم المشكلة 2. **التقارب**: التقارب غير مستقر بما فيه الكفاية على بعض الحالات الكبيرة 3. **حدود الذاكرة**: تحد حدود ذاكرة GPU من الحد الأقصى لحجم المشكلة التي يمكن معالجتها ### الاتجاهات المستقبلية 1. حل مشكلة رقم الشرط السيء في نظام نيوتن لطريقة النقطة الداخلية 2. التوسع إلى حالات أكبر (آلاف العقد، مئات الأعطال) 3. تحسين تقنيات التكييف المسبق لتحسين الاستقرار العددي ## التقييم المتعمق ### المزايا 1. **ابتكار الطريقة**: التطبيق الأول لـ NCL على AC-SCOPF، مع مسار تقني جديد 2. **جودة التنفيذ**: تطبيق عالي الجودة على GPU، يستفيد بشكل كامل من مزايا الحوسبة المتوازية 3. **التقييم الشامل**: تقييم تجريبي شامل، يشمل اختبارات قابلية التوسع والاستتباب 4. **القيمة العملية**: يجعل التحسن الكبير في الأداء التطبيقات الفعلية الكبيرة الحجم ممكنة ### أوجه القصور 1. **التحليل النظري**: نقص تحليل نظرية التقارب لـ NCL على مشاكل SCOPF 2. **الاستقرار العددي**: لا تزال هناك مشاكل في الاستقرار العددي على أكبر الحالات 3. **العمومية**: ينطبق تطبيق الطريقة بشكل أساسي على مجال تحسين الأنظمة الكهربائية ### التأثير 1. **المساهمة الأكاديمية**: توفير أفكار حل جديدة للتحسين غير المحدب على نطاق واسع 2. **القيمة العملية**: ذات أهمية عملية كبيرة لتشغيل وتخطيط الأنظمة الكهربائية 3. **نشر التكنولوجيا**: حالة نجاح لخوارزميات التحسين المسرعة على GPU ### السيناريوهات المناسبة 1. **جدولة الأنظمة الكهربائية**: التحسين المقيد بالأمان للسوق الفعلية واليومية 2. **التحسين غير المحدب على نطاق واسع**: مشاكل هندسية أخرى مع قيود تكاملية 3. **الحوسبة عالية الأداء على GPU**: تطبيقات التحسين التي تتطلب حلاً سريعاً ## المراجع تستشهد الورقة بـ 31 مرجعاً ذا صلة، تغطي نمذجة SCOPF وطرق حل MPCC ونظرية لاغرانج المعززة وتحسين GPU وغيرها من الأعمال المهمة في جوانب متعددة، مما يوفر أساساً نظرياً قوياً للبحث.