Global Convergence of a Line-Search Filter Differential Dynamic Programming Method

तकनीकी सारांश: एक लाइन-सर्च फ़िल्टर डिफरेंशियल डायनेमिक प्रोग्रामिंग विधि का वैश्विक अभिसरण (Global Convergence)

समस्या विवरण
यह शोध पत्र गैररेखीय समानता बाधाओं (nonlinear equality constraints) के साथ अवस्थाओं (states) और नियंत्रणों (controls) तथा सिस्टम डायनेमिक्स के लिए डिस्क्रीट-टाइम, परिमित-क्षितिज (finite-horizon) अनुकूलतम नियंत्रण समस्याओं (OCPs) को हल करने की चुनौती को संबोधित करता है। जबकि डिफरेंशियल डायनेमिक प्रोग्रामिंग (DDP) एल्गोरिदम, जिसे मूल रूप से मेन और जैकबसन द्वारा अनियंत्रित OCPs के लिए प्रस्तावित किया गया था, ज्ञात स्थानीय द्विघातीय अभिसरण (local quadratic convergence) के साथ एक स्थापित विधि है, इसके मौजूदा विस्तारों में बाधाओं वाले OCPs के अनुप्रयोग में औपचारिक वैश्विक अभिसरण गारंटी का अभाव है। पिछले बाधित DDP वेरिएंट, जैसे कि अनुक्रमिक द्विघाती प्रोग्रामिंग (sequential quadratic programming) या प्रिमल-डुअल (primal-dual) फॉर्मुलेशन पर आधारित, अक्सर स्थानीय अभिसरण परिणाम प्रदान करते हैं लेकिन वैश्विक विश्लेषण को छोड़ देते हैं। विशिष्ट अंतराल जिसे यह कार्य लक्षित करता है, वह FilterDDP एल्गोरिदम के लिए कठोर वैश्विक अभिसरण प्रमाण का अभाव है, जो कि जू (Xu) आदि द्वारा प्रस्तावित एक लाइन-सर्च फ़िल्टर विधि है जो Wächter और Biegler के सामान्य गैररेखीय प्रोग्रामिंग (NLP) फ़िल्टर दृष्टिकोण को DDP ढांचे में अनुकूलित करती है।

कार्यप्रणाली (Methodology)
लेखक FilterDDP एल्गोरिदम के औपचारिक विश्लेषण का प्रस्ताव करते हैं, जो एक लाइन-सर्च फ़िल्टर प्रक्रिया के साथ एकीकृत एक DDP-विशिष्ट ट्रायल पॉइंट जनरेशन प्रक्रिया का उपयोग करता है। इस प्रक्रिया में दो चरण शामिल हैं:

1. बैकवर्ड रिकर्सन (Backward Recursion): वैल्यू फंक्शन एप्रोक्सिमेशन और लैग्रेंज मल्टीप्लायर्स का एक पुनरावर्ती अपडेट। यह चरण कंट्रोल्स, मल्टीप्लायर्स और स्टेट्स के लिए अपडेट दिशाओं ($\zeta, \beta, \psi, \omega$) को निर्धारित करने के लिए विक्षेपित हेसियन (perturbed Hessians) की गणना करता है और एक रैखिक प्रणाली को हल करता है।
2. फॉरवर्ड सिमुलेशन (Forward Simulation): एक सिमुलेशन चरण जो कंप्यूट किए गए अपडेट और एक स्टेप साइज $\alpha$ के आधार पर एक नया प्रक्षेपवक्र (trajectory) उत्पन्न करता है। महत्वपूर्ण रूप से, यह चरण सुनिश्चित करता है कि प्रत्येक पुनरावृत्ति (iteration) में डायनेमिक बाधाएं ($x_{t+1} = f(x_t, u_t)$) संतुष्ट हों, जो कि DDP की एक अंतर्निहित विशेषता है।

एल्गोरिदम एक ट्रायल पॉइंट को स्वीकार करने के लिए एक फ़िल्टर तंत्र का उपयोग करता है, जो लैग्रेंजियन के न्यूनीकरण (एक उद्देश्य माप के रूप में) और बाधा उल्लंघन माप (constraint violation measure) के बीच संतुलन बनाता है। स्टेप स्वीकृति मानदंड में लैग्रेंजियन या बाधा उल्लंघन के लिए पर्याप्त न्यूनीकरण की शर्तें, "L-type" पुनरावृत्तियों के लिए एक आर्मिजो-टाइप (Armijo-type) स्थिति, और एक व्यवहार्यता बहाली (feasibility restoration) चरण शामिल है जिसे तब सक्रिय किया जाता है जब स्टेप साइज बहुत छोटा हो जाता है या बाधा जैकोबियन (constraint Jacobians) रैंक-डेफिशिएंट हो जाते हैं।

प्रमुख योगदान
इस कार्य का प्राथमिक योगदान FilterDDP एल्गोरिदम की वैश्विक अभिसरण (global convergence) की स्थापना है। लेखक इसे यह प्रदर्शित करके प्राप्त करते हैं कि DDP की विशिष्ट बैकवर्ड-फॉरवर्ड प्रक्रिया उन्हीं विश्लेषणात्मक गुणों को संतुष्ट करती है जो सामान्य NLP में लाइन-सर्च फ़िल्टर विधियों के वैश्विक अभिसरण के लिए आवश्यक हैं, जैसा कि Wächter और Biegler द्वारा स्थापित किया गया है।

इस योगदान में मुख्य तकनीकी चरण शामिल हैं:

• चरणों की तुल्यता (Equivalence of Steps): यह सिद्ध करना कि DDP बैकवर्ड रिकर्सन और फॉरवर्ड सिमुलेशन, जब वैश्विक अभिसरण विश्लेषण के लेंस से देखे जाते हैं, तो वे OCP के KKT (Karush-Kuhn-Tucker) स्थितियों पर लागू डैम्प्ड न्यूटन स्टेप के समान व्यवहार करते हैं।
• लेम्मा व्युत्पत्ति (Lemma Derivation): एक श्रृंखला में लेम्मा स्थापित करना (जो Wächter और Biegler के कार्य के लेम्मा 1-3 के समकक्ष है) जो अपडेट नियमों को बांधते हैं, गैर-इष्टतम व्यवहार्य बिंदुओं के लिए अवसादन (descent) गुणों को स्थापित करते हैं, और यह दिखाते हैं कि अपडेट नियम स्थानीय रूप से फ़िल्टर मानदंडों (लैग्रेंजियन और बाधा उल्लंघन) को रैखिकीकृत (linearize) करते हैं।
• इंटिरियर पॉइंट एक्सटेंशन (Interior Point Extension): एक बैरियर इंटीरियर पॉइंट विधि के माध्यम से असमानता बाधाओं (विशेष रूप से $u_t \geq 0$) को संभालने के लिए वैश्विक अभिसरण विश्लेषण का विस्तार करना। इसमें हेसियन एप्रोक्सिमेशन को अनुकूलित करना और यह सिद्ध करना शामिल है कि इटरेट्स (iterates) व्यवहार्य क्षेत्र की सीमाओं से दूर रहते हैं, जिससे यह सुनिश्चित होता है कि बैरियर ऑब्जेक्टिव और उसके डेरिवेटिव परिभाषित रहें।

परिणाम
समानता बाधाओं के लिए मानक नियमितता और सुगमता धारणाओं (Assumptions G के रूप में नामित) और बैरियर एक्सटेंशन के लिए Assumptions B के तहत, यह पत्र निम्नलिखित अभिसरण गुणों को सिद्ध करता है:

1. व्यवहार्यता (Feasibility): FilterDDP द्वारा उत्पन्न इटरेट्स के अनुक्रम के सीमा बिंदु (limit points) व्यवहार्य हैं; विशेष रूप से, $k \to \infty$ होने पर बाधा उल्लंघन माप $\theta(w_k)$ शून्य की ओर अभिसरित होता है।
2. इष्टतमता (Optimality): यदि इटरेट्स का अनुक्रम बाध्य (bounded) है, तो कम से कम एक सीमा बिंदु होता है जो बाधित OCP के लिए प्रथम-क्रम इष्टतमता स्थितियों (KKT स्थितियाँ) को संतुष्ट करता है। इसे यह दिखाकर प्रदर्शित किया गया है कि क्रिटिकलिटी मेजर $\chi(w_k)$, जो प्रोजेक्टेड ग्रेडिएंट घटकों के नॉर्म द्वारा परिभाषित है, का लिमिट इन्फीरियर शून्य है।
3. बैरियर अभिसरण (Barrier Convergence): इंटीरियर पॉइंट एक्सटेंशन के लिए, यह सिद्ध किया गया है कि इटरेट्स असमानता बाधाओं की सीमाओं से समान रूप से दूर रहते हैं, जो संपूर्ण अनुकूलन प्रक्रिया के दौरान बैरियर फॉर्मुलेशन की वैधता सुनिश्चित करता है।

महत्व और दावे
यह पत्र FilterDDP की व्यावहारिक सफलता और कठोर सैद्धांतिक गारंटियों के बीच के अंतर को औपचारिक रूप से पाटकर अपनी महत्ता का दावा करता है। लेखक कहते हैं कि जबकि FilterDDP के स्थानीय द्विघातीय अभिसरण को पहले स्थापित किया गया था (स्टेप स्वीकृति मानदंडों को अनदेखा करते हुए), वैश्विक अभिसरण विश्लेषण गायब था। Wächter और Biegler के विश्लेषण को अनुकूलित करके, यह पत्र प्रदर्शित करता है कि DDP संरचना फ़िल्टर विधि के वैश्विक अभिसरण गुणों में बाधा नहीं डालती है; बल्कि, बैकवर्ड-फॉरवर्ड रिकर्सन सामान्य NLP संदर्भ में न्यूटन स्टेप के समान भूमिका निभाता है।

लेखक विनम्रतापूर्वक नोट करते हैं कि यह विश्लेषण इस धारणा पर निर्भर करता है कि व्यवहार्यता बहाली चरण सफलतापूर्वक समाप्त होता है और एल्गोरिदम गैर-KKT बिंदु पर समय से पहले नहीं रुकता है। इसके अलावा, पेपर यह पहचान करता है कि FilterDDP के लिए तेज़ स्थानीय अभिसरण स्थापित करना (स्टेप स्वीकृति मानदंडों को अनदेखा किए बिना) एक खुला प्रश्न बना हुआ है, जो यह सुझाव देता है कि भविष्य के कार्य के लिए एक सेकंड-ऑर्डर करेक्शन स्टेप, जैसा कि सामान्य NLP में उपयोग किया जाता है, आवश्यक हो सकता है। यह पत्र कोई नए अनुप्रयोग या प्रायोगिक बेंचमार्क प्रस्तावित नहीं करता है, बल्कि पूरी तरह से एल्गोरिदम के सैद्धांतिक अभिसरण गुणों पर ध्यान केंद्रित करता है।