🥇SciPy, अटींसह ऑप्टिमायझेशन

SciPy (उच्चारित sai pie) हे एक numpy-आधारित गणित पॅकेज आहे ज्यामध्ये C आणि Fortran लायब्ररी देखील समाविष्ट आहेत. SciPy तुमचे संवादात्मक पायथन सत्र MATLAB, IDL, Octave, R किंवा SciLab सारख्या संपूर्ण डेटा विज्ञान वातावरणात बदलते.

या लेखात, आम्ही गणितीय प्रोग्रामिंगची मूलभूत तंत्रे पाहू - scipy.optimize पॅकेज वापरून अनेक व्हेरिएबल्सच्या स्केलर फंक्शनसाठी सशर्त ऑप्टिमायझेशन समस्या सोडवणे. अनियंत्रित ऑप्टिमायझेशन अल्गोरिदमची आधीच चर्चा केली गेली आहे शेवटचा लेख. हेल्प() कमांड, शिफ्ट+टॅब किंवा इन वापरून स्किपी फंक्शन्सवर अधिक तपशीलवार आणि अद्ययावत मदत नेहमी मिळवता येते. अधिकृत दस्तऐवजीकरण.

परिचय

scipy.optimize पॅकेजमधील सशर्त आणि अनियंत्रित ऑप्टिमायझेशन समस्या सोडवण्यासाठी एक सामान्य इंटरफेस फंक्शनद्वारे प्रदान केला जातो. minimize(). तथापि, हे ज्ञात आहे की सर्व समस्यांचे निराकरण करण्यासाठी कोणतीही सार्वत्रिक पद्धत नाही, म्हणून पुरेशी पद्धत निवडणे, नेहमीप्रमाणे, संशोधकाच्या खांद्यावर येते.
फंक्शन आर्ग्युमेंट वापरून योग्य ऑप्टिमायझेशन अल्गोरिदम निर्दिष्ट केला आहे minimize(..., method="").
अनेक व्हेरिएबल्सच्या फंक्शनच्या सशर्त ऑप्टिमायझेशनसाठी, खालील पद्धतींची अंमलबजावणी उपलब्ध आहे:

trust-constr — आत्मविश्वास क्षेत्रामध्ये स्थानिक किमान शोधा. विकी लेख, Habré वर लेख;
SLSQP — मर्यादांसह अनुक्रमिक चतुर्भुज प्रोग्रामिंग, लॅग्रेंज प्रणाली सोडवण्यासाठी न्यूटोनियन पद्धत. विकी लेख.
TNC - ट्रंकेटेड न्यूटन प्रतिबंधित, पुनरावृत्तीची मर्यादित संख्या, मोठ्या संख्येने स्वतंत्र व्हेरिएबल्ससह नॉनलाइनर फंक्शन्ससाठी चांगले. विकी लेख.
L-BFGS-B — Broyden–Fletcher–Goldfarb–Shanno टीमची एक पद्धत, हेसियन मॅट्रिक्समधून वेक्टर्सच्या आंशिक लोडिंगमुळे कमी मेमरी वापरासह लागू केली गेली. विकी लेख, Habré वर लेख.
COBYLA — रेखीय अंदाजानुसार MARE प्रतिबंधित ऑप्टिमायझेशन, रेखीय अंदाजे (ग्रेडियंट गणनाशिवाय) मर्यादित ऑप्टिमायझेशन. विकी लेख.

निवडलेल्या पद्धतीनुसार, समस्या सोडवण्यासाठी अटी आणि निर्बंध वेगळ्या पद्धतीने सेट केले आहेत:

वर्ग ऑब्जेक्ट Bounds L-BFGS-B, TNC, SLSQP, ट्रस्ट-कन्स्ट्र या पद्धतींसाठी;
यादी (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) शब्दकोषाच्या स्वरूपात निर्दिष्ट केलेल्या निर्बंधांसह किमान वर्ग पद्धती (पद्धत = "SLSQP") वापरून अनुक्रमिक प्रोग्रामिंगचा विचार करा {'type', 'fun', 'jac', 'args'};
3) वेब स्टुडिओचे उदाहरण वापरून उत्पादित उत्पादनांच्या ऑप्टिमायझेशनच्या उदाहरणाचे विश्लेषण करा.

