🥇SciPy, оптимизатсия

SciPy (талаффузи sai pie) як бастаи барномаҳои математикӣ дар асоси васеъшавии Numpy Python мебошад. Бо SciPy, сессияи интерактивии Python-и шумо ба ҳамон як илми мукаммали маълумот ва муҳити мураккаби прототипсозии система ҳамчун MATLAB, IDL, Octave, R-Lab ва SciLab табдил меёбад. Имрӯз ман мехоҳам ба таври мухтасар дар бораи чӣ гуна истифода бурдани баъзе алгоритмҳои маъруфи оптимизатсия дар бастаи scipy.optimize сӯҳбат кунам. Кӯмаки муфассал ва муосирро оид ба истифодаи функсияҳо ҳамеша бо ёрии фармони help() ё бо истифода аз Shift+Tab гирифтан мумкин аст.

Муқаддима

Барои наҷот додани худ ва хонандагон аз ҷустуҷӯ ва мутолиаи манбаъҳои аввалия, истинод ба тавсифи усулҳо асосан дар Википедия хоҳад буд. Чун қоида, ин маълумот барои фаҳмидани усулҳои умумӣ ва шартҳои татбиқи онҳо кифоя аст. Барои фаҳмидани моҳияти усулҳои риёзӣ, истинодҳоро ба нашрияҳои бонуфузе пайгирӣ кунед, ки онҳоро дар охири ҳар як мақола ё дар системаи ҷустуҷӯии дӯстдоштаи худ пайдо кардан мумкин аст.

Ҳамин тариқ, модули scipy.optimize татбиқи расмиёти зеринро дар бар мегирад:

Минимизатсияи шартӣ ва бидуни шарти функсияҳои скалярии якчанд тағирёбанда (минимум) бо истифода аз алгоритмҳои гуногун (Нелдер-Мид симплекс, BFGS, градиентҳои конъюгатии Нютон, КОБИЛА и SLSQP)
Оптимизатсияи глобалӣ (масалан: оббозӣ, diff_evolution)
Кам кардани боқимондаҳо MNC (камтарин_мураббаъҳо) ва алгоритмҳои мувофиқ кардани каҷ бо истифода аз квадратҳои хурдтарини ғайрихаттӣ (curve_fit)
Кам кардани функсияҳои скалярии як тағирёбанда (minim_scalar) ва ҷустуҷӯи решаҳо (root_scalar)
Ҳалли бисёрченакаи системаи муодилаҳо (реша) бо истифода аз алгоритмҳои гуногун (гибридии Пауэлл, Левенберг-Марквардт ё усулҳои миқёси калон ба монанди Нютон-Крылов).

Дар ин мақола мо танҳо ҷузъи якуми ин рӯйхатро баррасӣ хоҳем кард.

Минимумикунонии бечунучарои функсияи скалярии якчанд тағирёбанда

Функсияи минимум аз бастаи scipy.optimize интерфейси умумиро барои ҳалли масъалаҳои минимизатсияи шартӣ ва бидуни шарти функсияҳои скалярии якчанд тағирёбанда таъмин мекунад. Барои нишон додани он, ки он чӣ гуна кор мекунад, ба мо функсияи мувофиқи якчанд тағирёбанда лозим аст, ки мо онҳоро бо роҳҳои гуногун кам мекунем.

Барои ин мақсадҳо, функсияи Розенброк аз N тағирёбанда комил аст, ки шакли зерин дорад:

Сарфи назар аз он, ки функсияи Розенброк ва матритсаҳои Якоби ва Гессии он (ҳосилаҳои якум ва дуюм) аллакай дар бастаи 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 дар , биёед мисолҳои чӣ гуна муайян кардани арзиши ҳадди ақали функсияи Розенброкро бо истифода аз расмиёти гуногуни scipy.optimize дида бароем.

Усули симплекси Нелдер-Мид

Бигзор дар фазои 0-ченака нуқтаи ибтидоии x5 бошад. Бо истифода аз алгоритм нуқтаи минималии функсияи Розенброкро ба он наздиктар меёбем Нелдер-Мид симплекси (алгоритм ҳамчун арзиши параметри метод муайян карда мешавад):

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.]

