SciPy, otimização com condições

SciPy, otimização com condições

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 artigo anterior. 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 documentação oficial.

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. Artigo na wiki, artigo no habra;
  • SLSQP — programação quadrática sequencial com restrições, método de Newton para resolver o sistema de Lagrange. Artigo na wiki.
  • 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. Artigo na wiki.
  • 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. Artigo na wiki, artigo no habra.
  • COBYLA — Constrained Optimization By Linear Approximation, otimização restrita com aproximação linear (sem cálculo de gradiente). Artigo na wiki.

Dependendo do método escolhido, as condições e restrições para resolver o problema podem ser especificadas de diferentes maneiras:

  • objeto da classe Bounds para 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, NonlinearConstraint para 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 EQSQP para problemas com restrições de igualdade e em TRIP 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:

SciPy, otimização com condições

SciPy, otimização com condições

SciPy, otimização com condições

Para restrições de igualdade estrita, o limite inferior é definido como igual ao limite superior SciPy, otimização com condições.
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:

SciPy, otimização com condições

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

SciPy, otimização com condições

SciPy, otimização com condições

SciPy, otimização com condições

SciPy, otimização com condições

SciPy, otimização com condições

SciPy, otimização com condições

Em nosso caso, existe uma única solução no ponto SciPy, otimização com condições, 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 SciPy, otimização com condições e SciPy, otimização com condições definiremos usando o objeto Bounds.

from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])

Restrições SciPy, otimização com condições e SciPy, otimização com condições escreveremos na forma linear:

SciPy, otimização com condições

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:

SciPy, otimização com condições

Definiremos a matriz Jacobiana para essa restrição e uma combinação linear da matriz Hessiana com um vetor arbitrário SciPy, otimização com condições:

SciPy, otimização com condições

SciPy, otimização com condições

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 SciPy, otimização com condições exige altos custos, é possível usar a classe HessianUpdateStrategy. 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:

SciPy, otimização com condições

SciPy, otimização com condições

SciPy, otimização com condições

SciPy, otimização com condições

Onde SciPy, otimização com condições e SciPy, otimização com condições conjuntos de índices de expressões que descrevem restrições na forma de igualdades ou desigualdades. SciPy, otimização com condições 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:

SciPy, otimização com condições

O que é equivalente a:

SciPy, otimização com condições

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 (artigo no habra) pode ser vista em scipy-cookbook.

A principal fonte de informação é docs.scipy.org, aqueles que desejam contribuir na tradução desta e de outras seções scipy são bem-vindos ao GitHub.

Obrigado mephistopheies por participar da preparação da publicação.

Fonte: habr.com

Compre hospedagem confiável para sites com proteção contra DDoS, servidores VPS VDS 🔥 Compre hospedagem confiável para sites com proteção contra DDoS, servidores VPS VDS | ProHoster