SciPy, শর্ত সহ অপ্টিমাইজেশান

SciPy (উচ্চারিত সাই পাই) হল একটি নম্পি-ভিত্তিক গণিত প্যাকেজ যাতে C এবং Fortran লাইব্রেরিও অন্তর্ভুক্ত থাকে। SciPy আপনার ইন্টারেক্টিভ পাইথন সেশনকে MATLAB, IDL, Octave, R, বা SciLab-এর মতো একটি সম্পূর্ণ ডেটা বিজ্ঞান পরিবেশে পরিণত করে।

এই নিবন্ধে, আমরা গাণিতিক প্রোগ্রামিংয়ের প্রাথমিক কৌশলগুলি দেখব - scipy.optimize প্যাকেজ ব্যবহার করে বেশ কয়েকটি ভেরিয়েবলের একটি স্কেলার ফাংশনের জন্য শর্তসাপেক্ষ অপ্টিমাইজেশন সমস্যার সমাধান করা। অনিয়ন্ত্রিত অপ্টিমাইজেশান অ্যালগরিদম ইতিমধ্যে আলোচনা করা হয়েছে শেষ প্রবন্ধ. হেল্প() কমান্ড, শিফট+ট্যাব বা ইন ব্যবহার করে সর্বদা স্কিপি ফাংশন সম্পর্কে আরও বিস্তারিত এবং আপ-টু-ডেট সহায়তা পাওয়া যেতে পারে অফিসিয়াল ডকুমেন্টেশন.

ভূমিকা

scipy.optimize প্যাকেজে শর্তসাপেক্ষ এবং সীমাহীন উভয় অপ্টিমাইজেশন সমস্যা সমাধানের জন্য একটি সাধারণ ইন্টারফেস ফাংশন দ্বারা সরবরাহ করা হয়েছে minimize(). যাইহোক, এটি জানা যায় যে সমস্ত সমস্যা সমাধানের জন্য কোনও সর্বজনীন পদ্ধতি নেই, তাই একটি পর্যাপ্ত পদ্ধতির পছন্দ, সর্বদা হিসাবে, গবেষকের কাঁধে পড়ে।
উপযুক্ত অপ্টিমাইজেশান অ্যালগরিদম ফাংশন আর্গুমেন্ট ব্যবহার করে নির্দিষ্ট করা হয় minimize(..., method="").
বেশ কয়েকটি ভেরিয়েবলের একটি ফাংশনের শর্তাধীন অপ্টিমাইজেশনের জন্য, নিম্নলিখিত পদ্ধতিগুলির বাস্তবায়ন উপলব্ধ:

• trust-constr — আত্মবিশ্বাস অঞ্চলে একটি স্থানীয় সর্বনিম্ন অনুসন্ধান করুন। উইকি নিবন্ধ, Habré নিবন্ধ;
• SLSQP — সীমাবদ্ধতা সহ অনুক্রমিক দ্বিঘাত প্রোগ্রামিং, ল্যাগ্রেঞ্জ সিস্টেম সমাধানের জন্য নিউটনিয়ান পদ্ধতি। উইকি নিবন্ধ.
• TNC - সঙ্কুচিত নিউটন সীমাবদ্ধ, সীমিত সংখ্যক পুনরাবৃত্তি, বিপুল সংখ্যক স্বাধীন ভেরিয়েবল সহ অরৈখিক ফাংশনের জন্য ভাল। উইকি নিবন্ধ.
• L-BFGS-B — Broyden–Fletcher–Goldfarb–Shanno দলের একটি পদ্ধতি, যা হেসিয়ান ম্যাট্রিক্স থেকে ভেক্টরের আংশিক লোড হওয়ার কারণে মেমরির খরচ কমিয়ে প্রয়োগ করা হয়েছে। উইকি নিবন্ধ, Habré নিবন্ধ.
• COBYLA — MARE সীমাবদ্ধ অপ্টিমাইজেশন লিনিয়ার অ্যাপ্রোক্সিমেশন দ্বারা, রৈখিক আনুমানিকতার সাথে সীমাবদ্ধ অপ্টিমাইজেশন (গ্রেডিয়েন্ট গণনা ছাড়া)। উইকি নিবন্ধ.

