Pacote de software para otimização restrita?

21

Estou procurando resolver um problema de otimização restrito, onde conheço os limites de algumas das variáveis (especificamente uma restrição em caixa).

\arg min_{u} f (u, x)

$\arg \min_u f(u,x)$

sujeito a

c (u, x) = 0

$c(u,x) = 0$

a \leq d (u, x) \leq b

$a \le d(u,x) \le b$

onde $u$ é um vetor de variáveis de design, $x$ é um vetor de variáveis de estado $c(u,x)$ é uma restrição de igualdade (geralmente um PDE). As restrições inferiores e superiores $a$ e $b$ podem ser espacialmente variáveis.

Quais pacotes podem lidar com sistemas deste formulário?

pde optimization nonlinear-programming Sean Farley
fonte

11

A versão editada não parece um problema de otimização com restrição de caixa. Um problema de otimização com restrição de caixa teria

a \leq u \leq b

$a \leq u \leq b$ como restrição. É

u

$u$ suposto ser uma função de

x

$x$ ?

é

c

$c$ linear em

u

$u$ ? Se não for, é duas vezes diferenciável?

é

f

$f$ convexo em

u

$u$ ? É duas vezes diferenciável em

u

$u$ ? Finalmente,

\arg min_{u}

$\arg \min_{u}$ denota o conjunto de pontos em

u

$u$ no qual o valor mínimo de

f

$f$ é atingido. Você quer dizer

min_{u}

$\min_{u}$ ?

Geoff Oxberry

d (u, x) = u

$d(u,x) = u$ é um caso especial, mas essa forma mais geral é realmente comum na prática. Você sempre pode introduzir variáveis extras se seu método puder lidar apenas com restrições diretamente em

u

$u$ . Em geral, estamos mais interessados no valor

u

$u$ no qual um mínimo é atingido do que no valor mínimo de

f

$f$ . Sean adicionou a tag [pde], para que você possa obter alguma regularidade com isso. Ele não afirmou se o sistema era hiperbólico ou não, então não vamos assumir. Não vamos supor que

f

$f$ seja convexo, pois geralmente não é.

Jed Brown

É bastante comum

f

$f$ envolver a regularização

L^{1}

$L^1$ ou

W^{1, 1}

$W^{1,1}$ , portanto, não devemos assumir duas derivadas.

Jed Brown

@JedBrown: Isso faz sentido; foi confuso ver "restrição de caixa" mencionada sem, bem, uma restrição explícita de caixa. Para os tipos de problemas dos quais você está falando (problemas de design, problemas de controle),

u

$u$ é definitivamente mais interessante, mas os problemas de otimização geralmente são declarados usando a notação

m i n

$min$ e seus conjuntos de soluções são descritos na notação

\arg min

$\arg \min$ .

precisa saber é o seguinte

Pode ser útil especificar em qual idioma / ambiente você modela os PDEs. Pode restringir a escolha de otimizadores.

Dominique

18

Decidi editar radicalmente minha resposta com base em alguns dos comentários.

Eu não usei TAO. Ao examinar a documentação, parece que a única maneira pela qual o TAO pode lidar com problemas de otimização restrita (excluindo o caso especial de apenas restrições de caixa) é converter o problema em uma desigualdade variacional usando as condições de Karush-Kuhn-Tucker (KKT) , que são necessários sob a qualificação de restrição (o tipo que geralmente vejo é a condição do ponto Slater ) e suficiente sob a convexidade do objetivo e das restrições (mais geralmente, a invexidade do tipo 1). Se $f$ não é convexa, a formulação da desigualdade variacional usando as condições KKT NÃO é equivalente ao problema de otimização original; portanto, estritamente falando, se você deseja um ótimo global para o problema de otimização, não deve expressá-lo como uma desigualdade variacional. De qualquer maneira, seria difícil encontrar um ótimo global para a otimização com restrição de PDE (veja abaixo); portanto, talvez seja bom ignorar esses detalhes. Dado o que Wolfgang disse, eu ficaria cético em usar o TAO; Eu já sou cético porque ele não implementa métodos para resolver programas não lineares (PNL) como PNL, em vez de desigualdades variacionais.

Eu não sou especialista em otimização com restrição de PDE; colegas de trabalho e associados da mina trabalham em problemas de otimização restritos à ODE. Sei que, para formulações intrusivas, Larry Biegler (e outros) usará métodos de colocação para discretizar o PDE e torná-lo uma PNL muito grande e esparsa, e ele o resolverá usando métodos de pontos interiores. Para realmente resolver o problema da otimização global, você também precisará gerar relaxações convexas, mas, tanto quanto eu sei, essa abordagem não é adotada porque os problemas de otimização restritos ao PDE levam a PNLs tão grandes que seria difícil resolvê-los. otimização global. Menciono esses detalhes apenas porque a formulação do problema influencia fortemente a escolha do pacote do solucionador. Para formulações não intrusivas, a PDE repetida resolve informações de gradiente para algoritmos de otimização.

