🔢 mathematics

A Trust-Region Interior-Point Stochastic Sequential Quadratic Programming Method

यह शोधपत्र एक ट्रस्ट-रीजन इंटीरियर-पॉइंट स्टोकेस्टिक सीक्वेंशियल क्वाड्रेटिक प्रोग्रामिंग (TR-IP-SSQP) विधि प्रस्तावित करता है जो स्टोकेस्टिक उद्देश्यों और नियत (deterministic) नॉनलीनर बाधाओं वाले अनुकूलन समस्याओं को हल करने के लिए एडेप्टिव स्टोकेस्टिक ओरेकल्स का उपयोग करता है, जो प्रथम-क्रम के स्थिर बिंदुओं (first-order stationary points) की ओर इसके वैश्विक लगभग-निश्चित अभिसरण (global almost-sure convergence) को सिद्ध करता है और बेंचमार्क एवं लॉजिस्टिक रिग्रेशन समस्याओं पर व्यावहारिक प्रदर्शन प्रदर्शित करता है।

मूल लेखक: Yuchen Fang, Jihun Kim, Sen Na, James Demmel, Javad Lavaei

प्रकाशित 2026-03-12

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

CC BY 4.0

मूल लेखक: Yuchen Fang, Jihun Kim, Sen Na, James Demmel, Javad Lavaei

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

कल्पना कीजिए कि आप एक विशाल, धुंधली घाटी (ऑब्जेक्टिव फंक्शन) में सबसे निचले बिंदु को खोजने की कोशिश कर रहे हैं। आप वहां जितनी जल्दी हो सके पहुंचना चाहते हैं, लेकिन इसमें दो बड़ी समस्याएं हैं:

धुंध: आप पूरे मानचित्र को नहीं देख सकते। आप केवल अपने आस-पास की जमीन का एक नमूना ले सकते हैं ताकि यह अनुमान लगाया जा सके कि ढलान किस ओर है। यह स्टोकेस्टिक (Stochastic) हिस्सा है (अनिश्चितता और शोर से निपटना)।
बाड़ (Fences): वहां अदृश्य बाड़ (समानता बाधाएं/Equality Constraints) हैं जिन पर आपको बिल्कुल बने रहना है, और दीवारें (असमानता बाधाएं/Inequality Constraints) हैं जिन्हें आप पार नहीं कर सकते।

यह शोध पत्र एक नया, स्मार्ट नेविगेशन सिस्टम पेश करता है जिसे TR-IP-SSQP कहा जाता है, जो आपको बाधाओं से टकराए बिना और घनी धुंध में भी घाटी के निचले हिस्से तक पहुँचने में मदद करता है।

यह कैसे काम करता है, इसे सरल अवधारणाओं और उपमाओं में यहाँ समझाया गया है:

1. "ट्रस्ट रीजन" (सुरक्षित कदम)

कल्पना कीजिए कि आप घाटी में आंखों पर पट्टी बांधकर खड़े हैं। यदि आप एक लंबी छलांग लगाते हैं, तो आप किसी खाई में गिर सकते हैं या दीवार से टकरा सकते हैं। इसके बजाय, आप निर्णय लेते हैं कि आप अपने आस-पास एक "सुरक्षित घेरे" के भीतर ही छोटे कदम लेंगे।

रूपक (Metaphor): यह ट्रस्ट रीजन (Trust Region) है। एल्गोरिदम पूछता है, "यदि मैं इस दिशा में एक कदम लेता हूँ, तो क्या इससे मेरी स्थिति में सुधार होगा?" यह कदम तभी लेता है जब उसे विश्वास हो कि सुधार वास्तविक और सुरक्षित है। यदि कदम जोखिम भरा दिखता है या सुधार कम है, तो यह घेरे को छोटा कर देता है और फिर से प्रयास करता है।

2. "इंटिरियर पॉइंट" (दीवारों से दूर रहना)

कई नेविगेशन प्रणालियों में, यदि आप किसी दीवार के बहुत करीब पहुँच जाते हैं, तो गणित जटिल हो जाता है और कंप्यूटर क्रैश हो जाता है। यह विधि एक चतुर ट्रिक का उपयोग करती है: यह दीवारों के साथ ऐसा व्यवहार करती है जैसे वे एक प्रतिकर्षण बल (repulsive force) हों।

