SciPy (sai pie olarak telaffuz edilir), C ve Fortran kütüphanelerini de içeren numpy tabanlı bir matematik paketidir. SciPy, etkileşimli Python oturumunuzu MATLAB, IDL, Octave, R veya SciLab gibi eksiksiz bir veri bilimi ortamına dönüştürür.
Bu makalede, matematiksel programlamanın temel tekniklerine bakacağız - scipy.optimize paketini kullanarak çeşitli değişkenlerin skaler fonksiyonu için koşullu optimizasyon problemlerini çözme. Kısıtlanmamış optimizasyon algoritmaları daha önce tartışılmıştı. . Scipy işlevleriyle ilgili daha ayrıntılı ve güncel yardım her zaman help() komutu, Shift+Tab veya .
Giriş
Scipy.optimize paketindeki hem koşullu hem de kısıtlamasız optimizasyon problemlerini çözmek için ortak bir arayüz, fonksiyon tarafından sağlanır. minimize(). Ancak tüm sorunların çözümü için evrensel bir yöntemin olmadığı bilinmektedir, bu nedenle yeterli yöntemin seçimi her zaman olduğu gibi araştırmacının omuzlarına düşmektedir.
Uygun optimizasyon algoritması, fonksiyon argümanı kullanılarak belirtilir minimize(..., method="").
Birkaç değişkenli bir fonksiyonun koşullu optimizasyonu için aşağıdaki yöntemlerin uygulamaları mevcuttur:
trust-constr- güven bölgesinde yerel minimumu arayın. , ;SLSQP— Kısıtlı sıralı ikinci dereceden programlama, Lagrange sistemini çözmek için Newton yöntemi. .TNC- Kesilmiş Newton Kısıtlı, sınırlı sayıda yineleme, çok sayıda bağımsız değişkene sahip doğrusal olmayan fonksiyonlar için iyidir. .L-BFGS-B— Broyden-Fletcher-Goldfarb-Shanno ekibinin Hessian matrisinden vektörlerin kısmi yüklenmesi nedeniyle azaltılmış bellek tüketimiyle uygulanan bir yöntemi. , .COBYLA— Doğrusal Yaklaşımla MARE Kısıtlı Optimizasyon, doğrusal yaklaşımla kısıtlı optimizasyon (gradyan hesaplaması olmadan). .
Seçilen yönteme bağlı olarak, sorunu çözmeye yönelik koşullar ve kısıtlamalar farklı şekilde belirlenir:
- sınıf nesnesi
BoundsL-BFGS-B, TNC, SLSQP, Trust-Constr yöntemleri için; - liste
(min, max)aynı yöntemler için L-BFGS-B, TNC, SLSQP, Trust-constr; - bir nesne veya nesnelerin listesi
LinearConstraint,NonlinearConstraintCOBYLA, SLSQP, güven yapılandırma yöntemleri için; - sözlük veya sözlük listesi
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}COBYLA için SLSQP yöntemleri.
Makale özeti:
1) Nesneler olarak belirtilen kısıtlamalarla güven bölgesinde (method=”trust-constr”) koşullu bir optimizasyon algoritmasının kullanımını düşünün Bounds, LinearConstraint, NonlinearConstraint ;
2) Sözlük biçiminde belirtilen kısıtlamalarla en küçük kareler yöntemini (yöntem = "SLSQP") kullanarak sıralı programlamayı düşünün {'type', 'fun', 'jac', 'args'};
3) Bir web stüdyosu örneğini kullanarak üretilen ürünlerin optimizasyonuna ilişkin bir örneği analiz edin.
Koşullu optimizasyon yöntemi = "güven-yapılandırma"
Yöntemin uygulanması trust-constr dayalı eşitlik biçiminin kısıtlamaları olan problemler için ve eşitsizlik biçimindeki kısıtlamalara sahip problemler için. Her iki yöntem de güven bölgesinde yerel minimumu bulmaya yönelik algoritmalar tarafından uygulanır ve büyük ölçekli problemler için çok uygundur.
Minimum bulma probleminin genel formda matematiksel formülasyonu:
Katı eşitlik kısıtlamaları için alt sınır, üst sınıra eşit olarak ayarlanır 
.
Tek yönlü kısıtlama için üst veya alt sınır belirlenir np.inf karşılık gelen işaretle.
İki değişkenin bilinen bir Rosenbrock fonksiyonunun minimumunu bulmak gerekli olsun:
Bu durumda tanım alanına aşağıdaki kısıtlamalar getirilir:
Bizim durumumuzda ise bu noktada benzersiz bir çözüm var. 
, yalnızca birinci ve dördüncü kısıtlamalar geçerlidir.
Kısıtlamaları aşağıdan yukarıya doğru inceleyelim ve bunları scipy'de nasıl yazabileceğimize bakalım.
Kısıtlamalar 
и 
Bounds nesnesini kullanarak tanımlayalım.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])Kısıtlamalar 
и 
Bunu doğrusal formda yazalım:
Bu kısıtlamaları LinearConstraint nesnesi olarak tanımlayalım:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])Ve son olarak matris formundaki doğrusal olmayan kısıtlama:
Bu kısıtlama için Jacobian matrisini ve Hessian matrisinin keyfi bir vektörle doğrusal birleşimini tanımlarız. 
:
Artık doğrusal olmayan bir kısıtlamayı nesne olarak tanımlayabiliriz NonlinearConstraint:
from scipy.optimize import NonlinearConstraint
def cons_f(x):
return [x[0]**2 + x[1], x[0]**2 - x[1]]
def cons_J(x):
return [[2*x[0], 1], [2*x[0], -1]]
def cons_H(x, v):
return v[0]*np.array([[2, 0], [0, 0]]) + v[1]*np.array([[2, 0], [0, 0]])
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=cons_H)Boyut büyükse matrisler seyrek biçimde de belirtilebilir:
from scipy.sparse import csc_matrix
def cons_H_sparse(x, v):
return v[0]*csc_matrix([[2, 0], [0, 0]]) + v[1]*csc_matrix([[2, 0], [0, 0]])
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1,
jac=cons_J, hess=cons_H_sparse)veya bir nesne olarak LinearOperator:
from scipy.sparse.linalg import LinearOperator
def cons_H_linear_operator(x, v):
def matvec(p):
return np.array([p[0]*2*(v[0]+v[1]), 0])
return LinearOperator((2, 2), matvec=matvec)
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1,
jac=cons_J, hess=cons_H_linear_operator)Hessian matrisini hesaplarken 
çok çaba gerektirir, bir sınıf kullanabilirsiniz . Aşağıdaki stratejiler mevcuttur: BFGS и SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())Hessian aynı zamanda sonlu farklar kullanılarak da hesaplanabilir:
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')Kısıtlamalar için Jacobian matrisi sonlu farklar kullanılarak da hesaplanabilir. Ancak bu durumda Hessian matrisi sonlu farklar kullanılarak hesaplanamaz. Hessian, bir işlev olarak veya HessianUpdateStrategy sınıfı kullanılarak tanımlanmalıdır.
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())Optimizasyon probleminin çözümü şöyle görünür:
from scipy.optimize import minimize
from scipy.optimize import rosen, rosen_der, rosen_hess, rosen_hess_prod
x0 = np.array([0.5, 0])
res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hess=rosen_hess,
constraints=[linear_constraint, nonlinear_constraint],
options={'verbose': 1}, bounds=bounds)
print(res.x)`gtol` termination condition is satisfied.
Number of iterations: 12, function evaluations: 8, CG iterations: 7, optimality: 2.99e-09, constraint violation: 1.11e-16, execution time: 0.033 s.
[0.41494531 0.17010937]Gerekirse Hessian'ı hesaplamaya yönelik işlev LinearOperator sınıfı kullanılarak tanımlanabilir.
def rosen_hess_linop(x):
def matvec(p):
return rosen_hess_prod(x, p)
return LinearOperator((2, 2), matvec=matvec)
res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hess=rosen_hess_linop,
constraints=[linear_constraint, nonlinear_constraint],
options={'verbose': 1}, bounds=bounds)
print(res.x)veya Hessian'ın çarpımı ve parametre aracılığıyla keyfi bir vektör hessp:
res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hessp=rosen_hess_prod,
constraints=[linear_constraint, nonlinear_constraint],
options={'verbose': 1}, bounds=bounds)
print(res.x)Alternatif olarak optimize edilen fonksiyonun birinci ve ikinci türevleri yaklaşık olarak belirlenebilir. Örneğin, Hessian fonksiyonu kullanılarak yaklaşık olarak hesaplanabilir. SR1 (yarı Newton yaklaşımı). Gradyan sonlu farklarla tahmin edilebilir.
from scipy.optimize import SR1
res = minimize(rosen, x0, method='trust-constr', jac="2-point", hess=SR1(),
constraints=[linear_constraint, nonlinear_constraint],
options={'verbose': 1}, bounds=bounds)
print(res.x)Koşullu optimizasyon yöntemi = "SLSQP"
SLSQP yöntemi, formdaki bir işlevi en aza indirme sorunlarını çözmek için tasarlanmıştır:
Nerede 
и 
- eşitlikler veya eşitsizlikler biçimindeki kısıtlamaları açıklayan ifade endeksleri kümesi. 
- Fonksiyonun tanım alanı için alt ve üst sınır kümeleri.
Doğrusal ve doğrusal olmayan kısıtlamalar, anahtarlı sözlükler biçiminde açıklanmaktadır. type, fun и jac.
ineq_cons = {'type': 'ineq',
'fun': lambda x: np.array ([1 - x [0] - 2 * x [1],
1 - x [0] ** 2 - x [1],
1 - x [0] ** 2 + x [1]]),
'jac': lambda x: np.array ([[- 1.0, -2.0],
[-2 * x [0], -1.0],
[-2 * x [0], 1.0]])
}
eq_cons = {'type': 'eq',
'fun': lambda x: np.array ([2 * x [0] + x [1] - 1]),
'jac': lambda x: np.array ([2.0, 1.0])
}Minimum arama şu şekilde gerçekleştirilir:
x0 = np.array([0.5, 0])
res = minimize(rosen, x0, method='SLSQP', jac=rosen_der,
constraints=[eq_cons, ineq_cons], options={'ftol': 1e-9, 'disp': True},
bounds=bounds)
print(res.x)Optimization terminated successfully. (Exit mode 0)
Current function value: 0.34271757499419825
Iterations: 4
Function evaluations: 5
Gradient evaluations: 4
[0.41494475 0.1701105 ]Optimizasyon örneği
Beşinci teknolojik yapıya geçişle bağlantılı olarak, bize küçük ama istikrarlı bir gelir getiren bir web stüdyosu örneğini kullanarak üretim optimizasyonuna bakalım. Kendimizi üç çeşit ürün üreten bir mutfağın müdürü olarak hayal edelim:
- x0 - açılış sayfalarının satışı, 10 tr'den.
- x1 - kurumsal web siteleri, 20 tr'den itibaren.
- x2 - çevrimiçi mağazalar, 30 tr'den itibaren.
Güleryüzlü çalışma ekibimiz dört genç, iki orta ve bir son sınıftan oluşmaktadır. Aylık çalışma süresi fonları:
- Haziran:
4 * 150 = 600 чел * час, - ortalar:
2 * 150 = 300 чел * час, - Senyor:
150 чел * час.
Mevcut ilk gençlerin (x0, x1, x2), orta - (10, 20, 30), kıdemli - (7, 15, 20) tipinde bir sitenin geliştirilmesi ve dağıtımı için (5, 10, 15) saat harcamasına izin verin ) hayatınızın en güzel zamanının saatleri.
Her normal yönetici gibi biz de aylık karı maksimuma çıkarmak istiyoruz. Başarıya giden ilk adım amaç fonksiyonunu yazmaktır value Aylık üretilen ürünlerden elde edilen gelir miktarı olarak:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]Bu bir hata değildir; maksimum aranırken amaç fonksiyonu ters işaretle minimuma indirilir.
Bir sonraki adım, çalışanlarımızın aşırı çalışmasını yasaklamak ve çalışma saatlerine kısıtlamalar getirmektir:
Eşdeğer nedir:
ineq_cons = {'type': 'ineq',
'fun': lambda x: np.array ([600 - 10 * x [0] - 20 * x [1] - 30 * x[2],
300 - 7 * x [0] - 15 * x [1] - 20 * x[2],
150 - 5 * x [0] - 10 * x [1] - 15 * x[2]])
}Resmi bir kısıtlama, ürün çıktısının yalnızca pozitif olması gerektiğidir:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])Ve son olarak, en umut verici varsayım, düşük fiyat ve yüksek kalite nedeniyle, memnun müşterilerden oluşan bir kuyruğun sürekli olarak bizim için sıraya girdiğidir. Kısıtlı optimizasyon sorununun çözümüne dayalı olarak aylık üretim hacimlerini kendimiz seçebiliyoruz. scipy.optimize:
x0 = np.array([10, 10, 10])
res = minimize(value, x0, method='SLSQP', constraints=ineq_cons, bounds=bnds)
print(res.x)[7.85714286 5.71428571 3.57142857]Gevşek bir şekilde tam sayılara yuvarlayalım ve optimum ürün dağılımıyla kürekçilerin aylık yükünü hesaplayalım x = (8, 6, 3) :
- Haziran:
8 * 10 + 6 * 20 + 3 * 30 = 290 чел * час; - ortalar:
8 * 7 + 6 * 15 + 3 * 20 = 206 чел * час; - Senyor:
8 * 5 + 6 * 10 + 3 * 15 = 145 чел * час.
Sonuç: Yönetmenin hak ettiği maksimum değeri alabilmesi için ayda 8 açılış sayfası, 6 orta ölçekli site ve 3 mağaza oluşturmak en uygunudur. Bu durumda yaşlıların başını makineden kaldırmadan sürmesi gerekir, ortaların yükü yaklaşık 2/3, gençlerin ise yarıdan az olacaktır.
Sonuç
Makale paketle çalışmanın temel tekniklerini özetlemektedir scipy.optimizeKoşullu minimizasyon problemlerini çözmek için kullanılır. Şahsen ben kullanıyorum scipy tamamen akademik amaçlıdır, bu yüzden verilen örnek bu kadar komik niteliktedir.
Pek çok teori ve sanal örnek, örneğin I.L. Akulich'in "Örnekler ve problemlerde matematiksel programlama" kitabında bulunabilir. Daha sert uygulama scipy.optimize bir dizi görüntüden 3 boyutlu bir yapı oluşturmak için () içinde görüntülenebilir .
Bilginin ana kaynağı bu ve diğer bölümlerin çevirisine katkıda bulunmak isteyenler scipy Hoşgeldiniz .
Teşekkürler yayının hazırlanmasına katılım için.
Kaynak: habr.com
