SciPy (айтылған sai pie) - бұл C және Fortran кітапханаларын қамтитын numpy негізіндегі математикалық пакет. SciPy интерактивті Python сеансын MATLAB, IDL, Octave, R немесе SciLab сияқты толық деректер ғылымы ортасына айналдырады.
Бұл мақалада біз математикалық бағдарламалаудың негізгі әдістерін қарастырамыз – scipy.optimize бумасын пайдаланып бірнеше айнымалылардың скалярлық функциясы үшін шартты оңтайландыру есептерін шешу. Шектеусіз оңтайландыру алгоритмдері қазірдің өзінде талқыланған . Scipy функциялары бойынша толығырақ және жаңартылған анықтаманы әрқашан help() пәрмені, Shift+Tab немесе ішінен алуға болады. .
Кіріспе
scipy.optimize бумасындағы шартты және шектеусіз оңтайландыру мәселелерін шешуге арналған жалпы интерфейс функция арқылы қамтамасыз етілген. minimize(). Дегенмен, барлық мәселелерді шешудің әмбебап әдісі жоқ екені белгілі, сондықтан адекватты әдісті таңдау, әдеттегідей, зерттеушінің иығына түседі.
Сәйкес оңтайландыру алгоритмі функция аргументі арқылы көрсетіледі minimize(..., method="").
Бірнеше айнымалы функцияны шартты оңтайландыру үшін келесі әдістерді іске асыру қол жетімді:
trust-constr— сенімді аймақта жергілікті минимумды іздеу. , ;SLSQP— шектеулері бар дәйекті квадраттық бағдарламалау, Лагранж жүйесін шешудің Ньютон әдісі. .TNC- Кесілген Ньютон Шектеулі, итерациялардың шектеулі саны, тәуелсіз айнымалылары көп сызықтық емес функциялар үшін жақсы. .L-BFGS-B— Гессиан матрицасынан векторларды ішінара жүктеуге байланысты жадты тұтынуды азайту арқылы жүзеге асырылған Бройден-Флетчер-Голдфарб-Шанно командасының әдісі. , .COBYLA— Сызықтық жуықтау арқылы MARE шектеулі оңтайландыру, сызықтық жуықтаумен шектелген оңтайландыру (градиентті есептеусіз). .
Таңдалған әдіске байланысты мәселені шешудің шарттары мен шектеулері әртүрлі белгіленеді:
- сынып объектісі
BoundsL-BFGS-B, TNC, SLSQP, Trust-constr әдістері үшін; - тізім
(min, max)бірдей әдістер үшін L-BFGS-B, TNC, SLSQP, Trust-constr; - нысан немесе нысандар тізімі
LinearConstraint,NonlinearConstraintCOBYLA, SLSQP, Trust-constr әдістері үшін; - сөздік немесе сөздіктер тізімі
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}COBYLA, SLSQP әдістері үшін.
Мақаланың қысқаша мазмұны:
1) Объектілер ретінде көрсетілген шектеулермен сенімді аймақта шартты оңтайландыру алгоритмін пайдалануды қарастырыңыз (method="trust-constr") Bounds, LinearConstraint, NonlinearConstraint ;
2) Сөздік түрінде көрсетілген шектеулері бар ең кіші квадраттар әдісін (әдіс = «SLSQP») қолданатын тізбекті бағдарламалауды қарастырыңыз. {'type', 'fun', 'jac', 'args'};
3) Веб-студия мысалында өндірілген өнімдерді оңтайландыру мысалын талдаңыз.
Шартты оңтайландыру әдісі = "trust-constr"
Әдістің жүзеге асуы trust-constr негізделген теңдік түрінің шектеулері бар есептер үшін және т.б теңсіздіктер түріндегі шектеулері бар есептер үшін. Екі әдіс те сенімді аймақта жергілікті минимумды табу алгоритмдері арқылы жүзеге асырылады және ауқымды есептер үшін өте қолайлы.
Минималды табу есебінің жалпы формадағы математикалық тұжырымы:
Қатаң теңдік шектеулері үшін төменгі шекара жоғарғы шекке тең орнатылады .
Бір жақты шектеу үшін жоғарғы немесе төменгі шек орнатылады np.inf сәйкес белгісімен.
Екі айнымалының белгілі Розенброк функциясының минимумын табу қажет болсын:
Бұл жағдайда оның анықтау аймағына келесі шектеулер қойылады:
Біздің жағдайда нүктеде бірегей шешім бар , ол үшін тек бірінші және төртінші шектеулер жарамды.
Шектеулерді төменнен жоғарыға қарай қарастырайық және оларды scipy тілінде қалай жазуға болатынын қарастырайық.
Шектеулер и оны 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)Гессиан матрицасын есептеу кезінде көп күш жұмсауды талап етеді, сіз сыныпты пайдалана аласыз . Келесі стратегиялар қол жетімді: 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]Қажет болса, Hessian есептеу функциясын 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 тр. бастап қондырылған беттерді сату.
- x1 - корпоративтік веб-сайттар, 20 тр.
- 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 кескіндер жиынынан 3D құрылымын құру () ішінен көруге болады .
Негізгі ақпарат көзі болып табылады осы және басқа бөлімдердің аудармасына үлес қосқысы келетіндер scipy Қош келдіңіз .
сізге рахмет басылымды дайындауға қатысқаны үшін.
Ақпарат көзі: www.habr.com