SciPy, शर्तों के साथ अनुकूलन

SciPy (स्पष्ट साई पाई) एक संख्यात्मक आधारित गणित पैकेज है जिसमें C और फोरट्रान लाइब्रेरी भी शामिल हैं। SciPy के साथ, एक इंटरैक्टिव पायथन सत्र MATLAB, IDL, ऑक्टेव, R, या SciLab जैसे संपूर्ण डेटा प्रोसेसिंग वातावरण में बदल जाता है।

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

परिचय

Scipy.optimize पैकेज में सशर्त और बिना शर्त अनुकूलन कार्यों को हल करने के लिए सामान्य इंटरफ़ेस minimize() फ़ंक्शन द्वारा प्रदान किया गया है। हालांकि, यह ज्ञात है कि सभी समस्याओं को हल करने के लिए एक सार्वभौमिक तरीका मौजूद नहीं है, इसलिए, हमेशा की तरह, एक पर्याप्त विधि का विकल्प शोधकर्ता के साथ रहता है।

एक उपयुक्त ऑप्टिमाइज़ेशन एल्गोरिथ्म तर्क को minimize(..., method="") से minimize(..., method="") फ़ंक्शन का उपयोग करके निर्दिष्ट किया गया है।

कई चर के कार्य के सशर्त अनुकूलन के लिए, निम्नलिखित विधियाँ उपलब्ध हैं:

• trust-constr - विश्वास क्षेत्र में एक स्थानीय न्यूनतम के लिए खोज। विकी लेख ; हबर लेख ;
• SLSQP - बाधाओं के साथ अनुक्रमिक द्विघात प्रोग्रामिंग, लैगरेंज प्रणाली को हल करने का न्यूटोनियन तरीका। विकी लेख ।
• TNC - सीमित न्यूटन विवश, पुनरावृत्तियों की एक सीमित संख्या, बड़ी संख्या में स्वतंत्र चर के साथ गैर-रेखीय कार्यों के लिए अच्छा है। विकी लेख ।
• L-BFGS-B - चार ब्रायडेन से एक विधि - फ्लेचर - गोल्डफर्ब - शन्नो, हेसियन मैट्रिक्स से वैक्टर के आंशिक लोडिंग के कारण कम मेमोरी खपत के साथ लागू किया गया है। विकी लेख, हैबर लेख ।
• COBYLA - MARE रैखिक अनुमोदन द्वारा विवश अनुकूलन, रैखिक सन्निकटन के साथ सीमित अनुकूलन (ढाल गणना के बिना)। विकी लेख ।

चुनी हुई विधि के आधार पर, समस्या को हल करने के लिए शर्तों और प्रतिबंधों को अलग तरीके से निर्धारित किया जाता है:

• एल-बीएफजीएस-बी, टीएनसी, एसएलएसक्यूपी, ट्रस्ट-कॉस्टर के तरीकों के लिए Bounds वर्ग की एक वस्तु;
• समान विधियों के लिए सूची (min, max) L-BFGS-B, TNC, SLSQP, विश्वास-प्रतिबंध;
• ऑब्जेक्ट्स या ऑब्जेक्ट की सूची LinearConstraint , NonlinearConstraint तरीकों के लिए COBYLA, SLSQP, ट्रस्ट-कॉस्टर;
• शब्दकोश या शब्दकोष सूची {'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt} कॉल करने योग्य, 'जेक {'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt} कॉल करने {'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt} COBYLA, SLSQP विधियों के लिए।

लेख की रूपरेखा:
1) विश्वास क्षेत्र में सशर्त अनुकूलन एल्गोरिथ्म के आवेदन पर विचार करें (विधि = "विश्वास-बाधा") Bounds के रूप में निर्दिष्ट प्रतिबंधों के साथ, LinearConstraint , NonlinearConstraint ऑब्जेक्ट;
2) एक शब्दकोश {'type', 'fun', 'jac', 'args'} के रूप में निर्दिष्ट बाधाओं के साथ अनुक्रमिक कम से कम प्रोग्रामिंग (विधि = "SLSQP") पर विचार करें;
3) वेब स्टूडियो के उदाहरण पर उत्पादों के अनुकूलन के उदाहरण को इकट्ठा करना।

