तकनीकी सारांश: विसंयोजक वर्गों का योग (Disjunctive Sum of Squares)

समस्या विवरण

यह शोध पत्र बहुपदों (polynomials) की गैर-ऋणात्मकता (nonnegativity) को प्रमाणित करने की मौलिक समस्या को संबोधित करता है। जबकि एक बहुपद $p$ तब गैर-ऋणात्मक होता है जब $p(x) \geq 0$ सभी $x \in \mathbb{R}^n$ के लिए हो, इस गुण को निर्धारित करना आम तौर पर NP-hard है। मानक दृष्टिकोण, 'वर्गों का योग' (Sum of Squares - SOS) विधि, $p$ को एक एकल बीजगणितीय पहचान $p(x) = \sum q_i^2(x)$ के रूप में व्यक्त करके गैर-ऋणात्मकता को प्रमाणित करती है। हालांकि, सभी गैर-ऋणात्मक बहुपद SOS नहीं होते हैं (एक तथ्य जिसे हिलबर्ट ने स्थापित किया था), और उन बहुतों के लिए गैर-ऋणात्मकता सिद्ध करने के लिए जो SOS नहीं हैं, आमतौर पर $p$ को एक उच्च-डिग्री वाले SOS बहुपद से गुणा करने की आवश्यकता होती है (जैसे, हिलबर्ट की 17वीं समस्या के आर्टिन के समाधान के माध्यम से)। इसके परिणामस्वरूप ऐसी बीजगणितीय पहचानें प्राप्त होती हैं जिनकी डिग्री मूल बहुपद की तुलना में काफी अधिक होती है, जिससे सेमीडेफिनेट प्रोग्राम (SDPs) का आकार तेजी से बढ़ता है और वे गणनात्मक रूप से अव्यवहार्य (intractable) हो जाते हैं।

इस शोध को प्रेरित करने वाला केंद्रीय प्रश्न यह है: क्या एक एकल पहचान के बजाय कई बीजगणितीय पहचानों का निर्माण करके, बहुपद गैर-ऋणात्मकता के SOS-आधारित प्रमाण की जटिलता को कम किया जा सकता है?

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

लेखक विसंयोजक वर्गों का योग (Disjunctive Sum of Squares - Disjunctive SOS) की अवधारणा प्रस्तुत करते हैं। एक एकल वैश्विक पहचान के बजाय, गैर-ऋणात्मकता को बीजगणितीय पहचानों के एक संग्रह द्वारा प्रमाणित किया जाता है, जिनमें से प्रत्येक डोमेन के एक विशिष्ट उप-क्षेत्र (subregion) पर मान्य होता है। ये उप-क्षेत्र स्थान का एक विभाजन (partition) या आवरण (cover) बनाते हैं, जो एक बीजगणितीय विसंयोजन (algebraic disjunction) द्वारा परिभाषित होता है।

मुख्य परिभाषाएँ

1. बीजगणितीय विसंयोजन (Algebraic Disjunction): बहुपदों का एक संग्रह $\mathcal{D} = \{\{q_{k,j}\}\}$ ताकि क्षेत्रों का संघ $\Omega_k = \{x \mid q_{k,j}(x) \geq 0, \forall j\}$ पूरे $\mathbb{R}^n$ को कवर करे।
2. विसंयोजक SOS प्रमाण (Disjunctive SOS Proof): एक बहुपद $p$ एक $\mathcal{D}$ के सापेक्ष विसंयोजक SOS है यदि, प्रत्येक क्षेत्र $\Omega_k$ के लिए, SOS बहुपदों $s_{k,j}$ अस्तित्व में हैं कि:
   $$p(x) = s_{k,0}(x) + \sum_{j=1}^{n_k} s_{k,j}(x)q_{k,j}(x) \quad \text{सभी } x \in \Omega_k \text{ के लिए।}$$
   महत्वपूर्ण बात यह है कि $s_{k,j}$ के SOS बहुपदों की डिग्री को कम रखा जा सकता है (विशेष रूप से, $p$ की डिग्री तक सीमित), जैसा कि वैश्विक SOS प्रमाणों में होता है जहाँ डिग्री अक्सर बढ़नी पड़ती है।

सैद्धांतिक ढांचा (Theoretical Framework)

यह शोध पत्र दो मुख्य सैद्धांतिक परिणाम स्थापित करता है, जिन्हें विसंयोजक पोज़िटिवस्टेन्सैट्ज़ (Disjunctive Positivstellensätze) कहा जाता है:

