ProHoster > Π‘Π»ΠΎΠ³ > warta internet > SciPy, optimasi

SciPy, optimasi

SciPy, optimasi

SciPy (pocapan sai pie) iku paket aplikasi matematika adhedhasar extension Numpy Python. Kanthi SciPy, sesi Python interaktif sampeyan dadi ilmu data lengkap lan lingkungan prototipe sistem kompleks sing padha karo MATLAB, IDL, Octave, R-Lab, lan SciLab. Dina iki aku arep ngomong sedhela babagan carane nggunakake sawetara algoritma optimasi sing kondhang ing paket scipy.optimize. Bantuan luwih rinci lan up-to-date babagan nggunakake fungsi tansah bisa dipikolehi nggunakake printah bantuan () utawa nggunakake Shift + Tab.

Pambuka

Kanggo nylametake awake dhewe lan para pamaca saka nggoleki lan maca sumber-sumber primer, pranala menyang deskripsi metode utamane ana ing Wikipedia. Minangka aturan, informasi iki cukup kanggo ngerti cara ing syarat-syarat umum lan kondisi aplikasi. Kanggo mangerteni inti saka metode matematika, tututi pranala menyang publikasi sing luwih otoritatif, sing bisa ditemokake ing pungkasan saben artikel utawa ing mesin telusur favorit.

Dadi, modul scipy.optimize kalebu implementasine prosedur ing ngisor iki:

  1. Minimalisasi fungsi skalar kondisional lan tanpa syarat saka sawetara variabel (minim) nggunakake macem-macem algoritma (Nelder-Mead simplex, BFGS, gradien konjugat Newton, COBYLA ΠΈ SLSQP)
  2. Optimasi global (contone: basinhopping, diff_evolution)
  3. Minimizing residual MNC (least_squares) lan algoritma pas kurva nggunakake kuadrat paling ora linear (curve_fit)
  4. Minimisasi fungsi skalar saka siji variabel (minim_scalar) lan nggoleki root (root_scalar)
  5. Pemecah multidimensi sistem persamaan (root) nggunakake macem-macem algoritma (hibrid Powell, Levenberg-Marquardt utawa cara skala gedhe kayata Newton-Krylov).

Ing artikel iki kita bakal nimbang mung item pisanan saka kabeh dhaftar iki.

Minimalisasi tanpa syarat fungsi skalar saka sawetara variabel

Fungsi minimal saka paket scipy.optimize nyedhiyakake antarmuka umum kanggo ngrampungake masalah minimalake kondisional lan tanpa syarat fungsi skalar saka sawetara variabel. Kanggo nduduhake cara kerjane, kita butuh fungsi sing cocog saka sawetara variabel, sing bakal dikurangi kanthi cara sing beda-beda.

Kanggo tujuan kasebut, fungsi Rosenbrock saka variabel N sampurna, sing nduweni wujud:

SciPy, optimasi

Senadyan kasunyatan manawa fungsi Rosenbrock lan matriks Jacobi lan Hessian (turunan pisanan lan kaloro, masing-masing) wis ditetepake ing paket scipy.optimize, kita bakal nemtokake dhewe.

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)

Kanggo gamblang, ayo digambar ing 3D nilai fungsi Rosenbrock saka rong variabel.

Kode gambar

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, optimasi

Ngerti ing advance sing minimal 0 ing SciPy, optimasi, ayo kang katon ing conto carane nemtokake nilai minimal saka fungsi Rosenbrock nggunakake macem-macem prosedur scipy.optimize.

Metode Nelder-Mead simplex

Ayo ana titik awal x0 ing spasi 5 dimensi. Ayo goleki titik minimal saka fungsi Rosenbrock sing paling cedhak nggunakake algoritma kasebut Nelder-Mead simplex (algoritma kasebut ditemtokake minangka nilai parameter metode):

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

