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

GPU-তে নিরাপত্তা-সীমাবদ্ধ AC সর্বোত্তম শক্তি প্রবাহের জন্য একটি বর্ধিত ল্যাগ্রেঞ্জিয়ান পদ্ধতি

মৌলিক তথ্য

  • পত্র ID: 2510.13333
  • শিরোনাম: GPU-তে নিরাপত্তা-সীমাবদ্ধ AC সর্বোত্তম শক্তি প্রবাহের জন্য একটি বর্ধিত ল্যাগ্রেঞ্জিয়ান পদ্ধতি
  • লেখক: François Pacaud, Armin Nurkanović, Anton Pozharskiy, Alexis Montoison, Sungho Shin
  • শ্রেণীবিভাগ: math.OC (অপ্টিমাইজেশন এবং নিয়ন্ত্রণ)
  • প্রকাশনার সময়: ২০২৫ সালের ১৫ অক্টোবর
  • পত্র লিঙ্ক: https://arxiv.org/abs/2510.13333

সারসংক্ষেপ

এই পত্রটি বৃহৎ-স্কেল নিরাপত্তা-সীমাবদ্ধ AC সর্বোত্তম শক্তি প্রবাহ (AC-SCOPF) সমাধানের জন্য একটি নতুন অ্যালগরিদম প্রস্তাব করে। এই পদ্ধতিটি অরৈখিক সীমাবদ্ধতা বর্ধিত ল্যাগ্রেঞ্জিয়ান (NCL) পদ্ধতির উপর ভিত্তি করে তৈরি, যা অভ্যন্তরীণ বিন্দু পদ্ধতি ব্যবহার করে উপ-সমস্যা সমাধান করে। বৃহৎ-স্কেল SC-OPF-এর জন্য NCL-এর দুটি মূল সুবিধা রয়েছে: প্রথমত, NCL কঠিন সমস্যা যেমন অসম্ভব সমস্যা বা পরিপূরক সীমাবদ্ধতা সহ মডেল পরিচালনা করতে পারে; দ্বিতীয়ত, বর্ধিত ল্যাগ্রেঞ্জিয়ান পদটি অভ্যন্তরীণ বিন্দু পদ্ধতিতে নিউটন রৈখিক সিস্টেমকে স্বাভাবিকভাবে নিয়মিত করে, যা নিউটন সিস্টেমকে পিভট-মুক্ত বিয়োজন দিয়ে সমাধান করা সম্ভব করে, যা GPU-তে দক্ষতার সাথে সমান্তরালকৃত করা যায়। সংখ্যাগত ফলাফল দেখায় যে MadNCL ৫০০ নোড এবং ২৫৬টি ত্রুটি সহ AC-SCOPF সম্পূর্ণভাবে ৩ মিনিটের কম সময়ে GPU-তে সমাধান করতে পারে, যখন Knitro সমতুল্য সমাধান খুঁজে পেতে ৩ ঘন্টারও বেশি সময় প্রয়োজন।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার বর্ণনা

ট্রান্সমিশন নেটওয়ার্কে, সর্বোত্তম সময়সূচী সাধারণত নিরাপত্তা-সীমাবদ্ধ সর্বোত্তম শক্তি প্রবাহ (SCOPF) সমাধানের মাধ্যমে গণনা করা হয়। এই সময়সূচী ভৌত সীমাবদ্ধতা (শক্তি প্রবাহ, লাইন প্রবাহ সীমা) এবং জেনারেটর ক্ষমতা বিবেচনা করার সময় একটি প্রদত্ত মানদণ্ড (খরচ বা নেটওয়ার্ক ক্ষতি) হ্রাস করে। অতিরিক্তভাবে, সময়সূচীটি লাইন বা জেনারেটর ত্রুটির সাথে সম্পর্কিত একটি সিরিজ জরুরি পরিস্থিতিতে সম্ভাব্য থাকা উচিত (N-1 নিরাপত্তা মানদণ্ড)।

সমস্যার গুরুত্ব

SCOPF সাধারণত DC-SCOPF নামক বৃহৎ-স্কেল রৈখিক প্রোগ্রামিং সমস্যা হিসাবে প্রণয়ন করা হয়, যার স্কেল ত্রুটির সংখ্যার সাথে রৈখিকভাবে বৃদ্ধি পায়। তবে এটি অরৈখিক ভৌত সীমাবদ্ধতাগুলির রৈখিকীকরণের খরচে আসে, যা সমাধানের নির্ভুলতাকে প্রভাবিত করে। তবে, মূল অরৈখিক সূত্র দিয়ে AC-SCOPF সমাধান করা এখনও একটি খোলা চ্যালেঞ্জ।

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

