SciPy (تلفظ سای پای) یک بسته ریاضی مبتنی بر numpy است که شامل کتابخانه‌های C و Fortran نیز می‌شود. SciPy جلسه پایتون تعاملی شما را به یک محیط علمی داده کامل مانند MATLAB، IDL، Octave، R یا SciLab تبدیل می‌کند.
در این مقاله به بررسی تکنیک های اساسی برنامه نویسی ریاضی – حل مسائل بهینه سازی شرطی برای یک تابع اسکالر از چندین متغیر با استفاده از بسته scipy.optimize می پردازیم. الگوریتم‌های بهینه‌سازی نامحدود قبلاً در مورد بحث قرار گرفته‌اند . راهنمایی دقیق تر و به روزتر در مورد توابع scipy همیشه می توانید با استفاده از دستور help() Shift+Tab یا در .
معرفی
یک رابط مشترک برای حل مسائل بهینه سازی شرطی و بدون محدودیت در بسته scipy.optimize توسط تابع ارائه شده است. minimize(). با این حال، مشخص است که هیچ روش جهانی برای حل همه مشکلات وجود ندارد، بنابراین انتخاب یک روش مناسب، مانند همیشه، بر دوش محقق است.
الگوریتم بهینه سازی مناسب با استفاده از آرگومان تابع مشخص می شود minimize(..., method="").
برای بهینه سازی شرطی یک تابع از چندین متغیر، پیاده سازی روش های زیر در دسترس است:
trust-constr- حداقل محلی را در منطقه اطمینان جستجو کنید. , ;SLSQP- برنامه نویسی درجه دوم متوالی با قیود، روش نیوتنی برای حل سیستم لاگرانژ. .TNC- کوتاه نیوتن محدود، تعداد محدود تکرار، مناسب برای توابع غیر خطی با تعداد زیادی متغیر مستقل. .L-BFGS-B- روشی از تیم Broyden-Fletcher-Goldfarb-Shanno که با کاهش مصرف حافظه به دلیل بارگذاری جزئی بردارها از ماتریس Hessian پیاده سازی شده است. , .COBYLA— بهینه سازی محدود MARE با تقریب خطی، بهینه سازی محدود با تقریب خطی (بدون محاسبه گرادیان). .
بسته به روش انتخابی، شرایط و محدودیت‌های حل مشکل متفاوت است:
- شی کلاس
Boundsبرای روش های L-BFGS-B، TNC، SLSQP، trust-constr. - لیست
(min, max)برای روش های مشابه L-BFGS-B، TNC، SLSQP، trust-constr. - یک شی یا فهرستی از اشیاء
LinearConstraint,NonlinearConstraintبرای روش های COBYLA، SLSQP، trust-constr. - فرهنگ لغت یا فهرست لغت نامه ها
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}برای روش های COBYLA، SLSQP.
طرح کلی مقاله:
1) استفاده از یک الگوریتم بهینه سازی شرطی را در منطقه اعتماد (روش = "trust-constr") با محدودیت های مشخص شده به عنوان اشیا در نظر بگیرید. Bounds, LinearConstraint, NonlinearConstraint ;
2) برنامه نویسی متوالی را با استفاده از روش حداقل مربعات (روش = "SLSQP") با محدودیت های مشخص شده در قالب یک فرهنگ لغت در نظر بگیرید. {'type', 'fun', 'jac', 'args'};
3) نمونه ای از بهینه سازی محصولات تولیدی را با استفاده از مثال یک استودیو وب تحلیل کنید.
روش بهینه سازی مشروط = "trust-constr"
پیاده سازی روش trust-constr بر اساس برای مشکلات با محدودیت های شکل برابری و در برای مشکلات با محدودیت ها به شکل نابرابری. هر دو روش توسط الگوریتم‌هایی برای یافتن حداقل محلی در منطقه اطمینان پیاده‌سازی می‌شوند و برای مسائل در مقیاس بزرگ مناسب هستند.
فرمول ریاضی مسئله یافتن حداقل به صورت کلی:
برای قیود برابری دقیق، کران پایین برابر با کران بالا تنظیم می شود .
برای یک محدودیت یک طرفه، حد بالا یا پایین تنظیم شده است np.inf با علامت مربوطه
لازم است حداقل یک تابع روزنبراک شناخته شده از دو متغیر را پیدا کنیم:
در این مورد، محدودیت های زیر در حوزه تعریف آن تعیین می شود:
در مورد ما، یک راه حل منحصر به فرد در نقطه وجود دارد ، که فقط محدودیت اول و چهارم برای آن معتبر است.
بیایید محدودیت‌ها را از پایین به بالا مرور کنیم و ببینیم چگونه می‌توانیم آنها را به صورت دقیق بنویسیم.
محدودیت и بیایید آن را با استفاده از شی Bounds تعریف کنیم.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])محدودیت и بیایید آن را به صورت خطی بنویسیم:
بیایید این محدودیت ها را به عنوان یک شی LinearConstraint تعریف کنیم:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])و در نهایت محدودیت غیر خطی به صورت ماتریسی:
ماتریس ژاکوبین را برای این محدودیت و یک ترکیب خطی از ماتریس هسین با یک بردار دلخواه تعریف می کنیم. :
اکنون می توانیم یک محدودیت غیرخطی را به عنوان یک شی تعریف کنیم 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)اگر اندازه بزرگ است، ماتریس ها را می توان به صورت پراکنده نیز مشخص کرد:
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)یا به عنوان یک شی 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)هنگام محاسبه ماتریس هسین نیاز به تلاش زیادی دارد، می توانید از کلاس استفاده کنید . استراتژی های زیر در دسترس هستند: BFGS и SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())هسین را می توان با استفاده از تفاوت های محدود نیز محاسبه کرد:
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')ماتریس ژاکوبین برای قیود نیز می تواند با استفاده از تفاوت های محدود محاسبه شود. با این حال، در این مورد، ماتریس هسین را نمی توان با استفاده از تفاوت های محدود محاسبه کرد. Hessian باید به عنوان یک تابع یا با استفاده از کلاس HessianUpdateStrategy تعریف شود.
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())راه حل مسئله بهینه سازی به صورت زیر است:
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]در صورت لزوم، تابع محاسبه Hessian را می توان با استفاده از کلاس LinearOperator تعریف کرد.
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)یا حاصل ضرب هسین و یک بردار دلخواه از طریق پارامتر 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)از طرف دیگر، مشتقات اول و دوم تابع بهینه‌سازی شده را می‌توان تقریبی کرد. به عنوان مثال، Hessian را می توان با استفاده از تابع تقریب زد SR1 (تقریبا شبه نیوتنی). گرادیان را می توان با تفاوت های محدود تقریب زد.
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)روش بهینه سازی شرطی = "SLSQP"
روش SLSQP برای حل مشکلات کمینه کردن یک تابع به شکل زیر طراحی شده است:
Где и - مجموعه‌ای از شاخص‌های عباراتی که محدودیت‌ها را به شکل برابری یا نابرابری توصیف می‌کنند. - مجموعه ای از کران های پایین و بالایی برای دامنه تعریف تابع.
قیود خطی و غیر خطی در قالب فرهنگ لغت با کلید توضیح داده شده است 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])
}جستجو برای حداقل به شرح زیر انجام می شود:
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 ]مثال بهینه سازی
در رابطه با انتقال به ساختار تکنولوژی پنجم، بیایید بهینه سازی تولید را با استفاده از مثال استودیو وب بررسی کنیم که درآمدی اندک اما پایدار برای ما به ارمغان می آورد. بیایید خود را مدیر یک گالری تصور کنیم که سه نوع محصول تولید می کند:
- x0 - فروش صفحات فرود، از 10 ترون.
- x1 - وب سایت های شرکتی، از 20 ترون.
- x2 - فروشگاه های آنلاین، از 30 tr.
تیم کاری دوستانه ما شامل چهار جوان، دو میانی و یک بزرگسال است. صندوق زمان کار ماهانه آنها:
- ژوئن:
4 * 150 = 600 чел * час, - میانه ها:
2 * 150 = 300 чел * час, - سنسور:
150 чел * час.
اجازه دهید اولین جونیور موجود (0، 1، 2) ساعت را صرف توسعه و استقرار یک سایت از نوع (x10، x20، x30)، وسط - (7، 15، 20)، ارشد - (5، 10، 15) کند. ) ساعت از بهترین زمان زندگی شما.
مانند هر کارگردان معمولی، ما می خواهیم سود ماهانه را به حداکثر برسانیم. اولین قدم برای موفقیت، نوشتن تابع هدف است value به عنوان میزان درآمد حاصل از محصولات تولید شده در ماه:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]این یک خطا نیست، هنگام جستجو برای حداکثر، تابع هدف با علامت مخالف به حداقل می رسد.
گام بعدی این است که کارمندان خود را از کار بیش از حد منع کنیم و محدودیت هایی در ساعات کاری اعمال کنیم:
معادل چیست:
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]])
}یک محدودیت رسمی این است که خروجی محصول فقط باید مثبت باشد:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])و در نهایت، بدترین فرض این است که به دلیل قیمت پایین و کیفیت بالا، یک صف از مشتریان راضی دائما برای ما صف می کشند. ما می‌توانیم بر اساس حل مشکل بهینه‌سازی محدود، حجم تولید ماهانه را خودمان انتخاب کنیم 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]بیایید به اعداد کامل گرد کنیم و بار ماهانه قایقران را با توزیع بهینه محصولات محاسبه کنیم. x = (8, 6, 3) :
- ژوئن:
8 * 10 + 6 * 20 + 3 * 30 = 290 чел * час; - میانه ها:
8 * 7 + 6 * 15 + 3 * 20 = 206 чел * час; - سنسور:
8 * 5 + 6 * 10 + 3 * 15 = 145 чел * час.
نتیجه گیری: برای اینکه کارگردان حداکثر شایسته خود را دریافت کند، ایجاد 8 صفحه فرود، 6 سایت با اندازه متوسط و 3 فروشگاه در ماه بهینه است. در این حالت ، ارشد باید بدون نگاه کردن از دستگاه به بالا شخم بزند ، بار میانه ها تقریباً 2/3 خواهد بود ، جوانان کمتر از نصف.
نتیجه
این مقاله به تشریح تکنیک های اساسی برای کار با بسته می پردازد scipy.optimize، برای حل مسائل کمینه سازی شرطی استفاده می شود. من شخصا استفاده میکنم scipy صرفاً برای اهداف آکادمیک، به همین دلیل است که مثال ارائه شده دارای ماهیت طنز است.
تئوری و مثال های مجازی زیادی را می توان یافت، به عنوان مثال، در کتاب I.L. Akulich "برنامه نویسی ریاضی در مثال ها و مسائل". برنامه هاردکور بیشتر scipy.optimize برای ساختن یک ساختار سه بعدی از مجموعه ای از تصاویر () قابل مشاهده است .
منبع اصلی اطلاعات است کسانی که مایل به همکاری در ترجمه این بخش و سایر بخش ها هستند scipy خوش آمدید به .
سپاس ها برای مشارکت در تهیه نشریه.
منبع: www.habr.com