सशर्त अनुकूलन विधि = "विश्वास-बाधा"

trust-constr कास्ट trust-constr कार्यान्वयन समानता के रूप की बाधाओं के साथ और असमानताओं के रूप में बाधाओं के साथ समस्याओं के लिए TRIP पर समस्याओं के लिए EQSQP पर आधारित है। दोनों तरीकों को विश्वास क्षेत्र में एक स्थानीय न्यूनतम खोजने के लिए एल्गोरिदम द्वारा लागू किया जाता है और बड़े पैमाने पर कार्यों के लिए अच्छी तरह से अनुकूल है।

सामान्य रूप में न्यूनतम खोज समस्या का गणितीय सूत्रीकरण:

$$

$$\ min_x f (x)$$

$$

$$c ^ l \ leq c (x) \ leq c ^ u,$$

$$

$$x ^ l \ leq x \ leq x ^ u$$

सख्त समानता बाधाओं के लिए, निचली सीमा ऊपरी के बराबर सेट होती है $$$c ^ l_j = c ^ u_j$ ।
एक-तरफ़ा प्रतिबंध के लिए, np.inf द्वारा संबंधित चिह्न के साथ एक ऊपरी या निचली सीमा निर्धारित की जाती है।
चलो दो चरों के ज्ञात रोसेनब्रोक फ़ंक्शन का न्यूनतम पता लगाना आवश्यक है:

$$

$$\ min_ {x_0, x_1} 100 (x_0 - x_1 ^ 2) ^ 2 + (1-x_0) ^ 2$$

इस मामले में, निम्नलिखित प्रतिबंध परिभाषा के अपने डोमेन पर सेट किए गए हैं:

$$

$$x_0 ^ 2 + x_1 \ leq 1$$

$$

$$x_0 ^ 2 - x_1 \ leq 1$$

$$

$$2x_0 + x_1 = 1$$

$$

$$x_0 + 2x_1 \ leq 1$$

$$

$$0 \ leq x_0 \ leq 1$$

$$

$$-0.5 \ leq x_1 \ leq 2.0$$

हमारे मामले में, बिंदु पर एक अनूठा समाधान है $$$[x_0, x_1] = [0.4149, 0.1701]$ जिसके लिए केवल पहले और चौथे प्रतिबंध मान्य हैं।
चलो नीचे से प्रतिबंधों के माध्यम से चलते हैं और विचार करते हैं कि कैसे उन्हें डरपोक में लिखा जा सकता है।
प्रतिबंध $$$0 \ leq x_0 \ leq 1$ और $$$-0.5 \ leq x_1 \ leq 2.0$ सीमा वस्तु का उपयोग कर परिभाषित किया गया।

 from scipy.optimize import Bounds bounds = Bounds ([0, -0.5], [1.0, 2.0]) 

प्रतिबंध $$$x_0 + 2 x_1 \ leq 1$ और $$$2 x_0 + x_1 = 1$ हम रैखिक रूप में लिखते हैं:

$$

$$\ start {bmatrix} - \ infty \\ 1 \ end {bmatrix} \ leq \ start {bmatrix} 1 & 2 \\ 2 & 1 \ end {bmatrix} \ start {bmatrix} x__ \\ x_1 \ end {bmatrix } \ leq \ start {bmatrix} 1 \\ 1 \ end {bmatrix}$$

इन अड़चनों को एक रेखाकृति के रूप में परिभाषित करें:

 import numpy as np from scipy.optimize import LinearConstraint linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1]) 

और अंत में, मैट्रिक्स रूप में एक अरेखीय बाधा:

$$

$$c (x) = \ start {bmatrix} x_0 ^ 2 + x_1 \\ x_0 ^ 2 - x_1 \ end {bmatrix} \ leq \ start {bmatrix} 1 \\ 1 \ अंत {brixrix}$$

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

$$

$$J (x) = \ start {bmatrix} 2x_0 & 1 \\ 2x_0 & -1 \ end {bmatrix}$$

$$

