SciPy, ოპტიმიზაცია პირობებით

SciPy (გამოითქმის sai pie) არის numpy-ზე დაფუძნებული მათემატიკის პაკეტი, რომელიც ასევე მოიცავს C და Fortran ბიბლიოთეკებს. SciPy აქცევს თქვენს ინტერაქტიულ პითონის სესიას მონაცემთა მეცნიერების სრულ გარემოში, როგორიცაა MATLAB, IDL, Octave, R ან SciLab.

ამ სტატიაში განვიხილავთ მათემატიკური პროგრამირების ძირითად ტექნიკას - პირობითი ოპტიმიზაციის ამოცანების ამოხსნას რამდენიმე ცვლადის სკალარული ფუნქციისთვის scipy.optimize პაკეტის გამოყენებით. შეუზღუდავი ოპტიმიზაციის ალგორითმები უკვე განხილულია ბოლო სტატია. უფრო დეტალური და განახლებული დახმარება scipy ფუნქციების შესახებ ყოველთვის შეგიძლიათ მიიღოთ help() ბრძანების გამოყენებით, Shift+Tab ან ოფიციალური დოკუმენტაცია.

შესავალი

საერთო ინტერფეისი როგორც პირობითი, ისე შეუზღუდავი ოპტიმიზაციის პრობლემების გადასაჭრელად scipy.optimize პაკეტში მოცემულია ფუნქციით. minimize(). თუმცა ცნობილია, რომ ყველა პრობლემის გადაჭრის უნივერსალური მეთოდი არ არსებობს, ამიტომ ადეკვატური მეთოდის არჩევანი, როგორც ყოველთვის, მკვლევარის მხრებზე მოდის.
შესაბამისი ოპტიმიზაციის ალგორითმი მითითებულია ფუნქციის არგუმენტის გამოყენებით minimize(..., method="").
რამდენიმე ცვლადის ფუნქციის პირობითი ოპტიმიზაციისთვის ხელმისაწვდომია შემდეგი მეთოდების განხორციელება:

• trust-constr — მოძებნეთ ადგილობრივი მინიმუმი ნდობის რეგიონში. ვიკი სტატია, სტატია ჰაბრეზე;
• SLSQP — თანმიმდევრული კვადრატული პროგრამირება შეზღუდვებით, ნიუტონის მეთოდი ლაგრანგის სისტემის ამოხსნისთვის. ვიკი სტატია.
• TNC - Truncated Newton შეზღუდული, შეზღუდული რაოდენობის გამეორება, კარგია არაწრფივი ფუნქციებისთვის დიდი რაოდენობით დამოუკიდებელი ცვლადები. ვიკი სტატია.
• L-BFGS-B - მეთოდი Broyden-Fletcher-Goldfarb-Shanno-ს გუნდიდან, განხორციელებული მეხსიერების შემცირებული მოხმარებით ჰესიანური მატრიციდან ვექტორების ნაწილობრივი დატვირთვის გამო. ვიკი სტატია, სტატია ჰაბრეზე.
• 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) განიხილეთ პირობითი ოპტიმიზაციის ალგორითმის გამოყენება ნდობის რეგიონში (metod=”trust-constr”) ობიექტების სახით მითითებული შეზღუდვებით. Bounds, LinearConstraint, NonlinearConstraint ;
2) განვიხილოთ თანმიმდევრული პროგრამირება უმცირესი კვადრატების მეთოდის გამოყენებით (მეთოდი = "SLSQP") ლექსიკონის სახით მითითებული შეზღუდვებით. {'type', 'fun', 'jac', 'args'};
3) გაანალიზეთ წარმოებული პროდუქციის ოპტიმიზაციის მაგალითი ვებ სტუდიის მაგალითის გამოყენებით.

პირობითი ოპტიმიზაციის მეთოდი = "trust-constr"

მეთოდის განხორციელება trust-constr დაფუძნებული EQSQP თანასწორობის ფორმის შეზღუდვებთან დაკავშირებული პრობლემებისთვის და TRIP უტოლობების სახით შეზღუდვების პრობლემებისთვის. ორივე მეთოდი დანერგილია ალგორითმებით ნდობის რეგიონში ადგილობრივი მინიმუმის მოსაძებნად და კარგად შეეფერება ფართომასშტაბიან პრობლემებს.

ზოგადი ფორმით მინიმუმის პოვნის პრობლემის მათემატიკური ფორმულირება:

მკაცრი თანასწორობის შეზღუდვებისთვის, ქვედა ზღვარი დაყენებულია ზედა ზღვარის ტოლი .
ცალმხრივი შეზღუდვისთვის დაყენებულია ზედა ან ქვედა ზღვარი 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)

ჰესიანური მატრიცის გამოთვლისას დიდ ძალისხმევას მოითხოვს, შეგიძლიათ გამოიყენოთ კლასი 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]

საჭიროების შემთხვევაში, 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)

ალტერნატიულად, ოპტიმიზირებული ფუნქციის პირველი და მეორე წარმოებულები შეიძლება იყოს მიახლოებული. მაგალითად, ჰესიანის დაახლოება შესაძლებელია ფუნქციის გამოყენებით 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 ტრ.

ჩვენი მეგობრული სამუშაო გუნდი შედგება ოთხი უმცროსი, ორი შუა და ერთი უფროსი. მათი ყოველთვიური სამუშაო დროის ფონდი:

• ივნისი: 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 სტრუქტურის შექმნა სურათების ნაკრებიდან (სტატია ჰაბრეზე) შეგიძლიათ ნახოთ სციპიურ-კულინარიული წიგნი.

ინფორმაციის ძირითადი წყაროა docs.scipy.orgმსურველებს წვლილი შეიტანონ ამ და სხვა განყოფილებების თარგმნაში scipy Კეთილი იყოს თქვენი მობრძანება GitHub.

მადლობა მეფისტოფეები პუბლიკაციის მომზადებაში მონაწილეობისთვის.

წყარო: www.habr.com