Cara simplex minangka cara paling gampang kanggo nyilikake fungsi sing ditetepake kanthi jelas lan cukup lancar. Ora perlu ngitung turunan saka sawijining fungsi, cukup kanggo nemtokake nilai-nilai kasebut. Cara Nelder-Mead minangka pilihan sing apik kanggo masalah minimalisasi sing gampang. Nanging, amarga ora nggunakake prakiraan gradien, bisa uga butuh wektu sing luwih suwe kanggo nemokake minimal.

Metode Powell

Algoritma optimasi liyane sing mung diwilang nilai fungsi yaiku metode Powell. Kanggo nggunakake, sampeyan kudu nyetel method = 'powell' ing fungsi minimal.

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

Algoritma Broyden-Fletcher-Goldfarb-Shanno (BFGS).

Kanggo entuk konvergensi sing luwih cepet menyang solusi, prosedur kasebut BFGS nggunakake gradien fungsi objektif. Gradien bisa ditemtokake minangka fungsi utawa diwilang nggunakake beda urutan pisanan. Ing kasus apa wae, metode BFGS biasane mbutuhake panggilan fungsi luwih sithik tinimbang metode simpleks.

Ayo goleki turunan saka fungsi Rosenbrock ing wangun analitik:

SciPy, optimasi

SciPy, optimasi

Ekspresi iki bener kanggo turunan kabeh variabel kajaba sing pisanan lan pungkasan, sing ditetepake minangka:

SciPy, optimasi

SciPy, optimasi

Ayo goleki fungsi Python sing ngitung gradien iki:

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

Fungsi pitungan gradient ditemtokake minangka Nilai saka parameter jac saka fungsi minimal, minangka kapacak ing ngisor iki.

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]

Algoritma gradien konjugat (Newton)

Algoritma Gradien konjugasi Newton yaiku metode Newton sing diowahi.
Metode Newton didhasarake kanggo ngira-ngira fungsi ing wilayah lokal kanthi polinomial derajat kapindho:

SciPy, optimasi

ngendi SciPy, optimasi yaiku matriks saka turunan kapindho (matriks Hessian, Hessian).
Yen Hessian positif definite, banjur minimal lokal saka fungsi iki bisa ditemokakΓ© dening equating gradien nol saka wangun kuadrat kanggo nul. Asil bakal dadi ekspresi:

SciPy, optimasi

Hessian invers diwilang nggunakake metode gradien konjugat. Conto nggunakake cara iki kanggo nyilikake fungsi Rosenbrock diwenehi ngisor iki. Kanggo nggunakake metode Newton-CG, sampeyan kudu nemtokake fungsi sing ngitung Hessian.
Hessian saka fungsi Rosenbrock ing wangun analitis padha karo:

SciPy, optimasi

SciPy, optimasi

ngendi SciPy, optimasi ΠΈ SciPy, optimasi, nemtokake matriks SciPy, optimasi.

Unsur non-nol sing isih ana ing matriks padha karo:

SciPy, optimasi

SciPy, optimasi

SciPy, optimasi

SciPy, optimasi

Contone, ing spasi limang dimensi N = 5, matriks Hessian kanggo fungsi Rosenbrock nduweni wangun pita:

SciPy, optimasi

Kode sing ngitung Hessian iki bebarengan karo kode kanggo nyilikake fungsi Rosenbrock nggunakake cara conjugate gradien (Newton):

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]

Conto karo definisi fungsi produk saka Hessian lan vektor kasepakatan

Ing masalah nyata, komputasi lan nyimpen kabeh matriks Hessian bisa mbutuhake wektu lan sumber daya memori sing signifikan. Ing kasus iki, bener ora perlu kanggo nemtokake matriks Hessian dhewe, amarga prosedur minimization mbutuhake mung vektor witjaksono kanggo produk saka Hessian karo vektor kasepakatan liyane. Mangkono, saka sudut pandang komputasi, luwih becik kanggo nemtokake fungsi sing ngasilake asil saka produk Hessian kanthi vektor kasepakatan.

