🥇SciPy، حالتن سان اصلاح

SciPy (تلفظ ٿيل سائي پائي) ھڪڙو نمپي تي ٻڌل رياضي وارو پيڪيج آھي جنھن ۾ C ۽ Fortran لائبريريون پڻ شامل آھن. SciPy توهان جي انٽرويو پٿون سيشن کي مڪمل ڊيٽا سائنس ماحول جهڙوڪ MATLAB، IDL، Octave، R، يا SciLab ۾ تبديل ڪري ٿو.

هن آرٽيڪل ۾، اسان رياضياتي پروگرامنگ جي بنيادي ٽيڪنالاجي تي نظر ڪنداسين - scipy.optimize پيڪيج استعمال ڪندي ڪيترن ئي متغيرن جي اسڪيلر فنڪشن لاء مشروط اصلاح جي مسئلن کي حل ڪرڻ. غير محدود اصلاحي الگورتھم اڳ ۾ ئي بحث ڪيو ويو آھي آخري مضمون. وڌيڪ تفصيلي ۽ تازه ترين مدد اسڪائپي افعال تي هميشه حاصل ڪري سگھجن ٿيون مدد () ڪمانڊ، شفٽ + ٽيب يا ان ۾ سرڪاري دستاويز.

تعارف

scipy.optimize پيڪيج ۾ مشروط ۽ غير محدود اصلاح جي مسئلن کي حل ڪرڻ لاءِ هڪ عام انٽرفيس فنڪشن پاران مهيا ڪيل آهي minimize(). بهرحال، اهو معلوم ٿئي ٿو ته سڀني مسئلن کي حل ڪرڻ لاء ڪو عالمگير طريقو ناهي، تنهنڪري هڪ مناسب طريقو جو انتخاب، هميشه وانگر، محقق جي ڪلهن تي پوي ٿو.
مناسب اصلاح الورورٿم فنڪشن دليل استعمال ڪندي بيان ڪيو ويو آهي minimize(..., method="").
ڪيترن ئي متغيرن جي هڪ فنڪشن جي مشروط اصلاح لاءِ، هيٺين طريقن جا عمل موجود آهن:

trust-constr - اعتماد واري علائقي ۾ مقامي گھٽ ۾ گھٽ ڳولھيو. Wiki آرٽيڪل, Habré تي مضمون;
SLSQP - پابندين سان ترتيب وار چوٿين پروگرامنگ، Lagrange سسٽم کي حل ڪرڻ لاء نيوتونين طريقو. Wiki آرٽيڪل.
TNC - ٽوڙيو ويو نيوٽن محدود، محدود تعداد ۾ تکرار، وڏي تعداد ۾ آزاد متغيرن سان غير لائنر ڪمن لاءِ سٺو. Wiki آرٽيڪل.
L-BFGS-B - Broyden-Fletcher-Goldfarb-Shanno ٽيم جو ھڪڙو طريقو، ھيسين ميٽرڪس مان ویکٹر جي جزوي لوڊشيڊنگ جي ڪري ياداشت جي گھٽتائي سان لاڳو ڪيو ويو. Wiki آرٽيڪل, Habré تي مضمون.
COBYLA - MARE Constrained Optimization by Linear Approximation، Constrained Optimization with linear approximation (بغير گريڊيئيٽ حساب ڪتاب). Wiki آرٽيڪل.

چونڊيل طريقي تي مدار رکندي، مسئلا حل ڪرڻ لاء حالتون ۽ پابنديون مختلف طور تي مقرر ڪيا ويا آهن:

طبقاتي اعتراض Bounds طريقن لاءِ L-BFGS-B، TNC، SLSQP، ڀروسو-constr؛
فهرست (min, max) ساڳئي طريقن لاءِ L-BFGS-B, TNC, SLSQP, trust-constr؛
هڪ اعتراض يا شين جي فهرست LinearConstraint, NonlinearConstraint COBYLA لاءِ، SLSQP، ڀروسو ڪنٽر طريقن؛
لغت يا لغتن جي فهرست {'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt} COBYLA، SLSQP طريقن لاءِ.

آرٽيڪل جو خاڪو:
1) ڀروسي واري علائقي ۾ مشروط اصلاح الورورٿم جي استعمال تي غور ڪريو (طريقو= ”ٽرسٽ-ڪانسٽر“) اعتراضن سان بيان ڪيل رڪاوٽن سان Bounds, LinearConstraint, NonlinearConstraint ;
2) ترتيب وار پروگرامنگ تي غور ڪريو گھٽ ۾ گھٽ اسڪوائر جو طريقو استعمال ڪندي (طريقو = "SLSQP") پابندين سان گڏ ڊڪشنري جي صورت ۾ بيان ڪيل {'type', 'fun', 'jac', 'args'};
3) ويب اسٽوڊيو جو مثال استعمال ڪندي ٺاهيل شين جي اصلاح جي مثال جو تجزيو ڪريو.

