Ang SciPy (gilitok nga sai pie) maoy usa ka numpy-based mathematics package nga naglakip usab sa C ug Fortran nga mga librarya. Gihimo sa SciPy ang imong interactive nga sesyon sa Python nga usa ka kompleto nga palibot sa siyensya sa datos sama sa MATLAB, IDL, Octave, R, o SciLab.
Niini nga artikulo, atong tan-awon ang mga batakang teknik sa matematika nga programming - pagsulbad sa mga problema sa conditional optimization alang sa usa ka scalar function sa daghang mga variable gamit ang scipy.optimize nga pakete. Ang dili mapugngan nga mga algorithm sa pag-optimize nahisgutan na sa . Ang mas detalyado ug up-to-date nga tabang sa scipy functions kanunay makuha gamit ang help() command, Shift+Tab o sa .
Pasiuna
Usa ka komon nga interface alang sa pagsulbad sa kondisyon ug walay pagpugong nga mga problema sa pag-optimize sa scipy.optimize nga pakete gihatag sa function. minimize(). Bisan pa, nahibal-an nga wala’y unibersal nga pamaagi sa pagsulbad sa tanan nga mga problema, mao nga ang pagpili sa usa ka igong pamaagi, sama sa kanunay, nahulog sa mga abaga sa tigdukiduki.
Ang angay nga optimization algorithm gitino gamit ang function argument minimize(..., method="").
Para sa conditional optimization sa usa ka function sa daghang mga variables, ang mga pagpatuman sa mosunod nga mga pamaagi anaa:
trust-constr- pagpangita alang sa usa ka lokal nga minimum sa pagsalig nga rehiyon. , ;SLSQP— sequential quadratic programming nga adunay mga limitasyon, Newtonian nga pamaagi sa pagsulbad sa Lagrange system. .TNC- Giputol ang Newton Constrained, limitado nga gidaghanon sa mga pag-uli, maayo alang sa nonlinear nga mga gimbuhaton nga adunay daghang mga independent variable. .L-BFGS-B— usa ka pamaagi gikan sa grupo sa Broyden–Fletcher–Goldfarb–Shanno, nga gipatuman uban ang pagkunhod sa konsumo sa memorya tungod sa partial loading sa mga vector gikan sa Hessian matrix. , .COBYLA— Ang MARE Constrained Optimization Pinaagi sa Linear Approximation, gipugngan nga pag-optimize nga adunay linear approximation (walay gradient nga kalkulasyon). .
Depende sa gipili nga pamaagi, ang mga kondisyon ug mga pagdili alang sa pagsulbad sa problema lahi nga gitakda:
- butang sa klase
Boundsalang sa mga pamaagi L-BFGS-B, TNC, SLSQP, pagsalig-constr; - ang listahan
(min, max)alang sa sama nga mga pamaagi L-BFGS-B, TNC, SLSQP, pagsalig-constr; - usa ka butang o usa ka lista sa mga butang
LinearConstraint,NonlinearConstraintalang sa COBYLA, SLSQP, pagsalig-constr nga mga pamaagi; - diksyonaryo o listahan sa mga diksyonaryo
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}para sa COBYLA, mga pamaagi sa SLSQP.
Balay sa artikulo:
1) Hunahunaa ang paggamit sa usa ka conditional optimization algorithm sa pagsalig nga rehiyon (pamaagi = "trust-constr") nga adunay mga pagpugong nga gipiho nga mga butang Bounds, LinearConstraint, NonlinearConstraint ;
2) Ikonsiderar ang sequential least squares programming (pamaagi = "SLSQP") nga adunay mga limitasyon nga gipiho isip usa ka diksyonaryo {'type', 'fun', 'jac', 'args'};
3) Analisaha ang usa ka pananglitan sa pag-optimize sa mga gigama nga produkto gamit ang pananglitan sa usa ka web studio.
Conditional optimization method="trust-constr"
Pagpatuman sa pamaagi trust-constr base sa alang sa mga problema sa mga pagpugong sa porma sa pagkaparehas ug sa alang sa mga problema sa mga pagpugong sa porma sa dili managsama. Ang duha nga mga pamaagi gipatuman sa mga algorithm alang sa pagpangita sa usa ka lokal nga minimum sa rehiyon sa pagsalig ug maayo nga haum alang sa dagkong mga problema.
Ang pagporma sa matematika sa problema sa pagpangita sa usa ka minimum sa kinatibuk-ang porma:
Alang sa estrikto nga equality constraints, ang ubos nga bound gitakda nga parehas sa upper bound .
Alang sa usa ka paagi nga pagpugong, ang taas o ubos nga limitasyon gitakda np.inf uban ang katugbang nga timaan.
Himoa nga gikinahanglan ang pagpangita sa minimum sa usa ka nailhan nga Rosenbrock nga function sa duha ka mga baryable:
Sa kini nga kaso, ang mosunod nga mga pagdili gibutang sa iyang domain sa kahulugan:
Sa among kaso, adunay usa ka talagsaon nga solusyon sa punto , diin ang una ug ikaupat nga mga pagdili lamang ang balido.
Atong susihon ang mga pagdili gikan sa ubos hangtod sa taas ug tan-awon kung giunsa naton kini isulat sa scipy.
Mga pagbabag и atong ipasabot kini gamit ang Bounds object.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])Mga pagbabag и Atong isulat kini sa linear nga porma:
Atong ipasabut kini nga mga pagpugong ingon usa ka butang nga LinearConstraint:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])Ug sa katapusan ang nonlinear nga pagpugong sa matrix nga porma:
Atong gihubit ang Jacobian matrix alang niini nga pagpugong ug usa ka linear nga kombinasyon sa Hessian matrix nga adunay arbitraryong vector. :
Karon mahimo natong ipasabut ang usa ka dili linya nga pagpugong ingon usa ka butang 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)Kung ang gidak-on dako, ang mga matrice mahimo usab nga ipiho sa gamay nga porma:
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)o isip usa ka butang 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)Kung gikalkula ang Hessian matrix nagkinahanglan og daghang paningkamot, mahimo nimong gamiton ang usa ka klase . Ang mosunod nga mga estratehiya anaa: BFGS и SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())Ang Hessian mahimo usab nga kalkulado gamit ang limitado nga mga kalainan:
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')Ang Jacobian matrix alang sa mga limitasyon mahimo usab nga kalkulado gamit ang finite differences. Bisan pa, sa kini nga kaso ang Hessian matrix dili makalkula gamit ang limitado nga mga kalainan. Ang Hessian kinahanglang ipasabot isip usa ka function o gamit ang HessianUpdateStrategy nga klase.
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())Ang solusyon sa problema sa pag-optimize ingon niini:
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]Kung gikinahanglan, ang function alang sa pagkalkula sa Hessian mahimong ipasabut gamit ang LinearOperator nga klase
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)o ang produkto sa Hessian ug usa ka arbitraryong vector pinaagi sa parameter 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)Sa laing bahin, ang una ug ikaduhang derivatives sa function nga gi-optimize mahimong mabanabana. Pananglitan, ang Hessian mahimong mabanabana gamit ang function SR1 (quasi-Newtonian approximation). Ang gradient mahimong mabanabana pinaagi sa limitado nga mga kalainan.
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)Kondisyon nga pamaagi sa pag-optimize = "SLSQP"
Ang pamaagi sa SLSQP gidesinyo aron masulbad ang mga problema sa pagminus sa function sa porma:
Diin и — mga hugpong sa mga indeks sa mga ekspresyon nga naghulagway sa mga pagdili sa porma sa pagkaparehas o pagkadili managsama. — mga set sa ubos ug taas nga mga utlanan alang sa domain sa kahulugan sa function.
Ang linear ug nonlinear nga mga pagpugong gihulagway sa porma sa mga diksyonaryo nga adunay mga yawe 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])
}Ang pagpangita alang sa minimum gihimo sama sa mosunod:
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 ]Ehemplo sa Pag-optimize
May kalabotan sa pagbalhin sa ikalima nga istruktura sa teknolohiya, atong tan-awon ang pag-optimize sa produksiyon gamit ang panig-ingnan sa usa ka web studio, nga nagdala kanamo gamay apan lig-on nga kita. Atong handurawon ang atong kaugalingon ingong direktor sa usa ka galley nga naggama ug tulo ka matang sa mga produkto:
- x0 - pagbaligya sa mga landing page, gikan sa 10 tr.
- x1 - corporate websites, gikan sa 20 tr.
- x2 - mga online nga tindahan, gikan sa 30 tr.
Ang among mahigalaon nga working team naglakip sa upat ka juniors, duha ka middles ug usa ka senior. Ang ilang binulan nga pundo sa oras sa pagtrabaho:
- Hunyo:
4 * 150 = 600 чел * час, - tunga:
2 * 150 = 300 чел * час, - senor:
150 чел * час.
Himoa nga ang unang anaa nga junior mogasto (0, 1, 2) ka oras sa pagpalambo ug pag-deploy sa usa ka site sa tipo (x10, x20, x30), tunga-tunga - (7, 15, 20), senior - (5, 10, 15 ) mga oras sa pinakamaayong panahon sa imong kinabuhi.
Sama sa bisan unsang normal nga direktor, gusto namon nga mapadako ang binulan nga kita. Ang unang lakang sa kalampusan mao ang pagsulat sa tumong nga function value ingon ang kantidad sa kita gikan sa mga produkto nga gihimo kada bulan:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]Dili kini usa ka sayup; kung nangita alang sa labing kadaghan, ang katuyoan nga function gipamubu sa kaatbang nga timaan.
Ang sunod nga lakang mao ang pagdili sa among mga empleyado sa sobrang pagtrabaho ug pagpaila sa mga pagdili sa oras sa pagtrabaho:
Unsa ang katumbas:
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]])
}Ang usa ka pormal nga pagdili mao nga ang produkto nga output kinahanglan lamang nga positibo:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])Ug sa katapusan, ang labing kadaghan nga pangagpas mao nga tungod sa mubu nga presyo ug taas nga kalidad, usa ka pila sa natagbaw nga mga kostumer ang kanunay nga naglinya alang kanamo. Mahimo natong pilion ang binulan nga gidaghanon sa produksiyon sa atong kaugalingon, base sa pagsulbad sa gipugngan nga problema sa pag-optimize 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]Ilibot nato ang bug-os nga mga numero ug kuwentahon ang binulan nga karga sa mga tigbugsay nga adunay maayong pag-apod-apod sa mga produkto x = (8, 6, 3) :
- Hunyo:
8 * 10 + 6 * 20 + 3 * 30 = 290 чел * час; - tunga:
8 * 7 + 6 * 15 + 3 * 20 = 206 чел * час; - senor:
8 * 5 + 6 * 10 + 3 * 15 = 145 чел * час.
Konklusyon: aron ang direktor makadawat sa iyang angayan nga maximum, kini mao ang kamalaumon nga paghimo sa 8 landing page, 6 medium-sized nga mga site ug 3 nga mga tindahan matag bulan. Sa kini nga kaso, ang senior kinahanglan nga magdaro nga dili motan-aw gikan sa makina, ang karga sa mga tungatunga mahimong gibana-bana nga 2/3, ang mga junior wala’y katunga.
konklusyon
Ang artikulo naglatid sa sukaranang mga teknik sa pagtrabaho kauban ang pakete scipy.optimize, gigamit sa pagsulbad sa mga problema sa pagminus sa kondisyon. Personal nga gigamit nako scipy para lang sa akademikong katuyoan, mao nga ang ehemplo nga gihatag kay kataw-anan kaayo.
Daghang mga teorya ug virtual nga mga pananglitan ang makit-an, pananglitan, sa libro ni I.L. Akulich "Pagprograma sa matematika sa mga pananglitan ug mga problema." Dugang nga hardcore nga aplikasyon scipy.optimize sa paghimo sa usa ka 3D nga istruktura gikan sa usa ka set sa mga imahe () mahimong tan-awon sa .
Ang nag-unang tinubdan sa impormasyon mao ang kadtong gustong motampo sa paghubad niini ug sa ubang mga seksyon scipy Welcome sa .
Спасибо alang sa pag-apil sa pag-andam sa publikasyon.
Source: www.habr.com