1. SDP-आधारित विसंयोजक पोज़िटिवस्टेन्सैट्ज़ (प्रमेय 1):
   किसी भी धनात्मक निश्चित (positive definite) रूप $p$ के डिग्री $d$ के लिए, बीजगणितीय विसंयोजनों (गोलीय कैप्स के माध्यम से निर्मित) का एक स्पष्ट परिवार मौजूद है, जिससे $p$ एक विसंयोजक SOS प्रमाण स्वीकार करता है जहाँ SOS मल्टीप्लायर्स की डिग्री अधिकतम $d$ है। यह यूनिट स्फीयर पर बहुपद न्यूनीकरण के लिए निश्चित आकार (पदानुक्रम के स्तर से स्वतंत्र) के SDPs के माध्यम से निम्नतम सीमाओं (lower bounds) के एक अभिसारी पदानुक्रम की अनुमति देता है।

2. अनुकूलन-मुक्त विसंयोजक पोज़िटिवस्टेन्सैट्ज़ (प्रमेय 8):
   एक अधिक सशक्त परिणाम जो दर्शाता है कि किसी भी धनात्मक निश्चित रूप के लिए, सिम्प्लेक्सल विसंयोजनों (बहुफलकीय शंकु/polyhedral cones) का एक परिवार मौजूद है, जिससे $p$ को केवल प्रत्येक शंकु के भीतर निर्देशांकों के एक रैखिक परिवर्तन के बाद उसके गुणांकों के गैर-ऋणात्मक होने की जाँच करके प्रमाणित किया जा सकता है। इस दृष्टिकोण के लिए किसी अनुकूलन सॉल्वर (optimization solver) की आवश्यकता नहीं है (केवल रैखिक प्रोग्रामिंग या प्रत्यक्ष गुणांक जाँच), लेकिन इसके लिए अधिक क्षेत्रों की आवश्यकता हो सकती है।

एल्गोरिद्मिक ढांचा (Algorithmic Framework)

लेखक इन विसंयोजक प्रमाणों को अनुकूल रूप से खोजने के लिए एक स्थानिक ब्रांच-एंड-बाउंड (Spatial Branch-and-Bound - SBB) ढांचे का प्रस्ताव करते हैं। स्थान को समान रूप से विभाजित करने के बजाय, एल्गोरिदम:

• उप-क्षेत्रों (सिम्प्लेक्सल शंकुओं) का एक वृक्ष (tree) बनाए रखता है।
• प्रत्येक उप-क्षेत्र पर SDPs (या रैखिक जाँच) के माध्यम से निचली सीमाएँ (lower bounds) ज्ञात करता है।
• प्रक्षिप्त ग्रेडिएंट डिसेंट (projected gradient descent) के माध्यम से ऊपरी सीमाएँ (upper bounds) ज्ञात करता है।
• सबसे कम निचली सीमा वाले उप-क्षेत्र के सबसे लंबे किनारे को द्विभाजित (bisect) करके शाखाएँ (branching) बनाता है।
  यह अनुकूल दृष्टिकोण कम उप-क्षेत्रों के साथ प्रमाण खोजने का लक्ष्य रखता है।

मुख्य योगदान और परिणाम

1. सैद्धांतिक गारंटी

• निश्चित डिग्री: शोध पत्र सिद्ध करता है कि कम-डिग्री वाले विसंयोजक SOS प्रमाण हमेशा मौजूद होते हैं। प्रमाण में SOS बहुपदों की डिग्री को बढ़ना आवश्यक नहीं है; इसे मूल बहुपद की डिग्री पर स्थिर रखा जा सकता है।
• अभिसरण (Convergence): लेखक यूनिट स्फीयर पर सामान्य बहुपद अनुकूलन समस्याओं (POPs) के लिए एक अभिसारी निम्नतम सीमा पदानुक्रम का निर्माण करते हैं। वे $O(1/m)$ के अभिसरण दर को स्थापित करते हैं, जहाँ $m$ स्थानिक विभाजन के रिज़ॉल्यूशन से संबंधित है।
• अनुकूलन-मुक्त प्रमाण: दूसरा पोज़िटिवस्टेन्सैट्ज़ बिना SDP हल किए गैर-ऋणात्मकता को प्रमाणित करने का एक तरीका प्रदान करता है, जो रैखिक रूपांतरणों और गुणांक गैर-ऋणात्मकता जाँचों पर निर्भर करता है।

2. प्रतिबंधित अनुकूलन (Constrained Optimization) पर अनुप्रयोग