مشروط اصلاح جو طريقو="trust-constr"

عمل جي طريقيڪار trust-constr تي مبني EQSQP برابري جي شڪل جي پابندين سان مسئلن لاءِ سفر عدم مساوات جي صورت ۾ رڪاوٽن سان مسئلن لاء. ٻئي طريقا الگورتھم پاران لاڳو ڪيا ويا آھن مقامي گھٽ ۾ گھٽ اعتماد واري علائقي ۾ ڳولڻ لاءِ ۽ وڏي پيماني تي مسئلن لاءِ مناسب آھن.

عام فارم ۾ گھٽ ۾ گھٽ ڳولڻ جي مسئلي جي رياضياتي فارموليشن:

سخت برابري جي پابندين لاء، هيٺيون حدون مٿئين حد جي برابر آهي .
ھڪڙي طرفي پابندي لاء، مٿئين يا ھيٺئين حد مقرر ڪئي وئي آھي np.inf لاڳاپيل نشاني سان.
اچو ته اهو ضروري آهي ته گهٽ ۾ گهٽ معلوم ٿئي Rosenbrock فنڪشن جو ٻن متغيرن جو:

انهي حالت ۾، هيٺيون پابنديون ان جي تعريف جي ڊومين تي مقرر ٿيل آهن:

اسان جي حالت ۾، نقطي تي هڪ منفرد حل آهي ، جنهن لاءِ صرف پهرين ۽ چوٿين پابنديون صحيح آهن.
اچو ته هيٺئين کان مٿي تائين پابندين جي ذريعي وڃو ۽ ڏسو ته اسان انهن کي اسپيپي ۾ ڪيئن لکي سگهون ٿا.
پابنديون и اچو ته ان کي 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)

جڏهن هيسين ميٽرڪس جي حساب سان تمام گهڻي ڪوشش جي ضرورت آهي، توهان هڪ ڪلاس استعمال ڪري سگهو ٿا HessianUpdateStrategy. هيٺيون حڪمت عمليون موجود آهن: 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')

پابندين لاءِ جيڪوبين ميٽرڪس پڻ محدود فرقن کي استعمال ڪندي حساب ڪري سگھجي ٿو. بهرحال، هن معاملي ۾ هيسين ميٽرڪس کي محدود فرقن جي استعمال سان حساب نه ٿو ڪري سگهجي. هيسين کي هڪ فنڪشن جي طور تي يا 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]

جيڪڏهن ضروري هجي ته، هيسين کي ڳڻڻ جي فنڪشن کي لائنار آپريٽر ڪلاس استعمال ڪندي بيان ڪري سگهجي ٿو

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)

يا پيراميٽر جي ذريعي Hessian ۽ هڪ خودمختيار ویکٹر جي پيداوار 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)

متبادل طور تي، فنڪشن جو پهريون ۽ ٻيو نڪتل بهتر ٿي سگهي ٿو تقريبن ٿي سگهي ٿو. مثال طور، هيسين فنڪشن استعمال ڪندي تقريبن ٿي سگهي ٿو 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 tr کان.
x1 - ڪارپوريٽ ويب سائيٽون، 20 کان.
x2 - آن لائن اسٽور، 30 ٽر.

اسان جي دوستانه ڪم ڪندڙ ٽيم ۾ چار جونيئر، ٻه مڊل ۽ هڪ سينئر شامل آهن. سندن مھينا ڪم ڪندڙ وقت فنڊ:

جون: 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 تصويرن جي هڪ سيٽ مان هڪ 3D ساخت ٺاهڻ لاءِ (Habré تي مضمون) ۾ ڏسي سگھجي ٿو پچائڻ وارو ڪتاب.

معلومات جو مکيه ذريعو آهي docs.scipy.orgجيڪي هن ۽ ٻين حصن جي ترجمي ۾ حصو وٺڻ چاهين ٿا scipy ڀليڪار ڪيون ٿا GitHub.

Спасибо mephistophees اشاعت جي تياري ۾ حصو وٺڻ لاء.

جو ذريعو: www.habr.com

SciPy، حالتن سان اصلاح

تعارف

مشروط اصلاح جو طريقو="trust-constr"

مشروط اصلاح جو طريقو="SLSQP"

اصلاح جو مثال

ٿڪل

تبصرو شامل ڪريو جواب منسوخ