SciPy (tələffüz sai pie) C və Fortran kitabxanalarını da özündə cəmləşdirən bir sıra əsaslı riyaziyyat paketidir. SciPy interaktiv Python sessiyanızı MATLAB, IDL, Octave, R və ya SciLab kimi tam məlumat elmi mühitinə çevirir.
Bu yazıda biz riyazi proqramlaşdırmanın əsas texnikalarına - scipy.optimize paketindən istifadə etməklə bir neçə dəyişənin skalyar funksiyası üçün şərti optimallaşdırma məsələlərinin həllinə baxacağıq. Məhdudiyyətsiz optimallaşdırma alqoritmləri artıq müzakirə edilmişdir . Scipy funksiyaları ilə bağlı daha ətraflı və ən son yardımı həmişə help() əmri, Shift+Tab və ya .
Giriş
Scipy.optimize paketində həm şərti, həm də qeyri-məhdud optimallaşdırma problemlərinin həlli üçün ümumi interfeys funksiya tərəfindən təmin edilir. minimize(). Lakin məlumdur ki, bütün problemlərin həlli üçün universal üsul yoxdur, ona görə də adekvat metodun seçimi həmişə olduğu kimi tədqiqatçının çiyninə düşür.
Müvafiq optimallaşdırma alqoritmi funksiya arqumentindən istifadə etməklə müəyyən edilir minimize(..., method="").
Bir neçə dəyişənli funksiyanın şərti optimallaşdırılması üçün aşağıdakı metodların tətbiqi mövcuddur:
trust-constr— güvən bölgəsində yerli minimumu axtarın. , ;SLSQP— məhdudiyyətlərlə ardıcıl kvadratik proqramlaşdırma, Laqranj sisteminin həlli üçün Nyuton üsulu. .TNC- Kəsilmiş Nyuton Məhdud, məhdud sayda iterasiya, çoxlu sayda müstəqil dəyişənləri olan qeyri-xətti funksiyalar üçün yaxşıdır. .L-BFGS-B— Broyden-Fletcher-Goldfarb-Şanno komandasının metodu, Hessian matrisindən vektorların qismən yüklənməsi səbəbindən azaldılmış yaddaş istehlakı ilə həyata keçirilir. , .COBYLA— Xətti yaxınlaşma ilə MARE Məhdud Optimallaşdırma, xətti yaxınlaşma ilə məhdudlaşdırılmış optimallaşdırma (qradiyentin hesablanması olmadan). .
Seçilmiş metoddan asılı olaraq problemin həlli üçün şərtlər və məhdudiyyətlər fərqli olaraq təyin olunur:
- sinif obyekti
Boundsmetodlar üçün L-BFGS-B, TNC, SLSQP, trust-constr; - siyahı
(min, max)eyni üsullar üçün L-BFGS-B, TNC, SLSQP, trust-constr; - obyekt və ya obyektlərin siyahısı
LinearConstraint,NonlinearConstraintCOBYLA, SLSQP, etibar-konstr metodları üçün; - lüğət və ya lüğətlərin siyahısı
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}COBYLA, SLSQP üsulları üçün.
Məqalənin xülasəsi:
1) Etibar bölgəsində şərti optimallaşdırma alqoritminin istifadəsini nəzərdən keçirin (metod="trust-constr") obyektlər kimi göstərilən məhdudiyyətlərlə Bounds, LinearConstraint, NonlinearConstraint ;
2) Lüğət şəklində göstərilən məhdudiyyətlərlə ən kiçik kvadratlar metodundan (metod = "SLSQP") istifadə edərək ardıcıl proqramlaşdırmanı nəzərdən keçirin {'type', 'fun', 'jac', 'args'};
3) Veb studiya nümunəsindən istifadə edərək istehsal olunan məhsulların optimallaşdırılması nümunəsini təhlil edin.
Şərti optimallaşdırma metodu="trust-constr"
Metodunun həyata keçirilməsi trust-constr əsasən bərabərlik formasının məhdudiyyətləri ilə bağlı problemlər üçün və bərabərsizliklər şəklində məhdudiyyətlərlə bağlı problemlər üçün. Hər iki üsul etibarlılıq bölgəsində yerli minimumu tapmaq üçün alqoritmlərlə həyata keçirilir və genişmiqyaslı problemlər üçün yaxşı uyğun gəlir.
Minimum tapmaq probleminin ümumi formada riyazi formalaşdırılması:
Ciddi bərabərlik məhdudiyyətləri üçün aşağı hədd yuxarı həddə bərabər müəyyən edilir .
Birtərəfli məhdudiyyət üçün yuxarı və ya aşağı hədd təyin edilir np.inf müvafiq işarə ilə.
İki dəyişənin məlum Rosenbrock funksiyasının minimumunu tapmaq lazım olsun:
Bu halda, onun tərif sahəsinə aşağıdakı məhdudiyyətlər qoyulur:
Bizim vəziyyətimizdə nöqtədə unikal bir həll var , bunun üçün yalnız birinci və dördüncü məhdudiyyətlər etibarlıdır.
Aşağıdan yuxarıya doğru məhdudiyyətləri keçək və onları scipy-də necə yaza biləcəyimizə baxaq.
Məhdudiyyətlər и onu Bounds obyektindən istifadə edərək müəyyən edək.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])Məhdudiyyətlər и Onu xətti formada yazaq:
Bu məhdudiyyətləri LinearConstraint obyekti kimi təyin edək:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])Və nəhayət, matris şəklində qeyri-xətti məhdudiyyət:
Bu məhdudiyyət üçün Yakobi matrisini və Hessian matrisinin ixtiyari vektorla xətti kombinasiyasını təyin edirik. :
İndi biz qeyri-xətti məhdudiyyəti obyekt kimi təyin edə bilərik 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)Ölçü böyükdürsə, matrislər seyrək formada da göstərilə bilər:
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)və ya obyekt kimi 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)Hessian matrisini hesablayarkən çox səy tələb edir, bir sinifdən istifadə edə bilərsiniz . Aşağıdakı strategiyalar mövcuddur: BFGS и SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())Hessianı da sonlu fərqlərdən istifadə etməklə hesablamaq olar:
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')Məhdudiyyətlər üçün Yakobi matrisi də sonlu fərqlərdən istifadə etməklə hesablana bilər. Lakin bu halda Hessian matrisini sonlu fərqlərdən istifadə etməklə hesablamaq olmaz. Hessian funksiya kimi və ya HessianUpdateStrategy sinifindən istifadə etməklə müəyyən edilməlidir.
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())Optimallaşdırma probleminin həlli belə görünür:
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]Lazım gələrsə, Hessianın hesablanması funksiyası LinearOperator sinfindən istifadə etməklə müəyyən edilə bilər.
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)və ya Hessian və parametr vasitəsilə ixtiyari vektorun məhsulu 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)Alternativ olaraq optimallaşdırılan funksiyanın birinci və ikinci törəmələri təxminən hesablana bilər. Məsələn, Hessian funksiyasından istifadə edərək təxmini hesablana bilər SR1 (kvazi-Nyuton yaxınlaşması). Qradiyent sonlu fərqlərlə təxmini edilə bilər.
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)Şərti optimallaşdırma metodu = "SLSQP"
SLSQP metodu aşağıdakı formada funksiyanı minimuma endirmək problemlərini həll etmək üçün nəzərdə tutulmuşdur:
Harada? и — bərabərlik və ya bərabərsizlik formasında məhdudiyyətləri təsvir edən ifadələrin indeksləri toplusu. — funksiyanın təyini sahəsi üçün aşağı və yuxarı hədlər çoxluğu.
Xətti və qeyri-xətti məhdudiyyətlər düymələri olan lüğətlər şəklində təsvir edilmişdir 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])
}Minimum axtarış aşağıdakı kimi aparılır:
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 ]Optimallaşdırma nümunəsi
Beşinci texnoloji struktura keçidlə əlaqədar olaraq, bizə kiçik, lakin sabit gəlir gətirən veb-studiya nümunəsindən istifadə edərək istehsalın optimallaşdırılmasına baxaq. Özümüzü üç növ məhsul istehsal edən mətbəxin direktoru kimi təsəvvür edək:
- x0 - açılış səhifələrinin satışı, 10 tr.
- x1 - korporativ saytlar, 20 tr-dən.
- x2 - onlayn mağazalar, 30 tr-dən.
Bizim mehriban işçi komandamız dörd yeniyetmə, iki orta və bir böyükdən ibarətdir. Onların aylıq iş vaxtı fondu:
- İyun:
4 * 150 = 600 чел * час, - ortalar:
2 * 150 = 300 чел * час, - senor:
150 чел * час.
İlk mövcud olan gənc (x0, x1, x2), orta - (10, 20, 30), böyük - (7, 15, 20) tipli bir saytın hazırlanmasına və yerləşdirilməsinə (5, 10, 15) saat sərf etsin. ) həyatınızın ən yaxşı vaxtının saatları.
Hər hansı bir normal direktor kimi biz də aylıq mənfəəti maksimuma çatdırmaq istəyirik. Uğurun ilk addımı məqsəd funksiyasını yazmaqdır value ayda istehsal olunan məhsullardan əldə edilən gəlirin məbləği kimi:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]Bu səhv deyil, maksimumu axtararkən məqsəd funksiyası əks işarə ilə minimuma endirilir.
Növbəti addım işçilərimizin həddindən artıq işləməsini qadağan etmək və iş saatlarına məhdudiyyətlər qoymaqdır:
Ekvivalent nədir:
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]])
}Rəsmi məhdudiyyət ondan ibarətdir ki, məhsul çıxışı yalnız müsbət olmalıdır:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])Və nəhayət, ən çəhrayı fərziyyə odur ki, aşağı qiymətə və yüksək keyfiyyətə görə məmnun müştərilərin növbəsi daim bizim üçün növbəyə durur. Məhdud optimallaşdırma probleminin həllinə əsaslanaraq aylıq istehsal həcmini özümüz seçə bilərik 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]Gəlin tam ədədlərə yuvarlaqlaşdıraq və məhsulların optimal paylanması ilə avarçəkənlərin aylıq yükünü hesablayaq. x = (8, 6, 3) :
- İyun:
8 * 10 + 6 * 20 + 3 * 30 = 290 чел * час; - ortalar:
8 * 7 + 6 * 15 + 3 * 20 = 206 чел * час; - senor:
8 * 5 + 6 * 10 + 3 * 15 = 145 чел * час.
Nəticə: direktorun layiq olduğu maksimumu əldə etməsi üçün ayda 8 açılış səhifəsi, 6 orta ölçülü sayt və 3 mağaza yaratmaq optimaldır. Bu halda, böyüklər maşından yuxarı baxmadan şumlamalıdırlar, ortaların yükü təxminən 2/3, kiçiklər isə yarıdan az olacaq.
Nəticə
Məqalədə paketlə işləmək üçün əsas üsullar təsvir edilmişdir scipy.optimize, şərti minimumlaşdırma məsələlərini həll etmək üçün istifadə olunur. Şəxsən mən istifadə edirəm scipy sırf akademik məqsədlər üçün, ona görə də verilən misal belə komik xarakter daşıyır.
Bir çox nəzəriyyə və virtual nümunələrə, məsələn, İ.L.Akuliçin “Nümunələr və məsələlərdə riyazi proqramlaşdırma” kitabında rast gəlmək olar. Daha sərt tətbiq scipy.optimize şəkillər toplusundan 3D struktur yaratmaq ()-də baxa bilərsiniz .
Əsas məlumat mənbəyidir bu və digər bölmələrin tərcüməsinə töhfə vermək istəyənlər scipy xoş gəlmisiniz .
Təşəkkür nəşrin hazırlanmasında iştirakına görə.
Mənbə: www.habr.com