🔢 mathematics

Immunity to Increasing Condition Numbers of Linear Superiorization versus Linear Programming

यह शोध पत्र प्रयोगात्मक रूप से रैखिक बाधा प्रणालियों में बढ़ते कंडीशन नंबरों के प्रति शास्त्रीय लीनियर प्रोग्रामिंग (LP) और लीनियर सुपिरियराइजेशन (LinSup) एल्गोरिदम की संवेदनशीलता की जांच और तुलना करता है, जो विशेष रूप से इल-पोज़्ड (ill-posed) समस्याओं और त्रुटि प्रसार को संभालने की उनकी संबंधित क्षमताओं का मूल्यांकन करता है।

मूल लेखक: Jan Schröder, Yair Censor, Philipp Süss, Karl-Heinz Küfer

प्रकाशित 2026-07-10

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

CC BY 4.0

मूल लेखक: Jan Schröder, Yair Censor, Philipp Süss, Karl-Heinz Küfer

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

कल्पना कीजिए कि आप एक विशाल, भीड़भाड़ वाले भूलभुलैया (maze) में नींबू पानी का स्टॉल लगाने के लिए सबसे सटीक जगह खोजने की कोशिश कर रहे हैं। आपके दो लक्ष्य हैं: पहला, आपको भूलभुलैया की दीवारों के भीतर ही रहना है (ये आपकी सीमाएं/constraints हैं), और दूसरा, आप उस जगह पर रहना चाहते हैं जहाँ आप सबसे अधिक नींबू पानी बेच सकें (यह आपका उद्देश्य फलन/objective function है)।

गणित और कंप्यूटर की दुनिया में, इसे एक लीनियर प्रोग्रामिंग (LP) समस्या कहा जाता है। आमतौर पर, लोग सबसे सटीक जगह खोजने के लिए शक्तिशाली, हाई-टेक "सिम्प्लेक्स" या "इंटीरियर पॉइंट" एल्गोरिदम का उपयोग करते हैं। लेकिन एक नया, अधिक जुझारू तरीका है जिसे लीनियर सुपिरियराइजेशन (LinSup) कहा जाता है। एक आदर्श, सुनहरी जगह की तलाश करने के बजाय, LinSup बस एक ऐसी "अच्छी" जगह ढूंढना चाहता है जो भूलभुलैया की दीवारों के भीतर हो और जहाँ से वह एक यादृच्छिक (random) स्थान की तुलना में अधिक नींबू पानी बेच सके। यह बिल्कुल वैसा ही है जैसे "सैटिसफाइसिंग" (satisficing) का लक्ष्य रखना: एक ऐसा परिणाम प्राप्त करना जो पर्याप्त रूप से अच्छा हो, न कि पूर्णता के पीछे भागकर समय और ऊर्जा बर्बाद करना।

बड़ी समस्या: "लड़खड़ाती" भूलभुलैया

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

शोधकर्ता यह देखना चाहते थे: लड़खड़ाती भूलभुलैया को कौन बेहतर तरीके से संभालता है? हाई-टेक पूर्णता चाहने वाले (LP सॉल्वर्स) या जुझारू "काफी अच्छे" खोजकर्ता (LinSup)?

प्रयोग: समय के विरुद्ध एक दौड़

टीम ने अलग-अलग आकार की हजारों डिजिटल भूलभुलैया बनाईं (80x100 ग्रिड से लेकर विशाल 4000x5000 ग्रिड तक) और उन्हें अलग-अलग डिग्री तक "लड़खड़ाती" बनाया। उन्होंने एक नियम बनाया: दौड़ को तब रोक दें जब कोई धावक दीवारों के करीब पहुँच जाए बिना टकराए (एक विशिष्ट "इनफिजिबिलिटी" थ्रेशोल्ड $10^{-8}$ )। वे किसी के भी "परफेक्ट" स्थान तक पहुँचने का इंतज़ार नहीं कर रहे थे; वे बस यह देखना चाहते थे कि कौन दीवारों के करीब पहुँचने और बेहतर बिक्री करने का काम सबसे तेज़ और कुशलता से कर सकता है।

उन्होंने परीक्षण किया:

