🔢 mathematics

Scalable Deep Unfolding of Conic Optimizers

यह शोध पत्र बड़े पैमाने के सेमीडेफिनेट प्रोग्राम्स (semidefinite programs) के लिए एक स्केलेबल डीप अनफोल्डिंग फ्रेमवर्क पेश करता है जो मैट्रिक्स-फ्री इम्प्लिसिट डिफरेंशिएशन (matrix-free implicit differentiation) और एक सुदृढ़ आइजनवैल्यू-अवेयर बैकवर्ड रूल के माध्यम से मेमोरी और संख्यात्मक स्थिरता की बाधाओं को दूर करता है, जिससे सीखे गए नीतियां (learned policies) अत्याधुनिक कोनिक सॉल्वर्स (conic solvers) की तुलना में 50 $\times$ तक की गति वृद्धि प्राप्त करने में सक्षम होती हैं।

मूल लेखक: Alex Oshin, Rahul Vodeb Ghosh, Evangelos A. Theodorou

प्रकाशित 2026-06-15

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Alex Oshin, Rahul Vodeb Ghosh, Evangelos A. Theodorou

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक विशाल, जटिल पहेली को हल करने की कोशिश कर रहे हैं। रोबोटिक्स और इंजीनियरिंग की दुनिया में, इन पहेलियों को ऑप्टिमाइज़ेशन प्रॉब्लम्स (optimization problems) कहा जाता है। इनका उपयोग यह पता लगाने के लिए किया जाता है कि एक रोबोट के चलने का सबसे अच्छा तरीका क्या है, एक कार को सुरक्षित रूप से कैसे मोड़ा जाए, या एक पावर ग्रिड को कैसे प्रबंधित किया जाए।

लंबे समय से, कंप्यूटर इन पहेलियों को हल करने के लिए "इटरेटिव ऑप्टिमाइज़र्स" (iterative optimizers) का उपयोग करते रहे हैं। इन ऑप्टिमाइज़र्स को एक बहुत ही व्यवस्थित, लेकिन धीमे हाइकर (हाइकर - पैदल यात्री) के रूप में समझें जो घाटी के निचले हिस्से को खोजने की कोशिश कर रहा है। वे एक कदम उठाते हैं, देखते हैं कि क्या वे नीचे आए हैं, दूसरा कदम उठाते हैं, और इस प्रक्रिया को हजारों बार दोहराते हैं जब तक कि वे तल तक नहीं पहुँच जाते।

डीप अनफोल्डिंग (Deep Unfolding) इस हाइकर को चलने के बजाय दौड़ना सिखाने का एक नया तरीका है। केवल नियमों के एक कठोर सेट का पालन करने के बजाय, हाइकर को एक "कोच" (एक न्यूरल नेटवर्क) दिया जाता है जो अनुभव से सीखता है। कोच हाइकर को बताता है कि उसे ठीक कितना बड़ा कदम उठाना चाहिए और कब दिशा बदलनी चाहिए, यह इस आधार पर कि पिछले पहेलियों में क्या सबसे अच्छा काम कर गया था। यह पेपर इस बारे में है कि इस कोच को सबसे बड़े, सबसे कठिन पभलियों को संभालने के लिए कैसे प्रशिक्षित किया जाए।

यहाँ पेपर की कहानी का विवरण दिया गया, जिसमें सरल उपमाओं (analogies) का उपयोग किया गया है:

समस्या: "मेमोरी वॉल" और "स्टिकी फ्लोर"

शोधकर्ताओं ने इस "कोच" प्रणाली को एक विशिष्ट प्रकार के सॉल्वर (solver) पर लागू करने की कोशिश की जिसे COSMO कहा जाता है, जो बड़े पैमाने की समस्याओं के लिए बेहतरीन है। हालाँकि, उन्हें दो बहुत बड़ी बाधाओं का सामना करना पड़ा जिन्होंने कोच को प्रभावी ढंग से सिखाने में बाधा डाली:

मेमोरी वॉल (द लीनियर सिस्टम):
एक कदम उठाने के लिए, सॉल्वर को संख्याओं के एक विशाल ग्रिड (एक मैट्रिक्स) वाली एक बड़ी गणितीय समीकरण को हल करना होता है। कोच को सिखाने के लिए, कंप्यूटर को यह याद रखने की आवश्यकता होती है कि उसने उस समीकरण को कैसे हल किया ताकि वह बाद में अपनी गलतियों से सीख सके।

पुराना तरीका: यह समुद्र तट पर रेत के हर एक कण को याद रखने की कोशिश करने जैसा था ताकि यह समझा जा सके कि उस पर कैसे चला जाए। जैसे-जैसे पहेली बड़ी होती गई, कंप्यूटर की मेमोरी (RAM) विस्फोट की तरह बढ़ी और क्रैश हो गई। यह एक $O(n^2)$ समस्या थी—पहेली का आकार दोगुना होने पर मेमोरी की आवश्यकता चार गुना बढ़ जाती थी।
पेपर का समाधान: उन्होंने एक "मैट्रिक्स-फ्री" (Matrix-Free) ट्रिक का आविष्कार किया। पूरे नंबरों के ग्रिड को लिखने के बजाय, उन्होंने महसूस किया कि उन्हें केवल यह जानने की आवश्यकता है कि ग्रिड एक एकल धक्के (एक मैट्रिक्स-वेक्टर प्रोडक्ट) के प्रति कैसा व्यवहार करता है। यह समुद्र तट पर चलने के लिए पूरे समुद्र तट का नक्शा याद करने के बजाय, अपने पैरों के नीचे रेत को महसूस करके चलने के बारे में सीखने जैसा है। इसने आवश्यक मेमोरी को एक विशाल गोदाम से घटाकर एक छोटे बैकपैक ( $O(n)$ ) तक कम कर दिया, जिससे ऐसी पहेलियाँ सुलझाना संभव हो गया जो पहले असंभव थीं।

स्टिकी फ्लोर (द आइजनवैल्यू प्रॉब्लम):
कुछ पहेलियों में एक विशेष आकार शामिल होता है जिसे "PSD कोन" कहा जाता है। इसे हल करने के लिए, कंप्यूटर को पहेली के "आइजनवैल्यूज" (eigenvalues - इन्हें पहेली की अनूठी आवृत्तियाँ या स्वर मान लें) को देखना होता है।

पुराना तरीका: जब इनमें से दो स्वर (eigenvalues) बिल्कुल एक जैसे होते हैं (repeated eigenvalues), तो कोच को सिखाने वाली गणित टूट जाती है। यह एक ऐसे फर्श के ढलान की गणना करने की कोशिश करने जैसा है जो पूरी तरह से सपाट है; गणित कहता है "डिवाइड बाय ज़ीरो" (divide by zero), और कंप्यूटर क्रैश हो जाता है या गलत उत्तर देता है। यह उनकी विशिष्ट रोबोटिक्स समस्याओं में हर समय होता था।
पेपर का समाधान: उन्होंने डेलेकी-क्रीन फॉर्मूला (Daleckii–Krein formula) नामक एक परिष्कृत गणितीय उपकरण का उपयोग किया। इसे गणित के लिए एक विशेष "स्मूदी ब्लेंडर" के रूप में समझें। सपाट जगहों पर फंसने के बजाय, यह फॉर्मूला जानता है कि उन स्थितियों को कैसे संभालना है जहाँ दो स्वर समान होते हैं, जिससे गणित स्थिर रहता है और सीखने की प्रक्रिया जारी रहती है।

परिणाम: द सुपर-रनर

इन दोनों बाधाओं को ठीक करने के बाद, उन्होंने COSMO सॉल्वर को निर्देशित करने के लिए अपने "कोच" को प्रशिक्षित किया।