$$H (x, v) = \ sum \ limit_ {i = 0} ^ 1 v_i \ nabla ^ 2 c_i (x) = v_0 \ start {bmatrix} 2 और 0 \\ 2 & 0 \ अंत / bmatrix} + v_1 \ शुरू {bmatrix} 2 और 0 \\ 2 और 0 \ अंत {bmatrix}$$

अब हम नॉनलाइनर कंट्रास्ट को NonlinearConstraint ऑब्जेक्ट के रूप में परिभाषित कर सकते हैं:

 from scipy.optimize import NonlinearConstraint def cons_f(x): return [x[0]**2 + x[1], x[0]**2 - x[1]] def cons_J(x): return [[2*x[0], 1], [2*x[0], -1]] def cons_H(x, v): return v[0]*np.array([[2, 0], [0, 0]]) + v[1]*np.array([[2, 0], [0, 0]]) nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=cons_H) 

यदि आकार बड़ा है, तो विरल को विरल रूप में भी निर्दिष्ट किया जा सकता है:

 from scipy.sparse import csc_matrix def cons_H_sparse(x, v): return v[0]*csc_matrix([[2, 0], [0, 0]]) + v[1]*csc_matrix([[2, 0], [0, 0]]) nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=cons_H_sparse) 

या LinearOperator वस्तु के रूप में:

 from scipy.sparse.linalg import LinearOperator def cons_H_linear_operator(x, v): def matvec(p): return np.array([p[0]*2*(v[0]+v[1]), 0]) return LinearOperator((2, 2), matvec=matvec) nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=cons_H_linear_operator) 

जब हेसियन मैट्रिक्स की गणना $$$H (x, v)$ महंगा, आप HessianUpdateStrategy वर्ग का उपयोग कर सकते हैं। निम्नलिखित रणनीतियाँ उपलब्ध हैं: BFGS और BFGS ।

 from scipy.optimize import BFGS nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS()) 

हेसियन को परिमित अंतर का उपयोग करके भी गणना की जा सकती है:

 nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point') 

बाधाओं के लिए जैकोबी मैट्रिक्स को परिमित अंतर का उपयोग करके भी गणना की जा सकती है। हालाँकि, इस मामले में, हेसियन मैट्रिक्स की गणना परिमित अंतर का उपयोग करके नहीं की जा सकती है। Hessian को एक फ़ंक्शन के रूप में या HessianUpdateStrategy वर्ग का उपयोग करके परिभाषित किया जाना चाहिए।

 nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ()) 

अनुकूलन समस्या का समाधान इस प्रकार है:

 from scipy.optimize import minimize from scipy.optimize import rosen, rosen_der, rosen_hess, rosen_hess_prod x0 = np.array([0.5, 0]) res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hess=rosen_hess, constraints=[linear_constraint, nonlinear_constraint], options={'verbose': 1}, bounds=bounds) print(res.x) 

 `gtol` termination condition is satisfied. Number of iterations: 12, function evaluations: 8, CG iterations: 7, optimality: 2.99e-09, constraint violation: 1.11e-16, execution time: 0.033 s. [0.41494531 0.17010937] 

यदि आवश्यक हो, तो हेसियन गणना फ़ंक्शन को लिनियरऑपरेटर वर्ग का उपयोग करके परिभाषित किया जा सकता है

 def rosen_hess_linop(x): def matvec(p): return rosen_hess_prod(x, p) return LinearOperator((2, 2), matvec=matvec) res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hess=rosen_hess_linop, constraints=[linear_constraint, nonlinear_constraint], options={'verbose': 1}, bounds=bounds) print(res.x) 

या हेसियन के उत्पाद और hessp पैरामीटर के माध्यम से एक मनमाना वेक्टर:

 res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hessp=rosen_hess_prod, constraints=[linear_constraint, nonlinear_constraint], options={'verbose': 1}, bounds=bounds) print(res.x) 

