गैर-ऋणात्मक न्यूनतम वर्ग

गणितीय अनुकूलन में, गैर-नकारात्मक न्यूनतम वर्ग की समस्या (एनएनएलएस) एक प्रकार की प्रतिबंधित न्यूनतम वर्ग समस्या है जहां गुणांक को नकारात्मक बनने की अनुमति नहीं है। यानी एक मैट्रिक्स दिया गया है A और प्रतिक्रिया चर का एक (कॉलम) वेक्टर y, लक्ष्य खोजना है

$\operatorname {arg\,min} \limits _{\mathbf {x} }\|\mathbf {Ax} -\mathbf {y} \|_{2}^{2}$ का विषय है x ≥ 0.

यहाँ x ≥ 0 का अर्थ है कि वेक्टर का प्रत्येक घटक x गैर-नकारात्मक होना चाहिए, और ‖·‖₂ यूक्लिडियन मानदंड को दर्शाता है।

गैर-नकारात्मक न्यूनतम वर्ग समस्याएं मैट्रिक्स अपघटन में उप-समस्याओं के रूप में सामने आती हैं, उदाहरण के लिए सीपी अपघटन के लिए एल्गोरिदम मेंऔर गैर-नकारात्मक मैट्रिक्स गुणनखंडन|गैर-नकारात्मक मैट्रिक्स/टेंसर गुणनखंडन। उत्तरार्द्ध को एनएनएलएस का सामान्यीकरण माना जा सकता है।

एनएनएलएस का एक और सामान्यीकरण परिबद्ध-परिवर्तनीय न्यूनतम वर्ग (बीवीएलएस) है, जिसमें एक साथ ऊपरी और निचली सीमाएं होती हैं α_i ≤ x_i ≤ β_i.

द्विघात प्रोग्रामिंग संस्करण

एनएनएलएस समस्या द्विघात प्रोग्रामिंग समस्या के बराबर है

$\operatorname {arg\,min} \limits _{\mathbf {x\geq 0} }\left({\frac {1}{2}}\mathbf {x} ^{\mathsf {T}}\mathbf {Q} \mathbf {x} +\mathbf {c} ^{\mathsf {T}}\mathbf {x} \right),$

कहाँ Q = A^TA और c = −A^T y. यह समस्या उत्तल अनुकूलन है, जैसे Q सकारात्मक-अर्धनिश्चित मैट्रिक्स है और गैर-नकारात्मकता बाधाएं एक उत्तल व्यवहार्य सेट बनाती हैं।

एल्गोरिदम

इस समस्या को हल करने के लिए पहला व्यापक रूप से उपयोग किया जाने वाला एल्गोरिदम एक सक्रिय-सेट विधि है जिसे लॉसन और हैनसन ने अपनी 1974 की पुस्तक सॉल्विंग लीस्ट स्क्वेयर प्रॉब्लम्स में प्रकाशित किया है। छद्मकोड में, यह एल्गोरिदम इस प्रकार दिखता है:

• इनपुट:
  • एक वास्तविक-मूल्यवान मैट्रिक्स A आयाम का m × n,
  • एक वास्तविक-मूल्यवान वेक्टर y आयाम का m,
  • एक वास्तविक मूल्य ε, रुकने की कसौटी के लिए सहनशीलता।
• आरंभ करें:
  • तय करना P = ∅.
  • तय करना R = {1, ..., n}.
  • तय करना x आयाम के एक सर्व-शून्य वेक्टर के लिए n.
  • तय करना w = A^T(y − Ax).
  • होने देना w^R आर से इंडेक्स के साथ उप-वेक्टर को निरूपित करें
• मुख्य लूप: जबकि R ≠ ∅ और max(w^R) > ε:
  • होने देना j में R का सूचकांक हो max(w^R) में w.
  • जोड़ना j को P.
  • निकालना j से R.
  • होने देना A^P होना A में शामिल चर तक ही सीमित है P.
  • होने देना s के समान लंबाई का वेक्टर बनें x. होने देना s^P पी से इंडेक्स के साथ उप-वेक्टर को निरूपित करें, और चलो s^R आर से इंडेक्स के साथ उप-वेक्टर को निरूपित करें।
  • तय करना s^P = ((A^P)^T A^P)⁻¹ (A^P)^Ty
  • तय करना s^Rशून्य करने के लिए
  • जबकि min(s^P) ≤ 0:
    • होने देना α = min x_i/x_i − s_i for i in P where s_i ≤ 0.
    • तय करना x को x + α(s − x).
    • करने के लिए कदम R सभी सूचकांक j में P ऐसा है कि x_j ≤ 0.
    • तय करना s^P = ((A^P)^T A^P)⁻¹ (A^P)^Ty
    • तय करना s^Rशून्य करने के लिए.
  • तय करना x को s.
  • तय करना w को A^T(y − Ax).
• आउटपुट: एक्स

यह एल्गोरिदम किसी समाधान तक पहुंचने के लिए सीमित संख्या में कदम उठाता है और जैसे-जैसे आगे बढ़ता है, अपने उम्मीदवार समाधान को सुचारू रूप से बेहतर बनाता है (ताकि यह उचित संख्या में पुनरावृत्तियों में कट जाने पर अच्छे अनुमानित समाधान पा सके), लेकिन व्यवहार में यह बहुत धीमा है, जिसका मुख्य कारण मूर-पेनरोज़ स्यूडोइनवर्स की गणना है। ((A^P)^T A^P)⁻¹. इस एल्गोरिथम के वेरिएंट MATLAB में रूटीन के रूप में उपलब्ध हैं lsqnonneg और SciPy में के रूप में optimize.nnls. 1974 के बाद से कई बेहतर एल्गोरिदम का सुझाव दिया गया है। फास्ट एनएनएलएस (एफएनएनएलएस) लॉसन-हैनसन एल्गोरिदम का एक अनुकूलित संस्करण है। अन्य एल्गोरिदम में लैंडवेबर पुनरावृत्ति की ढतला हुआ वंश विधि के वेरिएंट शामिल हैं और उपरोक्त द्विघात प्रोग्रामिंग समस्या के आधार पर समन्वय अवतरण|समन्वय-वार अनुकूलन।

यह भी देखें

• एम-मैट्रिक्स
• पेरोन-फ्रोबेनियस प्रमेय