SciPy (айтылған sai pie) — Numpy Python кеңейтіміне негізделген математикалық қолданбалы пакет. SciPy көмегімен интерактивті Python сеансы MATLAB, IDL, Octave, R-Lab және SciLab сияқты толық деректер ғылымы мен күрделі жүйе прототипін жасау ортасына айналады. Бүгін мен scipy.optimize пакетінде белгілі оңтайландыру алгоритмдерін қалай пайдалану керектігі туралы қысқаша сөйлескім келеді. Функцияларды пайдалану бойынша толығырақ және жаңартылған анықтаманы әрқашан help() пәрмені немесе Shift+Tab пернелері арқылы алуға болады.
Кіріспе
Өзіңізді және оқырмандарды бастапқы дереккөздерді іздеуден және оқудан құтқару үшін әдістердің сипаттамасына сілтемелер негізінен Уикипедияда болады. Әдетте, бұл ақпарат әдістерді жалпы түрде және оларды қолдану шарттарын түсіну үшін жеткілікті. Математикалық әдістердің мәнін түсіну үшін әр мақаланың соңында немесе сүйікті іздеу жүйесінде табуға болатын беделді басылымдарға сілтемелерді орындаңыз.
Сонымен, scipy.optimize модулі келесі процедураларды орындауды қамтиды:
- Түрлі алгоритмдерді (Нелдер-Мид симплексі, BFGS, Ньютон конъюгаттық градиенттері, и )
- Ғаламдық оңтайландыру (мысалы: , )
- Қалдықтарды азайту (ең аз_шаршы) және сызықты емес ең кіші квадраттарды қолданатын қисық сызықтарды сәйкестендіру алгоритмдері (қисық_фигурация)
- Бір айнымалының скалярлық функцияларын азайту (minim_scalar) және түбірлерді іздеу (root_scalar)
- Әртүрлі алгоритмдерді (гибридті Пауэлл, немесе кең ауқымды әдістер сияқты ).
Бұл мақалада біз осы тізімнің бірінші тармағын ғана қарастырамыз.
Бірнеше айнымалылардың скалярлық функциясын шартсыз минимизациялау
Scipy.optimize бумасындағы минимум функциясы бірнеше айнымалылардың скалярлық функцияларын шартты және шартсыз минимизациялау есептерін шешуге арналған жалпы интерфейсті қамтамасыз етеді. Оның қалай жұмыс істейтінін көрсету үшін бізге әртүрлі тәсілдермен азайтатын бірнеше айнымалылардың қолайлы функциясы қажет болады.
Осы мақсаттар үшін N айнымалының Розенброк функциясы мінсіз болып табылады, оның пішіні бар:
Розенброк функциясы және оның Якоби және Гессиан матрицалары (тиісінше бірінші және екінші туындылар) scipy.optimize бумасында анықталғанына қарамастан, біз оны өзіміз анықтаймыз.
import numpy as np
def rosen(x):
"""The Rosenbrock function"""
return np.sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0, axis=0)Түсінікті болу үшін екі айнымалының Розенброк функциясының мәндерін 3D түрінде салайық.
Сурет салу коды
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
from matplotlib import cm
from matplotlib.ticker import LinearLocator, FormatStrFormatter
# Настраиваем 3D график
fig = plt.figure(figsize=[15, 10])
ax = fig.gca(projection='3d')
# Задаем угол обзора
ax.view_init(45, 30)
# Создаем данные для графика
X = np.arange(-2, 2, 0.1)
Y = np.arange(-1, 3, 0.1)
X, Y = np.meshgrid(X, Y)
Z = rosen(np.array([X,Y]))
# Рисуем поверхность
surf = ax.plot_surface(X, Y, Z, cmap=cm.coolwarm)
plt.show()
Минималды 0-де екенін алдын ала білу , әртүрлі scipy.optimize процедуралары арқылы Rosenbrock функциясының минималды мәнін анықтаудың мысалдарын қарастырайық.
Нельдер-Мид симплекс әдісі
0 өлшемді кеңістікте бастапқы х5 нүктесі болсын. Алгоритмнің көмегімен Розенброк функциясының ең жақын нүктесін табайық (алгоритм әдіс параметрінің мәні ретінде көрсетіледі):
from scipy.optimize import minimize
x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])
res = minimize(rosen, x0, method='nelder-mead',
options={'xtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 339
Function evaluations: 571
[1. 1. 1. 1. 1.]Симплекс әдісі - анық анықталған және жеткілікті тегіс функцияны азайтудың ең қарапайым тәсілі. Бұл функцияның туындыларын есептеуді қажет етпейді, тек оның мәндерін көрсету жеткілікті. Нелдер-Мид әдісі қарапайым минимизация есептері үшін жақсы таңдау болып табылады. Дегенмен, ол градиентті бағалауды пайдаланбайтындықтан, минимумды табу ұзағырақ уақыт алуы мүмкін.
Пауэлл әдісі
Оңтайландырудың тағы бір алгоритмі, онда тек функция мәндері есептеледі . Оны пайдалану үшін минимум функциясында method = 'powell' параметрін орнату керек.
x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])
res = minimize(rosen, x0, method='powell',
options={'xtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 19
Function evaluations: 1622
[1. 1. 1. 1. 1.]Broyden-Fletcher-Goldfarb-Shanno (BFGS) алгоритмі
Шешімге тезірек конвергенция алу үшін процедура мақсат функциясының градиентін пайдаланады. Градиент функция ретінде көрсетілуі немесе бірінші реттік айырмашылықтарды пайдаланып есептелуі мүмкін. Кез келген жағдайда, BFGS әдісі симплекс әдісіне қарағанда әдетте аз функция шақыруларын талап етеді.
Розенброк функциясының туындысын аналитикалық түрде табайық:
Бұл өрнек бірінші және соңғыдан басқа барлық айнымалылардың туындылары үшін жарамды, олар келесідей анықталады:
Осы градиентті есептейтін Python функциясын қарастырайық:
def rosen_der (x):
xm = x [1: -1]
xm_m1 = x [: - 2]
xm_p1 = x [2:]
der = np.zeros_like (x)
der [1: -1] = 200 * (xm-xm_m1 ** 2) - 400 * (xm_p1 - xm ** 2) * xm - 2 * (1-xm)
der [0] = -400 * x [0] * (x [1] -x [0] ** 2) - 2 * (1-x [0])
der [-1] = 200 * (x [-1] -x [-2] ** 2)
return derГрадиентті есептеу функциясы төменде көрсетілгендей минимум функциясының jac параметрінің мәні ретінде көрсетілген.
res = minimize(rosen, x0, method='BFGS', jac=rosen_der, options={'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 25
Function evaluations: 30
Gradient evaluations: 30
[1.00000004 1.0000001 1.00000021 1.00000044 1.00000092]Конъюгаттық градиент алгоритмі (Ньютон)
Алгоритм модификацияланған Ньютон әдісі болып табылады.
Ньютон әдісі жергілікті аймақтағы функцияны екінші дәрежелі көпмүшемен жуықтауға негізделген:
қайда екінші туындылардың матрицасы (Гессиан матрицасы, Гессиан).
Егер гессиан оң анықталған болса, онда бұл функцияның жергілікті минимумын квадрат форманың нөлдік градиентін нөлге теңестіру арқылы табуға болады. Нәтиже өрнек болады:
Кері Гессиан конъюгаттық градиент әдісі арқылы есептеледі. Rosenbrock функциясын азайту үшін осы әдісті пайдалану мысалы төменде келтірілген. Newton-CG әдісін қолдану үшін гессиенді есептейтін функцияны көрсету керек.
Розенброк функциясының гессині аналитикалық түрде мынаған тең:
қайда и , матрицаны анықтаңыз .
Матрицаның қалған нөлдік емес элементтері мынаған тең:
Мысалы, N = 5 бес өлшемді кеңістікте Розенброк функциясына арналған Гессий матрицасы жолақ пішініне ие:
Розенброк функциясын конъюгаттық градиент (Ньютон) әдісі арқылы азайтуға арналған кодпен бірге осы Гессианы есептейтін код:
def rosen_hess(x):
x = np.asarray(x)
H = np.diag(-400*x[:-1],1) - np.diag(400*x[:-1],-1)
diagonal = np.zeros_like(x)
diagonal[0] = 1200*x[0]**2-400*x[1]+2
diagonal[-1] = 200
diagonal[1:-1] = 202 + 1200*x[1:-1]**2 - 400*x[2:]
H = H + np.diag(diagonal)
return H
res = minimize(rosen, x0, method='Newton-CG',
jac=rosen_der, hess=rosen_hess,
options={'xtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 24
Function evaluations: 33
Gradient evaluations: 56
Hessian evaluations: 24
[1. 1. 1. 0.99999999 0.99999999]Гессиан және ерікті вектордың туынды функциясының анықтамасы бар мысал
Нақты әлемдегі мәселелерде бүкіл Гессиан матрицасын есептеу және сақтау айтарлықтай уақыт пен жад ресурстарын қажет етуі мүмкін. Бұл жағдайда гессий матрицасының өзін көрсетудің қажеті жоқ, өйткені минимизациялау процедурасы басқа ерікті вектормен Гессианның көбейтіндісіне тең векторды ғана қажет етеді. Осылайша, есептеу тұрғысынан, ерікті вектормен Гессиан көбейтіндісінің нәтижесін қайтаратын функцияны дереу анықтау әлдеқайда жақсырақ.
Минимизация векторын бірінші аргумент ретінде, ал екінші аргумент ретінде ерікті векторды (минимизацияланатын функцияның басқа аргументтерімен бірге) қабылдайтын hess функциясын қарастырайық. Біздің жағдайда Розенброк функциясының гессианының туындысын ерікті вектормен есептеу өте қиын емес. Егер p ерікті вектор болса, онда көбейтінді нысаны бар:
Гессиан мен ерікті вектордың көбейтіндісін есептейтін функция минимизациялау функциясына hessp аргументінің мәні ретінде беріледі:
def rosen_hess_p(x, p):
x = np.asarray(x)
Hp = np.zeros_like(x)
Hp[0] = (1200*x[0]**2 - 400*x[1] + 2)*p[0] - 400*x[0]*p[1]
Hp[1:-1] = -400*x[:-2]*p[:-2]+(202+1200*x[1:-1]**2-400*x[2:])*p[1:-1]
-400*x[1:-1]*p[2:]
Hp[-1] = -400*x[-2]*p[-2] + 200*p[-1]
return Hp
res = minimize(rosen, x0, method='Newton-CG',
jac=rosen_der, hessp=rosen_hess_p,
options={'xtol': 1e-8, 'disp': True})
Optimization terminated successfully.
Current function value: 0.000000
Iterations: 24
Function evaluations: 33
Gradient evaluations: 56
Hessian evaluations: 66Конъюгаттық градиент сенім аймағының алгоритмі (Ньютон)
Гессиан матрицасының нашар кондициясы және дұрыс емес іздеу бағыттары Ньютонның конъюгаттық градиент алгоритмінің тиімсіз болуына әкелуі мүмкін. Мұндай жағдайларда артықшылық беріледі (сенім-аймақ) конъюгаттық Ньютон градиенттері.
Гессиан матрицасының анықтамасы бар мысал:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 20
Function evaluations: 21
Gradient evaluations: 20
Hessian evaluations: 19
[1. 1. 1. 1. 1.]Гессиан және ерікті вектордың туынды функциясы бар мысал:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hessp=rosen_hess_p,
options={'gtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 20
Function evaluations: 21
Gradient evaluations: 20
Hessian evaluations: 0
[1. 1. 1. 1. 1.]Крылов типті әдістер
Trust-ncg әдісі сияқты, Крылов типті әдістер де ауқымды есептерді шешуге өте қолайлы, өйткені олар тек матрицалық-векторлық туындыларды пайдаланады. Олардың мәні қысқартылған Крылов қосалқы кеңістігімен шектелген сенімді аймақтағы мәселені шешу болып табылады. Белгісіз есептер үшін бұл әдісті қолданған дұрыс, өйткені ол сенім-ncg әдісімен салыстырғанда ішкі мәселе бойынша матрицалық-векторлық өнімдердің аз санына байланысты сызықты емес итерациялардың азырақ санын пайдаланады. Сонымен қатар, сенім-ncg әдісін қолданғаннан гөрі квадраттық ішкі есептің шешімі дәлірек табылады.
Гессиан матрицасының анықтамасы бар мысал:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
Optimization terminated successfully.
Current function value: 0.000000
Iterations: 19
Function evaluations: 20
Gradient evaluations: 20
Hessian evaluations: 18
print(res.x)
[1. 1. 1. 1. 1.]
Гессиан және ерікті вектордың туынды функциясы бар мысал:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hessp=rosen_hess_p,
options={'gtol': 1e-8, 'disp': True})
Optimization terminated successfully.
Current function value: 0.000000
Iterations: 19
Function evaluations: 20
Gradient evaluations: 20
Hessian evaluations: 0
print(res.x)
[1. 1. 1. 1. 1.]
Сенімділік аймағындағы жуық шешім алгоритмі
Барлық әдістер (Newton-CG, Trust-ncg және Trust-krylov) ауқымды есептерді (мыңдаған айнымалылар) шешуге жақсы сәйкес келеді. Бұл негізгі конъюгаттық градиент алгоритмі кері Гессиан матрицасын шамамен анықтауды болжайтындығына байланысты. Шешім гессианның айқын кеңеюінсіз итеративті түрде табылады. Гессиан мен ерікті вектордың туындысы үшін функцияны анықтау қажет болғандықтан, бұл алгоритм әсіресе сирек (диагональды диагональ) матрицалармен жұмыс істеу үшін жақсы. Бұл жадтың төмен шығындарын және уақытты айтарлықтай үнемдеуді қамтамасыз етеді.
Орташа өлшемді мәселелер үшін Гессианы сақтау және факторинг құны маңызды емес. Бұл сенімді аймақтың ішкі мәселелерін дәл дерлік шеше отырып, шешімді аз итерацияда алуға болатынын білдіреді. Ол үшін кейбір сызықтық емес теңдеулер әрбір квадраттық ішкі есеп үшін итеративті түрде шешіледі. Мұндай шешім әдетте Гессиан матрицасының 3 немесе 4 Холеский ыдырауын қажет етеді. Нәтижеде, әдіс азырақ итерацияда жинақталады және басқа іске асырылған сенімділік аймағы әдістеріне қарағанда, аз мақсатты функция есептеулерін қажет етеді. Бұл алгоритм тек толық Гессиан матрицасын анықтауды қамтиды және Гессианның туынды функциясын және ерікті векторды пайдалану мүмкіндігін қолдамайды.
Розенброк функциясын минимизациялау мысалы:
res = minimize(rosen, x0, method='trust-exact',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
res.xOptimization terminated successfully.
Current function value: 0.000000
Iterations: 13
Function evaluations: 14
Gradient evaluations: 13
Hessian evaluations: 14
array([1., 1., 1., 1., 1.])Біз сонда тоқтайтын шығармыз. Келесі мақалада мен шартты минимизациялау, жуықтау есептерін шешуде минимизацияны қолдану, бір айнымалының функциясын минимизациялау, ерікті минимизаторлар және scipy.optimize көмегімен теңдеулер жүйесінің түбірін табу туралы ең қызықты нәрселерді айтуға тырысамын. пакет.
Ақпарат көзі:
Ақпарат көзі: www.habr.com