SciPy, ოპტიმიზაცია

SciPy (გამოითქმის sai pie) არის მათემატიკური აპლიკაციის პაკეტი, რომელიც დაფუძნებულია Numpy Python გაფართოებაზე. SciPy-ით, თქვენი ინტერაქტიული Python სესია ხდება იგივე სრული მონაცემთა მეცნიერება და რთული სისტემის პროტოტიპების გარემო, როგორც MATLAB, IDL, Octave, R-Lab და SciLab. დღეს მინდა მოკლედ ვისაუბრო იმაზე, თუ როგორ გამოვიყენოთ ზოგიერთი ცნობილი ოპტიმიზაციის ალგორითმი scipy.optimize პაკეტში. უფრო დეტალური და განახლებული დახმარება ფუნქციების გამოყენებასთან დაკავშირებით ყოველთვის შეგიძლიათ მიიღოთ help() ბრძანების ან Shift+Tab-ის გამოყენებით.

შესავალი

იმისათვის, რომ დაიცვათ თავი და მკითხველები პირველადი წყაროების ძიებისა და წაკითხვისგან, მეთოდების აღწერილობის ბმულები ძირითადად ვიკიპედიაში იქნება. როგორც წესი, ეს ინფორმაცია საკმარისია მეთოდების ზოგადი თვალსაზრისით და მათი გამოყენების პირობების გასაგებად. მათემატიკური მეთოდების არსის გასაგებად, მიჰყევით უფრო ავტორიტეტული პუბლიკაციების ბმულებს, რომლებიც შეგიძლიათ იხილოთ ყოველი სტატიის ბოლოს ან თქვენს საყვარელ საძიებო სისტემაში.

ასე რომ, scipy.optimize მოდული მოიცავს შემდეგი პროცედურების განხორციელებას:

1. რამდენიმე ცვლადის (მინიმალური) სკალარული ფუნქციების პირობითი და უპირობო მინიმიზაცია სხვადასხვა ალგორითმების გამოყენებით (Nelder-Mead simplex, BFGS, Newton conjugate gradients, კობილა и SLSQP)
2. გლობალური ოპტიმიზაცია (მაგალითად: ბასინჰოპინგი, diff_evolution)
3. ნარჩენების მინიმიზაცია MNC (უმცირესი_კვადრატები) და მრუდის მორგების ალგორითმები არაწრფივი უმცირესი კვადრატების გამოყენებით (curve_fit)
4. ერთი ცვლადის სკალარული ფუნქციების მინიმიზაცია (minim_scalar) და ფესვების ძიება (root_scalar)
5. განტოლებათა სისტემის მრავალგანზომილებიანი ამომხსნელები (ფესვი) სხვადასხვა ალგორითმების გამოყენებით (ჰიბრიდული პაუელი, ლევენბერგ-მარკვარტი ან ფართომასშტაბიანი მეთოდები, როგორიცაა ნიუტონ-კრილოვი).

ამ სტატიაში განვიხილავთ მხოლოდ პირველ პუნქტს მთელი სიიდან.

რამდენიმე ცვლადის სკალარული ფუნქციის უპირობო მინიმიზაცია

მინიმალური ფუნქცია scipy.optimize პაკეტიდან უზრუნველყოფს ზოგად ინტერფეისს რამდენიმე ცვლადის სკალარული ფუნქციების პირობითი და უპირობო მინიმიზაციის პრობლემების გადასაჭრელად. იმის დემონსტრირებისთვის, თუ როგორ მუშაობს, დაგვჭირდება რამდენიმე ცვლადის შესაბამისი ფუნქცია, რომელსაც მინიმიზაციას ვახდენთ სხვადასხვა გზით.

ამ მიზნებისათვის სრულყოფილია N ცვლადის როზენბროკის ფუნქცია, რომელსაც აქვს ფორმა:

მიუხედავად იმისა, რომ Rosenbrock ფუნქცია და მისი Jacobi და Hessian მატრიცები (პირველი და მეორე წარმოებული, შესაბამისად) უკვე განსაზღვრულია scipy.optimize პაკეტში, ჩვენ თვითონ განვსაზღვრავთ მას.

import numpy as np

def rosen(x):
    """The Rosenbrock function"""
    return np.sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0, axis=0)