অরৈখিক সূত্রে দুটি সমস্যা রয়েছে:

  1. AC-SCOPF একটি বিশাল স্কেলের অরৈখিক প্রোগ্রামিং সমস্যা, যার স্কেল Ipopt বা Knitro-এর মতো অত্যাধুনিক অরৈখিক অপ্টিমাইজেশন সমাধানকারীদের ক্ষমতার বাইরে
  2. AC-SCOPF মডেলে পরিপূরক সীমাবদ্ধতা সংখ্যাগতভাবে পরিচালনা করা কঠিন, বিশেষায়িত অ্যালগরিদম গ্রহণ করতে হবে

গবেষণা প্রেরণা

বৃহৎ-স্কেল AC-SCOPF-এর বৈশিষ্ট্যগুলি অ্যালগরিদমকে সীমানায় ঠেলে দেয়, কারণ পরিপূরক সীমাবদ্ধতার সংখ্যা ত্রুটির সংখ্যার সাথে রৈখিকভাবে বৃদ্ধি পায়। এই চ্যালেঞ্জ মোকাবেলা করতে, লেখকরা AC-SCOPF সমাধানের জন্য বর্ধিত ল্যাগ্রেঞ্জিয়ান পদ্ধতি ব্যবহার করার প্রস্তাব দেন যা অরৈখিক সীমাবদ্ধতা বর্ধিত ল্যাগ্রেঞ্জিয়ান (NCL) এর উপর ভিত্তি করে।

মূল অবদান

  1. বর্ধিত ল্যাগ্রেঞ্জিয়ান পদ্ধতির প্রথম প্রয়োগ: পরিপূরক সীমাবদ্ধতা সহ সংশোধনমূলক SCOPF সমাধানের জন্য প্রথমবারের মতো বর্ধিত ল্যাগ্রেঞ্জিয়ান-ভিত্তিক অ্যালগরিদম প্রয়োগ করা
  2. GPU ত্বরণ বাস্তবায়ন: MadNCL বিকাশ করা, একটি GPU-ত্বরিত NCL বাস্তবায়ন যা রৈখিক সমাধানের জন্য NVIDIA cuDSS ব্যবহার করে
  3. পরিপূরক সীমাবদ্ধতা পরিচালনা: MadNCL AC-SCOPF-এ পরিপূরক সীমাবদ্ধতা ভালভাবে পরিচালনা করতে এবং অসম্ভব সমস্যা কার্যকরভাবে সনাক্ত করতে পারে তা প্রদর্শন করা
  4. উল্লেখযোগ্য কর্মক্ষমতা উন্নতি: বৃহৎ-স্কেল উদাহরণে ঐতিহ্যবাহী পদ্ধতির তুলনায় উল্লেখযোগ্য ত্বরণ অর্জন করা, GPU সংস্করণ CPU সংস্করণের চেয়ে ৬ গুণেরও বেশি দ্রুত

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

