🥇SciPy, pag-optimize

Ang SciPy (gipahayag nga sai pie) usa ka pakete sa aplikasyon sa matematika base sa extension sa Numpy Python. Uban sa SciPy, ang imong interactive nga sesyon sa Python mahimong parehas nga kompleto nga siyensya sa datos ug komplikado nga sistema sa prototyping nga palibot sama sa MATLAB, IDL, Octave, R-Lab, ug SciLab. Karon gusto nako nga hisgutan sa makadiyot kung giunsa ang paggamit sa pipila ka ilado nga mga algorithm sa pag-optimize sa package nga scipy.optimize. Ang mas detalyado ug pinakabag-o nga tabang sa paggamit sa mga function kanunay makuha gamit ang help() command o gamit ang Shift+Tab.

Pasiuna

Aron maluwas ang imong kaugalingon ug ang mga magbabasa gikan sa pagpangita ug pagbasa sa mga nag-unang tinubdan, ang mga link sa mga deskripsyon sa mga pamaagi anaa sa Wikipedia. Ingon sa usa ka lagda, kini nga kasayuran igo na aron masabtan ang mga pamaagi sa kinatibuk-ang termino ug ang mga kondisyon alang sa ilang aplikasyon. Aron masabtan ang esensya sa mga pamaagi sa matematika, sunda ang mga link sa mas may awtoridad nga mga publikasyon, nga makita sa katapusan sa matag artikulo o sa imong paborito nga search engine.

Busa, ang scipy.optimize module naglakip sa pagpatuman sa mosunod nga mga pamaagi:

Conditional ug unconditional minimization sa scalar functions sa pipila ka variables (minim) gamit ang lain-laing algorithms (Nelder-Mead simplex, BFGS, Newton conjugate gradients, COBYLA и SLSQP)
Global optimization (pananglitan: basinhopping, diff_evolution)
Pagminus sa mga nahabilin MNC (least_squares) ug curve fitting algorithms gamit ang nonlinear least squares (curve_fit)
Pagminus sa scalar function sa usa ka variable (minim_scalar) ug pagpangita sa mga gamut (root_scalar)
Multidimensional solvers sa sistema sa mga equation (gamut) gamit ang lain-laing mga algorithm (hybrid Powell, Levenberg-Marquardt o dagkong mga paagi sama sa Newton-Krylov).

Niini nga artikulo atong hisgotan lamang ang unang butang gikan niining tibuok listahan.

Walay kondisyon nga pagminus sa usa ka scalar function sa daghang mga variable

Ang minimum nga function gikan sa scipy.optimize nga pakete naghatag og usa ka kinatibuk-ang interface alang sa pagsulbad sa kondisyon ug walay kondisyon nga pagminus nga mga problema sa scalar function sa daghang mga variable. Aron ipakita kung giunsa kini molihok, kinahanglan namon ang usa ka angay nga function sa daghang mga variable, nga among paminusan sa lainlaing mga paagi.

Alang niini nga mga katuyoan, ang Rosenbrock function sa N variables hingpit, nga adunay porma:

Bisan pa sa kamatuoran nga ang Rosenbrock function ug ang Jacobi ug Hessian matrices (ang una ug ikaduha nga derivatives, matag usa) gihubit na sa scipy.optimize nga pakete, kita mismo ang maghubit niini.

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)

Alang sa katin-awan, atong idrowing sa 3D ang mga kantidad sa function sa Rosenbrock sa duha ka mga variable.

Kodigo sa pagdrowing

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()

Nahibal-an daan nga ang minimum mao ang 0 sa , atong tan-awon ang mga pananglitan kon unsaon pagtino ang minimum nga bili sa Rosenbrock function gamit ang nagkalain-laing pamaagi sa scipy.optimize.

Nelder-Mead simplex nga pamaagi

Himoa nga adunay inisyal nga punto x0 sa 5-dimensional nga luna. Atong pangitaon ang minimum nga punto sa Rosenbrock function nga labing duol niini gamit ang algorithm Nelder-Mead simplex (ang algorithm gipiho ingon nga kantidad sa parameter nga pamaagi):

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

Ang simplex nga pamaagi mao ang pinakasimple nga paagi sa pagpamenos sa usa ka klaro nga gihubit ug medyo hapsay nga function. Wala kini magkinahanglan og kalkulasyon sa mga derivatives sa usa ka function; igo na nga ipiho ang mga kantidad niini. Ang pamaagi sa Nelder-Mead usa ka maayong pagpili alang sa yano nga mga problema sa pagminus. Bisan pa, tungod kay wala kini mogamit mga gradient nga pagbanabana, mahimo’g magdugay aron makit-an ang minimum.

