SciPy (sai pie olarak telaffuz edilir), Numpy Python uzantısını temel alan bir matematiksel uygulama paketidir. SciPy ile etkileşimli Python oturumunuz, MATLAB, IDL, Octave, R-Lab ve SciLab ile aynı eksiksiz veri bilimi ve karmaşık sistem prototip oluşturma ortamına dönüşür. Bugün scipy.optimize paketinde bilinen bazı optimizasyon algoritmalarının nasıl kullanılacağından kısaca bahsetmek istiyorum. İşlevlerin kullanımına ilişkin daha ayrıntılı ve güncel yardım her zaman help() komutu veya Shift+Tab kullanılarak elde edilebilir.
Giriş
Kendinizi ve okuyucuları birincil kaynakları arama ve okuma zahmetinden kurtarmak için, yöntemlerin açıklamalarına yönelik bağlantılar esas olarak Vikipedi'de olacaktır. Kural olarak bu bilgiler, yöntemlerin genel anlamda ve uygulama koşullarının anlaşılması için yeterlidir. Matematiksel yöntemlerin özünü anlamak için, her makalenin sonunda veya favori arama motorunuzda bulabileceğiniz daha yetkili yayınların bağlantılarını takip edin.
Yani scipy.optimize modülü aşağıdaki prosedürlerin uygulanmasını içerir:
- Çeşitli algoritmalar (Nelder-Mead simpleks, BFGS, Newton eşlenik gradyanları) kullanılarak çeşitli değişkenlerin (minimum) skaler fonksiyonlarının koşullu ve koşulsuz minimizasyonu, и )
- Küresel optimizasyon (örneğin: , )
- Artıkların en aza indirilmesi (en küçük kareler) ve doğrusal olmayan en küçük kareleri (curve_fit) kullanan eğri uydurma algoritmaları
- Bir değişkenin skaler fonksiyonlarını en aza indirme (minim_scalar) ve kökleri arama (root_scalar)
- Çeşitli algoritmalar (hibrit Powell, veya büyük ölçekli yöntemler gibi ).
Bu yazıda tüm listeden yalnızca ilk öğeyi ele alacağız.
Çeşitli değişkenlerin skaler fonksiyonunun koşulsuz minimizasyonu
scipy.optimize paketindeki minim işlevi, çeşitli değişkenlerin skaler fonksiyonlarının koşullu ve koşulsuz minimizasyon problemlerini çözmek için genel bir arayüz sağlar. Nasıl çalıştığını göstermek için, çeşitli değişkenlerden oluşan uygun bir fonksiyona ihtiyacımız olacak ve bunu farklı şekillerde minimuma indireceğiz.
Bu amaçlar için, N sayıda değişkenin Rosenbrock fonksiyonu mükemmeldir ve şu forma sahiptir:
Rosenbrock fonksiyonu ve onun Jacobi ve Hessian matrisleri (sırasıyla birinci ve ikinci türevler) scipy.optimize paketinde zaten tanımlanmış olmasına rağmen, onu kendimiz tanımlayacağız.
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)Netlik sağlamak için, iki değişkenin Rosenbrock fonksiyonunun değerlerini 3 boyutlu olarak çizelim.
Çizim kodu
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()
Minimumun 0 olduğunu önceden bilmek 
, çeşitli scipy.optimize prosedürlerini kullanarak Rosenbrock fonksiyonunun minimum değerinin nasıl belirleneceğine ilişkin örneklere bakalım.
Nelder-Mead simpleks yöntemi
0 boyutlu uzayda x5 başlangıç noktası olsun. Algoritmayı kullanarak Rosenbrock fonksiyonunun kendisine en yakın minimum noktasını bulalım. (algoritma, yöntem parametresinin değeri olarak belirtilir):
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 yöntemi, açıkça tanımlanmış ve oldukça düzgün bir işlevi en aza indirmenin en basit yoludur. Bir fonksiyonun türevlerinin hesaplanmasını gerektirmez; yalnızca değerlerinin belirtilmesi yeterlidir. Nelder-Mead yöntemi basit minimizasyon problemleri için iyi bir seçimdir. Ancak gradyan tahminlerini kullanmadığından minimumu bulmak daha uzun sürebilir.
Powell yöntemi
Yalnızca fonksiyon değerlerinin hesaplandığı bir diğer optimizasyon algoritması ise . Bunu kullanmak için minim fonksiyonunda method = 'powell' değerini ayarlamanız gerekir.
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) algoritması
Çözüme daha hızlı yakınsama sağlamak için prosedür amaç fonksiyonunun gradyanını kullanır. Gradyan bir fonksiyon olarak belirtilebilir veya birinci dereceden farklar kullanılarak hesaplanabilir. Her durumda, BFGS yöntemi tipik olarak simpleks yöntemine göre daha az işlev çağrısı gerektirir.
Rosenbrock fonksiyonunun türevini analitik biçimde bulalım:
Bu ifade, aşağıdaki şekilde tanımlanan, ilk ve sonuncu dışındaki tüm değişkenlerin türevleri için geçerlidir:
Bu degradeyi hesaplayan Python fonksiyonuna bakalım:
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 derGradyan hesaplama fonksiyonu, aşağıda gösterildiği gibi minim fonksiyonunun jac parametresinin değeri olarak belirtilir.
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]Eşlenik gradyan algoritması (Newton)
Algoritma değiştirilmiş bir Newton yöntemidir.
Newton'un yöntemi, yerel bir alandaki bir fonksiyona ikinci dereceden bir polinomla yaklaşmaya dayanır:
nerede 
ikinci türevlerin matrisidir (Hessian matrisi, Hessian).
Hessian pozitif tanımlıysa, bu fonksiyonun yerel minimumu ikinci dereceden formun sıfır gradyanını sıfıra eşitleyerek bulunabilir. Sonuç şu ifade olacaktır:
Ters Hessian, eşlenik gradyan yöntemi kullanılarak hesaplanır. Rosenbrock fonksiyonunu en aza indirmek için bu yöntemin kullanımına bir örnek aşağıda verilmiştir. Newton-CG yöntemini kullanmak için Hessian'ı hesaplayan bir fonksiyon belirtmeniz gerekir.
Rosenbrock fonksiyonunun analitik formdaki Hessian'ı şuna eşittir:
nerede 
и 
, matrisi tanımlayın 
.
Matrisin geri kalan sıfır olmayan elemanları şuna eşittir:
Örneğin, beş boyutlu bir uzayda N = 5, Rosenbrock fonksiyonunun Hessian matrisi bir bant biçimindedir:
Eşlenik gradyan (Newton) yöntemini kullanarak Rosenbrock fonksiyonunu en aza indirmeye yönelik kodla birlikte bu Hessian'ı hesaplayan kod:
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]Hessian'ın çarpım fonksiyonunun ve keyfi bir vektörün tanımına bir örnek
Gerçek dünya problemlerinde, Hessian matrisinin tamamının hesaplanması ve saklanması önemli miktarda zaman ve bellek kaynağı gerektirebilir. Bu durumda aslında Hessian matrisinin kendisini belirtmeye gerek yoktur çünkü minimizasyon prosedürü yalnızca Hessian'ın başka bir isteğe bağlı vektörle çarpımına eşit bir vektör gerektirir. Bu nedenle, hesaplama açısından bakıldığında, Hessian çarpımının sonucunu keyfi bir vektörle döndüren bir fonksiyonun hemen tanımlanması daha çok tercih edilir.
İlk argüman olarak minimizasyon vektörünü ve ikinci argüman olarak isteğe bağlı bir vektörü (minimizasyona tabi tutulacak fonksiyonun diğer argümanlarıyla birlikte) alan hess fonksiyonunu düşünün. Bizim durumumuzda Rosenbrock fonksiyonunun Hessian çarpımının keyfi bir vektörle hesaplanması çok zor değil. Eğer p keyfi bir vektör ise çarpım 
şuna benziyor:
Hessian ve isteğe bağlı bir vektörün çarpımını hesaplayan işlev, hessp argümanının değeri olarak simge durumuna küçültme işlevine iletilir:
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: 66Eşlenik degrade güven bölgesi algoritması (Newton)
Hessian matrisinin kötü koşullandırılması ve yanlış arama yönleri, Newton'un eşlenik gradyan algoritmasının etkisiz olmasına neden olabilir. Bu gibi durumlarda tercih edilir (güven bölgesi) eşlenik Newton gradyanları.
Hessian matrisinin tanımına örnek:
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.]Hessian'ın çarpım fonksiyonuna ve isteğe bağlı bir vektöre örnek:
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 tipi yöntemler
Trust-ncg yöntemi gibi, Krylov tipi yöntemler de yalnızca matris vektör çarpımlarını kullandıklarından büyük ölçekli problemleri çözmek için çok uygundur. Bunların özü, kesik bir Krylov alt uzayı ile sınırlı bir güven bölgesindeki bir sorunu çözmektir. Belirsiz problemler için, Trust-ncg yöntemiyle karşılaştırıldığında alt problem başına matris vektör çarpımlarının sayısının daha az olması nedeniyle daha az sayıda doğrusal olmayan yineleme kullandığından bu yöntemi kullanmak daha iyidir. Ayrıca ikinci dereceden alt problemin çözümü Trust-NCG yöntemine göre daha doğru bulunmuştur.
Hessian matrisinin tanımına örnek:
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.]
Hessian'ın çarpım fonksiyonuna ve isteğe bağlı bir vektöre örnek:
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.]
Güven bölgesinde yaklaşık çözüm için algoritma
Tüm yöntemler (Newton-CG, Trust-ncg ve Trust-krylov) büyük ölçekli (binlerce değişkenli) sorunların çözümü için çok uygundur. Bunun nedeni, temeldeki eşlenik gradyan algoritmasının, ters Hessian matrisinin yaklaşık olarak belirlenmesini gerektirmesidir. Çözüm, Hessian'ın açık bir şekilde genişletilmesi olmadan yinelemeli olarak bulunur. Yalnızca bir Hessian ve rastgele bir vektörün çarpımı için bir fonksiyon tanımlamanız gerektiğinden, bu algoritma özellikle seyrek (bant köşegen) matrislerle çalışmak için iyidir. Bu, düşük bellek maliyetleri ve önemli ölçüde zaman tasarrufu sağlar.
Orta büyüklükteki problemler için, Hessian'ın saklanması ve çarpanlarına ayrılmasının maliyeti kritik değildir. Bu, güven bölgesinin alt problemlerini neredeyse tam olarak çözerek daha az yinelemede bir çözüm elde etmenin mümkün olduğu anlamına gelir. Bunu yapmak için, bazı doğrusal olmayan denklemler her ikinci dereceden alt problem için yinelemeli olarak çözülür. Böyle bir çözüm genellikle Hessian matrisinin 3 veya 4 Cholesky ayrıştırmasını gerektirir. Sonuç olarak, yöntem daha az yinelemede yakınsar ve uygulanan diğer güven bölgesi yöntemlerine göre daha az amaç fonksiyonu hesaplaması gerektirir. Bu algoritma yalnızca Hessian matrisinin tamamının belirlenmesini gerektirir ve Hessian'ın çarpım fonksiyonunu ve isteğe bağlı bir vektörü kullanma yeteneğini desteklemez.
Rosenbrock fonksiyonunun minimizasyonuna örnek:
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.])Muhtemelen orada duracağız. Bir sonraki makalede koşullu minimizasyon, yaklaşım problemlerinin çözümünde minimizasyon uygulaması, tek değişkenli bir fonksiyonun minimizasyonu, keyfi minimizasyonlar ve scipy.optimize kullanarak bir denklem sisteminin köklerini bulma hakkında en ilginç şeyleri anlatmaya çalışacağım. paket.
Kaynak:
Kaynak: habr.com