Algumas pessoas que estudam problemas de otimização com restrição de EDO usam uma abordagem semelhante para discretizar o problema usando a colocação e um método numérico e depois relaxam a PNL resultante para produzir uma formulação convexa usada em um algoritmo de otimização global. Uma abordagem alternativa à otimização com restrição de ODE é relaxar o problema e depois discretizar a ODE, que é a abordagem adotada em meu laboratório. Pode ser possível relaxar certas classes de problemas de otimização restritos ao PDE, mas não conheço nenhum trabalho existente feito sobre esse problema. (Foi um projeto em potencial em meu laboratório em um ponto.)

Por fim, o que importa não é a diferenciabilidade do PDE original, mas a diferenciabilidade da discretização em relação às variáveis de decisão.

Se o problema discretizado for diferenciável duas vezes em relação às variáveis de decisão, os seguintes pacotes calcularão uma solução local:

IPOPT é um solucionador de pontos interiores de código aberto desenvolvido por Andreas Wächter na IBM. É um código de qualidade muito alta. Como solucionador de pontos internos, é melhor para funções objetivas com matrizes jacobianas grandes e esparsas e seria útil para otimização com restrição de PDE
O SNOPT é um solucionador de programação quadrática seqüencial comercial que é outro código de alta qualidade. É melhor para funções objetivas com matrizes jacobianas pequenas e densas, então eu não esperaria que fosse útil para otimização com restrição de PDE, mas você pode tentar.
NLopt é um pequeno código-fonte aberto escrito por Steven Johnson no MIT que contém implementações básicas de vários algoritmos de otimização não-lineares. Todos os algoritmos devem ser adequados para resolver problemas de restrição de limites.
fmincon no Matlab implementa vários algoritmos (incluindo ponto interior e programação quadrática sequencial) para otimização não linear
GAMS e AMPL são linguagens de modelagem comerciais usadas para formular problemas de otimização e contêm interfaces para um grande número de solucionadores de programação não-lineares. Sei que o GAMS possui uma versão de avaliação que pode ser usada para problemas menores e as instâncias de problemas também podem ser enviadas ao servidor NEOS para solução também.

No entanto, é possível que a discretização seja diferenciada apenas uma vez em relação às variáveis de decisão; nesse caso, você deve usar a descida mais íngreme projetada ou algum outro método de otimização de primeira ordem ao calcular uma solução local. Como muitos estudos se concentram em problemas nos quais métodos de segunda ordem podem ser usados (e quando você pode usá-los, suas propriedades de convergência superiores os tornam uma escolha melhor), não consegui encontrar muitas implementações de descidas mais íngremes que não fossem soluções problemas de lição de casa. A Biblioteca Científica GNU tem uma implementação, mas é apenas para fins de demonstração. Você provavelmente precisaria codificar sua própria implementação.

Se o problema for contínuo apenas em relação às variáveis de decisão, você poderá usar métodos diretos para resolvê-lo localmente. Há uma excelente pesquisa sobre métodos diretos de Kolda, Lewis e Torczon . O mais conhecido desses métodos é o algoritmo simplex Nelder-Mead . Não é garantido que converja para um mínimo local em várias dimensões, mas encontrou um uso prático considerável de qualquer maneira.

A escolha do pacote realmente depende da linguagem que você deseja usar para resolver o problema, se a solução do problema com restrição de limite for apenas parte de um algoritmo que você deseja implementar (ou se é a única etapa do algoritmo, nesse caso, linguagens de modelagem se tornar mais viável para o código de produção), o tipo e tamanho do problema e se você precisar de algum paralelismo.

Geoff Oxberry
fonte

4

Tentamos o TAO, mas descobrimos que não é muito útil para problemas restritos à desigualdade. Também está essencialmente apenas no modo de manutenção desde pelo menos 2003, sem novos recursos reais além de atualizações para rastrear alterações no PETSc no qual ele é construído.

Wolfgang Bangerth
fonte

3

Outra alternativa é o OPT ++ . Ele suporta restrições lineares e não-lineares com um solucionador de pontos interno não-linear eficiente, fornece controle da precisão das funções (se for necessária diferenciação numérica), controle de tamanhos de etapas etc. Normalmente, estou otimizando grandes funções implícitas (por exemplo, FEM) onde esses tipos de controles podem ser úteis.

Barron
fonte

Você poderia explicar por que o OPT ++ é um bom pacote para usar? Você (ou seus colegas) tem alguma experiência com isso?

Geoff Oxberry

Para ser claro, não tenho motivos para dizer que o OPT ++ é superior a qualquer um dos que você listou anteriormente porque não tenho nenhuma experiência com eles (apesar de ter marcado alguns deles para check-out). Mas tenho experiência com o OPT ++ e achei adequado para minhas necessidades. Ele suporta restrições lineares e não-lineares com um solucionador de pontos interno não-linear eficiente, fornece controle da precisão das funções (se for necessária diferenciação numérica), controle de tamanhos de etapas etc. Normalmente, estou otimizando grandes funções implícitas (por exemplo, FEM) onde esses tipos de controles podem ser úteis.

Barron

2

@ Barron: você deveria ter colocado isso em sua resposta para começar. :)

JM

2