LinSup: वह जुझारू धावक जो छोटे कदम लेता है, दीवारों की जाँच करता है, और खुद को बेहतर बिक्री की ओर धकेलता है।
Scipy Simplex: एक क्लासिक धावक जो एक कोने से दूसरे कोने तक जाता है।
Gurobi Simplex: एक सुपर-फास्ट कमर्शियल धावक।
Interior Point: एक धावक जो भूलभुलैया के बीच से रास्ता काटने की कोशिश करता है।

परिणाम: लड़खड़ाती भूलभुलैया में जुझारू धावक की जीत

1. जब भूलभुलैया विशाल हो जाती है:
छोटी भूलभुलैया में, हाई-टेक धावक (Simplex) तेज़ होते हैं। लेकिन जैसे-जैसे भूलभुलैया विशाल आकार (जैसे 4000x5000) में बढ़ी, हाई-टेक धावक लड़खड़ाने लगे। उन्हें दीवारों के करीब पहुँचने में बहुत अधिक समय लगा। सबसे बड़ी भूलभलैया में, LinSup ने दौड़ तब तक पूरी कर ली जब तक Gurobi धावक अपनी दौड़ भी पूरी नहीं कर पाया था। शोध पत्र दिखाता है कि इन बड़ी, कठिन समस्याओं के लिए, LinSup बहुत अधिक मजबूत (robust) है और "काफी करीब" पहुँचने का कार्य बहुत तेज़ी से पूरा करता है।

2. जब भूलभुलैया "लड़खड़ाती" (Wobbly) होती है (उच्च कंडीशन नंबर):
यही वह जगह है जहाँ इस शोध की मुख्य खोज चमकती है। जैसे-जैसे भूलभलैया अधिक "इल-कंडीशन्ड" (अधिक टेढ़ी-मेढ़ी) होती गई:

Simplex धावक (विशेष रूप से मुफ्त Scipy वाले) घबराने लगे। उन्हें एहसास हुआ कि भूलभलैया बहुत पेचीदा है, उन्होंने हार मान ली, और खराब नींबू पानी की बिक्री के साथ रुक गए। वे हार मानने में तेज़ थे, लेकिन वे एक अच्छा स्थान खोजने में विफल रहे।
Interior Point धावक शुरुआत में तेज़ लग रहा था, लेकिन इसमें एक गुप्त दोष था: यह बार-बार दीवारों के बाहर पहुँच जाता था। भले ही इसने बिक्री का एक अच्छा नंबर खोज लिया था, लेकिन तकनीकी रूप से यह गलत जगह पर था (उच्च इनफिजिबिलिटी)। सबसे अधिक लड़खड़ाती भूलभलैया में, इसकी इनफिजिबिलिटी वैल्यू $100 $से$ 10^1$ तक पहुँच गई, जिसका अर्थ था कि यह पूरी तरह से भटक गया था।
LinSup हालांकि, स्थिर रहा। भूलभलैया कितनी भी लड़खड़ाती क्यों न हो, LinSup ने लगातार एक ऐसा स्थान खोजा जो दीवारों से बिल्कुल निर्धारित दूरी पर था। इसे इस बात से फर्क नहीं पड़ा कि गणित कितना "लड़खड़ाता" था; यह बस अपने छोटे, सावधानीपूर्ण कदम बढ़ाता रहा।

LinSup क्यों जीतता है?

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

निचोड़

यह शोध दावा नहीं करता कि LinSup एक "परफेक्ट" गणितीय समाधान खोजता है। यह स्पष्ट रूप से कहता है कि LinSup एक LP सॉल्वर नहीं है। इसका लक्ष्य पूर्ण न्यूनतम (absolute minimum) प्राप्त करना नहीं है।

हालाँकि, एक व्यवहार्य (feasible) स्थान (एक ऐसा स्थान जो नियमों को नहीं तोड़ता) खोजने के लिए जो एक यादृच्छिक स्थान से बेहतर हो, LinSup ने मानक उपकरणों की तुलना में "लड़खड़ाती" गणितीय समस्याओं के प्रति अधिक प्रतिरोधक क्षमता प्रदर्शित की।