सशर्त ऑप्टिमायझेशन पद्धत="trust-constr"

पद्धतीची अंमलबजावणी trust-constr आधारीत EQSQP समानतेच्या स्वरूपातील अडचणी आणि चालू असलेल्या समस्यांसाठी ट्रिप असमानतेच्या स्वरुपातील अडचणींसह समस्यांसाठी. आत्मविश्वास क्षेत्रामध्ये स्थानिक किमान शोधण्यासाठी अल्गोरिदमद्वारे दोन्ही पद्धती लागू केल्या जातात आणि मोठ्या प्रमाणात समस्यांसाठी योग्य आहेत.

सामान्य स्वरूपात किमान शोधण्याच्या समस्येचे गणितीय सूत्रीकरण:

कठोर समानता मर्यादांसाठी, खालची सीमा वरच्या बाउंडच्या बरोबरीने सेट केली जाते .
एकेरी मर्यादांसाठी, वरची किंवा खालची मर्यादा सेट केली आहे np.inf संबंधित चिन्हासह.
दोन व्हेरिएबल्सचे किमान ज्ञात रोसेनब्रॉक फंक्शन शोधणे आवश्यक आहे:

या प्रकरणात, त्याच्या परिभाषाच्या डोमेनवर खालील निर्बंध सेट केले आहेत:

आमच्या बाबतीत, बिंदूवर एक अद्वितीय उपाय आहे , ज्यासाठी फक्त पहिले आणि चौथे निर्बंध वैध आहेत.
चला खालपासून वरपर्यंतच्या निर्बंधांचा अभ्यास करूया आणि आपण ते स्किपमध्ये कसे लिहू शकतो ते पाहू या.
निर्बंध и Bounds ऑब्जेक्ट वापरून ते परिभाषित करू.

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

मर्यादांसाठी जेकोबियन मॅट्रिक्स देखील मर्यादित फरक वापरून मोजले जाऊ शकते. तथापि, या प्रकरणात हेसियन मॅट्रिक्स मर्यादित फरक वापरून मोजले जाऊ शकत नाही. 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]

आवश्यक असल्यास, हेसियनची गणना करण्याचे कार्य 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 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]

ही त्रुटी नाही; जास्तीत जास्त शोधताना, वस्तुनिष्ठ कार्य विरुद्ध चिन्हासह कमी केले जाते.

पुढील पायरी म्हणजे आमच्या कर्मचार्‍यांना जास्त काम करण्यापासून प्रतिबंधित करणे आणि कामाच्या तासांवर निर्बंध आणणे:

समतुल्य काय आहे:

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 पूर्णपणे शैक्षणिक हेतूंसाठी, म्हणूनच दिलेले उदाहरण अशा कॉमिक स्वरूपाचे आहे.

बरेच सिद्धांत आणि आभासी उदाहरणे आढळू शकतात, उदाहरणार्थ, I.L. Akulich च्या पुस्तकात "उदाहरणे आणि समस्यांमध्ये गणितीय प्रोग्रामिंग." अधिक हार्डकोर अनुप्रयोग scipy.optimize प्रतिमांच्या संचामधून 3D रचना तयार करण्यासाठी (Habré वर लेख) मध्ये पाहता येईल मसालेदार-कुकबुक.

माहितीचा मुख्य स्त्रोत आहे docs.scipy.orgया आणि इतर विभागांच्या अनुवादात योगदान देऊ इच्छिणारे scipy आपले स्वागत आहे GitHub.

Спасибо मेफिस्टोफीस प्रकाशनाच्या तयारीत सहभागी होण्यासाठी.

स्त्रोत: www.habr.com

SciPy, अटींसह ऑप्टिमायझेशन

परिचय

सशर्त ऑप्टिमायझेशन पद्धत="trust-constr"

सशर्त ऑप्टिमायझेशन पद्धत="SLSQP"

ऑप्टिमायझेशन उदाहरण

निष्कर्ष

एक टिप्पणी जोडा Отменить ответ