क्या सी ++ में एक वर्गिक प्रोग्रामिंग लाइब्रेरी है?

Question

मुझे मिला एकमात्र Google खोज परिणाम QuadProg ++ है लेकिन यह वर्ग प्रोग्रामिंग समस्या को हल नहीं कर सकता है जिसका मैट्रिक्स Cholesky अपघटन के लिए लागू नहीं है।

तो क्या कोई मुझे अन्य पुस्तकालय पर कुछ सुझाव दे सकता है? धन्यवाद।

Answer 1

LAPACK में कई Cholesky अपघटन दिनचर्या हैं (वे इसे Cholesky कारककरण कहते हैं)। LAPACK के लिए सी ++ रैपर उपलब्ध हैं (सूची के लिए यह SO question देखें)।

उस पोस्ट में एनोकॉम का उत्तर थोड़ा सा गूढ़ है, लेकिन उसका मतलब था कि लैपैक बाइंडिंग्स हैं जिनका उपयोग बूस्ट की रैखिक बीजगणित लाइब्रेरी, uBLAS के साथ किया जा सकता है।

---

मैं इस पुस्तकालय मिल गया है: OOQP (द्विघात प्रोग्रामिंग के लिए वस्तु उन्मुख सॉफ्टवेयर)। यदि आप उस पृष्ठ को स्क्रॉल करते हैं, तो आपको एक शोध पत्र और उपयोगकर्ता मार्गदर्शिका मिल जाएगी। उस पुस्तकालय के लिए एक सी ++ एपीआई प्रतीत होता है। उम्मीद है की यह मदद करेगा।

Answer 2

CGAL वर्गबद्ध प्रोग्रामिंग के लिए बहुत अच्छा लग रहा है। a manual भी है।

// by default, we have a nonnegative QP with Ax <= b 
    Program qp (CGAL::SMALLER, true, 0, false, 0); 

    // now set the non-default entries: 
    const int X = 0; 
    const int Y = 1; 
    qp.set_a(X, 0, 1); qp.set_a(Y, 0, 1); qp.set_b(0, 7); // x + y <= 7 
    qp.set_a(X, 1, -1); qp.set_a(Y, 1, 2); qp.set_b(1, 4); // -x + 2y <= 4 
    qp.set_u(Y, true, 4);         //  y <= 4 
    qp.set_d(X, X, 2); qp.set_d (Y, Y, 8); // !!specify 2D!! x^2 + 4 y^2 
    qp.set_c(Y, -32);          // -32y 
    qp.set_c0(64);           // +64 

    // solve the program, using ET as the exact type 
    Solution s = CGAL::solve_quadratic_program(qp, ET()); 
    assert (s.solves_quadratic_program(qp)); 

the first example से कोड।

Answer 3

यदि आप भुगतान करना चाहते हैं, तो आप Mosek का उपयोग कर सकते हैं। हालांकि, निशुल्क 30 दिन का परीक्षण है। इसे आम तौर पर उपलब्ध सबसे तेज़ सॉल्वर माना जाता है (कोई उद्धरण नहीं, क्षमा करें) इंटरफ़ेस सी शैली है, हालांकि स्पष्ट रूप से सी ++ से पूरी तरह से कॉलबल है। मोसेक वास्तव में एक शंकु प्रोग्रामिंग सॉल्वर का अधिक है, लेकिन यदि आप एक शंकु समस्या के रूप में अपनी समस्या को दोबारा सुधारने की तरह महसूस नहीं करते हैं (मोसेक के पास यह करने के तरीके पर बहुत सारे दस्तावेज हैं), तो आप अभी भी हल करने के लिए अपने स्टोकास्टिक ग्रेडिएंट वंश सॉल्वर का उपयोग कर सकते हैं आपका वर्गबद्ध फॉर्मूलेशन।

Answer 4

उपरोक्त उत्तरों में से कई उत्तर गायब हैं, यह है कि मैट्रिक्स केवल सकारात्मक अर्ध-निश्चित (PSD) है या वास्तव में अनिश्चित है। मैंने क्वाडप्रोग का उपयोग नहीं किया है, लेकिन यदि यह एक PSD उद्देश्य मैट्रिक्स पर विफल रहता है, तो यह सॉफ़्टवेयर की मजबूती की कमी का संकेत है (उत्तल क्यूपी अक्सर PSD होते हैं, जहां केवल कड़ाई से उत्तल क्यूपी सकारात्मक निश्चित होते हैं)। गोलब की पुस्तक "मैट्रिक्स कम्प्यूटेशंस" के मुताबिक, चॉल्सकी कारककरण को PSD मैट्रिस पर लागू किया जा सकता है, लेकिन संख्यात्मक स्थिरता का सामना करना पड़ता है।

सामान्य nonlinear प्रोग्रामिंग सॉफ़्टवेयर के लिए- उत्तल और गैर-उत्तल, दोनों COIN-OR प्रोजेक्ट मुफ़्त और गैर-मुक्त सॉफ़्टवेयर की सूचियां बनाए रखता है। उनके द्वारा सूचीबद्ध हलकों में से एक आईपीओपीटी है, जो निश्चित रूप से आपकी समस्या को हल करने में सक्षम है। आईपीओपीटी एक इंटीरियर-पॉइंट एल्गोरिदम का उपयोग करता है, जो छोटी समस्याओं के लिए, आमतौर पर सक्रिय-सेट विधियों (जैसे क्वाडप्रोग उपयोग) से धीमा होता है। एक विकल्प के रूप में, आप अपने क्यूपी को रैखिक पूरकता समस्या (एलसीपी) के रूप में तैयार कर सकते हैं और फिर इसे एलसीपी सॉल्वर का उपयोग करके हल कर सकते हैं। मुझे फ़ैकलर और मिरांडा के मैटलैब कोड लेमेक को सी ++ में आसानी से पोर्टेबल पाया गया है।

Answer 5

कई पुस्तकालय हैं जिनमें क्यूपी सॉल्वर शामिल हैं। खुले स्रोत और वाणिज्यिक विकल्प दोनों हैं। मौजूदा उत्तरों में से कुछ सूचीबद्ध हैं। मैं इस मुद्दे को मैट्रिक्स के साथ स्पष्ट करना चाहता हूं।

मुझे लगता है कि आप उद्देश्य मैट्रिक्स का जिक्र कर रहे हैं। बाधा मैट्रिक्स केवल एक खाली खाली व्यवहार्य सेट की ओर ले जाने की जरूरत है। आपने बताया कि मैट्रिक्स Cholesky अपघटन के लिए उपयुक्त नहीं है। चूंकि चोलस्की अपघटन किसी भी सकारात्मक निश्चित मैट्रिक्स के लिए बनाया जा सकता है, इसलिए यह संकेत है कि आपका मैट्रिक्स सकारात्मक निश्चित नहीं है।

यदि मैट्रिक्स सकारात्मक अर्ध-निश्चित है (यानी इसमें एक या एक से अधिक शून्य eigenvalues ​​है) तो समस्या एक उत्तल QP है और इसे कुशलता से हल किया जा सकता है। हालांकि, कई solvers एक सकारात्मक निश्चित उद्देश्य की आवश्यकता है। चूंकि सकारात्मक अर्द्ध-निश्चित क्यूपी के उद्देश्य में एक गैर-तुच्छ नलस्पेस है, इसलिए कई समाधान हो सकते हैं। वास्तव में, समाधानों का सेट भी असंबद्ध हो सकता है। संख्यात्मक एल्गोरिदम केवल वैसे भी एक अनुमानित समाधान प्रदान करेगा, इसलिए यह शायद ही कभी महत्वपूर्ण है कि मैट्रिक्स में eigenvalues ​​हैं जो बिल्कुल शून्य हैं। आप विकर्ण पर एक छोटे सकारात्मक मूल्य के साथ एक विकर्ण मैट्रिक्स जोड़कर मैट्रिक्स सकारात्मक निश्चित कर सकते हैं। यह अनिवार्य रूप से सबसे छोटे 2-मानदंड के साथ समाधान का चयन करेगा। व्यावहारिक रूप से, यह भी एक अच्छा विचार है जब मैट्रिक्स सकारात्मक निश्चित होता है क्योंकि मैट्रिस जिनके पास शून्य के करीब ईजिनवेल्स होते हैं, वे अक्सर संख्यात्मक हलकों के साथ समस्याएं पैदा कर सकते हैं। स्थिरता और सटीकता के बीच एक व्यापारिकता जोड़ने के लिए कितना विकर्ण है।

यदि मैट्रिक्स अनिश्चित है (यानी यह भी एक नकारात्मक eigenvalue है) तो समस्या एनपी-हार्ड है। इसका मतलब है कि वर्तमान में उपलब्ध एल्गोरिदम के आधार पर किसी भी कोड में मध्यम आकार की समस्याओं के लिए भी अनावश्यक सबसे खराब केस चलने का समय होगा। अगर आपकी समस्या में कुछ विशेष संरचना है या आपको वैश्विक स्तर पर इष्टतम समाधान की आवश्यकता नहीं है तो आप ठीक हो सकते हैं। एक सामान्य दृष्टिकोण एक उत्तल विश्राम की तलाश है।