रूपक: कल्पना करें कि दीवारें चुंबकों से बनी हैं जो आपको दूर धकेलती हैं। जैसे-जैसे आप दीवार के करीब आते हैं, धक्का मजबूत होता जाता है। यह आपको अनुमत क्षेत्र के बीच में सुरक्षित रखता है (जिसे "इंटिरियर" कहा जाता है)।
ट्विस्ट: समय के साथ, चुंबक कमजोर होते जाते हैं (बैरियर पैरामीटर घटता है)। यह आपको धीरे-धीरे दीवार के करीब जाने की अनुमति देता है ताकि आप सटीक रूप से सबसे अच्छे स्थान को खोज सकें, लेकिन वास्तव में उससे टकराते नहीं हैं।

3. "स्टोकेस्टिक ऑरेकल" (स्मार्ट अनुमान लगाने का खेल)

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

रूपक: यह शोध पत्र एक स्मार्ट ऑरेकल (Smart Oracle) का उपयोग करता है। हर बार एक सटीक अनुमान की मांग करने के बजाय, यह कहता है: "मुझे सटीक अनुमान की आवश्यकता नहीं है। मुझे बस एक ऐसे अनुमान की आवश्यकता है जो उच्च संभावना के साथ 'काफी अच्छा' हो।"
अनुकूली सटीकता (Adaptive Accuracy): यदि आप लक्ष्य से दूर हैं, तो एक मोटा अनुमान ठीक है। लेकिन जैसे-जैसे आप नीचे की ओर बढ़ते हैं, एल्गोरिदम स्वचालित रूप से अधिक सटीक अनुमान (अधिक डेटा नमूनों को देखकर) की मांग करता है। यह गति और सटीकता के बीच गतिशील रूप से संतुलन बनाता है।

4. "एसक्यूपी (SQP)" (स्थानीय मानचित्र)

किस दिशा में कदम बढ़ाना है, यह तय करने के लिए, एल्गोरिदम केवल तत्काल जमीन को नहीं देखता; बल्कि यह आपके खड़े होने के स्थान पर एक छोटा, स्थानीय 3D मॉडल बनाता है।

रूपक: यह आपके आस-पास के केवल 10 फीट के कागज के मानचित्र को खोलने जैसा है। यह मानचित्र एक सरल वक्र (एक द्विघाती आकार/quadratic shape) है जो जटिल, टेढ़े-मेढ़े इलाके का अनुमान लगाता है। यह सबसे अच्छा दिशा तय करने के लिए इस सरल मानचित्र पर समस्या को हल करता है, और फिर जांच करता है कि क्या वह दिशा वास्तविक दुनिया में काम करेगी।

यह शोध पत्र क्यों विशेष है?

इससे पहले, इस प्रकार की समस्याओं के लिए अधिकांश विधियों में कुछ खामियां थीं:

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

नई विधि की महाशक्तियाँ:

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

परिणाम

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

संक्षेप में: यह एक धुंधली, बाड़ वाली घाटी के लिए एक नेविगेशन सिस्टम है जो जानता है कि स्मार्ट, सुरक्षित कदम कैसे लिए जाएं, अपनी भविष्यवाणियों को समय के साथ कैसे बदला जाए, और पूर्णतः सर्वश्रेष्ठ स्थान खोजने के लिए दीवारों के साथ धीरे से कैसे फिसला जाए।

यहाँ फंग एट अल. के शोध पत्र "A Trust-Region Interior-Point Stochastic Sequential Quadratic Programming Method" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या का निरूपण (Problem Formulation)

यह शोध पत्र निम्नलिखित रूप के प्रतिबंधित स्टोकेस्टिक अनुकूलन (constrained stochastic optimization) समस्याओं को संबोधित करता है:
$\min_{x \in \mathbb{R}^d} f(x) = \mathbb{E}_{\xi}[F(x; \xi)]$
$\text{s.t. } c(x) = 0, \quad h(x) \leq 0$
जहाँ:

