SciPy (сай бялуу гэж нэрлэдэг) нь Numpy Python өргөтгөл дээр суурилсан математикийн хэрэглээний багц юм. SciPy-ийн тусламжтайгаар таны интерактив Python сесс нь MATLAB, IDL, Octave, R-Lab, SciLab-тай ижил иж бүрэн өгөгдлийн шинжлэх ухаан, цогц системийн загварчлалын орчин болж хувирдаг. Өнөөдөр би scipy.optimize багц дахь алдартай оновчлолын алгоритмуудыг хэрхэн ашиглах талаар товч ярихыг хүсч байна. Функцуудыг ашиглах талаар илүү нарийвчилсан, хамгийн сүүлийн үеийн тусламжийг help() команд эсвэл Shift+Tab ашиглан үргэлж авч болно.
Танилцуулга
Өөрийгөө болон уншигчдыг үндсэн эх сурвалжаас хайх, уншихаас аврахын тулд аргуудын тайлбарын холбоосыг голчлон Википедиа дээр байрлуулах болно. Дүрмээр бол энэ мэдээлэл нь аргуудыг ерөнхийд нь ойлгоход хангалттай бөгөөд тэдгээрийг хэрэглэх нөхцлийг ойлгоход хангалттай. Математик аргуудын мөн чанарыг ойлгохын тулд нийтлэл бүрийн төгсгөлд эсвэл дуртай хайлтын системээсээ олж болох илүү эрх мэдэл бүхий нийтлэлүүдийн холбоосыг дагана уу.
Тиймээс, scipy.optimize модуль нь дараахь процедурыг хэрэгжүүлдэг.
- Төрөл бүрийн алгоритм (Nelder-Mead simplex, BFGS, Newton conjugate градиент, и )
- Глобал оновчлол (жишээ нь: , )
- Үлдэгдлийг багасгах (хамгийн бага_квадрат) болон шугаман бус хамгийн бага квадратуудыг ашиглан муруй тохируулах алгоритмууд (муруй_тохируулга)
- Нэг хувьсагчийн скаляр функцийг багасгах (миним_скаляр) ба үндэс хайх (root_scalar)
- Төрөл бүрийн алгоритмуудыг ашиглан тэгшитгэлийн системийн олон хэмжээст шийдэгч (эрлийз Пауэлл эсвэл том хэмжээний аргууд гэх мэт ).
Энэ нийтлэлд бид энэ бүх жагсаалтын зөвхөн эхний зүйлийг авч үзэх болно.
Хэд хэдэн хувьсагчийн скаляр функцийг болзолгүй багасгах
Scipy.optimize багцын минимум функц нь хэд хэдэн хувьсагчийн скаляр функцүүдийн нөхцөлт болон болзолгүй багасгах бодлогуудыг шийдвэрлэх ерөнхий интерфейсийг хангадаг. Энэ нь хэрхэн ажилладагийг харуулахын тулд бидэнд хэд хэдэн хувьсагчийн тохирох функц хэрэгтэй бөгөөд бид үүнийг янз бүрийн аргаар багасгах болно.
Эдгээр зорилгын үүднээс N хувьсагчийн Rosenbrock функц төгс бөгөөд дараах хэлбэртэй байна.
Rosenbrock функц болон түүний Якоби ба Гессийн матрицууд (эхний болон хоёр дахь деривативууд) 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)Тодорхой болгохын тулд хоёр хувьсагчийн Rosenbrock функцийн утгыг 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 хэмжээст орон зайд анхны x5 цэг байг. Розенброк функцийн хамгийн бага цэгийг алгоритмын тусламжтайгаар олъё (алгоритмыг аргын параметрийн утга гэж тодорхойлсон):
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.]Симплекс арга нь тодорхой тодорхойлогдсон, нэлээд жигд функцийг багасгах хамгийн энгийн арга юм. Энэ нь функцийн деривативыг тооцоолох шаардлагагүй бөгөөд зөвхөн утгыг нь зааж өгөхөд хангалттай. Nelder-Mead арга нь энгийн багасгах асуудлыг шийдвэрлэхэд тохиромжтой сонголт юм. Гэсэн хэдий ч энэ нь градиент тооцооллыг ашигладаггүй тул хамгийн бага хэмжээг олоход удаан хугацаа шаардагдах болно.
Пауэллийн арга
Зөвхөн функцийн утгыг тооцдог өөр нэг оновчлолын алгоритм юм . Үүнийг ашиглахын тулд та минимум функцэд 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]Коньюгат градиент алгоритм (Ньютон)
Алгоритм нь өөрчлөгдсөн Ньютоны арга юм.
Ньютоны арга нь орон нутгийн функцийг хоёрдугаар зэргийн олон гишүүнтээр ойртуулахад суурилдаг.
хаана нь хоёр дахь деривативын матриц юм (Гессийн матриц, Гессийн).
Хэрэв Hessian эерэг тодорхой бол квадрат хэлбэрийн тэг градиентыг тэгтэй тэнцүүлэх замаар энэ функцийн локал минимумыг олж болно. Үр дүн нь илэрхийлэл байх болно:
Урвуу Hessian-ийг коньюгат градиент аргыг ашиглан тооцоолно. Rosenbrock функцийг багасгахын тулд энэ аргыг ашиглах жишээг доор өгөв. Newton-CG аргыг ашиглахын тулд та Hessian-ийг тооцоолох функцийг зааж өгөх ёстой.
Аналитик хэлбэрээр Розенброк функцийн Гессиан нь дараахтай тэнцүү байна.
хаана и , матрицыг тодорхойлно .
Матрицын үлдсэн тэг бус элементүүд нь дараахтай тэнцүү байна.
Жишээлбэл, таван хэмжээст орон зайд 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]Hessian ба дурын векторын бүтээгдэхүүний функцийг тодорхойлсон жишээ
Бодит асуудалд Hessian матрицыг бүхэлд нь тооцоолох, хадгалахад ихээхэн цаг хугацаа, санах ойн нөөц шаардлагатай байдаг. Энэ тохиолдолд Hessian матрицыг өөрөө зааж өгөх шаардлагагүй, учир нь багасгах процедур нь зөвхөн өөр дурын вектортой Hessian-ийн үржвэртэй тэнцүү векторыг шаарддаг. Тиймээс, тооцооллын үүднээс авч үзвэл, дурын вектороор Hessian-ийн үржвэрийн үр дүнг буцаадаг функцийг нэн даруй тодорхойлох нь илүү дээр юм.
Багажуулсан векторыг эхний аргумент болгон, дурын векторыг хоёр дахь аргумент болгон авдаг hess функцийг (багасгах функцийн бусад аргументуудын хамт) авч үзье. Манай тохиолдолд дурын вектороор Розенброк функцийн Гессийн үржвэрийг тооцоолох нь тийм ч хэцүү биш юм. Хэрэв p нь дурын вектор, дараа нь бүтээгдэхүүн дараах байдалтай байна:
Hessian ба дурын векторын үржвэрийг тооцоолох функцийг 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Коньюгат градиент итгэлцлийн бүсийн алгоритм (Ньютон)
Hessian матрицын нөхцөл муутай, хайлтын чиглэл буруу байгаа нь Ньютоны коньюгат градиент алгоритмыг үр дүнгүй болгоход хүргэдэг. Ийм тохиолдолд давуу эрх олгодог (итгэлцлийн бүс) Ньютоны градиент коньюгат.
Hessian матрицын тодорхойлолттой жишээ:
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.]Hessian ба дурын векторын үржвэрийн функцтэй жишээ:
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 аргатай харьцуулахад дэд асуудалд ногдох матриц-векторын үржвэрийн тоо цөөн байдаг тул шугаман бус давталтуудыг ашиглах нь илүү дээр юм. Түүнчлэн, квадрат дэд асуудлын шийдлийг Trust-ncg аргыг ашиглахаас илүү нарийвчлалтай олдог.
Hessian матрицын тодорхойлолттой жишээ:
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.]
Hessian ба дурын векторын үржвэрийн функцтэй жишээ:
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) нь том хэмжээний (мянган хувьсагчтай) асуудлыг шийдвэрлэхэд тохиромжтой. Энэ нь үндсэн коньюгат градиент алгоритм нь урвуу Hessian матрицыг ойролцоогоор тодорхойлохыг илэрхийлдэгтэй холбоотой юм. Шийдэл нь Hessian-ийн тодорхой тэлэлтгүйгээр давтагдах байдлаар олддог. Та зөвхөн Hessian ба дурын векторын үржвэрийн функцийг тодорхойлох шаардлагатай байдаг тул энэ алгоритм нь сийрэг (зурваа диагональ) матрицуудтай ажиллахад тохиромжтой. Энэ нь санах ойн зардал бага, цагийг ихээхэн хэмнэдэг.
Дунд зэргийн хэмжээтэй асуудлуудын хувьд Hessian-ыг хадгалах, хүчин зүйл болгох зардал тийм ч чухал биш юм. Энэ нь итгэлцлийн бүсийн дэд асуудлуудыг бараг яг таг шийдэж, цөөн давталтаар шийдлийг олж авах боломжтой гэсэн үг юм. Үүний тулд зарим шугаман бус тэгшитгэлийг квадрат дэд бодлого тус бүрээр давталттайгаар шийддэг. Ийм шийдэл нь ихэвчлэн Hessian матрицын 3 эсвэл 4 Cholesky задралыг шаарддаг. Үүний үр дүнд арга нь цөөн давталтаар нийлдэг бөгөөд бусад хэрэгжсэн итгэлцлийн бүсийн аргуудаас цөөн тооны зорилгын функцийн тооцоолол шаарддаг. Энэ алгоритм нь зөвхөн Гессийн матрицыг бүрэн тодорхойлоход хамаарах ба Hessian болон дурын векторын бүтээгдэхүүний функцийг ашиглах боломжийг дэмждэггүй.
Rosenbrock функцийг багасгах жишээ:
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