Nonlinear programming — अरैखिक प्रोग्रामिंग

अरेखीय प्रोग्रामिंग (NLP) — यह गणितीय प्रोग्रामिंग और संक्रिया अनुसंधान का एक विभाग है, जो उन अनुकूलन समस्याओं से संबंधित है जहाँ उद्देश्य फ़ंक्शन और/या कम से कम एक प्रतिबंध, निर्णय चरों के अरेखीय फ़ंक्शन होते हैं।

NLP रेखीय प्रोग्रामिंग का सामान्यीकरण है और वास्तविक प्रणालियों तथा प्रक्रियाओं के एक व्यापक वर्ग का मॉडलिंग करने की अनुमति देता है, जहाँ चरों के बीच संबंध कड़ाई से आनुपातिक नहीं होते (अर्थात्, वे सीधी रेखाओं के बजाय वक्रों द्वारा वर्णित होते हैं)।

विषय और उद्देश्य

अरेखीय प्रोग्रामिंग का उपयोग उन परिस्थितियों में इष्टतम समाधान खोजने के लिए किया जाता है जब:

• नियंत्रित मापदंडों पर लक्ष्य संकेतक (लाभ, लागत, दक्षता आदि) की निर्भरता अरेखीय हो (उदाहरण के लिए, पैमाने की घटती प्रतिफल, द्विघाती लागत)।
• संसाधनों या तकनीकी प्रक्रियाओं पर प्रतिबंध अरेखीय संबंधों द्वारा वर्णित हों (उदाहरण के लिए, रासायनिक अभिक्रियाएँ, भौतिक नियम, आर्थिक निर्भरताएँ)।

NLP समस्याएँ अनेक क्षेत्रों में उत्पन्न होती हैं:

• इंजीनियरी डिज़ाइन (संरचनाओं, प्रक्रियाओं का अनुकूलन)।
• अर्थशास्त्र और वित्त (जोखिम को ध्यान में रखते हुए पोर्टफ़ोलियो का अनुकूलन, बाज़ार मॉडलिंग)।
• रासायनिक प्रौद्योगिकी (रिएक्टर प्रचालन स्थितियों का अनुकूलन)।
• Machine Learning (Neural Network का प्रशिक्षण, Support Vector Machine)।
• उत्पादन प्रक्रियाओं का प्रबंधन। लॉजिस्टिक्स (अरेखीय लागतों को ध्यान में रखते हुए)।

NLP समस्या का गणितीय सूत्रीकरण

अरेखीय प्रोग्रामिंग की सामान्य समस्या को निम्नलिखित प्रकार से परिभाषित किया जाता है:

ऐसे निर्णय चरों के मानों का समुच्चय खोजना आवश्यक है जो अरेखीय उद्देश्य फ़ंक्शन को अधिकतम या न्यूनतम करे। इसके साथ ही चरों के मान प्रतिबंधों की प्रणाली को संतुष्ट करने चाहिए, जिन्हें असमानताओं के रूप में (उदाहरण के लिए, "मान A को B से कम या बराबर होना चाहिए") अथवा समानताओं के रूप में (उदाहरण के लिए, "मान C को ठीक D के बराबर होना चाहिए") व्यक्त किया जा सकता है। महत्त्वपूर्ण बात यह है कि लक्ष्य या प्रतिबंधों का वर्णन करने वाले फ़ंक्शनों में से कम से कम एक अरेखीय हो। प्रायः चरों की अऋणात्मकता की शर्तें भी जोड़ी जाती हैं, अर्थात् यह आवश्यकता कि उनके मान शून्य से अधिक या बराबर हों।

चरों के उन सभी मान-समुच्चयों का संग्रह जो प्रतिबंधों को संतुष्ट करते हैं, स्वीकार्य समाधान क्षेत्र (ОДР) बनाता है।

रेखीय प्रोग्रामिंग से अंतर

अरेखीय प्रोग्रामिंग, रेखीय प्रोग्रामिंग (LP) से महत्त्वपूर्ण रूप से भिन्न है:

• अरेखीयता: उद्देश्य फ़ंक्शन या प्रतिबंध (अथवा दोनों) में अरेखीय निर्भरताएँ होती हैं।
• स्वीकार्य क्षेत्र के गुण: NLP में स्वीकार्य समाधान क्षेत्र उत्तल (convex) नहीं हो सकता (LP के विपरीत जहाँ स्वीकार्य क्षेत्र सदैव एक उत्तल बहुफलक होता है)।
• इष्टतम के गुण: NLP में इष्टतम समाधान आवश्यक रूप से स्वीकार्य क्षेत्र के शीर्ष पर नहीं होता, यह सीमा पर या क्षेत्र के भीतर भी हो सकता है। NLP में स्थानीय इष्टतम मौजूद हो सकते हैं जो वैश्विक इष्टतम नहीं होते।
• समाधान की जटिलता: NLP समस्याएँ सामान्यतः LP समस्याओं की तुलना में काफ़ी अधिक जटिल होती हैं। सभी NLP समस्याओं के लिए simplex विधि के समान कोई एकल सार्वभौमिक एल्गोरिदम उपलब्ध नहीं है।

NLP की प्रमुख कठिनाइयाँ और चुनौतियाँ

अरेखीय प्रोग्रामिंग समस्याओं के समाधान में कई कठिनाइयाँ होती हैं:

• स्थानीय चरम बिंदुओं की उपस्थिति: अधिकांश NLP विधियाँ केवल स्थानीय इष्टतम (एक निश्चित पड़ोस में सर्वोत्तम समाधान) खोजने की गारंटी देती हैं। वैश्विक इष्टतम (पूरे स्वीकार्य क्षेत्र में सर्वोत्तम समाधान) खोजना एक जटिल कार्य है, विशेषकर अनुत्तल समस्याओं के लिए।
• अनुत्तलता: यदि समस्या उत्तल नहीं है (उद्देश्य फ़ंक्शन या स्वीकार्य क्षेत्र अनुत्तल है), तो अनेक स्थानीय इष्टतम हो सकते हैं और मानक gradient विधियाँ उनमें से किसी एक में "अटक" सकती हैं।
• परिकलनात्मक जटिलता: NLP समाधान एल्गोरिदम को LP की तुलना में प्रायः काफ़ी अधिक परिकलन संसाधनों की आवश्यकता होती है।

NLP समस्याओं के महत्त्वपूर्ण वर्ग

सामान्य जटिलता के बावजूद, NLP समस्याओं के ऐसे महत्त्वपूर्ण उपवर्ग हैं जिनके लिए प्रभावी समाधान विधियाँ विकसित की गई हैं:

• उत्तल प्रोग्रामिंग: उत्तल स्वीकार्य समाधान समुच्चय पर उत्तल फ़ंक्शन के न्यूनीकरण (या अवतल फ़ंक्शन के अधिकतमीकरण) की समस्या। मुख्य गुण: कोई भी स्थानीय न्यूनतम वैश्विक न्यूनतम भी होता है। यह इष्टतम समाधान की खोज को काफ़ी सरल बनाता है।
• द्विघाती प्रोग्रामिंग: उद्देश्य फ़ंक्शन द्विघाती है और सभी प्रतिबंध रेखीय हैं।
• पृथक्करणीय प्रोग्रामिंग: उद्देश्य फ़ंक्शन और प्रतिबंधों को ऐसे फ़ंक्शनों के योग के रूप में प्रदर्शित किया जा सकता है जिनमें से प्रत्येक केवल एक चर पर निर्भर करता है।

NLP समस्याओं के समाधान की विधियाँ

अरेखीय प्रोग्रामिंग (NLP) समस्याओं के समाधान की विधियाँ

I. बिना प्रतिबंध के अनुकूलन की विधियाँ (unconstrained optimization):

• Gradient विधियाँ (steepest descent विधि, conjugate gradient विधि);
• Newton की विधि और quasi-Newton विधियाँ (उदाहरण के लिए, BFGS);
• Hessian approximation का उपयोग करने वाली विधियाँ।

II. प्रतिबंध-सहित अनुकूलन की विधियाँ (constrained optimization):

• रूपांतरण विधियाँ:
  • दंड फ़ंक्शन की विधि (penalty methods);
  • बाधा फ़ंक्शन की विधि (barrier methods)।
• दिशा-प्रत्यक्ष खोज विधियाँ:
  • संभाव्य दिशाओं की विधि।
• इष्टतमता शर्तों पर आधारित विधियाँ:
  • Karush-Kuhn-Tucker विधियाँ (KKT-शर्तें);
  • Lagrange गुणक विधि।
• पुनरावृत्ति विधियाँ:
  • अनुक्रमिक द्विघाती प्रोग्रामिंग (SQP);
  • आंतरिक बिंदु विधियाँ।

III. वैश्विक अनुकूलन की विधियाँ:

• Heuristic और meta-heuristic विधियाँ:
  • Genetic algorithms;
  • Simulated annealing;
  • Tabu search।
• निर्धारणवादी विधियाँ:
  • Branch and bound;
  • विशेष संरचना वाली समस्याओं के लिए वैश्विक अनुकूलन एल्गोरिदम।

साहित्य

• बज़ारा एम., शेट्टी के. अरेखीय प्रोग्रामिंग। सिद्धांत और एल्गोरिदम। — मॉस्को: मीर, 1982।
• फ़ियाको ए., मैककॉर्मिक जी. अरेखीय प्रोग्रामिंग। अनुक्रमिक बिना-प्रतिबंध न्यूनीकरण की विधियाँ। — मॉस्को: मीर, 1972।
• हिमेलब्लाउ डी. अनुप्रयुक्त अरेखीय प्रोग्रामिंग। — मॉस्को: मीर, 1975।
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

यह भी देखें

• संक्रिया अनुसंधान
• अनुकूलन
• रेखीय प्रोग्रामिंग
• उत्तल प्रोग्रामिंग
• उद्देश्य फ़ंक्शन
• प्रतिबंध
• स्वीकार्य समाधान क्षेत्र