სიცხადისთვის, მოდით დავხატოთ 3D-ში ორი ცვლადის როზენბროკის ფუნქციის მნიშვნელობები.

ნახატის კოდი

from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
from matplotlib import cm
from matplotlib.ticker import LinearLocator, FormatStrFormatter

# Настраиваем 3D график
fig = plt.figure(figsize=[15, 10])
ax = fig.gca(projection='3d')

# Задаем угол обзора
ax.view_init(45, 30)

# Создаем данные для графика
X = np.arange(-2, 2, 0.1)
Y = np.arange(-1, 3, 0.1)
X, Y = np.meshgrid(X, Y)
Z = rosen(np.array([X,Y]))

# Рисуем поверхность
surf = ax.plot_surface(X, Y, Z, cmap=cm.coolwarm)
plt.show()

წინასწარ იცოდეთ, რომ მინიმალური არის 0 at , მოდით შევხედოთ მაგალითებს, თუ როგორ განვსაზღვროთ Rosenbrock ფუნქციის მინიმალური მნიშვნელობა სხვადასხვა scipy.optimize პროცედურების გამოყენებით.

Nelder-Mead simplex მეთოდი

0-განზომილებიან სივრცეში იყოს საწყისი წერტილი x5. ვიპოვოთ როზენბროკის ფუნქციის მასთან ყველაზე ახლოს მყოფი მინიმალური წერტილი ალგორითმის გამოყენებით Nelder-Mead simplex (ალგორითმი მითითებულია, როგორც მეთოდის პარამეტრის მნიშვნელობა):

from scipy.optimize import minimize
x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])
res = minimize(rosen, x0, method='nelder-mead',
    options={'xtol': 1e-8, 'disp': True})
print(res.x)

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 339
         Function evaluations: 571
[1. 1. 1. 1. 1.]

სიმპლექსის მეთოდი არის ყველაზე მარტივი გზა აშკარად განსაზღვრული და საკმაოდ გლუვი ფუნქციის შესამცირებლად. ის არ საჭიროებს ფუნქციის წარმოებულების გამოთვლას, საკმარისია მხოლოდ მისი მნიშვნელობების მითითება. Nelder-Mead მეთოდი კარგი არჩევანია მარტივი მინიმიზაციის პრობლემებისთვის. თუმცა, რადგან ის არ იყენებს გრადიენტურ შეფასებებს, შეიძლება მეტი დრო დასჭირდეს მინიმუმის პოვნას.

პაუელის მეთოდი

არის კიდევ ერთი ოპტიმიზაციის ალგორითმი, რომელშიც გამოითვლება მხოლოდ ფუნქციის მნიშვნელობები პაუელის მეთოდი. მის გამოსაყენებლად, თქვენ უნდა დააყენოთ მეთოდი = 'powell' მინიმალური ფუნქციაში.

x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])
res = minimize(rosen, x0, method='powell',
    options={'xtol': 1e-8, 'disp': True})
print(res.x)

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 19
         Function evaluations: 1622
[1. 1. 1. 1. 1.]

ბროიდენ-ფლეტჩერ-გოლდფარბ-შანოს (BFGS) ალგორითმი

გამოსავალთან უფრო სწრაფი კონვერგენციის მისაღებად პროცედურა BFGS იყენებს ობიექტური ფუნქციის გრადიენტს. გრადიენტი შეიძლება განისაზღვროს როგორც ფუნქცია ან გამოითვალოს პირველი რიგის განსხვავებების გამოყენებით. ნებისმიერ შემთხვევაში, BFGS მეთოდი ჩვეულებრივ მოითხოვს ნაკლებ ფუნქციის გამოძახებას, ვიდრე simplex მეთოდი.

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

ეს გამოთქმა მოქმედებს ყველა ცვლადის წარმოებულებისთვის, გარდა პირველისა და უკანასკნელისა, რომლებიც განისაზღვრება როგორც:

მოდით შევხედოთ პითონის ფუნქციას, რომელიც ითვლის ამ გრადიენტს:

def rosen_der (x):
    xm = x [1: -1]
    xm_m1 = x [: - 2]
    xm_p1 = x [2:]
    der = np.zeros_like (x)
    der [1: -1] = 200 * (xm-xm_m1 ** 2) - 400 * (xm_p1 - xm ** 2) * xm - 2 * (1-xm)
    der [0] = -400 * x [0] * (x [1] -x [0] ** 2) - 2 * (1-x [0])
    der [-1] = 200 * (x [-1] -x [-2] ** 2)
    return der

გრადიენტის გამოთვლის ფუნქცია მითითებულია მინიმალური ფუნქციის jac პარამეტრის მნიშვნელობად, როგორც ეს ნაჩვენებია ქვემოთ.

res = minimize(rosen, x0, method='BFGS', jac=rosen_der, options={'disp': True})
print(res.x)

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 25
         Function evaluations: 30
         Gradient evaluations: 30
[1.00000004 1.0000001  1.00000021 1.00000044 1.00000092]

კონიუგატური გრადიენტის ალგორითმი (ნიუტონი)

ალგორითმი ნიუტონის კონიუგირებული გრადიენტები არის ნიუტონის შეცვლილი მეთოდი.
ნიუტონის მეთოდი ემყარება ლოკალურ არეში ფუნქციის მიახლოებას მეორე ხარისხის მრავალწევრით:

სადაც არის მეორე წარმოებულების მატრიცა (Hessian matrix, Hessian).
თუ ჰესიანი დადებითი განსაზღვრულია, მაშინ ამ ფუნქციის ლოკალური მინიმუმის პოვნა შესაძლებელია კვადრატული ფორმის ნულოვანი გრადიენტის ნულთან გათანაბრებით. შედეგი იქნება გამოხატულება:

ინვერსიული ჰესიანი გამოითვლება კონიუგატური გრადიენტის მეთოდით. როზენბროკის ფუნქციის შესამცირებლად ამ მეთოდის გამოყენების მაგალითი მოცემულია ქვემოთ. Newton-CG მეთოდის გამოსაყენებლად, თქვენ უნდა მიუთითოთ ფუნქცია, რომელიც ითვლის ჰესიანს.
როზენბროკის ფუნქციის ჰესიანი ანალიტიკური ფორმით უდრის:

სადაც и , განსაზღვრეთ მატრიცა .

მატრიცის დარჩენილი არანულოვანი ელემენტები უდრის:

მაგალითად, ხუთგანზომილებიან სივრცეში N = 5, ჰესიან მატრიცას როზენბროკის ფუნქციისთვის აქვს ზოლის ფორმა:

კოდი, რომელიც ითვლის ამ ჰესიანს კოდთან ერთად როზენბროკის ფუნქციის მინიმიზაციისთვის კონიუგირებული გრადიენტის (ნიუტონი) მეთოდის გამოყენებით:

def rosen_hess(x):
    x = np.asarray(x)
    H = np.diag(-400*x[:-1],1) - np.diag(400*x[:-1],-1)
    diagonal = np.zeros_like(x)
    diagonal[0] = 1200*x[0]**2-400*x[1]+2
    diagonal[-1] = 200
    diagonal[1:-1] = 202 + 1200*x[1:-1]**2 - 400*x[2:]
    H = H + np.diag(diagonal)
    return H

res = minimize(rosen, x0, method='Newton-CG', 
               jac=rosen_der, hess=rosen_hess,
               options={'xtol': 1e-8, 'disp': True})
print(res.x)

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 24
         Function evaluations: 33
         Gradient evaluations: 56
         Hessian evaluations: 24
[1.         1.         1.         0.99999999 0.99999999]

მაგალითი ჰესიანის პროდუქტის ფუნქციის განსაზღვრით და თვითნებური ვექტორით

რეალურ სამყაროში არსებულ პრობლემებში, მთელი ჰესიანური მატრიცის გამოთვლასა და შენახვას შეიძლება დასჭირდეს მნიშვნელოვანი დრო და მეხსიერების რესურსები. ამ შემთხვევაში, რეალურად არ არის საჭირო თავად ჰესიანური მატრიცის დაზუსტება, რადგან მინიმიზაციის პროცედურა მოითხოვს მხოლოდ ვექტორს, რომელიც ტოლია ჰესიანის ნამრავლს სხვა თვითნებურ ვექტორთან. ამრიგად, გამოთვლითი თვალსაზრისით, გაცილებით სასურველია დაუყოვნებლივ განისაზღვროს ფუნქცია, რომელიც აბრუნებს ჰესიანის ნამრავლის შედეგს თვითნებური ვექტორით.

