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

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

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

परिचय

scipy.optimize पैकेज में सशर्त और अप्रतिबंधित दोनों अनुकूलन समस्याओं को हल करने के लिए एक सामान्य इंटरफ़ेस फ़ंक्शन द्वारा प्रदान किया गया है minimize(). हालाँकि, यह ज्ञात है कि सभी समस्याओं को हल करने के लिए कोई सार्वभौमिक तरीका नहीं है, इसलिए एक पर्याप्त विधि का चुनाव, हमेशा की तरह, शोधकर्ता के कंधों पर आता है।
फ़ंक्शन तर्क का उपयोग करके उपयुक्त अनुकूलन एल्गोरिदम निर्दिष्ट किया गया है minimize(..., method="").
कई चर वाले फ़ंक्शन के सशर्त अनुकूलन के लिए, निम्नलिखित विधियों का कार्यान्वयन उपलब्ध है:

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

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

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

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

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

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

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

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

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

हमारे मामले में, इस बिंदु पर एक अनूठा समाधान है , जिसके लिए केवल पहला और चौथा प्रतिबंध ही मान्य है।
आइए नीचे से ऊपर तक प्रतिबंधों को देखें और देखें कि हम उन्हें scipy में कैसे लिख सकते हैं।
सीमाएं и आइए इसे बाउंड्स ऑब्जेक्ट का उपयोग करके परिभाषित करें।

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

सीमाएं и आइए इसे रैखिक रूप में लिखें:

आइए इन बाधाओं को LinearConstraint ऑब्जेक्ट के रूप में परिभाषित करें:

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

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

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

अब हम एक अरैखिक बाधा को एक वस्तु के रूप में परिभाषित कर सकते हैं 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)

हेस्सियन मैट्रिक्स की गणना करते समय बहुत अधिक प्रयास की आवश्यकता है, आप कक्षा का उपयोग कर सकते हैं HessianUpdateStrategy. निम्नलिखित रणनीतियाँ उपलब्ध हैं: BFGS и SR1.

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')

बाधाओं के लिए जैकोबियन मैट्रिक्स की गणना परिमित अंतरों का उपयोग करके भी की जा सकती है। हालाँकि, इस मामले में हेसियन मैट्रिक्स की गणना परिमित अंतरों का उपयोग करके नहीं की जा सकती है। हेसियन को एक फ़ंक्शन के रूप में या 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]

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

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 विधि को किसी फ़ंक्शन को निम्न रूप में छोटा करने की समस्याओं को हल करने के लिए डिज़ाइन किया गया है:

जहाँ и - समानता या असमानताओं के रूप में प्रतिबंधों का वर्णन करने वाले अभिव्यक्तियों के सूचकांकों का सेट। - फ़ंक्शन की परिभाषा के क्षेत्र के लिए निचली और ऊपरी सीमाओं के सेट।

रैखिक और अरेखीय बाधाओं को कुंजियों वाले शब्दकोशों के रूप में वर्णित किया गया है 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 ट्र से।

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

जून: 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]

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

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

समतुल्य क्या है:

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 чел * час;
मध्य: 8 * 7 + 6 * 15 + 3 * 20 = 206 чел * час;
वरिष्ठ: 8 * 5 + 6 * 10 + 3 * 15 = 145 чел * час.

निष्कर्ष: निर्देशक को अपना सुयोग्य अधिकतम प्राप्त करने के लिए, प्रति माह 8 लैंडिंग पृष्ठ, 6 मध्यम आकार की साइटें और 3 स्टोर बनाना इष्टतम है। इस मामले में, वरिष्ठ को मशीन से ऊपर देखे बिना जुताई करनी चाहिए, मध्य का भार लगभग 2/3 होगा, कनिष्ठों का भार आधे से भी कम होगा।

निष्कर्ष

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

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

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

धन्यवाद mephistophees प्रकाशन की तैयारी में भागीदारी के लिए.

स्रोत: www.habr.com

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

परिचय

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

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

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

निष्कर्ष

एक टिप्पणी जोड़ें उत्तर रद्द