स्पीडअप (गति में वृद्धि): सीखा हुआ सॉल्वर अविश्वसनीय रूप से तेज़ हो गया। कुछ परीक्षणों में, इसने मानक, बिना प्रशिक्षित सॉल्वर की तुलना में 50 गुना तेज़ी से समस्याओं को हल किया।
वास्तविक दुनिया का परीक्षण: उन्होंने इसे "कोवेरियेंस स्टीयरिंग" (Covariance Steering) की समस्या पर परखा। कल्पना कीजिए कि एक रोबोट अनिश्चितता के बादल (जैसे मधुमक्खियों का झुंड) को किसी चीज़ से टकराए बिना बिंदु A से बिंदु B तक ले जाने की कोशिश कर रहा है। जब इस नए सॉल्वर का उपयोग एक बड़े प्लानिंग सिस्टम के अंदर एक सहायक के रूप में किया गया, तो इसने पूरी प्रक्रिया को 30 गुना तेज़ बना दिया।
तुलना: यह "गोल्ड स्टैंडर्ड" सॉल्वर्स (जैसे Clarabel) के साथ भी प्रतिस्पर्धा करता है जिन्हें आमतौर पर सबसे अच्छा माना जाता है, लेकिन इसने वास्तविक समय में रोबोटों द्वारा सामना किए जाने वाले विशिष्ट प्रकार के कार्यों के लिए बहुत अधिक तेज़ी से काम किया।

सारांश

इस पेपर ने कोई नया रोबोट या नया प्रकार का गणितीय प्रश्न नहीं बनाया। इसके बजाय, इसने उन समस्याओं को हल करने वाले "इंजन" को ठीक किया है।

उन्होंने मेमोरी बॉटलनेक को हटा दिया ताकि इंजन बिना ईंधन खत्म हुए बड़ी पहेलियों को चला सके।
उन्होंने गणितीय अस्थिरता को ठीक किया ताकि रास्ता कठिन होने पर इंजन बंद न हो जाए।

परिणामस्वरूप, एक "लर्नड" (learned) ऑप्टिमाइज़र प्राप्त हुआ जो एक अनुभवी हाइकर की तरह कार्य करता है जिसे पता है कि इलाके में कैसे नेविगेट करना है, और जटिल रोबोटिक्स समस्याओं को पुराने समय की तुलना में बहुत कम समय में हल करता है।

तकनीकी सारांश: कोनिक ऑप्टिमाइज़र्स का स्केलेबल डीप अनफोल्डिंग (Scalable Deep Unfolding of Conic Optimizers)

समस्या विवरण (Problem Statement)

डीप अनफोल्डिंग (DU) ने विभिन्न डोमेन, जिनमें कम्प्रेस्ड सेंसिंग और रोबोटिक्स शामिल हैं, के लिए पुनरावृत्ति ऑप्टिमाइज़र्स (iterative optimizers) को गति देने में प्रभावशीलता सिद्ध की है। हालांकि, बड़े पैमाने के सेमिडेफिनेट प्रोग्राम्स (SDPs) तक DU का विस्तार करना—जो कोवेरियेंस स्टीयरिंग जैसे रोबोटिक्स अनुप्रयोगों में सामान्य हैं—दो विशिष्ट बाधाओं के कारण बाधित रहा है जब फुल-अपडेट ADMM-आधारित कोनिक सॉल्वर (जैसे COSMO) को अनरोल किया जाता है:

लीनियर-सिस्टम सॉल्व्स में मेमोरी बाधा (Memory Bottleneck in Linear-System Solves): प्रत्येक पुनरावृत्ति (iteration) में लीनियर-सिस्टम सॉल्व के माध्यम से बैकप्रोपैगेशन करने के लिए आमतौर पर कोएफिशिएंट मैट्रिक्स को स्पष्ट रूप से बनाने की आवश्यकता होती है। ADMM के लिए, इसमें $A^\top A$ शब्द शामिल है। भले ही बाधा मैट्रिक्स (constraint matrix) $A$ स्पार्स (sparse) हो, $A^\top A$ अक्सर डेंस (dense) होता है, जिससे $O(n^2)$ मेमोरी कॉम्प्लेक्सिटी उत्पन्न होती है। यह उन बड़े समस्या आकारों को रोकता है जहाँ डायरेक्ट फैक्टराइजेशन मेमोरी समाप्त कर देता है।
PSD प्रोजेक्शन में संख्यात्मक अस्थिरता (Numerical Instability in PSD Projections): पॉजिटिव सेमिडेफिनेट (PSD) कोन पर प्रोजेक्शन के लिए आइजनडिकम्पोजिशन (eigendecomposition) की आवश्यकता होती है। इस ऑपरेशन के माध्यम से मानक बैकप्रोपैगेशन में $1/(\lambda_i - \lambda_j)$ के रूप में टर्म्स शामिल होते हैं। जब आइजनवैल्यू (eigenvalues) समान होती हैं (विशेष रूप से आइसोट्रोपिक कोवेरियेंस टारगेट्स के साथ प्रशिक्षण के दौरान, यह एक सामान्य घटना है), तो ये टर्म्स संख्यात्मक अस्थिरता या अनडिफाइंड ग्रेडिएंट्स (NaNs) का कारण बनते हैं।

कार्यप्रणाली (Methodology)

लेखक COSMO सॉल्वर के लिए एक डीप अनफोल्डिंग फ्रेमवर्क का प्रस्ताव करते हैं जो इन दो बाधाओं को कस्टम बैकवर्ड रूल्स के माध्यम से संबोधित करता है, जिससे बड़े पैमाने की कोनिक समस्याओं के लिए हाइपरपैरामीटर पॉलिसी और वॉर्म-स्टार्ट्स (warm-starts) सीखना संभव हो जाता है।

1. लीनियर सॉल्व्स के लिए मैट्रिक्स-फ्री इम्प्लिसिट डिफरेंशिएशन (Matrix-Free Implicit Differentiation for Linear Solves)

$O(n^2)$ मेमोरी लागत से बचने के लिए, जो डेंस $A^\top A$ मैट्रिक्स बनाने की आवश्यकता होती है, लेखक कॉन्जुगेट ग्रेडिएंट (CG) आधारित लीनियर-सिस्टम सॉल्व के लिए एक मैट्रिक्स-फ्री इम्प्लिसिट डिफरेंशिएशन नियम का उपयोग करते हैं।

फॉरवर्ड पास (Forward Pass): सॉल्वर 'इनडायरेक्ट मोड' का उपयोग करता है, जो रिड्यूस्ड नॉर्मल इक्वेशंस $(P + \sigma I + A^\top D(\rho)A)\tilde{x} = \xi$ को CG का उपयोग करके हल करता है, जो केवल मैट्रिक्स-वेक्टर प्रोडक्ट्स (matvecs) पर निर्भर करता है।
बैकवर्ड पास (Backward Pass): CG पुनरावृत्तियों को अनरोल करने या डेंस जैकोबियन बनाने के बजाय, लेखक एडजॉइंट सिस्टम (adjoint system) पर आधारित एक नियम निकालते हैं। एडजॉइंट सिस्टम $M\tilde{\lambda} = -\nabla_{\tilde{x}}L$ को उसी CG विधि का उपयोग करके हल करके, हाइपरपैरामीटर्स $\rho$ के सापेक्ष ग्रेडिएंट $\nabla_\rho L = (A\tilde{\lambda}) \odot (A\tilde{x})$ के रूप में कंप्यूट किया जाता है।
परिणाम: यह दृष्टिकोण कभी भी डेंस कोएफिशिएंट मैट्रिक्स को स्पष्ट रूप से नहीं बनाता है, जिससे मेमोरी कॉम्प्लेक्सिटी $O(n^2)$ से घटकर $O(n + \text{nnz}(A))$ हो जाती है और उन पैमानों पर बैकप्रोपैगेशन सक्षम होता है जहाँ पिछले तरीके विफल हो जाते हैं।