নির্বাচিত পদ্ধতির উপর নির্ভর করে, সমস্যা সমাধানের জন্য শর্ত এবং সীমাবদ্ধতা ভিন্নভাবে সেট করা হয়েছে:

• ক্লাস অবজেক্ট Bounds L-BFGS-B, TNC, SLSQP, বিশ্বাস-কনস্ট্র পদ্ধতির জন্য;
• ক্রমতালিকা (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 সংশ্লিষ্ট চিহ্ন দিয়ে।
দুটি ভেরিয়েবলের একটি পরিচিত রোজেনব্রক ফাংশনের ন্যূনতম সন্ধান করা প্রয়োজন:

এই ক্ষেত্রে, নিম্নলিখিত সীমাবদ্ধতাগুলি এর সংজ্ঞার ডোমেনে সেট করা হয়েছে:

আমাদের ক্ষেত্রে, পয়েন্ট এ একটি অনন্য সমাধান আছে , যার জন্য শুধুমাত্র প্রথম এবং চতুর্থ সীমাবদ্ধতা বৈধ।
আসুন নীচে থেকে উপরে সীমাবদ্ধতার মধ্য দিয়ে যাওয়া যাক এবং আমরা কীভাবে সেগুলিকে স্কিপিতে লিখতে পারি তা দেখি।
সীমাবদ্ধতা и এর Bounds অবজেক্ট ব্যবহার করে এটি সংজ্ঞায়িত করা যাক।

from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])

সীমাবদ্ধতা и আসুন এটি লিনিয়ার আকারে লিখি:

আসুন এই সীমাবদ্ধতাগুলিকে লিনিয়ার কনস্ট্রেন্ট অবজেক্ট হিসাবে সংজ্ঞায়িত করি:

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')

সীমাবদ্ধতার জন্য জ্যাকোবিয়ান ম্যাট্রিক্সও সসীম পার্থক্য ব্যবহার করে গণনা করা যেতে পারে। যাইহোক, এই ক্ষেত্রে হেসিয়ান ম্যাট্রিক্স সসীম পার্থক্য ব্যবহার করে গণনা করা যাবে না। 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]

যদি প্রয়োজন হয়, হেসিয়ান গণনার ফাংশনটি 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)

বিকল্পভাবে, অপ্টিমাইজ করা ফাংশনের প্রথম এবং দ্বিতীয় ডেরিভেটিভ আনুমানিক করা যেতে পারে। উদাহরণস্বরূপ, হেসিয়ান ফাংশন ব্যবহার করে আনুমানিক করা যেতে পারে 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 tr থেকে।
• 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 সম্পূর্ণরূপে একাডেমিক উদ্দেশ্যে, যে কারণে প্রদত্ত উদাহরণটি এমন একটি কমিক প্রকৃতির।

অনেক তত্ত্ব এবং ভার্চুয়াল উদাহরণ পাওয়া যাবে, উদাহরণস্বরূপ, আইএল আকুলিচের বই "উদাহরণ এবং সমস্যাগুলিতে গাণিতিক প্রোগ্রামিং"। আরো হার্ডকোর অ্যাপ্লিকেশন scipy.optimize ছবির একটি সেট থেকে একটি 3D কাঠামো তৈরি করতে (Habré নিবন্ধ) এ দেখা যাবে স্কিপি-রান্নার বই.

তথ্যের প্রধান উৎস হল docs.scipy.orgযারা এই এবং অন্যান্য বিভাগের অনুবাদে অবদান রাখতে ইচ্ছুক scipy স্বাগতম GitHub.

Спасибо মেফিস্টোফিস প্রকাশনার প্রস্তুতিতে অংশগ্রহণের জন্য।

উত্স: www.habr.com