Алгоритми Broyden-Fletcher-Goldfarb-Shanno (BFGS).

Барои ба даст овардани конвергенсия тезтар ба ҳалли, тартиби BFGS градиенти вазифаи максадро истифода мебарад. Градиентро ҳамчун функсия муайян кардан мумкин аст ё бо истифода аз фарқиятҳои тартиби аввал ҳисоб карда мешавад. Дар ҳар сурат, усули BFGS маъмулан нисбат ба усули симплекс зангҳои функсионалии камтарро талаб мекунад.

Ҳосилаи функсияи Розенброкро дар шакли аналитикӣ пайдо кунем:

Ин ифода барои ҳосилаҳои ҳама тағирёбандаҳо, ба истиснои якум ва охирин, ки чунин муайян карда шудаанд, дуруст аст:

Биёед ба функсияи Python назар кунем, ки ин градиентро ҳисоб мекунад:

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]

Алгоритм градиенти конъюгатӣ (Ньютон)

Алгоритм Градиентҳои конъюгатии Нютон усули тағирёфтаи Нютон мебошад.
Усули Нютон ба наздик кардани функсия дар минтақаи маҳаллӣ бо полиномии дараҷаи дуюм асос ёфтааст:

ки матритсаи ҳосилаҳои дуюм (матритсаи гессӣ, гессӣ) мебошад.
Агар Гесси муайяни мусбат бошад, пас минимуми локалии ин функсияро тавассути баробар кардани градиенти сифрии шакли квадратӣ ба сифр ёфтан мумкин аст. Натиҷа ин ифода хоҳад буд:

Ҳесси баръакс бо усули градиенти конъюгатӣ ҳисоб карда мешавад. Намунаи истифодаи ин усул барои кам кардани функсияи Rosenbrock дар зер оварда шудааст. Барои истифодаи усули 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 вектори ихтиёрӣ аст, пас маҳсулот ба назар мерасад:

Функсияе, ки ҳосили гессӣ ва вектори ихтиёриро ҳисоб мекунад, ҳамчун арзиши аргументи hessp ба функсияи ҳадди ақалл интиқол дода мешавад:

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 шумораи камтари итератсияҳои ғайрихаттӣ аз ҳисоби миқдори ками маҳсулоти матритса-вектор барои як зерпроблемаро истифода мебарад. Илова бар ин, ҳалли зермасъалаи квадратӣ нисбат ба истифодаи усули трест-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.]

Алгоритм барои ҳалли тахминӣ дар минтақаи эътимод

Ҳама усулҳо (Ньютон-CG, трест-ncg ва трест-крылов) барои ҳалли масъалаҳои калонҳаҷм (бо ҳазорҳо тағирёбанда) мувофиқанд. Ин аз он сабаб аст, ки алгоритми асосии градиенти конъюгатӣ муайянкунии тахминии матритсаи баръакси Гессиро дар назар дорад. Ҳалли он ба таври такрорӣ, бидуни тавсеаи равшани Ҳессиан пайдо мешавад. Азбаски ба шумо танҳо лозим аст, ки функсияро барои ҳосили гессӣ ва вектори худсарона муайян кунед, ин алгоритм махсусан барои кор бо матритсаҳои пароканда (диагонали банд) хуб аст. Ин хароҷоти ками хотира ва сарфаи назарраси вақтро таъмин мекунад.

Барои мушкилоти миёна, арзиши нигоҳдорӣ ва факторинги Hessian муҳим нест. Ин маънои онро дорад, ки дар такрори камтар ҳалли мушкилот ба даст овардан мумкин аст, ки зерпроблемаҳои минтақаи трестро қариб дақиқ ҳал мекунанд. Барои ин барои ҳар як зермасъалаи квадратӣ баъзе муодилаҳои ғайрихаттӣ ба таври такрорӣ ҳал карда мешаванд. Чунин ҳалли одатан 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/

Манбаъ: will.com

SciPy, оптимизатсия