🥇SciPy, Օպտիմիզացում պայմաններով

SciPy-ը (արտասանվում է sai pie) մաթեմատիկական մաթեմատիկայի փաթեթ է, որը ներառում է նաև C և Fortran գրադարանները: SciPy-ն ձեր Python-ի ինտերակտիվ նիստը վերածում է տվյալների գիտության ամբողջական միջավայրի, ինչպիսիք են MATLAB-ը, IDL-ը, Octave-ը, R-ը կամ SciLab-ը:

Այս հոդվածում մենք կդիտարկենք մաթեմատիկական ծրագրավորման հիմնական տեխնիկան՝ պայմանական օպտիմալացման խնդիրների լուծում մի քանի փոփոխականների սկալյար ֆունկցիայի համար՝ օգտագործելով scipy.optimize փաթեթը: Անսահմանափակ օպտիմալացման ալգորիթմներն արդեն քննարկվել են վերջին հոդվածը. Scipy ֆունկցիաների վերաբերյալ ավելի մանրամասն և արդի օգնություն միշտ կարելի է ստանալ՝ օգտագործելով help() հրամանը, Shift+Tab կամ պաշտոնական փաստաթղթեր.

Ներածություն

Ընդհանուր ինտերֆեյս scipy.optimize փաթեթում պայմանական և անսահմանափակ օպտիմալացման խնդիրները լուծելու համար տրամադրվում է ֆունկցիայի կողմից: minimize(). Սակայն հայտնի է, որ բոլոր խնդիրները լուծելու ունիվերսալ մեթոդ գոյություն չունի, ուստի ադեկվատ մեթոդի ընտրությունը, ինչպես միշտ, ընկնում է հետազոտողի ուսերին։
Համապատասխան օպտիմալացման ալգորիթմը նշվում է ֆունկցիայի փաստարկի միջոցով minimize(..., method="").
Մի քանի փոփոխականների ֆունկցիայի պայմանական օպտիմալացման համար հասանելի են հետևյալ մեթոդների իրականացումը.

trust-constr — որոնել տեղական նվազագույնը վստահության շրջանում: Վիքի հոդված, հոդված Habré-ի մասին;
SLSQP — հաջորդական քառակուսի ծրագրավորում սահմանափակումներով, Նյուտոնյան մեթոդ Լագրանժի համակարգի լուծման համար։ Վիքի հոդված.
TNC - Կտրված Նյուտոն Կաշկանդված, սահմանափակ թվով կրկնություններ, լավ է մեծ թվով անկախ փոփոխականներով ոչ գծային ֆունկցիաների համար: Վիքի հոդված.
L-BFGS-B — մեթոդ Բրոյդեն–Ֆլետչեր–Գոլդֆարբ–Շաննո թիմից, որն իրականացվել է հիշողության կրճատմամբ՝ Հեսսիական մատրիցից վեկտորների մասնակի բեռնման պատճառով։ Վիքի հոդված, հոդված Habré-ի մասին.
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) Դիտարկենք պայմանական օպտիմալացման ալգորիթմի օգտագործումը վստահության տարածաշրջանում (մեթոդ=”վստահություն-կոնստրուկ”)՝ որպես օբյեկտներ նշված սահմանափակումներով 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])

Սահմանափակումները и Գրենք այն գծային տեսքով.

Եկեք սահմանենք այս սահմանափակումները որպես 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 կառուցվածք (հոդված Habré-ի մասին) կարելի է դիտել scipy-cookbook.

Տեղեկատվության հիմնական աղբյուրն է docs.scipy.orgնրանք, ովքեր ցանկանում են նպաստել այս և այլ բաժինների թարգմանությանը scipy Բարի գալուստ GitHub.

Շնորհակալություն մեֆիստոֆեներ հրապարակման պատրաստմանը մասնակցելու համար։

Source: www.habr.com