2. PSD प्रोजेक्शन के लिए स्थिर बैकवर्ड नियम (Stable Backward Rule for PSD Projection)

दोहराए गए आइजनवैल्यूज के तहत आइजनडिकम्पोजिशन ग्रेडिएंट्स की अस्थिरता को हल करने के लिए, लेखक मानक ऑटोग्रैड (autograd) को Dalečii–Krein (DK) रिप्रेजेंटेशन के आधार पर एक बैकवर्ड नियम से बदलते हैं।

तंत्र (Mechanism): PSD प्रोजेक्शन को एक प्राइमरी मैट्रिक्स फंक्शन $T = U f(\Lambda) U^\top$ के रूप में माना जाता है जहाँ $f(x) = \max(x, 0)$ है। DK प्रमेय एक ऐसे फॉर्मूले के लिए एक सूत्र प्रदान करता है जहाँ सिंगुलर टर्म $1/(\lambda_j - \lambda_i)$ को न्यूमरेटर $f(\lambda_j) - f(\lambda_i)$ द्वारा गुणा किया जाता है।
स्थिरता (Stability): जब आइजनवैल्यूज समान होती हैं ( $\lambda_i = \lambda_j$ ), तो न्यूमरेटर उसी दर से शून्य हो जाता है जिस दर से डिनोमिनेटर, जिसके परिणामस्वरूप एक 'रिमूवेबल सिंगुलैरिटी' (removable singularity) प्राप्त होती है जिसे $f'(\lambda_i)$ के रूप में परिभाषित किया गया है। यह सुनिश्चित करता है कि ग्रेडिएंट भी सीमित और सुपरिभाषित रहे, भले ही आइजनवैल्यूज दोहराए गए हों।
दक्षता (Efficiency): यह नियम फॉरवर्ड पास में कंप्यूट किए गए आइजनडिकम्पोजिशन का पुन: उपयोग करता है, जिससे न्यूटन-शुलज़ (Newton-Schulz) इटरेशन को अनरोल करने जैसे विकल्पों के विपरीत, कोई अतिरिक्त एसिम्प्टोटिक कंप्यूटेशनल लागत नहीं आती है।

मुख्य योगदान (Key Contributions)

स्केलेबल लीनियर-सिस्टम डिफरेंशिएशन: एक मैट्रिक्स-फ्री इम्प्लिसिट डिफरेंशिएशन नियम जो मेमोरी उपयोग को $O(n^2)$ से घटाकर $O(n)$ कर देता है, जिससे बड़े पैमाने के SDPs पर फुल-अपडेट कोनिक सॉल्वर्स का डीप अनफोल्डिंग संभव होता है।
संख्यात्मक रूप से स्थिर PSD प्रोजेक्शन: Dalečii–Krein प्रमेय पर आधारित एक बैकवर्ड नियम जो दोहराए गए आइजनवैल्यूज के तहत भी सुपरिभाषित रहता है, जो कोवेरियेंस स्टीयरिंग और अन्य SDP समस्याओं पर प्रशिक्षण के लिए एक महत्वपूर्ण आवश्यकता है।
अनुभवजन्य सत्यापन (Empirical Validation): एक प्रदर्शन कि ये नियम स्टैंडर्ड COSMO सॉल्वर के विरुद्ध हल्के हाइपरपैरामीटर पॉलिसी और वॉर्म-स्टार्ट्स सीखने के लिए अनरोलिंग को सक्षम करते हैं। सीखा गया दृष्टिकोण स्टैंडअलोन SDPs/SOCPs और नॉनलीनियर कोवेरियेंस स्टीयरिंग के लिए सीक्वेंशियल कॉन्वेक्स प्रोग्रामिंग (SCP) में एक सबरूटीन के रूप में मूल्यांकन किया गया है।

परिणाम (Results)