इन सिमुलेशन में, जब समस्याएँ बड़ी और अस्त-व्यस्त हुईं, तो "काफी अच्छा" (good enough) वाला दृष्टिकोण "परफेक्ट" वाले दृष्टिकोण की तुलना में तेज़ और अधिक विश्वसनीय साबित हुआ। लेखकों को संदेह है कि ऐसा इसलिए है क्योंकि LinSup उन त्रुटियों के प्रति कम संवेदनशील है जो उच्च कंडीशन नंबर पैदा करते हैं। हालाँकि वे इन आकारों के लिए इन परिणामों के प्रति आश्वस्त हैं, वे उल्लेख करते हैं कि यह एक प्रयोगात्मक निष्कर्ष है, और वे यह देखना चाहते हैं कि क्या यह रुझान भविष्य में और भी बड़ी समस्याओं के लिए बना रहता है।

इसलिए, यदि आपके पास एक अस्त-व्यस्त, विशाल और लड़खड़ाती समस्या है, तो आपको शायद उस महंगी, शानदार पूर्णता मशीन की आवश्यकता नहीं है। कभी-कभी, वह जुझारू, "काफी अच्छा" धावक ही होता है जो वास्तव में काम पूरा करता है।

तकनीकी सारांश: लीनियर सुपरियराइजेशन बनाम लीनियर प्रोग्रामिंग की बढ़ती कंडीशन नंबर्स के प्रति प्रतिरक्षा

समस्या विवरण
यह शोध पत्र बढ़ते हुए कंडीशन नंबर्स (condition numbers) वाले लीनियर प्रोग्रामिंग समस्याओं पर लागू होने वाले लीनियर प्रोग्रामिंग (LP) एल्गोरिदम और लीनियर सुपरियराइजेशन (LinSup) पद्धति के तुलनात्मक प्रदर्शन को संबोधित करता है। जबकि शास्त्रीय LP एक इष्टतम बिंदु (बाधाओं के अधीन ऑब्जेक्टिव फंक्शन को न्यूनतम करना) खोजने का लक्ष्य रखता है, LinSup एक ऐसा व्यवहार्य (feasible) बिंदु खोजने का लक्ष्य रखता है जिसका ऑब्जेक्टिव फंक्शन मान "सुपीरियर" (कम, हालांकि आवश्यक रूप से न्यूनतम नहीं) हो। मुख्य रूप से जांचा गया प्रश्न यह है कि बढ़ती हुई कंडीशन नंबर्स के प्रति दोनों दृष्टिकोणों की संवेदनशीलता कैसी है, विशेष रूप से कैसे कंडीशन नंबर के बढ़ने से एल्गोरिदम के रनटाइम, व्यवहार्यता प्राप्ति (feasibility attainment), और ऑब्जेक्टिव फंक्शन में कमी प्रभावित होती है।

कार्यप्रणाली
लेखकों ने स्थापित LP सॉल्वर के विरुद्ध LinSup की तुलना करने के लिए एक नियंत्रित प्रयोगात्मक अध्ययन आयोजित किया।