Coba fungsi hess, sing njupuk vektor minimisasi minangka argumen pisanan, lan vektor arbitrer minangka argumen kapindho (bebarengan karo argumen fungsi liyane sing bakal diminimalisir). Ing kasus kita, ngetung prodhuk saka fungsi Hessian saka Rosenbrock kanthi vektor sewenang-wenang ora angel banget. Yen p minangka vektor kasepakatan, banjur produk SciPy, optimasi katon kaya:

SciPy, optimasi

Fungsi sing ngitung produk saka Hessian lan vektor arbitrer diterusake minangka nilai argumen hessp menyang fungsi minimalake:

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

Algoritma wilayah kepercayaan gradien konjugat (Newton)

Pengkondisian matriks Hessian sing ora apik lan arah telusuran sing salah bisa nyebabake algoritma gradien konjugat Newton dadi ora efektif. Ing kasus kaya mengkono, preferensi diwenehi kanggo metode wilayah kepercayaan (wilayah kepercayaan) konjugasi gradien Newton.

Conto karo definisi matriks 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.]

Conto karo fungsi produk saka Hessian lan vektor arbitrer:

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

metode jinis Krylov

Kaya metode trust-ncg, metode Krylov-type cocok kanggo ngrampungake masalah skala gedhe amarga mung nggunakake produk matriks-vektor. Intine yaiku ngrampungake masalah ing wilayah kapercayan sing diwatesi dening subruang Krylov sing dipotong. Kanggo masalah sing ora mesthi, luwih becik nggunakake metode iki, amarga nggunakake jumlah iterasi nonlinear sing luwih cilik amarga jumlah produk matriks-vektor sing luwih cilik saben submasalah, dibandhingake karo metode kepercayaan-ncg. Kajaba iku, solusi kanggo subproblem kuadrat ditemokake luwih akurat tinimbang nggunakake metode trust-ncg.
Conto karo definisi matriks 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.]

Conto karo fungsi produk saka Hessian lan vektor arbitrer:

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

Algoritma kanggo solusi kira-kira ing wilayah kapercayan

Kabeh cara (Newton-CG, trust-ncg lan trust-krylov) cocok kanggo ngrampungake masalah skala gedhe (karo ewu variabel). Iki amarga kasunyatan manawa algoritma gradien konjugat sing ndasari nuduhake penentuan kira-kira matriks Hessian invers. Solusi kasebut ditemokake kanthi iteratif, tanpa ekspansi eksplisit saka Hessian. Amarga sampeyan mung kudu nemtokake fungsi kanggo produk saka Hessian lan vektor kasepakatan, algoritma iki utamanΓ© apik kanggo nggarap matriks jarang (band diagonal). Iki nyedhiyakake biaya memori sing sithik lan irit wektu sing signifikan.

Kanggo masalah ukuran medium, biaya nyimpen lan anjak Hessian ora kritis. Iki tegese sampeyan bisa entuk solusi ing iterasi sing luwih sithik, ngrampungake subproblem wilayah kepercayaan meh persis. Kanggo nindakake iki, sawetara persamaan nonlinier ditanggulangi kanthi iteratif kanggo saben submasalah kuadrat. Solusi kasebut biasane mbutuhake 3 utawa 4 dekomposisi Cholesky saka matriks Hessian. AkibatΓ©, cara converge ing iterasi luwih sithik lan mbutuhake petungan fungsi obyektif luwih sithik tinimbang metode wilayah kapercayan liyane. Algoritma iki mung melu nemtokake matriks Hessian sing lengkap lan ora ndhukung kemampuan kanggo nggunakake fungsi produk saka Hessian lan vektor sing sewenang-wenang.

Conto kanthi minimalake fungsi 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.])

Kita mbokmenawa bakal mandheg ana. Ing artikel sabanjure, aku bakal nyoba nyritakake perkara sing paling menarik babagan minimisasi kondisional, aplikasi minimalisasi ing ngrampungake masalah perkiraan, minimalake fungsi siji variabel, minimizer sewenang-wenang, lan nemokake akar sistem persamaan nggunakake scipy.optimize. paket.

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

Source: www.habr.com

Add a comment