Se o problema for formulado como um problema de complementaridade, você poderá usar o TAO (Toolkit for Advanced Optimization). Alguns dos métodos no TAO, como o método de espaço reduzido (uma variante do método de conjunto ativo), estão atualmente disponíveis como parte do SNES no PETSc ( SNESVI ).

Jungho Lee
fonte

1

O módulo MINUTE do CERNLIB (há muito tempo portado para o ROOT ) usa uma transformação no espaço de entrada para renderizar as restrições da caixa em um espaço onde elas executam e, portanto, pode ser manipulado sem casos especiais (a custo de alguma velocidade, é claro). $[-\infty,+\infty]$

Não acho que o MINUTE funcione bem para as suas necessidades, mas a transformação poderá ocorrer se você for forçado a escrever parte ou todo o código.

dmckee
fonte

Essa transformação parece desagradável; não é de admirar que seja acompanhado por alguns parágrafos.

Geoff Oxberry

1

Como o @Geoff Oxberry apontou, vários pacotes permitem encontrar uma solução local. Se você quiser comparar esses diferentes solucionadores de PNL para um mesmo problema, use o RobOptim .

Embora o RobOptim tenha sido desenvolvido inicialmente com problemas de otimização de robótica, ele é adequado para qualquer problema de otimização não linear. Ele fornece uma interface C ++ simples com plug-ins para vários solucionadores de PNL (por exemplo, Ipopt, NAG). Se você não pode fornecer gradientes, o cálculo de diferenças finitas pode ser feito automaticamente.

É de código aberto para que você possa conferir o código-fonte no GitHub: https://github.com/roboptim/

Nota: Eu sou um dos desenvolvedores deste projeto.

BenC
fonte

11

Deve salientar que outras respostas descrevem solucionadores , não estruturas. É mais fácil encontrar uma estrutura aceitável ( driver ) do que um bom solucionador,

Deer Hunter

@DeerHunter Quando você procura um solucionador para resolver um determinado problema, geralmente é difícil saber a priori qual solucionador calculará a melhor solução e / ou será o mais rápido. Você está falando de um "bom solucionador", mas isso realmente depende do que você está resolvendo: não existe um "melhor solucionador geral". Além disso, as APIs do solver geralmente são bem diferentes, portanto, usar uma boa estrutura que permita alternar facilmente de um solucionador para outro pode ser realmente útil. A pergunta era sobre "pacotes de software para otimização restrita", e os frameworks também se enquadram nessa categoria.

BenC

1

Aqui está uma lista parcial dos pacotes de otimização com restrição de PDE.

Dolfin Adjoint faz parte do FEniCS FEM:

http://dolfin-adjoint.org/

ROL, MOOCHO, Sundance são partes de Trilinos:

https://github.com/trilinos/trilinos/tree/master/packages/rol/

https://github.com/trilinos/trilinos/tree/master/packages/Sundance/

http://trilinos.org/packages/moocho/

Exemplo de PYOMO para otimização com restrição de PDE:

https://software.sandia.gov/trac/pyomo/browser/pyomo/trunk/examples/dae

O manual do TAO fornece exemplos de solução de problemas de otimização com restrição de PDE:

http://www.mcs.anl.gov/petsc/petsc-3.5/docs/tao_manual.pdf

denfromufa
fonte

11

Bem-vindo ao SciComp.SE! Apenas fornecer um link (por mais útil que seja) não é realmente uma boa resposta; consulte meta.stackexchange.com/questions/8231 . Você poderia expandir um pouco isso (linguagem de computação, que tipo de restrições podem ser tratadas, quais métodos são implementados etc.)?

Christian Clason

Eu concordo com @ChristianClason. Houve um desenvolvimento substancial nos solucionadores de software de otimização com restrição de PDE; no entanto, essa resposta não fornece essencialmente nenhum conhecimento sobre quais algoritmos esses pacotes realmente implementam.

precisa

0

Os pacotes APM MATLAB e APM Python podem resolver em larga escala (mais de 100.000 variáveis) de sistemas de equações algébricas diferenciais de números inteiros mistos. O software está disponível como um serviço da Web para uso comercial ou acadêmico. Se você estiver solucionando um sistema PDE, poderá discretizar uma vez para colocá-lo no formato DAE ou ODE e colocá-lo na linguagem de modelagem APMonitor. A linguagem de modelagem usa os solucionadores APOPT , BPOPT, IPOPT, SNOPT e MINOS.

John Hedengren
fonte

11

Divulgue sua afiliação como desenvolvedor do APMonitor nesta e em futuras respostas que mencionam seu software. Consulte as Perguntas frequentes para obter detalhes sobre nossa política de divulgação.

Geoff Oxberry

Geoff, obrigado pela dica. Comecei a trabalhar na plataforma APMonitor em 2004 como estudante de graduação na Universidade do Texas em Austin. Agora o usamos em nosso grupo de pesquisa da Universidade Brigham Young para controle e otimização de processos ( apm.byu.edu/prism ) de aplicações biológicas, químicas, aeroespaciais e outras. Eu o disponibilizo gratuitamente para usuários comerciais ou acadêmicos.

John Hedengren

Pacote de software para otimização restrita?

Respostas: