SciPy-ը (արտասանվում է sai pie) մաթեմատիկական կիրառական փաթեթ է՝ հիմնված Numpy Python ընդլայնման վրա։ SciPy-ի միջոցով ձեր Python-ի ինտերակտիվ նիստը դառնում է նույն ամբողջական տվյալների գիտությունը և համալիր համակարգի նախատիպային միջավայրը, ինչ MATLAB-ը, IDL-ն, Octave-ը, R-Lab-ը և SciLab-ը: Այսօր ես ուզում եմ համառոտ խոսել այն մասին, թե ինչպես օգտագործել որոշ հայտնի օպտիմալացման ալգորիթմներ scipy.optimize փաթեթում: Ֆունկցիաների օգտագործման վերաբերյալ ավելի մանրամասն և արդի օգնություն միշտ կարելի է ստանալ help() հրամանի կամ Shift+Tab-ի միջոցով:
Ներածություն
Որպեսզի ձեզ և ընթերցողներին փրկեք առաջնային աղբյուրները որոնելուց և կարդալուց, մեթոդների նկարագրությունների հղումները հիմնականում կլինեն Վիքիպեդիայում: Որպես կանոն, այս տեղեկատվությունը բավարար է մեթոդները ընդհանուր տերմիններով և դրանց կիրառման պայմանները հասկանալու համար: Մաթեմատիկական մեթոդների էությունը հասկանալու համար հետևեք ավելի հեղինակավոր հրապարակումների հղումներին, որոնք կարող եք գտնել յուրաքանչյուր հոդվածի վերջում կամ ձեր սիրելի որոնման համակարգում:
Այսպիսով, scipy.optimize մոդուլը ներառում է հետևյալ ընթացակարգերի իրականացումը.
- Մի քանի փոփոխականների սկալյար ֆունկցիաների պայմանական և անվերապահ նվազագույնիում (նվազագույն)՝ օգտագործելով տարբեր ալգորիթմներ (Nelder-Mead simplex, BFGS, Newton conjugate gradients, и )
- Համաշխարհային օպտիմիզացում (օրինակ. , )
- Նվազագույնի հասցնել մնացորդները (նվազագույն_քառակուսիներ) և կորի տեղադրման ալգորիթմներ՝ օգտագործելով ոչ գծային նվազագույն քառակուսիները (կորի_համապատասխանում)
- Նվազագույնի հասցնել մեկ փոփոխականի սկալյար ֆունկցիաները (minim_scalar) և գտնել արմատներ (root_scalar)
- Հավասարումների համակարգի (արմատ) բազմաչափ լուծիչներ՝ օգտագործելով տարբեր ալգորիթմներ (հիբրիդ Փաուել, կամ լայնածավալ մեթոդներ, ինչպիսիք են ).
Այս հոդվածում մենք կքննարկենք միայն առաջին կետը այս ամբողջ ցանկից:
Մի քանի փոփոխականների սկալյար ֆունկցիայի անվերապահ նվազագույնիացում
Scipy.optimize փաթեթից նվազագույն ֆունկցիան ապահովում է ընդհանուր ինտերֆեյս մի քանի փոփոխականների սկալային ֆունկցիաների պայմանական և անվերապահ նվազագույնի հասցնելու խնդիրների լուծման համար: Որպեսզի ցույց տանք, թե ինչպես է այն աշխատում, մեզ անհրաժեշտ կլինի մի քանի փոփոխականների համապատասխան ֆունկցիա, որը մենք տարբեր կերպ կնվազեցնենք:
Այս նպատակների համար կատարյալ է N փոփոխականների Rosenbrock ֆունկցիան, որն ունի ձև.
Չնայած այն հանգամանքին, որ Rosenbrock ֆունկցիան և նրա Jacobi և Hessian մատրիցները (համապատասխանաբար առաջին և երկրորդ ածանցյալները) արդեն սահմանված են 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 ձևով գծենք երկու փոփոխականների Rosenbrock ֆունկցիայի արժեքները:
Նկարչական ծածկագիր
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 է , եկեք դիտենք օրինակներ, թե ինչպես կարելի է որոշել Rosenbrock ֆունկցիայի նվազագույն արժեքը՝ օգտագործելով տարբեր scipy.optimize ընթացակարգեր։
Nelder-Mead simplex մեթոդ
Թող 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.]Սիմպլեքս մեթոդը հստակ սահմանված և բավականին հարթ գործառույթը նվազագույնի հասցնելու ամենապարզ միջոցն է: Այն չի պահանջում ֆունկցիայի ածանցյալների հաշվարկ, բավական է նշել միայն դրա արժեքները։ Նելդեր-Միդ մեթոդը լավ ընտրություն է նվազագույնի հասցնելու պարզ խնդիրների համար: Այնուամենայնիվ, քանի որ այն չի օգտագործում գրադիենտ գնահատումներ, նվազագույնը գտնելու համար կարող է ավելի երկար տևել:
Փաուելի մեթոդ
Մեկ այլ օպտիմալացման ալգորիթմ, որում հաշվարկվում են միայն ֆունկցիայի արժեքները . Այն օգտագործելու համար նվազագույն ֆունկցիայի մեջ պետք է սահմանել մեթոդ = «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.]Բրոյդեն-Ֆլետչեր-Գոլդֆարբ-Շաննո (BFGS) ալգորիթմ
Լուծմանը ավելի արագ կոնվերգենցիա ստանալու համար ընթացակարգը օգտագործում է օբյեկտիվ ֆունկցիայի գրադիենտը։ Գրադիենտը կարող է սահմանվել որպես ֆունկցիա կամ հաշվարկվել՝ օգտագործելով առաջին կարգի տարբերությունները: Ամեն դեպքում, BFGS մեթոդը սովորաբար պահանջում է ավելի քիչ ֆունկցիայի կանչեր, քան simplex մեթոդը:
Եկեք գտնենք Ռոզենբրոկ ֆունկցիայի ածանցյալը վերլուծական ձևով.
Այս արտահայտությունը վավեր է բոլոր փոփոխականների ածանցյալների համար, բացառությամբ առաջինի և վերջինի, որոնք սահմանվում են հետևյալ կերպ.
Եկեք նայենք 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]Կոնյուգացիոն գրադիենտ ալգորիթմ (Նյուտոն)
Ալգորիթմ Նյուտոնի փոփոխված մեթոդ է։
Նյուտոնի մեթոդը հիմնված է տեղական տարածքում ֆունկցիան երկրորդ աստիճանի բազմանդամով մոտավորելու վրա.
որտեղ երկրորդ ածանցյալների մատրիցն է (Հեսսիական մատրիցա, Հեսսյան)։
Եթե Հեսսիանը դրական որոշակի է, ապա այս ֆունկցիայի տեղական նվազագույնը կարելի է գտնել՝ քառակուսի ձևի զրոյական գրադիենտը հավասարեցնելով զրոյի։ Արդյունքը կլինի արտահայտությունը.
Հակադարձ Հեսսիանը հաշվարկվում է խոնարհված գրադիենտ մեթոդով: Ռոզենբրոկ ֆունկցիան նվազագույնի հասցնելու համար այս մեթոդի կիրառման օրինակ տրված է ստորև: 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]Օրինակ Հեսսիի արտադրական ֆունկցիայի սահմանմամբ և կամայական վեկտորով
Իրական աշխարհի խնդիրների դեպքում ամբողջ Հեսսի մատրիցը հաշվելը և պահպանելը կարող է պահանջել զգալի ժամանակ և հիշողության ռեսուրսներ: Այս դեպքում իրականում կարիք չկա նշելու բուն Հեսսիական մատրիցը, քանի որ նվազագույնի հասցնելու ընթացակարգը պահանջում է միայն մեկ այլ կամայական վեկտորի հետ Հեսսիի արտադրյալին հավասար վեկտոր: Այսպիսով, հաշվողական տեսանկյունից շատ նախընտրելի է անմիջապես սահմանել մի ֆունկցիա, որը վերադարձնում է Հեսսիի արտադրյալի արդյունքը կամայական վեկտորով։
Դիտարկենք 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 մեթոդի նման, Կրիլովի տիպի մեթոդները հարմար են լայնածավալ խնդիրների լուծման համար, քանի որ դրանք օգտագործում են միայն մատրիցա-վեկտորային արտադրանքներ: Դրանց էությունն այն է, որ խնդիրը լուծվի վստահության տարածաշրջանում, որը սահմանափակված է կտրված Կրիլովյան ենթատարածքով: Անորոշ խնդիրների դեպքում ավելի լավ է օգտագործել այս մեթոդը, քանի որ այն օգտագործում է ավելի փոքր թվով ոչ գծային կրկնություններ՝ յուրաքանչյուր ենթախնդիրի համար մատրիցա-վեկտոր արտադրանքների ավելի փոքր քանակի պատճառով՝ համեմատած trust-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) հարմար են լայնածավալ խնդիրների լուծման համար (հազարավոր փոփոխականներով): Դա պայմանավորված է այն հանգամանքով, որ հիմքում ընկած կոնյուգացիոն գրադիենտ ալգորիթմը ենթադրում է հակադարձ Հեսսի մատրիցի մոտավոր որոշում։ Լուծումը գտնվում է կրկնվող՝ առանց հեսիականի բացահայտ ընդլայնման։ Քանի որ անհրաժեշտ է միայն ֆունկցիա սահմանել Հեսսիանի և կամայական վեկտորի արտադրյալի համար, այս ալգորիթմը հատկապես լավ է նոսր (շերտավոր անկյունագծով) մատրիցների հետ աշխատելու համար: Սա ապահովում է հիշողության ցածր ծախսեր և ժամանակի զգալի խնայողություն:
Միջին չափի խնդիրների դեպքում Hessian-ի պահպանման և ֆակտորինգի արժեքը կարևոր չէ: Սա նշանակում է, որ հնարավոր է լուծում ստանալ ավելի քիչ կրկնություններով՝ գրեթե ճշգրիտ լուծելով վստահության շրջանի ենթախնդիրները։ Դա անելու համար որոշ ոչ գծային հավասարումներ լուծվում են կրկնվող յուրաքանչյուր քառակուսի ենթախնդրի համար: Նման լուծումը սովորաբար պահանջում է Հեսսիական մատրիցայի 3 կամ 4 Չոլեսկի տարրալուծում։ Արդյունքում, մեթոդը համընկնում է ավելի քիչ կրկնություններով և պահանջում է ավելի քիչ օբյեկտիվ ֆունկցիայի հաշվարկներ, քան ներդրված վստահության շրջանի մյուս մեթոդները: Այս ալգորիթմը միայն ենթադրում է ամբողջական Հեսսիական մատրիցի որոշումը և չի աջակցում Հեսսիանի արտադրյալ ֆունկցիան և կամայական վեկտորն օգտագործելու կարողությանը:
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-ի միջոցով հավասարումների համակարգի արմատները գտնելու մասին: փաթեթ.
Source:
Source: www.habr.com