SciPy (talaffuzi sai pie) - bu C va Fortran kutubxonalarini o'z ichiga olgan numpy asosidagi matematika to'plami. SciPy interaktiv Python seansingizni MATLAB, IDL, Octave, R yoki SciLab kabi to'liq ma'lumot faniga aylantiradi.
Ushbu maqolada biz matematik dasturlashning asosiy usullarini ko'rib chiqamiz - scipy.optimize paketi yordamida bir nechta o'zgaruvchilarning skalyar funksiyasi uchun shartli optimallashtirish masalalarini hal qilish. Cheklanmagan optimallashtirish algoritmlari allaqachon muhokama qilingan . Scipy funktsiyalari bo'yicha batafsil va dolzarb yordamni har doim help() buyrug'i, Shift+Tab yoki ichidan olish mumkin. .
kirish
Scipy.optimize paketidagi shartli va cheklanmagan optimallashtirish muammolarini hal qilish uchun umumiy interfeys funksiya tomonidan taqdim etiladi. minimize(). Biroq, ma'lumki, barcha muammolarni hal qilishning universal usuli yo'q, shuning uchun adekvat usulni tanlash, har doimgidek, tadqiqotchining yelkasiga tushadi.
Tegishli optimallashtirish algoritmi funktsiya argumenti yordamida belgilanadi minimize(..., method="").
Bir nechta o'zgaruvchilar funksiyasini shartli optimallashtirish uchun quyidagi usullarni qo'llash mumkin:
trust-constr— ishonchli mintaqada mahalliy minimumni izlash. , ;SLSQP— cheklovlar bilan ketma-ket kvadratik dasturlash, Lagranj tizimini yechishning Nyuton usuli. .TNC- Kesilgan Nyuton Cheklangan, takrorlanishlar soni cheklangan, ko'p sonli mustaqil o'zgaruvchilarga ega chiziqli bo'lmagan funksiyalar uchun yaxshi. .L-BFGS-B- Broyden-Fletcher-Goldfarb-Shanno jamoasining usuli, Hessian matritsasidan vektorlarning qisman yuklanishi tufayli xotira sarfini kamaytirish bilan amalga oshirildi. , .COBYLA— Lineer yaqinlashish orqali MARE cheklangan optimallashtirish, chiziqli yaqinlashish bilan cheklangan optimallashtirish (gradient hisobisiz). .
Tanlangan usulga qarab, muammoni hal qilish uchun shartlar va cheklovlar boshqacha o'rnatiladi:
- sinf ob'ekti
Boundsusullari uchun L-BFGS-B, TNC, SLSQP, trust-constr; - ro'yxati
(min, max)bir xil usullar uchun L-BFGS-B, TNC, SLSQP, trust-constr; - ob'ekt yoki ob'ektlar ro'yxati
LinearConstraint,NonlinearConstraintCOBYLA, SLSQP, trust-constr usullari uchun; - lug'at yoki lug'atlar ro'yxati
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}COBYLA, SLSQP usullari uchun.
Maqola tavsifi:
1) Ob'ektlar sifatida belgilangan cheklovlar bilan ishonchli mintaqada shartli optimallashtirish algoritmidan foydalanishni ko'rib chiqing (metod="trust-constr"). Bounds, LinearConstraint, NonlinearConstraint ;
2) Lug'at shaklida ko'rsatilgan cheklovlar bilan eng kichik kvadratlar usuli (metod = "SLSQP") yordamida ketma-ket dasturlashni ko'rib chiqing. {'type', 'fun', 'jac', 'args'};
3) Veb-studiya misolida ishlab chiqarilgan mahsulotlarni optimallashtirish misolini tahlil qiling.
Shartli optimallashtirish usuli = "trust-constr"
Usulni amalga oshirish trust-constr asoslangan tenglik shaklidagi cheklovlar bilan bog'liq muammolar uchun va boshqalar tengsizliklar ko'rinishidagi cheklovlar bilan bog'liq muammolar uchun. Ikkala usul ham ishonchli mintaqada mahalliy minimumni topish algoritmlari bilan amalga oshiriladi va keng ko'lamli muammolar uchun juda mos keladi.
Minimumni topish masalasini umumiy shaklda matematik shakllantirish:
Qattiq tenglik cheklovlari uchun pastki chegara yuqori chegaraga tenglashtiriladi .
Bir tomonlama cheklov uchun yuqori yoki pastki chegara o'rnatiladi np.inf tegishli belgi bilan.
Ikki o'zgaruvchining ma'lum Rosenbrok funktsiyasining minimalini topish kerak bo'lsin:
Bunday holda, uning ta'rif sohasiga quyidagi cheklovlar qo'yiladi:
Bizning holatda, nuqtada o'ziga xos yechim mavjud , ular uchun faqat birinchi va to'rtinchi cheklovlar amal qiladi.
Keling, cheklovlarni pastdan yuqoriga qarab ko'rib chiqamiz va ularni scipy-da qanday yozishni ko'rib chiqamiz.
Cheklovlar и uni Bounds obyekti yordamida aniqlaymiz.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])Cheklovlar и Uni chiziqli shaklda yozamiz:
Keling, ushbu cheklovlarni LinearConstraint obyekti sifatida belgilaymiz:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])Va nihoyat, matritsa ko'rinishidagi chiziqli bo'lmagan cheklov:
Biz ushbu cheklov uchun Yakobiy matritsasi va Gessian matritsasining ixtiyoriy vektor bilan chiziqli birikmasini aniqlaymiz. :
Endi biz chiziqli bo'lmagan cheklovni ob'ekt sifatida belgilashimiz mumkin 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)Agar o'lcham katta bo'lsa, matritsalar siyrak shaklda ham ko'rsatilishi mumkin:
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)yoki ob'ekt sifatida 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 matritsasini hisoblashda ko'p harakat talab qiladi, siz sinfdan foydalanishingiz mumkin . Quyidagi strategiyalar mavjud: BFGS и SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())Hessianni chekli farqlar yordamida ham hisoblash mumkin:
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')Cheklovlar uchun Yakobiy matritsasi cheklangan farqlar yordamida ham hisoblanishi mumkin. Biroq, bu holda Hessian matritsasi cheklangan farqlar yordamida hisoblab bo'lmaydi. Hessian funksiya sifatida aniqlanishi yoki HessianUpdateStrategy sinfidan foydalanishi kerak.
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())Optimallashtirish muammosining yechimi quyidagicha ko'rinadi:
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]Agar kerak bo'lsa, Hessianni hisoblash funktsiyasi LinearOperator klassi yordamida aniqlanishi mumkin.
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)yoki parametr orqali Hessian va ixtiyoriy vektorning mahsuloti 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)Shu bilan bir qatorda optimallashtirilayotgan funksiyaning birinchi va ikkinchi hosilalarini taxminan hisoblash mumkin. Masalan, Hessian funksiyasi yordamida taxminiy hisoblanishi mumkin SR1 (kvazi-Nyuton yaqinlashuvi). Gradientni chekli farqlar bilan taxmin qilish mumkin.
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)Shartli optimallashtirish usuli = "SLSQP"
SLSQP usuli funktsiyani quyidagi shaklda minimallashtirish muammolarini hal qilish uchun mo'ljallangan:
Qaerda и — tenglik yoki tengsizlik koʻrinishidagi cheklovlarni tavsiflovchi iboralar koʻrsatkichlari toʻplami. — funksiyani aniqlash sohasi uchun pastki va yuqori chegaralar to‘plami.
Chiziqli va chiziqli bo'lmagan cheklovlar kalitli lug'atlar ko'rinishida tasvirlangan 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])
}Minimalni qidirish quyidagicha amalga oshiriladi:
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 ]Optimallashtirish misoli
Beshinchi texnologik tuzilmaga o'tish munosabati bilan, bizga kichik, ammo barqaror daromad keltiradigan veb-studiya misolida ishlab chiqarishni optimallashtirishni ko'rib chiqaylik. Keling, o'zimizni uchta turdagi mahsulotlarni ishlab chiqaradigan oshxona direktori sifatida tasavvur qilaylik:
- x0 - ochilish sahifalarini sotish, 10 tr dan.
- x1 - korporativ veb-saytlar, 20 tr dan.
- x2 - onlayn-do'konlar, 30 tr dan.
Bizning do'stona ishchi jamoamiz to'rtta kichik, ikkita o'rta va bitta katta yoshlilardan iborat. Ularning oylik ish vaqti fondi:
- Iyun:
4 * 150 = 600 чел * час, - o'rtalari:
2 * 150 = 300 чел * час, - senor:
150 чел * час.
Birinchi mavjud bo'lgan o'smirlar (x0, x1, x2), o'rta - (10, 20, 30), kattalar - (7, 15, 20) turdagi saytlarni ishlab chiqish va joylashtirishga (5, 10, 15) soat sarflashlariga ruxsat bering. ) hayotingizdagi eng yaxshi vaqt soatlari.
Har qanday oddiy direktor singari, biz oylik daromadni maksimal darajada oshirishni xohlaymiz. Muvaffaqiyatga erishish uchun birinchi qadam maqsad funktsiyasini yozishdir value oyiga ishlab chiqarilgan mahsulotdan olingan daromad miqdori sifatida:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]Bu xato emas, maksimalni qidirishda maqsad funktsiyasi qarama-qarshi belgi bilan minimallashtiriladi.
Keyingi qadam - xodimlarimizga ortiqcha ishlashni taqiqlash va ish vaqtiga cheklovlarni joriy etish:
Ekvivalent nima:
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]])
}Rasmiy cheklov shundan iboratki, mahsulot chiqishi faqat ijobiy bo'lishi kerak:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])Va nihoyat, eng qizg'in taxmin shuki, past narx va yuqori sifat tufayli biz uchun qoniqarli mijozlar navbati doimiy ravishda paydo bo'ladi. Biz cheklangan optimallashtirish muammosini hal qilish asosida oylik ishlab chiqarish hajmlarini o'zimiz tanlashimiz mumkin 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]Keling, butun sonlargacha yaxlitlashamiz va mahsulotlarni optimal taqsimlash bilan eshkakchilarning oylik yukini hisoblaymiz. x = (8, 6, 3) :
- Iyun:
8 * 10 + 6 * 20 + 3 * 30 = 290 чел * час; - o'rtalari:
8 * 7 + 6 * 15 + 3 * 20 = 206 чел * час; - senor:
8 * 5 + 6 * 10 + 3 * 15 = 145 чел * час.
Xulosa: direktor o'zining munosib maksimalini olishi uchun oyiga 8 ta ochilish sahifasi, 6 ta o'rta o'lchamli sayt va 3 ta do'kon yaratish maqbuldir. Bunday holda, kattalar mashinadan bosh ko'tarmasdan haydashlari kerak, o'rtalarning yuki taxminan 2/3, kichiklar esa yarmidan kam bo'ladi.
xulosa
Maqolada paket bilan ishlashning asosiy usullari ko'rsatilgan scipy.optimize, shartli minimallashtirish masalalarini hal qilish uchun ishlatiladi. Shaxsan men foydalanaman scipy faqat ilmiy maqsadlar uchun, shuning uchun berilgan misol juda kulgili xususiyatga ega.
Ko'pgina nazariya va virtual misollarni, masalan, I.L.Akulichning "Matematik dasturlash misollar va muammolarda" kitobida topish mumkin. Ko'proq qattiq dastur scipy.optimize tasvirlar to'plamidan 3D tuzilmani qurish () ichida ko'rish mumkin .
Asosiy ma'lumot manbai ushbu va boshqa bo'limlarni tarjima qilishga hissa qo'shishni xohlovchilar scipy Ga Xush kelibsiz .
Rahmat nashrni tayyorlashda ishtirok etgani uchun.
Manba: www.habr.com