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

गणितीय अनुकूलन में, गैर-ऋणात्मक न्यूनतम वर्ग की समस्या (एनएनएलएस) प्रकार की प्रतिबंधित न्यूनतम वर्ग समस्या है जहां गुणांक को ऋणात्मक बनने की अनुमति नहीं है। अर्थात आव्यूह दिया गया है 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)⁻¹. इस कलन के प्रकार मैट लैब में रूटीन के रूप में उपलब्ध हैं लसक्नोनग और SciPy में के रूप में ऑप्टिमाइज़.एनएनएलएस होता है.|

1974 के बाद से अनेक उत्तम कलन का सुझाव दिया गया है। फास्ट एनएनएलएस (एफएनएनएलएस) लॉसन-हैनसन कलन का अनुकूलित संस्करण है। अन्य कलन में लैंडवेबर पुनरावृत्ति की ढतला हुआ वंश विधि के प्रकार सम्मिलित हैं और उपरोक्त द्विघात प्रोग्रामिंग समस्या के आधार पर समन्वय अवतरण या समन्वय-वार अनुकूलन करता है।

यह भी देखें

• एम-आव्यूह
• पेरोन-फ्रोबेनियस प्रमेय