নিরাপত্তা-সীমাবদ্ধ AC সর্বোত্তম শক্তি প্রবাহ (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 বিয়োজনের মতো পিভট-মুক্ত পদ্ধতি ব্যবহার করা সম্ভব করে, যা GPU-তে দক্ষতার সাথে সমান্তরালকৃত করা যায় 3. **অসম্ভবতা সনাক্তকরণ**: যখন সমস্যা অসম্ভব হয়, NCL স্বয়ংক্রিয়ভাবে সম্ভাব্যতা সমস্যায় ফিরে যায়, শাস্তি পরামিতি $ρ^{(n)}$ অসীমে বৃদ্ধি করে ## পরীক্ষামূলক সেটআপ ### ডেটাসেট MATPOWER লাইব্রেরি থেকে উদাহরণ ব্যবহার করা: - 118ieee, ACTIVSg200, 300ieee, ACTIVSg500 - 1354pegase, ACTIVSg2000, 2869pegase - ত্রুটির সংখ্যা ২ থেকে ২৫৬ পর্যন্ত ### মূল্যায়ন মেট্রিক্স - **সমাধান সময়**: মোট সমাধান সময় এবং প্রতি পুনরাবৃত্তি সময় - **পুনরাবৃত্তি সংখ্যা**: অভ্যন্তরীণ বিন্দু পদ্ধতি পুনরাবৃত্তি সংখ্যা - **উদ্দেশ্য মান**: সর্বোত্তম সমাধানের উদ্দেশ্য ফাংশন মান - **সম্ভাব্যতা**: অসম্ভব ত্রুটি সনাক্ত করার ক্ষমতা ### তুলনা পদ্ধতি - **Knitro**: MPCC সমর্থনকারী অত্যাধুনিক অপ্টিমাইজেশন সমাধানকারী, $\ell_1$ সঠিক শাস্তি পদ্ধতি ব্যবহার করে - **MadNCL-CPU**: HSL MA57 ব্যবহার করে CPU সংস্করণ - **MadNCL-GPU**: NVIDIA cuDSS ব্যবহার করে GPU সংস্করণ ### বাস্তবায়ন বিবরণ - **প্রোগ্রামিং ভাষা**: Julia 1.11 - **সংমিশ্রণ সহনশীলতা**: 1e-6 - **ন্যূনতম বাধা পরামিতি**: $μ_{min} = 10^{-7}$ - **হার্ডওয়্যার**: AMD EPYC 7430 প্রসেসর, NVIDIA A30 GPU (24GB মেমরি) ## পরীক্ষামূলক ফলাফল ### প্রধান ফলাফল #### ত্রুটি স্ক্রীনিং কর্মক্ষমতা ত্রুটি স্ক্রীনিং কাজে, MadNCL Knitro-কে উল্লেখযোগ্যভাবে ছাড়িয়ে যায়: | উদাহরণ | Knitro (s) | MadNCL-CPU (s) | |--------|------------|----------------| | 118ieee | 0.5 | 0.01 | | ACTIVSg500 | 5.4 | 0.3 | | 2869pegase | 238.4 | 14.1 | MadNCL ৩০০ নোডের বেশি উদাহরণে কমপক্ষে ১০ গুণ দ্রুত। #### বৃহৎ-স্কেল AC-SCOPF সমাধান ACTIVSg500 উদাহরণের জন্য, ত্রুটির সংখ্যা বৃদ্ধির সাথে: | K | ভেরিয়েবল সংখ্যা | Knitro সময় (s) | MadNCL-GPU সময় (s) | ত্বরণ অনুপাত | |---|---------|-----------------|-------------------|----------| | 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 সংস্করণ CPU সংস্করণের চেয়ে প্রায় ৬ গুণ দ্রুত - K≥64 এর জন্য, GPU সংস্করণ 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. **তাত্ত্বিক বিশ্লেষণ**: SCOPF সমস্যায় NCL-এর সংমিশ্রণ তাত্ত্বিক বিশ্লেষণের অভাব 2. **সংখ্যাগত স্থিতিশীলতা**: সর্বাধিক স্কেল উদাহরণে এখনও সংখ্যাগত স্থিতিশীলতা সমস্যা বিদ্যমান 3. **সাধারণত্ব**: পদ্ধতির প্রয়োজনীয়তা প্রধানত বৈদ্যুতিক সিস্টেম অপ্টিমাইজেশন ক্ষেত্রে সীমাবদ্ধ ### প্রভাব 1. **একাডেমিক অবদান**: বৃহৎ-স্কেল অ-উত্তল অপ্টিমাইজেশনের জন্য নতুন সমাধান চিন্তাভাবনা প্রদান করে 2. **ব্যবহারিক মূল্য**: বৈদ্যুতিক সিস্টেম অপারেশন এবং পরিকল্পনার জন্য গুরুত্বপূর্ণ ব্যবহারিক মূল্য 3. **প্রযুক্তি প্রচার**: GPU ত্বরিত অপ্টিমাইজেশন অ্যালগরিদমের সফল কেস স্টাডি ### প্রযোজ্য পরিস্থিতি 1. **বৈদ্যুতিক সিস্টেম সময়সূচী**: রিয়েল-টাইম এবং দিনের আগে বাজারের নিরাপত্তা-সীমাবদ্ধ অপ্টিমাইজেশন 2. **বৃহৎ-স্কেল অ-উত্তল অপ্টিমাইজেশন**: পরিপূরক সীমাবদ্ধতা সহ অন্যান্য প্রকৌশল অপ্টিমাইজেশন সমস্যা 3. **GPU উচ্চ-কর্মক্ষমতা গণনা**: দ্রুত সমাধানের প্রয়োজন এমন অপ্টিমাইজেশন প্রয়োগ ## সংদর্ভ পত্রটি ৩১টি সম্পর্কিত সংদর্ভ উদ্ধৃত করে, যা SCOPF মডেলিং, MPCC সমাধান পদ্ধতি, বর্ধিত ল্যাগ্রেঞ্জিয়ান তত্ত্ব এবং GPU অপ্টিমাইজেশন সহ একাধিক দিক কভার করে, গবেষণার জন্য একটি শক্তিশালী তাত্ত্বিক ভিত্তি প্রদান করে।