🥇SciPy, ऑप्टिमायझेशन | प्रोहोस्टर

SciPy (उच्चारित sai pie) हे Numpy Python विस्तारावर आधारित गणितीय अनुप्रयोग पॅकेज आहे. SciPy सह, तुमचे परस्परसंवादी पायथन सत्र हे MATLAB, IDL, Octave, R-Lab आणि SciLab सारखेच संपूर्ण डेटा सायन्स आणि जटिल सिस्टम प्रोटोटाइपिंग वातावरण बनते. आज मला scipy.optimize पॅकेजमध्ये काही सुप्रसिद्ध ऑप्टिमायझेशन अल्गोरिदम कसे वापरायचे याबद्दल थोडक्यात बोलायचे आहे. फंक्शन्स वापरण्याबाबत अधिक तपशीलवार आणि अद्ययावत मदत हेल्प() कमांड किंवा Shift+Tab वापरून नेहमी मिळवता येते.

परिचय

स्वतःला आणि वाचकांना प्राथमिक स्रोत शोधण्यापासून आणि वाचण्यापासून वाचवण्यासाठी, पद्धतींच्या वर्णनाच्या लिंक्स प्रामुख्याने विकिपीडियावर असतील. नियमानुसार, ही माहिती सामान्य अटींमध्ये पद्धती आणि त्यांच्या अर्जाच्या अटी समजून घेण्यासाठी पुरेशी आहे. गणितीय पद्धतींचे सार समजून घेण्यासाठी, अधिक अधिकृत प्रकाशनांच्या दुव्यांचे अनुसरण करा, जे प्रत्येक लेखाच्या शेवटी किंवा आपल्या आवडत्या शोध इंजिनमध्ये आढळू शकतात.

तर, scipy.optimize मॉड्यूलमध्ये खालील प्रक्रियांची अंमलबजावणी समाविष्ट आहे:

विविध अल्गोरिदम (नेल्डर-मीड सिम्प्लेक्स, बीएफजीएस, न्यूटन कंजुगेट ग्रेडियंट्स, COBYLA и SLSQP)
ग्लोबल ऑप्टिमायझेशन (उदाहरणार्थ: बेसिनहॉपिंग, diff_evolution)
अवशेष कमी करणे MNC (कमीतकमी_चौरस) आणि वक्र फिटिंग अल्गोरिदम नॉनलाइनर किमान चौरस (वक्र_फिट) वापरून
एका व्हेरिएबलची स्केलर फंक्शन्स कमी करणे (मिनिम_स्केलर) आणि रूट्स शोधणे (रूट_स्केलर)
विविध अल्गोरिदम वापरून समीकरण प्रणालीचे बहुआयामी निराकरण (रूट) लेव्हनबर्ग-मार्क्वार्ड किंवा मोठ्या प्रमाणावर पद्धती जसे की न्यूटन-क्रिलोव्ह).

या लेखात आम्ही या संपूर्ण यादीतील फक्त पहिल्या आयटमचा विचार करू.

अनेक व्हेरिएबल्सच्या स्केलर फंक्शनचे बिनशर्त कमी करणे

scipy.optimize पॅकेजमधील मिनिम फंक्शन अनेक व्हेरिएबल्सच्या स्केलर फंक्शन्सच्या सशर्त आणि बिनशर्त कमी करण्याच्या समस्या सोडवण्यासाठी एक सामान्य इंटरफेस प्रदान करते. ते कसे कार्य करते हे दाखवण्यासाठी, आम्हाला अनेक व्हेरिएबल्सचे योग्य कार्य आवश्यक आहे, जे आम्ही वेगवेगळ्या प्रकारे कमी करू.

या हेतूंसाठी, एन व्हेरिएबल्सचे रोझेनब्रॉक फंक्शन परिपूर्ण आहे, ज्याचे स्वरूप आहे:

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

स्पष्टपणे परिभाषित आणि बर्‍यापैकी गुळगुळीत कार्य कमी करण्यासाठी सिम्प्लेक्स पद्धत ही सर्वात सोपी पद्धत आहे. फंक्शनच्या डेरिव्हेटिव्ह्जची गणना करणे आवश्यक नाही; फक्त त्याची मूल्ये निर्दिष्ट करणे पुरेसे आहे. नेल्डर-मीड पद्धत सोप्या कमीतकमी समस्यांसाठी एक चांगला पर्याय आहे. तथापि, ते ग्रेडियंट अंदाज वापरत नसल्यामुळे, किमान शोधण्यासाठी जास्त वेळ लागू शकतो.

पॉवेल पद्धत