$f(x)$ एक निरंतरतः अवकलनीय (continuously differentiable) उद्देश्य फलन है जो एक स्टोकेस्टिक यथार्थ के प्रत्याशा (expectation) के रूप में परिभाषित है।
$c(x)$ और $h(x)$ क्रमशः नियतात्मक गैररेखीय समानता (deterministic nonlinear equality) और असमानता (inequality) बाधाओं का प्रतिनिधित्व करते हैं।
मुख्य चुनौती: $f(x)$ और $\nabla f(x)$ का सटीक मूल्यांकन उपलब्ध नहीं है। इसके बजाय, उन्हें नमूनाकरण (sampling) के माध्यम से अनुमानित किया जाना चाहिए। मौजूदा विधियाँ अक्सर गैररेखीय असमानता बाधाओं के साथ संघर्ष करती हैं, उनके लिए सीमित विचरण (bounded variance) वाले निष्पक्ष ग्रेडिएंट अनुमानकों की आवश्यकता होती है, या वे जटिल मल्टी-लूप संरचनाओं पर निर्भर करती हैं।

2. कार्यप्रणाली: TR-IP-SSQP

लेखक एक ट्रस्ट-रीजन इंटीरियर-पॉइंट स्टोकेस्टिक सीक्वेंशियल क्वाड्रेटिक प्रोग्रामिंग (TR-IP-SSQP) विधि प्रस्तावित करते हैं। यह एल्गोरिदम तीन मुख्य घटकों को एकीकृत करता है:

A. इंटीरियर-पॉइंट फ्रेमवर्क (IPM)

बैरियर पुनर्गठन (Barrier Reformulation): असमानता बाधाओं $h(x) \leq 0$ को एक पैरामीटर $\theta_k$ के साथ स्लैक वेरिएबल्स $s$ और एक लॉगरिदमिक बैरियर टर्म पेश करके संभाला जाता है। समस्या $f(x) - \theta_k \sum \ln(s^{(i)})$ को न्यूनतम करने में बदल जाती है, जहाँ $h(x) + s = 0$ और $s > 0$ है।
सिंगल-लूप संरचना (Single-Loop Structure): नियतात्मक IPMs के विपरीत, जो नेस्टेड लूप्स ( $\theta$ के लिए बाहरी लूप, सब-प्रॉब्लम हल करने के लिए आंतरिक लूप) का उपयोग करते हैं, यह विधि एक सिंगल-लूप फ्रेमवर्क का उपयोग करती है। बैरियर पैरामीटर $\theta_k$ एक पूर्व निर्धारित घटते क्रम ( $\theta_k \downarrow 0$ ) का अनुसरण करता है, जिससे जटिल इनर-लूप समाप्ति मानदंडों की आवश्यकता समाप्त हो जाती है जो स्टोकेस्टिक परिवेश में अविश्वसनीय होते हैं।
शिथिल व्यवहार्यता (Relaxed Feasibility): यह विधि प्रत्येक इटरेशन में सख्त व्यवहार्यता (strict feasibility) को लागू नहीं करती है। यह इटरेट्स को बाधाओं के संबंध में असंगत (infeasible) होने की अनुमति देती है, जिससे एक व्यवहार्य प्रारंभिक बिंदु खोजने के लिए सहायक प्रक्रियाओं की आवश्यकता समाप्त हो जाती है।

B. ट्रस्ट-रीजन SQP सबप्रॉब्लम

प्रत्येक इटरेशन $k$ पर, चरण $(\Delta x_k, \Delta s_k)$ निर्धारित करने के लिए एक क्वाड्रेटिक सबप्रॉब्लम हल किया जाता है:

उद्देश्य: ग्रेडिएंट ( $\bar{g}_k$ ) और हेसियन ( $\bar{H}_k$ ) के स्टोकेस्टिक अनुमानों का उपयोग करके लैग्रेंजियन के एक क्वाड्रेटिक सन्निकटन (approximation) को न्यूनतम करना।
बाधाएं:
- रैखिक समानता बाधाएं: $c_k + G_k \Delta x_k = 0$ ।
- स्लैक्स के साथ रैखिक असमानता बाधाएं: $h_k + s_k + J_k \Delta x_k + \Delta s_k = 0$ ।
- ट्रस्ट-रीजन: $\|(\Delta x_k; S_k^{-1} \Delta s_k)\| \leq \Delta_k$ ।
- फ्रैक्शन-टू-बाउंड्री (Fraction-to-Boundary): $s_k + \Delta s_k \geq (1-\epsilon_s)s_k$ ताकि यह सुनिश्चित हो सके कि स्लैक वेरिएबल्स धनात्मक बने रहें, जिसके लिए किसी उपयोगकर्ता-निर्दिष्ट लोअर बाउंड अनुक्रम की आवश्यकता नहीं है।
स्टेप डिकंपोजिशन: ट्रायल स्टेप को एक नॉर्मल स्टेप (बाधाओं को संतुष्ट करने के लिए) और एक टैन्जेंशियल स्टेप (उद्देश्य को कम करने के लिए) में विभाजित किया जाता है, जिसे ट्रस्ट रीजन के भीतर गणना किया जाता है।

C. एडेप्टिव सैंपलिंग और प्रोबेबिलिस्टिक ओरेकल

विधि निश्चित नमूना आकार के बजाय एडेप्टिव सैंपलिंग का उपयोग करती है।

प्रोबेबिलिस्टिक ओरेकल: प्रत्येक इटरेशन में, स्टोकेस्टिक ओरेकल उद्देश्य मान और ग्रेडिएंट के लिए अनुमान उत्पन्न करते हैं। इन अनुमानों के लिए एक निश्चित उच्च संभावना (जैसे, त्रुटि $\leq \kappa \Delta_k$ ) के साथ एडेप्टिव एक्यूरेसी कंडीशंस को पूरा करना आवश्यक है।
शिथिल धारणाएं (Relaxed Assumptions):
- बायस्ड अनुमान (Biased Estimates): यह विधि बायस्ड ऑब्जेक्टिव अनुमानों की अनुमति देती है।
- अनबाउंडेड वेरिएंस (Unbounded Variance): इसके लिए ग्रेडिएंट अनुमानकों के पास सीमित विचरण होना आवश्यक नहीं है, जो हेवी-टेल्ड नॉइज़ डिस्ट्रीबशंस को भी समाहित करता है।
मेरिट फंक्शन: एक $\ell_2$ मेरिट फंक्शन उद्देश्य में कमी और बाधा उल्लंघन के बीच संतुलन बनाता है। एल्गोरिदम वास्तविक और अनुमानित कमी के अनुपात और अनुमानों की विश्वसनीयता के आधार पर इटरेशन को "सफल", "विश्वसनीय" या "अविश्वसनीय" के रूप में वर्गीकृत करता है, जिससे ट्रस्ट-रीजन रेडियस और सैंपल साइज को गतिशील रूप से समायोजित किया जाता है।

3. मुख्य योगदान

गैररेखीय असमानताओं तक विस्तार: लेखकों ने ट्रस्ट-रीजन SSQP (जो पहले केवल समानता बाधाओं तक सीमित था) को गैररेखीय असमानता बाधाओं को संभालने के लिए विस्तारित किया है। इसके लिए स्लैक वेरिएबल अपडेट को स्पष्ट रूप से शामिल करने के लिए एक नया स्टेप कंप्यूटेशन संशोधन आवश्यक था, जिससे फ्रैक्शन-टू-बाउंड्री कंडीशन के माध्यम से धनात्मकता बनी रहे।
एडेप्टिव सैंपलिंग रणनीति: पूर्ववर्ती स्टोकेस्टिक IPMs के विपरीत, जिन्हें बाउंडेड वेरिएन्स वाले अनबायस्ड ग्रेडिएंट्स की आवश्यकता होती है, यह विधि एडेप्टिव सैंपलिंग का उपयोग करती है। यह बायस्ड अनुमानों और अनबाउंडेड वेरिएंस की अनुमति देता है, जिससे लागू होने वाले सैंपलिंग तंत्रों का दायरा काफी बढ़ जाता है।
शिथिल व्यवहार्यता और सिंगल-लूप: यह विधि एक रिलैक्स्ड-फिजिबिलिटी फ्रेमवर्क के भीतर काम करती है, जो व्यवहार्य प्रारंभिक बिंदु की आवश्यकता को हटा देती है और नेस्टेड लूप्स की जटिलता से बचाती है। यह कई परस्पर निर्भर पैरामीटर अनुक्रमों और बैरियर पैरामीटर क्षय दर (decay rate) पर सख्त नियंत्रण की आवश्यकता को भी समाप्त करती है।
अभिसरण गारंटी (Convergence Guaranteances): मानक धारणाओं (लिप्शिट्ज़ निरंतरता, परिबद्धता) के तहत, लेखक ग्लोबल ऑलमोस्ट-श्योर कन्वर्जेंस सिद्ध करते हैं। विशेष रूप से, इटरेट्स का एक सब-सीक्वेंस मूल समस्या के प्रथम-क्रम स्थिर बिंदुओं (KKT पॉइंट्स) की ओर लगभग निश्चित रूप से अभिसरित होता है।

4. संख्यात्मक परिणाम

विधि का परीक्षण किया गया:

CUTEst टेस्ट सेट: विभिन्न शोर स्तरों ( $\sigma^2 \in \{10^{-8}, 10^{-4}, 10^{-2}, 10^{-1}\}$ ) के साथ 22 असमानता-बाधित समस्याएं।
लॉजिस्टिक्स रिग्रेशन: UCI डेटासेट्स (German Credit, Mushroom) और सिंथेटिक डेटा का उपयोग करके प्रतिबंधित लॉजिस्टिक रिग्रेशन समस्याएं।

प्रमुख निष्कर्ष:

शोर के प्रति मजबूती (Robustness to Noise): एडेप्टिव सैंपलिंग के साथ TR-IP-SSQP, फिक्स्ड-सैंपलिंग समकक्षों (Fully-TR-IP-SSQP) की तुलना में काफी बेहतर प्रदर्शन करता है, विशेष रूपकर जब शोर का स्तर बढ़ता है।
हेसियन सन्निकटन (Hessian Approximations):
- आइडेंटिटी (Id) और एवरेज हेसियन (AveH): इन्होंने अच्छा प्रदर्शन किया, हालांकि AveH ने उच्च शोर या विशिष्ट बैरियर शेड्यूल्स के तहत घटते रिटर्न दिखाए।
- SR1 अपडेट: इसने उच्च संवेदनशीलता प्रदर्शित की, जिससे खराब प्रदर्शन और अस्थिरता हुई।
- एस्टीमेटेड हेसियन (EstH): मध्यम शोर सेटिंग्स में श्रेष्ठ दक्षता दिखाई।
बैरियर पैरामीटर: बैरियर पैरामीटर $\theta_k$ के लिए एक धीमा क्षय शेड्यूल (जैसे, $0.999 \dots^k$ ) शोर के विरुद्ध मजबूती बनाए रखने के लिए महत्वपूर्ण साबित हुआ। तेज़ क्षय से बैरियर प्रभाव समय से पहले समाप्त हो गया और समाधान की गुणवत्ता गिर गई।
तुलना: TR-IP-SSQP ने फिक्स्ड-सैंपलिंग विधियों की तुलना में लगातार कम एपोच (epochs) में अभिसरण प्राप्त किया, विशेष रूप से जब कर्वेचर सूचना (EstH/AveH) का उपयोग किया गया।

5. महत्व

यह कार्य स्टोकेस्टिक कंस्ट्रेंड ऑप्टिमाइज़ेशन में एक महत्वपूर्ण प्रगति का प्रतिनिधित्व करता है। ट्रस्ट-रीजन विधियों, इंटीरियर-पॉइंट तकनीकों और एडेप्टिव सैंपलिंग को जोड़कर, यह मौजूदा दृष्टिकोणों की प्रमुख सीमाओं को दूर करता है:

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

प्रस्तावित TR-IP-SSQP विधि जटिल बाधाओं वाली बड़े पैमाने की स्टोकेस्टिक अनुकूलन समस्याओं (जैसे सेफ रिइन्फोर्समेंट लर्निंग और कंस्ट्रेंड मशीन लर्निंग में पाई जाने वाली) को हल करने के लिए एक मजबूत, सैद्धांतिक रूप से सुदृढ़ और व्यावहारिक रूप से कुशल ढांचा प्रदान करती है।