ProHoster > Blog > интернет жаңылыктары > SciPy, оптималдаштыруу

SciPy, оптималдаштыруу

SciPy, оптималдаштыруу

SciPy (айтылышы sai pie) бул Numpy Python кеңейтүүсүнө негизделген математикалык колдонмо пакети. SciPy менен сиздин интерактивдүү Python сессияңыз MATLAB, IDL, Octave, R-Lab жана SciLab сыяктуу толук маалымат илимине жана комплекстүү системаны прототиптөө чөйрөсүнө айланат. Бүгүн мен scipy.optimize пакетинде кээ бир белгилүү оптималдаштыруу алгоритмдерин кантип колдонуу керектиги жөнүндө кыскача айткым келет. Функцияларды колдонуу боюнча кеңири жана актуалдуу жардамды ар дайым help() буйругу же Shift+Tab аркылуу алууга болот.

тааныштыруу

Өзүңүздү жана окурмандарды негизги булактарды издөөдөн жана окуудан сактап калуу үчүн ыкмалардын сүрөттөмөсүнө шилтемелер негизинен Википедияда болот. Эреже катары, бул маалымат жалпы терминдерди жана аларды колдонуу шарттарын түшүнүү үчүн жетиштүү болуп саналат. Математикалык ыкмалардын маңызын түшүнүү үчүн, ар бир макаланын аягында же сүйүктүү издөө системаңыздан тапса болот, авторитеттүү басылмаларга шилтемелер менен өтүңүз.

Ошентип, scipy.optimize модулу төмөнкү процедураларды ишке ашырууну камтыйт:

  1. Ар кандай алгоритмдерди (Нелдер-Мид симплекси, BFGS, Ньютон конъюгациялык градиенттери, КОБИЛА и SLSQP)
  2. Глобалдык оптималдаштыруу (мисалы: basinhopping, diff_evolution)
  3. калдыктарды минималдаштыруу MNC (кичине_квадраттар) жана сызыктуу эмес эң кичине квадраттарды колдонуу менен ийри сызыктарды тууралоо алгоритмдери (curve_fit)
  4. Бир өзгөрмөнүн скалярдык функцияларын минималдаштыруу (minim_scalar) жана тамырларды издөө (root_scalar)
  5. Ар кандай алгоритмдерди (гибрид Пауэлл, Левенберг-Марквардт же сыяктуу ири масштабдагы методдор Ньютон-Крылов).

Бул макалада биз бул тизменин биринчи пунктун гана карап чыгабыз.

Бир нече өзгөрмөлүү скалярдык функцияны шартсыз минимизациялоо

Scipy.optimize пакетинен минималдуу функция бир нече өзгөрмөлүү скалярдык функцияларды шарттуу жана шартсыз минимизациялоо маселелерин чечүү үчүн жалпы интерфейсти камсыз кылат. Анын кантип иштээрин көрсөтүү үчүн бизге бир нече өзгөрмөлөрдөн турган ылайыктуу функция керек болот, биз аларды ар кандай жолдор менен азайтабыз.

Бул максаттар үчүн, N өзгөрмөлөрүнүн Розенброк функциясы идеалдуу, ал төмөнкү формага ээ:

SciPy, оптималдаштыруу

Розенброк функциясы жана анын Якоби жана Гессиан матрицалары (тиешелүүлүгүнө жараша биринчи жана экинчи туундулары) 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()

SciPy, оптималдаштыруу

Минималдуу 0 экенин алдын ала билип SciPy, оптималдаштыруу, келгиле, ар кандай scipy.optimize процедураларын колдонуу менен Розенброк функциясынын минималдуу маанисин аныктоонун мисалдарын карап көрөлү.

Нелдер-Мид симплекс ыкмасы

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.]

Симплекс ыкмасы ачык аныкталган жана кыйла жылмакай функцияны минималдаштыруунун эң жөнөкөй жолу. Функциянын туундуларын эсептөөнү талап кылбайт, анын маанилерин гана көрсөтүү жетиштүү. Нелдер-Мид ыкмасы жөнөкөй минималдаштыруу көйгөйлөрү үчүн жакшы тандоо болуп саналат. Бирок, ал градиенттик баалоолорду колдонбогондуктан, минимумду табууга көбүрөөк убакыт талап кылынышы мүмкүн.

Пауэлл ыкмасы

