ProHoster > Blogs > interneta ziņas > SciPy, optimizācija

SciPy, optimizācija

SciPy, optimizācija

SciPy (izrunā sai pie) ir matemātiskas lietojumprogrammas pakotne, kuras pamatā ir Numpy Python paplaÅ”inājums. Izmantojot SciPy, jÅ«su interaktÄ«vā Python sesija kļūst par tādu paÅ”u pilnÄ«gu datu zinātni un sarežģītu sistēmu prototipÄ“Å”anas vidi kā MATLAB, IDL, Octave, R-Lab un SciLab. Å odien es vēlos Ä«si runāt par to, kā izmantot dažus labi zināmus optimizācijas algoritmus scipy.optimize pakotnē. Detalizētāku un jaunāko palÄ«dzÄ«bu par funkciju lietoÅ”anu vienmēr var iegÅ«t, izmantojot komandu help() vai izmantojot taustiņu kombināciju Shift+Tab.

Ievads

Lai pasargātu sevi un lasÄ«tājus no primāro avotu meklÄ“Å”anas un lasÄ«Å”anas, saites uz metožu aprakstiem galvenokārt bÅ«s Vikipēdijā. Parasti Ŕī informācija ir pietiekama, lai vispārÄ«gi izprastu metodes un to piemēroÅ”anas nosacÄ«jumus. Lai saprastu matemātisko metožu bÅ«tÄ«bu, sekojiet saitēm uz autoritatÄ«vākām publikācijām, kuras var atrast katra raksta beigās vai savā iecienÄ«tākajā meklētājā.

Tātad modulis scipy.optimize ietver Ŕādu procedūru ievieŔanu:

  1. Vairāku mainÄ«go skalāro funkciju nosacÄ«ta un beznosacÄ«juma minimizÄ“Å”ana (minimums), izmantojot dažādus algoritmus (Nelder-Mead simplex, BFGS, Newton konjugāta gradienti, KOBILA Šø SLSQP)
  2. Globālā optimizācija (piemēram: peldÄ“Å”ana baseinā, diff_evolution)
  3. Atlikumu samazināŔana MNC (least_squares) un lÄ«kņu pielāgoÅ”anas algoritmi, izmantojot nelineāros mazākos kvadrātus (curve_fit)
  4. Viena mainÄ«gā skalāro funkciju samazināŔana (minim_scalar) un sakņu meklÄ“Å”ana (root_scalar)
  5. Daudzdimensionāli vienādojumu sistēmas (saknes) risinātāji, izmantojot dažādus algoritmus (hibrīds Pauels, Levenbergs-Marquardt vai liela mēroga metodes, piemēram, Ņūtons-Krilovs).

Å ajā rakstā mēs apskatÄ«sim tikai pirmo vienumu no visa Ŕī saraksta.

Vairāku mainīgo skalārās funkcijas beznosacījumu samazināŔana

Minimālā funkcija no pakotnes scipy.optimize nodroÅ”ina vispārÄ«gu saskarni vairāku mainÄ«go skalāro funkciju nosacÄ«tās un beznosacÄ«juma minimizÄ“Å”anas problēmu risināŔanai. Lai parādÄ«tu, kā tas darbojas, mums bÅ«s nepiecieÅ”ama piemērota funkcija no vairākiem mainÄ«gajiem, kurus mēs dažādos veidos samazināsim.

Šiem nolūkiem ir ideāla N mainīgo Rozenbroka funkcija, kurai ir Ŕāda forma:

SciPy, optimizācija

Neskatoties uz to, ka Rozenbroka funkcija un tās Jacobi un Hessian matricas (attiecÄ«gi pirmais un otrais atvasinājums) jau ir definētas scipy.optimize pakotnē, mēs to definēsim paÅ”i.

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)

Skaidrības labad uzzīmēsim 3D divu mainīgo Rozenbroka funkcijas vērtības.

ZīmēŔanas kods

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, optimizācija

Jau iepriekÅ” zinot, ka minimums ir 0 plkst SciPy, optimizācija, apskatÄ«sim piemērus, kā noteikt Rozenbroka funkcijas minimālo vērtÄ«bu, izmantojot dažādas scipy.optimize procedÅ«ras.

Neldera-Mīda vienkārŔā metode

Lai 0-dimensiju telpā ir sākuma punkts x5. Izmantojot algoritmu, atradīsim tai tuvāko Rozenbroka funkcijas minimālo punktu Nelder-Mead simplex (algoritms ir norādīts kā metodes parametra vērtība):

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