Powell nga pamaagi

Ang lain nga algorithm sa pag-optimize diin ang mga kantidad sa function ra ang kalkulado Pamaagi ni Powell. Aron magamit kini, kinahanglan nimo nga itakda ang pamaagi = 'powell' sa minim function.

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) algorithm

Aron makakuha og mas paspas nga panagtapok sa usa ka solusyon, ang pamaagi BFGS naggamit sa gradient sa tumong nga function. Ang gradient mahimong ipiho isip usa ka function o kalkulado gamit ang first order differences. Sa bisan unsang kaso, ang pamaagi sa BFGS kasagarang nanginahanglan gamay nga tawag sa function kaysa sa simplex nga pamaagi.

Atong pangitaon ang derivative sa Rosenbrock function sa analytical nga porma:

Kini nga ekspresyon balido alang sa mga gigikanan sa tanan nga mga variable gawas sa una ug katapusan, nga gihubit ingon:

Atong tan-awon ang Python function nga nagkalkula niini nga gradient:

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

Ang gradient kalkulasyon function gipiho isip ang bili sa jac parameter sa minimum function, sama sa gipakita sa ubos.

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]

Conjugate gradient algorithm (Newton)

Ang algorithm Ang conjugate gradients ni Newton usa ka giusab nga pamaagi ni Newton.
Ang pamaagi ni Newton gibase sa pagbanabana sa usa ka function sa usa ka lokal nga lugar pinaagi sa usa ka polynomial sa ikaduhang degree:

diin mao ang matrix sa ikaduhang derivatives (Hessian matrix, Hessian).
Kung ang Hessian positibo nga tino, nan ang lokal nga minimum niini nga function makit-an pinaagi sa pag-equate sa zero gradient sa quadratic nga porma sa zero. Ang resulta mao ang ekspresyon:

Ang inverse Hessian kalkulado gamit ang conjugate gradient method. Ang usa ka pananglitan sa paggamit niini nga pamaagi aron maminusan ang function sa Rosenbrock gihatag sa ubos. Aron magamit ang Newton-CG nga pamaagi, kinahanglan nimong itakda ang usa ka function nga nagkalkula sa Hessian.
Ang Hessian sa Rosenbrock function sa analytical nga porma katumbas sa:

diin и , ipasabot ang matrix .

Ang nahabilin nga dili zero nga mga elemento sa matrix parehas sa:

Pananglitan, sa lima ka dimensyon nga luna N = 5, ang Hessian matrix alang sa Rosenbrock function adunay porma sa usa ka banda:

Kodigo nga nagkalkula niini nga Hessian uban sa kodigo para sa pagpamenos sa Rosenbrock function gamit ang conjugate gradient (Newton) nga pamaagi:

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]

Usa ka pananglitan nga adunay kahulugan sa function sa produkto sa Hessian ug usa ka arbitraryong vector

Sa mga problema sa tinuud nga kalibutan, ang pag-compute ug pagtipig sa tibuuk nga matrix sa Hessian mahimong magkinahanglan daghang oras ug mga kapanguhaan sa panumduman. Sa kini nga kaso, sa tinuud dili kinahanglan nga ipiho ang Hessian matrix mismo, tungod kay ang pamaagi sa pagminus nagkinahanglan lamang ug vector nga katumbas sa produkto sa Hessian nga adunay laing arbitraryong vector. Busa, gikan sa usa ka computational nga punto sa panglantaw, kini mao ang mas maayo nga diha-diha dayon sa paghubit sa usa ka function nga mobalik sa resulta sa produkto sa Hessian uban sa usa ka arbitraryong vector.

Ikonsiderar ang hess function, nga nagkuha sa minimization vector isip unang argumento, ug usa ka arbitraryong vector isip ikaduhang argumento (uban sa ubang mga argumento sa function nga maminusan). Sa among kaso, ang pagkalkula sa produkto sa Hessian sa Rosenbrock function nga adunay usa ka arbitraryong vector dili kaayo lisud. Kung p usa ka arbitraryong vector, unya ang produkto murag:

Ang function nga nagkalkula sa produkto sa Hessian ug usa ka arbitraryong vector gipasa ingon nga kantidad sa argumento sa hessp sa pagminus nga function:

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