वैकल्पिक रूप से, अनुकूलित फ़ंक्शन के पहले और दूसरे डेरिवेटिव की गणना लगभग की जा सकती है। उदाहरण के लिए, हेसियन को SR1 फ़ंक्शन (अर्ध-न्यूटोनियन सन्निकटन) का उपयोग करके अनुमानित किया जा सकता है। ढाल को बारीक अंतर द्वारा अनुमानित किया जा सकता है।

 from scipy.optimize import SR1 res = minimize(rosen, x0, method='trust-constr', jac="2-point", hess=SR1(), constraints=[linear_constraint, nonlinear_constraint], options={'verbose': 1}, bounds=bounds) print(res.x) 

सशर्त अनुकूलन विधि = "SLSQP"

SLSQP विधि को फ़ंक्शन को न्यूनतम करने की समस्या को हल करने के लिए डिज़ाइन किया गया है:

$$

$$\ min_x f (x)$$

$$

$$c_j (x) = 0, j \ in \ mathcal {E}$$

$$

$$c_j (x) \ geq 0, j \ in \ mathcal {I}$$

$$

$$lb_i \ leq x_i \ leq ub_i, i = 1, ..., N$$

जहाँ $$$\ mathcal {E}$ और $$$\ mathcal {I}$ - अभिव्यक्ति सूचकांकों के सेट समानता या असमानताओं के रूप में बाधाओं का वर्णन करते हैं। $$$[lb_i, ub_i]$ - फंक्शन डेफिनिशन डोमेन के लिए निचले और ऊपरी सीमा के सेट।

रैखिक और nonlinear बाधाओं कुंजी type , fun और jac साथ शब्दकोशों के रूप में वर्णित हैं।

 ineq_cons = {'type': 'ineq', 'fun': lambda x: np.array ([1 - x [0] - 2 * x [1], 1 - x [0] ** 2 - x [1], 1 - x [0] ** 2 + x [1]]), 'jac': lambda x: np.array ([[- 1.0, -2.0], [-2 * x [0], -1.0], [-2 * x [0], 1.0]]) } eq_cons = {'type': 'eq', 'fun': lambda x: np.array ([2 * x [0] + x [1] - 1]), 'jac': lambda x: np.array ([2.0, 1.0]) } 

न्यूनतम खोज निम्न प्रकार से की जाती है:

 x0 = np.array([0.5, 0]) res = minimize(rosen, x0, method='SLSQP', jac=rosen_der, constraints=[eq_cons, ineq_cons], options={'ftol': 1e-9, 'disp': True}, bounds=bounds) print(res.x) 

 Optimization terminated successfully. (Exit mode 0) Current function value: 0.34271757499419825 Iterations: 4 Function evaluations: 5 Gradient evaluations: 4 [0.41494475 0.1701105 ] 

अनुकूलन का उदाहरण

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

• x0 - जमीन की बिक्री, 10 tr से
• X1 - कॉर्पोरेट साइट्स, 20 tr से
• x2 - ऑनलाइन स्टोर, 30 tr से

हमारी मित्रवत कार्य टीम में चार जून, दो मध्य और एक वरिष्ठ शामिल हैं। एक महीने के लिए उनके काम का समय:

• जून: 4 * 150 = 600 * ,
• मिडल: 2 * 150 = 300 * ,
• सीनियर: 150 *

मान लीजिए कि एक प्रकार की साइट (x0, X1, x2) को विकसित करने और तैनात करने पर खर्च करने वाले पहले जूनियर को (10, 20, 30) घंटे, मध्य - (7, 15, 20), वरिष्ठ - (5, 10, 15, सर्वश्रेष्ठ) घंटे खर्च करने चाहिए। उनके जीवन का समय।

किसी भी सामान्य निर्देशक की तरह, हम अपने मासिक लाभ को अधिकतम करना चाहते हैं। सफलता के लिए पहला कदम मासिक उत्पादन से आय के योग के रूप में उद्देश्य समारोह value लिखना है:

 def value(x): return - 10*x[0] - 20*x[1] - 30*x[2] 

यह कोई गलती नहीं है; जब अधिकतम की खोज की जाती है, तो उद्देश्य फ़ंक्शन विपरीत संकेत के साथ कम से कम होता है।

अगला कदम हमारे कर्मचारियों पर प्रसंस्करण को प्रतिबंधित करना और कार्य समय निधि पर प्रतिबंध लागू करना है:

$$

$$\ start {bmatrix} 10 & 20 & 30 \\ 7 & 15 & 20 \\ 5 & 10 & 15 \ end {bmatrix} \ start {bmatrix} x_0 \\ x_1 \\ x_2 \ end {bamrix} \ leq \ {bmatrix} 600 \\ 300 \\ 150 \ end {bmatrix} $ शुरू करे$$

जो समतुल्य है:

$$

$$\ start {bmatrix} 600 \\ 300 \\ 150 \ end {bmatrix} - \ start {bmatrix} 10 & 20 & 30 \\ 7 & 15 & 20 \\ 5 & 10 & 15 \ end {bmatrix} शुरू {bmatrix} x_0 \\ x_1 \\ x_2 \ end {bmatrix} \ geq 0$$

 ineq_cons = {'type': 'ineq', 'fun': lambda x: np.array ([600 - 10 * x [0] - 20 * x [1] - 30 * x[2], 300 - 7 * x [0] - 15 * x [1] - 20 * x[2], 150 - 5 * x [0] - 10 * x [1] - 15 * x[2]]) } 

औपचारिक प्रतिबंध - उत्पादन केवल सकारात्मक होना चाहिए:

 bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf]) 

और अंत में, सबसे आशावादी धारणा - कम कीमत और उच्च गुणवत्ता के कारण, संतुष्ट ग्राहकों की एक पंक्ति हमारे लिए लगातार अस्तर है। हम scipy.optimize साथ सशर्त अनुकूलन की समस्या के समाधान के आधार पर, स्वयं मासिक उत्पादन वॉल्यूम चुन सकते हैं:

 x0 = np.array([10, 10, 10]) res = minimize(value, x0, method='SLSQP', constraints=ineq_cons, bounds=bnds) print(res.x) 

 [7.85714286 5.71428571 3.57142857] 

हम लॉलीपॉप को निकटतम पूर्णांक तक गोल करते हैं और उत्पादन x = (8, 6, 3) इष्टतम वितरण के साथ रोवर्स के मासिक भार की गणना करते हैं:

• जून: 8 * 10 + 6 * 20 + 3 * 30 = 290 * ;
• middles: 8 * 7 + 6 * 15 + 3 * 20 = 206 * ;
• वरिष्ठ: 8 * 5 + 6 * 10 + 3 * 15 = 145 * ।

निष्कर्ष: निर्देशक को उसकी अच्छी-खासी योग्यता प्राप्त करने के लिए, यह 8 लैंडिंग, 6 मध्यम साइट और 3 स्टोर प्रति माह बनाने के लिए इष्टतम है। इसी समय, मशीन से अलग होने के बिना सीग्नॉरिटी को हल करना चाहिए, मध्य का भार जून के आधे से कम लगभग 2/3 है।

निष्कर्ष

लेख scipy.optimize पैकेज के साथ काम करने के लिए बुनियादी तकनीकों की रूपरेखा तैयार करता है जो scipy.optimize समस्याओं को हल करने के लिए उपयोग किए जाते हैं। व्यक्तिगत रूप से, मैं अकादमिक उद्देश्यों के लिए पूरी तरह से scipy उपयोग करता हूं, इसलिए यह उदाहरण बहुत हास्यपूर्ण है।

उदाहरण के लिए I L. Akulich की पुस्तक "उदाहरणों और समस्याओं में गणितीय प्रोग्रामिंग" पर बहुत सारे सिद्धांत और वाइनर उदाहरण पाए जा सकते हैं। छवियों का एक सेट ( हब पर एक लेख ) के लिए एक 3D संरचना बनाने के लिए scipy.optimize का एक और अधिक कट्टर आवेदन, scipy.optimize रसोई की किताब में पाया जा सकता है।

जानकारी का मुख्य स्रोत docs.scipy.org है। यदि आप अनुवाद में इस और scipy अन्य अनुभागों का अनुवाद करना चाहते हैं, तो GitHub में आपका स्वागत है ।

इस प्रकाशन में योगदान के लिए mephistopheies का धन्यवाद।