
SciPy (pronuncia-se sai pai) é um pacote matemático baseado no numpy, que também inclui bibliotecas em C e Fortran. Com o SciPy, uma sessão interativa do Python se transforma em um ambiente de processamento de dados completo, como MATLAB, IDL, Octave, R ou SciLab.
Neste artigo, abordaremos as principais técnicas de programação matemática — soluções para problemas de otimização com condições para funções escalares de várias variáveis usando o pacote scipy.optimize. Algoritmos de otimização incondicional já foram discutidos na . Para uma referência mais detalhada e atual sobre as funções do scipy, você sempre pode usar o comando help(), Shift+Tab ou em .
Introdução
A interface geral para resolver problemas tanto de otimização com condições quanto sem condições no pacote scipy.optimize é fornecida pela função minimize(). No entanto, sabe-se que não existe uma maneira universal de resolver todos os problemas, portanto, a escolha do método adequado sempre recai sobre o pesquisador.
O algoritmo de otimização apropriado é especificado pelo argumento da função minimize(..., method="").
Para otimização com condições de funções de várias variáveis, estão disponíveis implementações dos seguintes métodos:
trust-constr— busca pelo mínimo local em uma área de confiança. , ;SLSQP— programação quadrática sequencial com restrições, método de Newton para resolver o sistema de Lagrange. .TNC— Truncated Newton Constrained, número limitado de iterações, bom para funções não lineares com um grande número de variáveis independentes. .L-BFGS-B— método dos quatro Broyden–Fletcher–Goldfarb–Shanno, implementado com consumo reduzido de memória por meio do carregamento parcial de vetores da matriz Hessiana. , .COBYLA— Constrained Optimization By Linear Approximation, otimização restrita com aproximação linear (sem cálculo de gradiente). .
Dependendo do método escolhido, as condições e restrições para resolver o problema podem ser especificadas de diferentes maneiras:
- objeto da classe
Boundspara os métodos L-BFGS-B, TNC, SLSQP, trust-constr; - lista
(min, max)para esses mesmos métodos L-BFGS-B, TNC, SLSQP, trust-constr; - objeto ou lista de objetos
LinearConstraint,NonlinearConstraintpara os métodos COBYLA, SLSQP, trust-constr; - dicionário ou lista de dicionários
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}para os métodos COBYLA, SLSQP.
Estrutura do artigo:
1) Considerar a aplicação do algoritmo de otimização condicional na região de confiança (method=»trust-constr») com restrições definidas na forma de objetos Bounds, LinearConstraint, NonlinearConstraint ;
2) Analisar a programação sequencial pelo método dos mínimos quadrados (method=»SLSQP») com restrições definidas na forma de dicionário {'type', 'fun', 'jac', 'args'};
3) Examinar um exemplo de otimização da produção usando o caso de um estúdio de web.
Otimização condicional method=»trust-constr»
Implementação do método trust-constr baseada em para problemas com restrições de igualdade e em para problemas com restrições de desigualdade. Ambos os métodos são implementados por algoritmos de busca de mínimo local na região de confiança e se adequam bem a problemas em grande escala.
Formulação matemática do problema de busca de mínimo em sua forma geral:



Para restrições de igualdade estrita, o limite inferior é definido como igual ao limite superior
.
Para uma restrição unidimensional, o limite superior ou inferior é definido np.inf com o sinal correspondente.
Suponha que precisamos encontrar o mínimo da conhecida função de Rosenbrock de duas variáveis:

Neste caso, são impostas as seguintes restrições ao seu domínio de definição:






Em nosso caso, existe uma única solução no ponto
, onde apenas as primeiras e quarta restrições são válidas.
Vamos analisar as restrições de baixo para cima e ver como podemos expressá-las no scipy.
Restrições
e
definiremos usando o objeto Bounds.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])Restrições
e
escreveremos na forma linear:

Definiremos essas restrições na forma de objeto LinearConstraint:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])E finalmente, a restrição não linear na forma matricial:

Definiremos a matriz Jacobiana para essa restrição e uma combinação linear da matriz Hessiana com um vetor arbitrário
:


Agora, a restrição não linear pode ser definida como um objeto 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)Se o tamanho for grande, as matrizes podem ser definidas também na forma esparsa:
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)ou como um objeto 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)Quando o cálculo da matriz Hessiana
exige altos custos, é possível usar a classe . As seguintes estratégias estão disponíveis: BFGS e SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())A Hessiana também pode ser calculada usando diferenças finitas:
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')A matriz Jacobiana para as restrições também pode ser calculada usando diferenças finitas. No entanto, nesse caso, a matriz Hessiana não pode ser calculada usando diferenças finitas. A Hessiana deve ser definida como uma função ou através da classe HessianUpdateStrategy.
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())A solução do problema de otimização é a seguinte:
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` condição de término satisfeita.
Número de iterações: 12, avaliações de função: 8, iterações CG: 7, optimalidade: 2.99e-09, violação de restrição: 1.11e-16, tempo de execução: 0.033 s.
[0.41494531 0.17010937]Se necessário, a função para calcular a Hessiana pode ser definida através da classe 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)ou o produto da Hessiana e um vetor arbitrário através do parâmetro 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)Alternativamente, as primeiras e segundas derivadas da função a ser otimizada podem ser calculadas de forma aproximada. Por exemplo, a Hessiana pode ser aproximada usando uma função SR1 (aproximação quasi-Newton). O gradiente pode ser aproximado por diferenças finitas.
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)Otimização condicional method="SLSQP"
O método SLSQP é destinado a resolver problemas de minimização de funções na forma:




Onde
e
conjuntos de índices de expressões que descrevem restrições na forma de igualdades ou desigualdades.
conjuntos de limites inferiores e superiores para o domínio da função.
Restrições lineares e não lineares são descritas na forma de dicionários com chaves tipo, função e 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])
}A busca pelo mínimo é realizada da seguinte forma:
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)A otimização foi encerrada com sucesso. (Modo de saída 0)
Valor atual da função: 0.34271757499419825
Iterações: 4
Avaliações da função: 5
Avaliações do gradiente: 4
[0.41494475 0.1701105 ]Exemplo de otimização
Com a transição para o quinto ciclo tecnológico, vamos considerar a otimização da produção usando o exemplo de uma web studio, que nos traz uma renda pequena, mas estável. Vamos nos imaginar como diretores de uma galeria que produz três tipos de produtos:
- x0 — landing pages de vendas, a partir de 10 mil.
- x1 — sites corporativos, a partir de 20 mil.
- x2 — lojas virtuais, a partir de 30 mil.
Nossa equipe de trabalho amigável inclui quatro juniores, dois intermediários e um sênior. O fundo de tempo de trabalho deles por mês:
- juniores:
4 * 150 = 600 horas * pessoa, - intermediários:
2 * 150 = 300 horas * pessoa, - sênior:
150 horas * pessoa.
Suponha que para desenvolver e implantar um site do tipo (x0, x1, x2), um júnior deve gastar (10, 20, 30) horas, um intermediário — (7, 15, 20), um sênior — (5, 10, 15) horas do melhor tempo de suas vidas.
Como qualquer diretor normal, queremos maximizar o lucro mensal. O primeiro passo para o sucesso é escrever a função objetivo valor como a soma das receitas da produção realizada durante o mês:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]Isso não é um erro, ao buscar o máximo, a função objetivo é minimizada com o sinal invertido.
O próximo passo é proibir a sobrecarga de trabalho de nossos funcionários e estabelecer restrições no fundo de horas de trabalho:

O que é equivalente a:

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]])
}A restrição formal é que a produção deve ser apenas positiva:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])E, finalmente, a suposição mais otimista é que, devido ao preço baixo e à alta qualidade, sempre temos uma fila de clientes satisfeitos. Podemos escolher sozinhos os volumes mensais de produção, com base na solução de um problema de otimização condicional com 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]Arredondamos levemente para inteiros e calculamos a carga mensal dos remadores na configuração ideal de produção x = (8, 6, 3) :
- juniores:
8 * 10 + 6 * 20 + 3 * 30 = 290 pessoas * hora; - intermediários:
8 * 7 + 6 * 15 + 3 * 20 = 206 pessoas * hora; - sênior:
8 * 5 + 6 * 10 + 3 * 15 = 145 pessoas * hora.
Conclusão: para que o diretor receba seu merecido máximo, é ideal produzir mensalmente 8 landing pages, 6 sites médios e 3 lojas. O sênior deve trabalhar sem parar na máquina, a carga dos mid-levels será de aproximadamente 2/3, e a dos juniores será menos da metade.
Conclusão
O artigo apresenta os principais métodos de trabalho com o pacote scipy.optimize, utilizados para resolver problemas de minimização condicional. Pessoalmente, uso scipy estritamente para fins acadêmicos, portanto, o exemplo apresentado tem um caráter humorístico.
Muita teoria e exemplos raros podem ser encontrados, por exemplo, no livro de I.L. Akulich "Programação Matemática em Exemplos e Problemas". Uma aplicação mais hardcore scipy.optimize para construção de estruturas 3D a partir de um conjunto de imagens () pode ser vista em .
A principal fonte de informação é , aqueles que desejam contribuir na tradução desta e de outras seções scipy são bem-vindos ao .
Obrigado por participar da preparação da publicação.
Fonte: habr.com