Функциянын маанилери гана эсептелген дагы бир оптималдаштыруу алгоритми Пауэллдин ыкмасы. Аны колдонуу үчүн минималдуу функцияда 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 максаттуу функциянын градиентин колдонот. Градиент функция катары көрсөтүлүшү мүмкүн же биринчи тартиптеги айырмачылыктар менен эсептелиши мүмкүн. Кандай болгон күндө да, BFGS ыкмасы, адатта, симплекс ыкмасына караганда азыраак функцияларды талап кылат.

Розенброк функциясынын туундусун аналитикалык түрдө табалы:

SciPy, оптималдаштыруу

SciPy, оптималдаштыруу

Бул туюнтма биринчи жана акыркыдан башка бардык өзгөрмөлөрдүн туундулары үчүн жарактуу, алар төмөнкүдөй аныкталат:

SciPy, оптималдаштыруу

SciPy, оптималдаштыруу

Бул градиентти эсептеген 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]

Коньюгаттык градиент алгоритми (Ньютон)

алгоритми Ньютондун конъюгациялык градиенттери модификацияланган Ньютон ыкмасы болуп саналат.
Ньютон методу локалдык аймактагы функцияны экинчи даражадагы көп мүчө менен жакындатууга негизделген:

SciPy, оптималдаштыруу

кайда SciPy, оптималдаштыруу экинчи туундулардын матрицасы (Гессиан матрицасы, Гессиан).
Эгерде гессий оң аныкталган болсо, анда бул функциянын локалдык минимумун квадраттык форманын нөлдүк градиентин нөлгө теңештирүү жолу менен табууга болот. Натыйжада сөз болот:

SciPy, оптималдаштыруу

Тескери Гессиан коньюгаттык градиент ыкмасы менен эсептелет. Rosenbrock функциясын минималдаштыруу үчүн бул ыкманы колдонуунун мисалы төмөндө келтирилген. Newton-CG ыкмасын колдонуу үчүн, Гессианды эсептеген функцияны көрсөтүү керек.
Розенброк функциясынын гессианы аналитикалык түрдө төмөнкүгө барабар:

SciPy, оптималдаштыруу

SciPy, оптималдаштыруу

кайда SciPy, оптималдаштыруу и SciPy, оптималдаштыруу, матрицаны аныктаңыз SciPy, оптималдаштыруу.

Матрицанын нөл эмес калган элементтери төмөнкүгө барабар:

SciPy, оптималдаштыруу

SciPy, оптималдаштыруу

SciPy, оптималдаштыруу

SciPy, оптималдаштыруу

Мисалы, беш өлчөмдүү мейкиндикте N = 5, Розенброк функциясы үчүн Гессиан матрицасы тилке формасына ээ:

SciPy, оптималдаштыруу

Розенброк функциясын коньюгаттык градиент (Ньютон) ыкмасын колдонуу менен минималдаштыруу үчүн код менен бирге бул Гессианы эсептеген код:

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 ыктыярдуу вектор, анда продукт SciPy, оптималдаштыруу формасы бар:

SciPy, оптималдаштыруу

Гессиан жана ыктыярдуу вектордун көбөйтүндүсүн эсептеген функция 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 Чолеский ажыратууларын талап кылат. Натыйжада, метод азыраак итерацияда биригет жана башка ишке ашырылган ишеним аймагынын ыкмаларына караганда объективдүү функциялардын азыраак эсептөөлөрүн талап кылат. Бул алгоритм толук Гессиан матрицасын аныктоону гана билдирет жана Гессиандын продукт функциясын жана ыктыярдуу векторду колдонуу мүмкүнчүлүгүн колдобойт.

Rosenbrock функциясын минималдаштырууга мисал:

res = minimize(rosen, x0, method='trust-exact',
               jac=rosen_der, hess=rosen_hess,
               options={'gtol': 1e-8, 'disp': True})
res.x

Optimization 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 аркылуу теңдемелер системасынын тамырларын табуу жөнүндө эң кызыктуу нерселерди айтып берүүгө аракет кылам. пакет.

Source: https://docs.scipy.org/doc/scipy/reference/

Source: www.habr.com

DDoS коргоосу, VPS VDS серверлери бар сайттар үчүн ишенимдүү хостинг сатып алыңыз 🔥 DDoS коргоосу, VPS VDS серверлери бар ишенимдүү веб-сайт хостингин сатып алыңыз | ProHoster