• बहुपद अनुकूलन (Polynomial Optimization): [2] से एक न्यूनीकरण तकनीक को विसंयोजक दृष्टिकोण के साथ जोड़कर, लेखक कॉम्पैक्ट बेसिक सेमी-अलजेब्रिक सेट्स पर सामान्य बहुपद अनुकूलन समस्याओं (POPs) के लिए एक अभिसारी निम्नतम सीमा पदानुक्रम का निर्माण करते हैं।
• कोपोजिटिव प्रोग्रामिंग (Copositive Programming): विधि को मैट्रसेज़ की कोपोज़िटिविटी को प्रमाणित करने के लिए विशेष बनाया गया है ($x^T Q x \geq 0$ जहाँ $x \geq 0$)। लेखक एक "विसंयोजक P+N" स्थिति को परिभाषित करते हैं जहाँ एक मैट्रिक्स को तब कोपोज़िटिव प्रमाणित किया जाता है यदि वह गैर-ऋणात्मक ऑर्थोडेक्स के प्रत्येक सिम्प्लेक्सल उप-क्षेत्र में, एक धनात्मक निश्चित और एक गैर-ऋणात्मक मैट्रिक्स में विभाजित किया जा सकता है। यह एक पूर्ण पदानुक्रम प्रदान करता है जहाँ SDP बाधा का आकार स्थिर ($n \times n$) रहता है, जो मौजूदा पदानुक्रमों के विपरीत है जहाँ बाधा का आकार पदानुक्रम स्तर के साथ बहुपद रूप से बढ़ता है।

3. संख्यात्मक प्रयोग

लेखक निम्नलिखित पर संख्यात्मक प्रयोग प्रस्तुत करते हैं:

• गैर-SOS बहुपद: एल्गोरिदम ने शास्त्रीय गैर-SOS बहुपदों (जैसे मोटकिन, रॉबिन्सन, चोई-लाम, डेलज़ेल) की गैर-ऋणात्मकता को SBB ढांचे के माध्यम से कम उप-क्षेत्रों (अक्सर 20 से कम) का उपयोग करके सफलतापूर्वक प्रमाणित किया।
• कोपोज़िटिव प्रोग्राम: एल्गोरिदम ने गैर-रैखिक द्विघातीय प्रोग्रामों (nonconvex quadratic programs) को हल किया और रैंडम इंस्टेंस पर ग्राफ के क्लिक संख्या (क्लिक नंबर) की गणना की (मोटकिन-स्ट्रॉस प्रमेय के माध्यम से)।
• प्रदर्शन: परिणाम दर्शाते हैं कि विसंयोजक दृष्टिकोण पारंपरिक SOS पदानुक्रमों की तुलना में काफी कम उप-क्षेत्रों का उपयोग करके गैर-ऋणात्मकता को प्रमाणित कर सकता है और अनुकूलन समस्याओं को हल कर सकता है, और SDP बाधाएं प्रबंधनीय आकार की रहती हैं।

महत्व और दावे

शोध पत्र का दावा है कि विसंयोजक वर्गों का योग दृष्टिकोण प्रमाण की जटिलता (SOS बहुपदों की डिग्री) को उपयोग किए जाने वाले बीजगणितीय पहचानों की संख्या से अलग करके पारंपरिक SOS पदानुक्रमों के लिए एक व्यवहार्य विकल्प प्रदान करता है।

• गणना दक्षता: SOS बहुपदों की डिग्री को कम और स्थिर रखकर, यह मूल बहुपद की डिग्री बढ़ने से जुड़े "डायमेंशनलिटी के अभिशाप" (curse of dimensionality) से बचता है और underlying SDPs का आकार स्थिर रखता है।
• लचीलापन: ढांचा कम क्षेत्रों के साथ कड़े बाउंड (SDP-आधारित खोज) और तेज़, हालांकि संभावित रूप से मोटे (coarser) प्रमाणों (अनुकूलन-मुक्त खोज) दोनों का समर्थन करता है।
• पूर्णता: लेखक सिद्ध करते हैं कि यह दृष्टिकोण पूर्ण (complete) है; किसी भी धनात्मक निश्चित बहुपद (या धनात्मक निश्चित मैट्रिक्स) के लिए, उनके ढांचे के भीतर एक प्रमाण मौजूद है।

शोध पत्र यह निष्कर्ष निकालता है कि जबकि सैद्धांतिक निर्माण समान विभाजनों (uniform partitions) का उपयोग करते हैं, व्यावहारिक SBB एल्गोरिदम स्थान को अनुकूल रूप से परिष्कृत करता है, जो यह सुझाव देता है कि विशिष्ट-मामला विसंयोजनों (instance-specific disjunctions) से आवश्यक क्षेत्रों की संख्या को और कम किया जा सकता है। यह कार्य विसंयोजक SOS को स्पर्सिटी (sparsity) और सिमेट्री (symmetry) के दोहन के साथ जोड़ने और इसके द्वैत मोमेंट (dual moment) पक्ष की खोज के नए मार्ग खोलता है।