लेखक विभिन्न समस्या वर्गों में स्टैंडर्ड COSMO सॉल्वर (अनुकूली ह्यूरिस्टिक्स के साथ) और स्टेट-ऑफ-द-आर्ट इंटीरियर-पॉइंट सॉल्वर Clarabel के विरुद्ध सीखे गए COSMO सॉल्वर का मूल्यांकन करते हैं:

स्टैंडअलोन SDPs और SOCPs: सीखा गया पॉलिसी समस्या वर्ग के आधार पर महत्वपूर्ण स्पीडअप प्राप्त करता है:
- Lovász $\vartheta$ SDPs: वॉल-क्लॉक टाइम में 50.4× तक की तेजी।
- Max-cut SDPs: 2.62× की तेजी।
- Robust Kalman Filters: 4.91× की तेजी।
- Lyapunov LMIs: 1.16× की तेजी।
नॉनलीनियर कोवेरियेंस स्टीयरिंग (SCP): जब इसे नॉनलीनियर सिस्टम (डबल इंटीग्रेटर और यूनिसाइकिल डायनेमिक्स) के लिए SCP में एक सबरूटीन के रूप में उपयोग किया जाता है, तो सीखा गया दृष्टिकोण वेनिला COSMO की तुलना में 30× की तेजी प्रदान करता है।
मेमोरी स्केलिंग: प्रयोग दिखाते हैं कि जबकि बेसलाइन तरीके $n \approx 20\text{--}50k$ वेरिएबल्स पर GPU मेमोरी (24 GB) समाप्त कर देते हैं, प्रस्तावित मैट्रिक्स-फ्री विधि रैखिक रूप से स्केल करती है, $n=50k$ पर भी 300 MB से कम रहती है।

महत्व और सीमाएं (Significance and Limitations)

यह पेपर दावा करता है कि ये योगदान बड़े पैमाने की कोनिक ऑप्टिमाइजेशन को लागू करना संभव बनाते हैं, जो पहले मेमोरी और संख्यात्मक स्थिरता बाधाओं द्वारा सीमित था। सीखी गई पॉलिसी वास्तविक समय के रोबोटिक्स अनुप्रयोगों के लिए पर्याप्त त्वरण प्रदान करती है जहाँ निश्चित कंप्यूटेशनल बजट की आवश्यकता होती है।

लेखक विशिष्ट सीमाओं को नोट करते हैं:

स्केलेबिलिटी: जबकि लीनियर सॉल्व मैट्रिक्स-फ्री है, PSD प्रोजेक्शन अभी भी प्रत्येक semidefinite ब्लॉक के लिए एक डेंस $O(p^3)$ आइजनडिकम्पोजिशन की आवश्यकता रखता है। स्केलेबिलिटी लाभ वेरिएबल्स/कंस्ट्रेंट्स की संख्या में मिलते हैं, न कि ब्लॉक साइज में।
सटीकता का क्षेत्र (Accuracy Regime): यह विधि कम-से-मध्यम सटीकता ( $\epsilon \approx 10^{-3}$ ) को लक्षित करती है, जो वास्तविक समय के नियंत्रण के लिए विशिष्ट है। यह टाइट टॉलरेंस (tight tolerances) पर फर्स्ट-ऑर्डर मेथड्स की तुलना में बेहतर प्रदर्शन करने का दावा नहीं करती है जहाँ इंटीरियर-पॉइंट सॉल्वर (जैसे Clarabel) धीमी गति से अभिसरण (converge) करते हैं।
प्रशिक्षण ओवरहेड (Training Overhead): प्रत्येक समस्या परिवार के लिए एक अलग पॉलिसी प्रशिक्षित की जाती है, जिसमें एक अग्रिम लागत (लगभग 100 समस्याएं प्रति क्लास) आती है जिसे कई समाधानों पर एमोर्टाइज (amortize) किया जाना चाहिए। वर्तमान कार्य परिवारों के बीच स्थानांतरण (transfer) या प्रशिक्षण के दौरान देखे गए से काफी बड़े इंस्टेंस तक स्केलिंग का प्रदर्शन नहीं करता है।