განვიხილოთ ჰესის ფუნქცია, რომელიც პირველ არგუმენტად იღებს მინიმიზაციის ვექტორს, ხოლო მეორე არგუმენტად თვითნებურ ვექტორს (მინიმიზირებული ფუნქციის სხვა არგუმენტებთან ერთად). ჩვენს შემთხვევაში, როზენბროკის ფუნქციის ჰესიანის ნამრავლის გამოთვლა თვითნებური ვექტორით არ არის ძალიან რთული. თუ p არის თვითნებური ვექტორი, შემდეგ პროდუქტი აქვს ფორმა:

ფუნქცია, რომელიც ითვლის ჰესიანური და თვითნებური ვექტორის ნამრავლს, გადაეცემა როგორც ჰესპის არგუმენტის მნიშვნელობა მინიმიზაციის ფუნქციას:

def rosen_hess_p(x, p):
    x = np.asarray(x)
    Hp = np.zeros_like(x)
    Hp[0] = (1200*x[0]**2 - 400*x[1] + 2)*p[0] - 400*x[0]*p[1]
    Hp[1:-1] = -400*x[:-2]*p[:-2]+(202+1200*x[1:-1]**2-400*x[2:])*p[1:-1] 
    -400*x[1:-1]*p[2:]
    Hp[-1] = -400*x[-2]*p[-2] + 200*p[-1]
    return Hp

res = minimize(rosen, x0, method='Newton-CG',
               jac=rosen_der, hessp=rosen_hess_p,
               options={'xtol': 1e-8, 'disp': True})

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 24
         Function evaluations: 33
         Gradient evaluations: 56
         Hessian evaluations: 66

კონიუგირებული გრადიენტის ნდობის რეგიონის ალგორითმი (ნიუტონი)

ჰესიანური მატრიცის ცუდი კონდიცირება და არასწორი ძიების მიმართულებები შეიძლება გამოიწვიოს ნიუტონის კონიუგირებული გრადიენტის ალგორითმი არაეფექტური. ასეთ შემთხვევებში უპირატესობა ენიჭება ნდობის რეგიონის მეთოდი (ნდობა-რეგიონი) კონიუგირებული ნიუტონის გრადიენტები.

მაგალითი ჰესიანური მატრიცის განმარტებით:

res = minimize(rosen, x0, method='trust-ncg',
               jac=rosen_der, hess=rosen_hess,
               options={'gtol': 1e-8, 'disp': True})
print(res.x)

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 20
         Function evaluations: 21
         Gradient evaluations: 20
         Hessian evaluations: 19
[1. 1. 1. 1. 1.]

მაგალითი ჰესიანის ნამრავლის ფუნქციით და თვითნებური ვექტორით:

res = minimize(rosen, x0, method='trust-ncg', 
                jac=rosen_der, hessp=rosen_hess_p, 
                options={'gtol': 1e-8, 'disp': True})
print(res.x)

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 20
         Function evaluations: 21
         Gradient evaluations: 20
         Hessian evaluations: 0
[1. 1. 1. 1. 1.]

კრილოვის ტიპის მეთოდები

ნდობა-ncg მეთოდის მსგავსად, კრილოვის ტიპის მეთოდები კარგად არის შესაფერისი ფართომასშტაბიანი პრობლემების გადასაჭრელად, რადგან ისინი იყენებენ მხოლოდ მატრიცულ-ვექტორულ პროდუქტებს. მათი არსი არის პრობლემის გადაჭრა ნდობის რეგიონში, რომელიც შემოიფარგლება შეკვეცილი კრილოვის ქვესივრცით. გაურკვეველი პრობლემებისთვის უმჯობესია გამოვიყენოთ ეს მეთოდი, რადგან ის იყენებს არაწრფივი გამეორებების უფრო მცირე რაოდენობას ქვეპრობლემზე მატრიცა-ვექტორული პროდუქტების მცირე რაოდენობის გამო, სანდო-ncg მეთოდთან შედარებით. გარდა ამისა, კვადრატული ქვეპრობლემის გადაწყვეტა უფრო ზუსტად არის ნაპოვნი, ვიდრე trust-ncg მეთოდის გამოყენებით.
მაგალითი ჰესიანური მატრიცის განმარტებით:

res = minimize(rosen, x0, method='trust-krylov',
               jac=rosen_der, hess=rosen_hess,
               options={'gtol': 1e-8, 'disp': True})

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 19
         Function evaluations: 20
         Gradient evaluations: 20
         Hessian evaluations: 18

print(res.x)

    [1. 1. 1. 1. 1.]

მაგალითი ჰესიანის ნამრავლის ფუნქციით და თვითნებური ვექტორით:

res = minimize(rosen, x0, method='trust-krylov',
               jac=rosen_der, hessp=rosen_hess_p,
               options={'gtol': 1e-8, 'disp': True})

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 19
         Function evaluations: 20
         Gradient evaluations: 20
         Hessian evaluations: 0

print(res.x)

    [1. 1. 1. 1. 1.]

ნდობის რეგიონში სავარაუდო ამოხსნის ალგორითმი

ყველა მეთოდი (Newton-CG, trust-ncg და trust-krylov) კარგად არის შესაფერისი ფართომასშტაბიანი პრობლემების გადასაჭრელად (ათასობით ცვლადი). ეს გამოწვეულია იმით, რომ ფუძემდებლური კონიუგირებული გრადიენტის ალგორითმი გულისხმობს ინვერსიული ჰესიანური მატრიცის მიახლოებით განსაზღვრას. გამოსავალი ნაპოვნია განმეორებით, ჰესიანის აშკარა გაფართოების გარეშე. ვინაიდან საჭიროა მხოლოდ ჰესიანური და თვითნებური ვექტორის ნამრავლის ფუნქციის განსაზღვრა, ეს ალგორითმი განსაკუთრებით კარგია იშვიათ (ზოლის დიაგონალური) მატრიცებთან მუშაობისთვის. ეს უზრუნველყოფს მეხსიერების დაბალ ხარჯებს და მნიშვნელოვან დროს დაზოგავს.

საშუალო ზომის პრობლემებისთვის, ჰესიანის შენახვისა და ფაქტორინგის ღირებულება არ არის კრიტიკული. ეს ნიშნავს, რომ შესაძლებელია გამოსავლის მიღება ნაკლები გამეორებით, ნდობის რეგიონის ქვეპრობლემების თითქმის ზუსტად გადაჭრით. ამისათვის რამდენიმე არაწრფივი განტოლება წყდება იტერაციულად თითოეული კვადრატული ქვეპრობლემისთვის. ასეთი გამოსავალი ჩვეულებრივ მოითხოვს ჰესიანური მატრიცის 3 ან 4 ქოლესკის დაშლას. შედეგად, მეთოდი გადაიყრება ნაკლებ გამეორებებში და მოითხოვს ნაკლებ ობიექტური ფუნქციის გამოთვლებს, ვიდრე სხვა დანერგილი ნდობის რეგიონის მეთოდები. ეს ალგორითმი გულისხმობს მხოლოდ სრული ჰესიანური მატრიცის განსაზღვრას და არ უჭერს მხარს ჰესიანის პროდუქტის ფუნქციის და თვითნებური ვექტორის გამოყენების უნარს.

როზენბროკის ფუნქციის მინიმიზაციის მაგალითი:

res = minimize(rosen, x0, method='trust-exact',
               jac=rosen_der, hess=rosen_hess,
               options={'gtol': 1e-8, 'disp': True})
res.x

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 13
         Function evaluations: 14
         Gradient evaluations: 13
         Hessian evaluations: 14

array([1., 1., 1., 1., 1.])

ჩვენ ალბათ იქ გავჩერდებით. შემდეგ სტატიაში შევეცდები გითხრათ ყველაზე საინტერესო პირობითი მინიმიზაციის შესახებ, მინიმიზაციის გამოყენება დაახლოების ამოცანების გადაჭრაში, ერთი ცვლადის ფუნქციის მინიმიზაცია, თვითნებური მინიმიზატორები და განტოლებათა სისტემის ფესვების პოვნა scipy.optimize-ის გამოყენებით. პაკეტი.

წყარო: https://docs.scipy.org/doc/scipy/reference/

წყარო: www.habr.com