Conjugate gradient trust region algorithm (Newton)

Ang dili maayo nga pagkondisyon sa Hessian matrix ug dili husto nga mga direksyon sa pagpangita mahimong hinungdan nga ang conjugate gradient algorithm ni Newton dili epektibo. Sa ingon nga mga kaso, gipalabi ang gihatag paagi sa pagsalig sa rehiyon (pagsalig-rehiyon) conjugate Newton gradients.

Pananglitan sa kahulugan sa Hessian matrix:

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

Panig-ingnan sa function sa produkto sa Hessian ug usa ka arbitraryong vector:

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

Krylov type nga mga pamaagi

Sama sa paagi sa pagsalig-ncg, ang Krylov-type nga mga pamaagi haom kaayo alang sa pagsulbad sa dagkong mga problema tungod kay gigamit lamang nila ang mga produkto nga matrix-vector. Ang ilang esensya mao ang pagsulbad sa usa ka problema sa usa ka rehiyon sa pagsalig nga limitado sa usa ka giputol nga subspace sa Krylov. Alang sa dili sigurado nga mga problema, mas maayo nga gamiton kini nga pamaagi, tungod kay naggamit kini usa ka gamay nga gidaghanon sa mga nonlinear nga pag-uli tungod sa gamay nga gidaghanon sa mga produkto nga matrix-vector matag subproblem, kung itandi sa paagi sa pagsalig-ncg. Dugang pa, ang solusyon sa quadratic subproblem mas tukma kay sa paggamit sa paagi sa pagsalig-ncg.
Pananglitan sa kahulugan sa Hessian matrix:

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

Panig-ingnan sa function sa produkto sa Hessian ug usa ka arbitraryong vector:

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

Algorithm alang sa gibanabana nga solusyon sa rehiyon sa pagsalig

Ang tanan nga mga pamaagi (Newton-CG, pagsalig-ncg ug pagsalig-krylov) haum kaayo alang sa pagsulbad sa dagkong mga problema (uban sa liboan ka mga variable). Kini tungod sa kamatuoran nga ang nagpahiping conjugate gradient algorithm nagpasabot sa usa ka gibanabana nga determinasyon sa inverse Hessian matrix. Ang solusyon nakit-an nga nagbalikbalik, nga wala’y klaro nga pagpalapad sa Hessian. Tungod kay kinahanglan ra nimo nga ipasabut ang usa ka function alang sa produkto sa usa ka Hessian ug usa ka arbitraryong vector, kini nga algorithm labi ka maayo alang sa pagtrabaho sa mga gamay (band diagonal) nga matrice. Naghatag kini og mubu nga gasto sa memorya ug hinungdanon nga pagtipig sa oras.

Alang sa medium-sized nga mga problema, ang gasto sa pagtipig ug pag-factor sa Hessian dili kritikal. Kini nagpasabut nga posible nga makakuha usa ka solusyon sa mas gamay nga mga pag-uli, nga masulbad ang mga subproblema sa rehiyon sa pagsalig nga hapit eksakto. Aron mahimo kini, pipila ka mga nonlinear nga equation ang gisulbad nga balikbalik alang sa matag quadratic subproblem. Ang ingon nga solusyon kasagaran nanginahanglan 3 o 4 nga Cholesky decompositions sa Hessian matrix. Ingon usa ka sangputanan, ang pamaagi naghiusa sa mas gamay nga mga pag-uli ug nanginahanglan gamay nga kalkulasyon sa katuyoan nga function kaysa sa uban nga gipatuman nga mga pamaagi sa rehiyon sa pagsalig. Kini nga algorithm naglakip lamang sa pagdeterminar sa kompletong Hessian matrix ug dili pagsuporta sa abilidad sa paggamit sa product function sa Hessian ug usa ka arbitraryong vector.

Panig-ingnan sa pagminus sa function sa 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.])

Mohunong na tingali ta didto. Sa sunod nga artikulo sulayan nako nga isulti ang labing makapaikag nga mga butang bahin sa pagminus sa kondisyon, ang aplikasyon sa pagminus sa pagsulbad sa mga problema sa pagbanabana, pagminus sa usa ka function sa usa ka variable, arbitraryong mga minimizer, ug pagpangita sa mga ugat sa usa ka sistema sa mga equation gamit ang scipy.optimize pakete.

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

Source: www.habr.com

SciPy, pag-optimize