आणखी एक ऑप्टिमायझेशन अल्गोरिदम ज्यामध्ये फक्त फंक्शन व्हॅल्यूज मोजल्या जातात पॉवेलची पद्धत. ते वापरण्यासाठी, तुम्हाला किमान फंक्शनमध्ये पद्धत = 'पॉवेल' सेट करणे आवश्यक आहे.

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 पद्धतीला सामान्यतः सिम्प्लेक्स पद्धतीपेक्षा कमी फंक्शन कॉल आवश्यक असतात.

विश्लेषणात्मक स्वरूपात रोझेनब्रॉक फंक्शनचे व्युत्पन्न शोधूया:

ही अभिव्यक्ती पहिली आणि शेवटची वगळता सर्व व्हेरिएबल्सच्या डेरिव्हेटिव्हसाठी वैध आहे, ज्याची व्याख्या खालीलप्रमाणे आहे:

या ग्रेडियंटची गणना करणारे पायथन फंक्शन पाहू:

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 फंक्शन कमी करण्यासाठी ही पद्धत वापरण्याचे उदाहरण खाली दिले आहे. न्यूटन-सीजी पद्धत वापरण्यासाठी, तुम्ही हेसियनची गणना करणारे फंक्शन निर्दिष्ट करणे आवश्यक आहे.
विश्लेषणात्मक स्वरूपात रोसेनब्रॉक फंक्शनचे हेसियन समान आहे:

जेथे и , मॅट्रिक्स परिभाषित करा .

मॅट्रिक्सचे उर्वरित शून्य नसलेले घटक समान आहेत:

उदाहरणार्थ, पंच-आयामी जागेत 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.]

Krylov प्रकार पद्धती

ट्रस्ट-एनसीजी पद्धतीप्रमाणे, क्रायलोव्ह-प्रकार पद्धती मोठ्या प्रमाणात समस्या सोडवण्यासाठी योग्य आहेत कारण त्या फक्त मॅट्रिक्स-वेक्टर उत्पादने वापरतात. ट्रंकेटेड क्रिलोव्ह सबस्पेसद्वारे मर्यादित आत्मविश्वास क्षेत्रामध्ये समस्या सोडवणे हे त्यांचे सार आहे. अनिश्चित समस्यांसाठी, ही पद्धत वापरणे अधिक चांगले आहे, कारण ती ट्रस्ट-एनसीजी पद्धतीच्या तुलनेत, प्रति सबप्रॉब्लेम मॅट्रिक्स-व्हेक्टर उत्पादनांच्या कमी संख्येमुळे नॉनलाइनर पुनरावृत्ती वापरते. याव्यतिरिक्त, ट्रस्ट-एनसीजी पद्धती वापरण्यापेक्षा क्वाड्रॅटिक सबप्रॉब्लेमचे निराकरण अधिक अचूकपणे आढळते.
हेसियन मॅट्रिक्सच्या व्याख्येसह उदाहरणः

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

आत्मविश्वास क्षेत्रामध्ये अंदाजे समाधानासाठी अल्गोरिदम

सर्व पद्धती (न्यूटन-सीजी, ट्रस्ट-एनसीजी आणि ट्रस्ट-क्रिलोव्ह) मोठ्या प्रमाणात समस्या सोडवण्यासाठी (हजारो व्हेरिएबल्ससह) योग्य आहेत. हे या वस्तुस्थितीमुळे आहे की अंतर्निहित संयुग्मित ग्रेडियंट अल्गोरिदम व्यस्त हेसियन मॅट्रिक्सचे अंदाजे निर्धारण सूचित करते. हेसियनचा स्पष्ट विस्तार न करता, उपाय पुनरावृत्तीने शोधला जातो. तुम्हाला केवळ हेसियन आणि अनियंत्रित वेक्टरच्या उत्पादनासाठी फंक्शन परिभाषित करणे आवश्यक असल्याने, हा अल्गोरिदम विरळ (बँड कर्ण) मॅट्रिकसह कार्य करण्यासाठी विशेषतः चांगला आहे. हे कमी मेमरी खर्च आणि लक्षणीय वेळेची बचत प्रदान करते.

मध्यम-आकाराच्या समस्यांसाठी, हेसियन संचयित करण्याची आणि फॅक्टरिंगची किंमत गंभीर नाही. याचा अर्थ असा आहे की कमी पुनरावृत्तीमध्ये समाधान मिळवणे शक्य आहे, ट्रस्ट क्षेत्राच्या उपप्रॉब्लेम्स जवळजवळ अचूकपणे सोडवणे. हे करण्यासाठी, प्रत्येक चतुर्भुज उपप्रश्नासाठी काही नॉनलाइनर समीकरणे पुनरावृत्तीने सोडवली जातात. अशा सोल्यूशनसाठी सामान्यतः हेसियन मॅट्रिक्सचे 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

SciPy, ऑप्टिमायझेशन