Simpleksā metode ir vienkārŔākais veids, kā samazināt skaidri definētu un diezgan vienmērÄ«gu funkciju. Tam nav jāaprēķina funkcijas atvasinājumi, pietiek norādÄ«t tikai tās vērtÄ«bas. Nelder-Mead metode ir laba izvēle vienkārŔām minimizÄ“Å”anas problēmām. Tomēr, tā kā tajā netiek izmantoti gradienta aprēķini, minimuma atraÅ”ana var aizņemt ilgāku laiku.

Pauela metode

Vēl viens optimizācijas algoritms, kurā tiek aprēķinātas tikai funkciju vērtības, ir Pauela metode. Lai to izmantotu, minimālajā funkcijā jāiestata metode = '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) algoritms

Lai panāktu ātrāku konverÄ£enci ar risinājumu, procedÅ«ra BFGS izmanto mērÄ·a funkcijas gradientu. Gradientu var norādÄ«t kā funkciju vai aprēķināt, izmantojot pirmās kārtas atŔķirÄ«bas. Jebkurā gadÄ«jumā BFGS metode parasti prasa mazāk funkciju izsaukumu nekā simpleksa metode.

Ļaujiet mums atrast Rozenbroka funkcijas atvasinājumu analītiskā formā:

SciPy, optimizācija

SciPy, optimizācija

Šī izteiksme ir derīga visu mainīgo atvasinājumiem, izņemot pirmo un pēdējo, kas definēti kā:

SciPy, optimizācija

SciPy, optimizācija

ApskatÄ«sim Python funkciju, kas aprēķina Å”o gradientu:

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

Gradienta aprēķina funkcija ir norādīta kā minimuma funkcijas jac parametra vērtība, kā parādīts tālāk.

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]

Konjugētā gradienta algoritms (Ņūtons)

Algoritms Ņūtona konjugācijas gradienti ir modificēta Ņūtona metode.
Ņūtona metode balstās uz funkcijas tuvināŔanu lokālā apgabalā ar otrās pakāpes polinomu:

SciPy, optimizācija

kur SciPy, optimizācija ir otro atvasinājumu matrica (Hesijas matrica, Hesijas matrica).
Ja Hess ir pozitīvs noteikts, tad Ŕīs funkcijas lokālo minimumu var atrast, pielīdzinot kvadrātiskās formas nulles gradientu nullei. Rezultāts būs izteiksme:

SciPy, optimizācija

Apgriezto Hesenes vērtÄ«bu aprēķina, izmantojot konjugāta gradienta metodi. Piemērs Ŕīs metodes izmantoÅ”anai Rosenbrock funkcijas samazināŔanai ir sniegts zemāk. Lai izmantotu Ņūtona-CG metodi, ir jānorāda funkcija, kas aprēķina Hesenes.
Rozenbroka funkcijas Hesene analītiskā formā ir vienāda ar:

SciPy, optimizācija

SciPy, optimizācija

kur SciPy, optimizācija Šø SciPy, optimizācija, definējiet matricu SciPy, optimizācija.

AtlikuŔie matricas elementi, kas nav nulle, ir vienādi ar:

SciPy, optimizācija

SciPy, optimizācija

SciPy, optimizācija

SciPy, optimizācija

Piemēram, piecdimensiju telpā N = 5 Rozenbroka funkcijas Hesenes matricai ir joslas forma:

SciPy, optimizācija

Kods, kas aprēķina Å”o Hesenes vērtÄ«bu kopā ar kodu Rozenbroka funkcijas minimizÄ“Å”anai, izmantojot konjugētā gradienta (Ņūtona) metodi:

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]

Piemērs ar Hesenes un patvaļīga vektora reizinājuma funkcijas definīciju

Reālās pasaules problēmās visas Hesenes matricas aprēķināŔana un glabāŔana var prasÄ«t ievērojamus laika un atmiņas resursus. Å ajā gadÄ«jumā faktiski nav nepiecieÅ”ams norādÄ«t paÅ”u Hesenes matricu, jo minimizÄ“Å”anas procedÅ«rai nepiecieÅ”ams tikai vektors, kas vienāds ar Hesenes reizinājumu ar citu patvaļīgu vektoru. Tādējādi no skaitļoÅ”anas viedokļa ir daudz labāk nekavējoties definēt funkciju, kas atgriež Hesenes reizinājuma rezultātu ar patvaļīgu vektoru.

Apsveriet Hesa ā€‹ā€‹funkciju, kas izmanto minimizÄ“Å”anas vektoru kā pirmo argumentu un patvaļīgu vektoru kā otro argumentu (kopā ar citiem minimizējamās funkcijas argumentiem). MÅ«su gadÄ«jumā Rozenbroka funkcijas Hesenes reizinājuma aprēķināŔana ar patvaļīgu vektoru nav Ä«paÅ”i sarežģīta. Ja p ir patvaļīgs vektors, tad reizinājums SciPy, optimizācija izskatās kā:

SciPy, optimizācija

Funkcija, kas aprēķina Hesenes un patvaļīga vektora reizinājumu, tiek nodota kā hessp argumenta vērtÄ«ba minimizÄ“Å”anas funkcijai:

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

Konjugētā gradienta uzticamības reģiona algoritms (Ņūtons)

Slikta Hesenes matricas kondicionÄ“Å”ana un nepareizi meklÄ“Å”anas virzieni var izraisÄ«t Ņūtona konjugētā gradienta algoritma neefektivitāti. Šādos gadÄ«jumos priekÅ”roka tiek dota uzticÄ«bas reÄ£iona metode (uzticÄ«bas reÄ£ions) konjugāts Ņūtona gradienti.

Piemērs ar Hesenes matricas definīciju:

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

Piemērs ar Hesenes reizinājuma funkciju un patvaļīgu vektoru:

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

Krilova tipa metodes

Tāpat kā uzticÄ«bas-ncg metode, arÄ« Krilova tipa metodes ir labi piemērotas liela mēroga problēmu risināŔanai, jo tajās tiek izmantoti tikai matricas vektoru produkti. To bÅ«tÄ«ba ir atrisināt problēmu uzticÄ«bas reÄ£ionā, kuru ierobežo saÄ«sināta Krilova apakÅ”telpa. Neskaidrām problēmām labāk izmantot Å”o metodi, jo tā izmanto mazāku nelineāro iterāciju skaitu, jo vienā apakÅ”problēmā ir mazāks matricas vektoru produktu skaits, salÄ«dzinot ar uzticÄ«bas-ncg metodi. Turklāt kvadrātiskās apakÅ”problēmas risinājums tiek atrasts precÄ«zāk, nekā izmantojot uzticÄ«bas-ncg metodi.
Piemērs ar Hesenes matricas definīciju:

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

Piemērs ar Hesenes reizinājuma funkciju un patvaļīgu vektoru:

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

Algoritms aptuvenam risinājumam ticamības reģionā

Visas metodes (Newton-CG, trust-ncg un trust-krylov) ir labi piemērotas liela mēroga problēmu risināŔanai (ar tÅ«kstoÅ”iem mainÄ«go). Tas ir saistÄ«ts ar faktu, ka pamatā esoÅ”ais konjugāta gradienta algoritms paredz aptuvenu apgrieztās Heses matricas noteikÅ”anu. Risinājums tiek atrasts iteratÄ«vi, bez tieÅ”as Hesenes valodas paplaÅ”ināŔanas. Tā kā funkcija ir jādefinē tikai Hesenes un patvaļīga vektora reizinājumam, Å”is algoritms ir Ä«paÅ”i piemērots darbam ar retām (joslas diagonāles) matricām. Tas nodroÅ”ina zemas atmiņas izmaksas un ievērojamu laika ietaupÄ«jumu.

Vidēja izmēra problēmām Hessian uzglabāŔanas un faktoringa izmaksas nav kritiskas. Tas nozÄ«mē, ka risinājumu ir iespējams iegÅ«t mazākās iterācijās, gandrÄ«z precÄ«zi atrisinot uzticÄ«bas reÄ£iona apakÅ”problēmas. Lai to izdarÄ«tu, katrai kvadrātiskajai apakÅ”problēmai iteratÄ«vi tiek atrisināti daži nelineāri vienādojumi. Šādam risinājumam parasti ir nepiecieÅ”ami 3 vai 4 Hesenes matricas Cholesky dekompozÄ«cijas. Rezultātā metode konverģē mazākās iterācijās un prasa mazāk mērÄ·a funkciju aprēķinu nekā citas ieviestās ticamÄ«bas apgabala metodes. Å is algoritms ietver tikai pilnÄ«gas Hesenes matricas noteikÅ”anu un neatbalsta iespēju izmantot Hesenes un patvaļīga vektora reizinājuma funkciju.

Piemērs ar Rosenbrock funkcijas minimizÄ“Å”anu:

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

DroÅ”i vien pie tā arÄ« apstāsimies. Nākamajā rakstā mēģināŔu pastāstÄ«t interesantāko par nosacÄ«to minimizÄ“Å”anu, minimizÄ“Å”anas pielietojumu aproksimācijas uzdevumu risināŔanā, viena mainÄ«gā funkcijas minimizÄ“Å”anu, patvaļīgiem minimizatoriem un vienādojumu sistēmas sakņu atraÅ”anu, izmantojot scipy.optimize. iepakojums.

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

Avots: www.habr.com

Pievieno komentāru