समस्या निर्माण: शोधकर्ताओं ने $Ax \le b$ और $\ell \le x \le u$ के अधीन $\min \langle c, x \rangle$ के रूप में लीनियर प्रोग्रामिंग समस्याओं का निर्माण किया। विभिन्न कंडीशन नंबर्स के लिए संरचनात्मक समानता सुनिश्चित करने के लिए, उन्होंने सिंगुलर वैल्यू डीकंपोजिशन (SVD) का उपयोग किया। उन्होंने रैंडम सेमी-ऑर्थोगोनल मैट्रिसेस $U$ और $V$ का निर्माण किया और विशिष्ट कंडीशन नंबर्स (जो $\kappa$ के रूप में $\kappa$ से लेकर अत्यधिक इल-कंडीशन्ड तक विस्तृत हैं) प्राप्त करने के लिए विशिष्ट डायगोनल मैट्रिसेस $\Sigma_\kappa$ के साथ सिंगुलर वैल्यूज को वितरित किया। मैट्रिक्स का आकार $80 \times 100$ से $4000 \times 5000$ तक था।
परीक्षण किए गए एल्गोरिदम:
- LinSup: इसे बेस फिजिबिलिटी-सीकिंग एल्गोरिदम के रूप में एगमोन-मोटज़किन-शॉनबर्ग (AMS) प्रोजेक्शन विधि का उपयोग करके कार्यान्वित किया गया। ऑब्जेक्टिव फंक्शन के नॉर्मलाइज्ड नेगेटिव ग्रेडिएंट का उपयोग करके विक्षोभ (perturbations) पेश किए गए। एल्गोरिदम ने बाउंडेड परटर्बेशन्स और विशिष्ट स्टेप-साइज़ शेड्यूल्स और रीस्टार्ट मैकेनिज्म के साथ साइक्लिक प्रोजेक्शंस का उपयोग किया।
- LP सॉल्वर: अध्ययन ने scipy.simplex, scipy.revised simplex, scipy.interior-point, और gurobi.primal simplex के विरुद्ध LinSup की तुलना की।
प्रायोगिक प्रोटोकॉल: एक समान स्टॉपिंग क्राइटेरिया (एक निश्चित इनफीजिबिलिटी थ्रेशोल्ड $\varepsilon = 10^{-8}$ $ε = 1 0^{- 8}$ के आधार पर) लागू करके निष्पक्ष तुलना सुनिश्चित करने के लिए, लेखकों ने निम्नलिखित किया:
- LinSup को इस थ्रेशोल्ड तक पहुँचने तक चलाया गया।
- LP सॉल्वर को उसी थ्रेशोल्ड के तहत चलाया गया। यदि कोई LP सॉल्वर समय $T_{sup}$ (वह समय जो LinSup को समाप्त होने में लगा) के भीतर थ्रेशोल्ड तक पहुँचने में विफल रहता, तो उसे $T_{sup}$ पर रोक दिया गया, और उसके वर्तमान इटरेट को रिकॉर्ड किया गया।
- टर्मिनेशन के समय और इटरेशन्स के दौरान रिकॉर्ड किए गए मेट्रिक्स में रनटाइम, ऑब्जेक्टिव फंक्शन मान और अधिकतम बाधा उल्लंघन (इनफीजिबिलिटी) शामिल थे।

मुख्य योगदान और परिणाम
अध्ययन विभिन्न प्रकार की समस्या कठिनाइयों के तहत शास्त्रीय LP सॉल्वर की तुलना में LinSup की मजबूती के संबंध में अनुभवजन्य साक्ष्य प्रदान करता है:

बढ़ते आयामों पर प्रदर्शन (निश्चित $\kappa$ ):
- छोटे आयामों के लिए, सिम्प्लेक्स-आधारित सॉल्वर अधिक तेज़ थे।
- जैसे-जैसे समस्या के आयाम बढ़े (4000 $\times$ 5000 तक), सिम्प्लेक्स कार्यान्वयन (Gurobi सहित) का रनटाइम काफी बढ़ गया। उच्च आयामों में, LinSup ने सिम्प्लेक्स एल्गोरिदम के व्यवहार्य होने से पहले ही व्यवहार्यता थ्रेशोल्ड प्राप्त कर लिया।
बढ़ते कंडीशन नंबर्स पर प्रतिरक्षा (निश्चित आयाम):
- सिम्प्लेक्स विधियाँ: जैसे-जैसे कंडीशन नंबर बढ़ा, scipy सिम्प्लेक्स कार्यान्वयन में गंभीर गिरावट देखी गई। वे अक्सर उप-इष्टतम (sub-optimal) ऑब्जेक्टिव मानों के साथ जल्दी समाप्त हो गए, जो प्रभावी रूप से समस्या की कठिनाई के कारण "हार" मान गए।
- इंटिरियर पॉइंट मेथड: हालांकि इस विधि ने तेजी से कम ऑब्जेक्टिव मान पाए, लेकिन यह उच्च कंडीशन नंबर्स के लिए आवश्यक स्तर की व्यवहार्यता प्राप्त करने में संघर्ष करता रहा, जिसके परिणामस्वरूप उच्च इनफीजिबिलिटी मान (10 $^1$ तक) प्राप्त हुए।
- LinSup: सुपरियराइजेशन विधि ने उल्लेखनीय स्थिरता प्रदर्शित की। इसका रनटाइम कंडीशन नंबर की परवाह किए बिना अपेक्षाकृत सुसंगत रहा, और इसने सभी परीक्षण किए गए कंडीशन नंबर्स के लिए लक्षित व्यवहार्यता स्तर ( $\varepsilon = 10^{-8}$ ) लगातार प्राप्त किया।
- ऑब्जेक्टिव फंक्शन: इल-कंडीशन्ड परिदृश्यों में LinSup ने टर्मिनेशन के बिंदु पर सिम्प्लेक्स विधियों की तुलना में लगातार बेहतर (कम) ऑब्जेक्टिव फंक्शन मान उत्पन्न किए।
प्रॉक्सिमिटी-टारगेट विश्लेषण:
- इनफीजिबिलिटी बनाम ऑब्जेक्टिव फंक्शन मान (प्रॉक्सिमिटी-टारगेट कर्व्स) के प्लॉट्स ने पुष्टि की कि LinSup ने ऑब्जेक्टिव को कम करते हुए व्यवहार्यता की ओर एक स्थिर पथ बनाए रखा। इसके विपरीत, इंटिरियर पॉइंट मेथड ने कम ऑब्जेक्टिव मान खोजने और बाधाओं को संतुष्ट करने के बीच एक विच्छेद दिखाया।

महत्व और दावे
शोध पत्र दावा करता है कि लीनियर सुपरियराइजेशन, विशेष रूप से बड़े पैमाने के परिदृश्यों में, इल-कंडीशन्ड लीनियर सिस्टम के साथ निपटने के लिए शास्त्रीय LP सॉल्वर की तुलना में एक विशिष्ट लाभ प्रदान करता है।

मजबूती (Robustness): लेखक निष्कर्ष निकालते हैं कि LinSup, परीक्षण किए गए LP सॉल्वर्स की तुलना में उच्च कंडीशन नंबर्स से कम प्रभावित होता है। वे इस प्रभाव को एल्गोरिदम की प्रकृति के कारण बताते हैं: LinSup पूरे सिस्टम को एक साथ हल करने के बजाय हाफ-स्पेस पर व्यक्तिगत प्रोजेक्शन करता है, और बेस एल्गोरिदम की "बाउंडेड परटर्बेशन रेजिलिएंस" उन कम्प्यूटेशनल त्रुटियों को अवशोषित करने में मदद कर सकती है जो अन्यथा इल-कंडिशनिंग द्वारा बढ़ा दी जाती हैं।
व्यावहारिक उपयोगिता: अध्ययन सुझाव देता है कि उन अनुप्रयोगों के लिए जहाँ एक कम ऑब्जेक्टिव मान वाले व्यवहार्य बिंदु को खोजना पर्याप्त है (एक "सैटिस्फाइसिंग" दृष्टिकोण, न कि सख्त इष्टतमता), LinSup इल-पोज़्ड समस्याओं के लिए एक अधिक विश्वसनीय और कुशल उपकरण है।
सीमित दायरा: लेखक स्पष्ट रूप से कहते हैं कि उनके परिणाम विशिष्ट प्रयोगात्मक सेटअप और समस्या आकारों पर आधारित हैं। वे विश्वास व्यक्त करते हैं कि देखे गए रुझान बड़े उदाहरणों में भी बने रहेंगे, लेकिन वे यह दावा नहीं करते कि LinSup सभी अनुकूलन कार्यों के लिए LP सॉल्वर को बदल देता है। वे नोट करते हैं कि LinSup एक LP सॉल्वर नहीं है और न ही यह बाधित इष्टतमता (constrained optimality) का लक्ष्य रखता है, बल्कि एक "सुपीरियर" व्यवहार्य बिंदु के लिए है।
भावी कार्य: शोध पत्र सुझाव देता है कि लीनियर सेटिंग्स में LinSup की देखी गई मजबूती की जांच नॉन-लीनियर सेटिंग्स में भी की जानी चाहिए, विशेष रूप से वहां जहां इंटिरियर-पॉइंट मेथड्स को इल-कंडिशनिंग के कारण संघर्ष करना पड़ता है (जैसे, इंटेंसिटी-मॉड्यूलेटेड रेडियोथेरेपी)।

बड़ी समस्या: "लड़खड़ाती" भूलभुलैया

प्रयोग: समय के विरुद्ध एक दौड़

परिणाम: लड़खड़ाती भूलभुलैया में जुझारू धावक की जीत

LinSup क्यों जीतता है?

निचोड़

इसी तरह के और पेपर