Eles usam programação semidefinida na indústria?

10

Não vejo menção a isso nas listas de empregos. Já vi programação inteira mencionada, MIP, programação não-linear com números inteiros mistos, LP, programação dinâmica etc., mas sem SDP. É muito mais moderno na academia do que na indústria?

Da minha exposição limitada a acadêmicos e participantes da indústria em sistemas de energia elétrica, acho que há uma boa chance de que o SDP seja aplicado em problemas ótimos de fluxo de energia por operadores independentes, mas depende da extensão em que as cabeças dos ovos possam escalar abordagens atuais para lidar com instâncias de problemas maiores.

GrayOnGray
fonte

Respostas:

8

De minha própria experiência limitada no setor de energia, ninguém está resolvendo SDPs nesse tipo de escala. Eu tenho um conhecimento limitado do que a ISO da Nova Inglaterra está fazendo e acho que eles estão mais interessados ​​em incorporar a estocástica nos seus modelos MILP existentes. De amigos que trabalharam em sistemas de energia em laboratórios governamentais de pesquisa nos EUA, eles também estão pensando em estocástico (programação estocástica, restrições de chance, otimização robusta ...).

Pela minha experiência no setor de grandes empresas de tecnologia, as pessoas estão resolvendo os MILPs nos modelos mais complicados e geralmente determinísticos.

Pelo lado da engenharia química, eles parecem interessados ​​no MINLP, em particular na otimização quadrática de restrições não-convexas, que surge naturalmente em problemas de mistura. Também existem problemas limitados do PDE e todas essas outras coisas divertidas, mas isso é principalmente fruto da minha experiência.

Se eu tivesse que especular, o SDP poderia ser usado no projeto de semicondutores como uma sub-rotina (por exemplo, para MAXCUT), mas, dada a falta de solucionadores de qualidade, acho que não há uma demanda enorme (pelo menos).

Eu diria que na academia, o SDP é mais interessante como uma ferramenta de prova, ou seja, "veja, esse problema é hora polinomial!" se você pode descobrir como se comportar como um SDP. Os solucionadores de SDP são tão delicados (em comparação com outras classes de problemas convexos) que acho que as pessoas não estão realmente empolgadas com a ideia de ter que resolvê-las.

IainDunning
fonte
SDP não é conhecido por ser sempre em tempo polinomial, eu acho. IIRC, você precisa de restrições adicionais para saber isso com certeza.
user541686
Claro, mas se essas restrições não fossem atendidas, você não a veria como prova, porque não haveria muito sentido.
precisa saber é o seguinte
7

A programação semidefinida e a programação em cone de segunda ordem não foram adotadas tão rapidamente na prática quanto muitos de nós esperávamos. Eu estive envolvido nisso nos últimos 20 anos, e foi muito decepcionante ver um progresso lento. Deixe-me apontar alguns dos desafios:

  1. O(m2)mO(m2) Os requisitos de armazenamento são um tópico ativo da pesquisa, mas na área do SDP eles simplesmente não provaram ser suficientemente robustos para serem usados ​​em um solucionador de propósito geral.

  2. Os fornecedores de software LP ainda não consideraram adequado incluir suporte para SDP em seus produtos. Algum suporte limitado ao SOCP está começando a aparecer.

  3. O conhecimento sobre programação semidefinida se espalhou lentamente. O livro de Boyd e Vandenberghe tem sido extremamente útil a esse respeito, mas ainda há um longo caminho a percorrer antes que essa tecnologia seja tão amplamente conhecida quanto as técnicas de otimização mais antigas.

  4. Linguagens e sistemas de modelagem (como GAMS, AMPL etc.) ainda não oferecem um bom suporte para SOCP e SDP. O pacote CVX é o trabalho mais interessante nessa direção, mas mesmo requer alguma sofisticação por parte do usuário.

O SDP encontrou aplicações em nível de pesquisa em muitas áreas da engenharia e ciência. Parece provável que estes acabem por se tornar importantes também na indústria.

Brian Borchers
fonte
5
Apenas para acrescentar: o único solucionador comercial de SDP disponível é o MOSEK e, de qualquer forma, é bastante recente. Penso que a robustez é mais importante do que se pode pensar: em muitas aplicações, você pode alocar mais tempo, mas se um solucionador falha, o que se deve fazer?
AndreaCassioli
5

A maior parte do trabalho que conheço nos laboratórios para problemas de fluxo de energia também está na otimização estocástica, concentrando-se principalmente em MILPs.

Na engenharia química, eles estão interessados ​​nos MINLPs, e o exemplo clássico é um problema de mistura (especificamente, o problema prototípico de pooling de Haverly), de modo que termos bilineares surgem muito. Termos trilineares ocasionalmente aparecem, dependendo dos modelos de mistura termodinâmica ou de reação usados. Há também uma quantidade limitada de interesse na otimização com restrição de ODE ou PDE; nada desse trabalho usa SDPs.

A maior parte do trabalho de otimização com restrição de PDE que eu já vi (estou pensando especificamente na otimização de topologia) não usa SDPs. As restrições do PDE podem ser lineares e, em teoria, podem admitir uma formulação de SDP, dependendo de quais são as restrições objetivas e restantes. Na prática, os problemas de engenharia tendem a ser não-lineares e geram problemas não-convexos que são então resolvidos para ótimos locais (possivelmente também usando vários estágios). Às vezes, formulações de penalidade são usadas para excluir ótimos locais subótimos conhecidos.

Eu pude ver que talvez esteja sendo usado na teoria de controle. A pequena quantidade de trabalho que eu vi sobre "desigualdades matriciais lineares" sugere que poderia ser útil lá, mas a teoria do controle na indústria tende a confiar em métodos testados e comprovados, em vez de formulações matemáticas avançadas, por isso duvido que os SDPs será usado por um tempo até que eles possam provar sua utilidade.

Existem alguns solucionadores de SDP que estão bem, e eles resolveram problemas muito grandes para a academia (a última vez que verifiquei foi há 3-4 anos atrás, e eles estavam resolvendo dezenas a centenas de milhares de variáveis), mas os cenários de fluxo de energia envolvem problemas muito maiores (dezenas de milhões a bilhões de variáveis), e não acho que os solucionadores ainda estejam lá. Eu acho que eles poderiam chegar lá - tem havido uma quantidade considerável de trabalhos recentes sobre métodos de pontos interiores sem matriz que sugerem que seria viável ampliar os solucionadores de SDP usando essas técnicas - mas ninguém fez isso ainda, provavelmente porque LPs, MILPs e PNL convexas surgem com muito mais frequência e são tecnologias estabelecidas.

Geoff Oxberry
fonte
2
Agora, sou muito pouco sobre isso, mas o engraçado é que os aplicativos para controlar a teoria já existem há algum tempo. Desigualdades matriciais lineares em Sistemas e Controle , foi publicado em 1994. Stephen Boyd faz a maior parte de sua pesquisa no cruzamento da otimização e controle, e ele também tem feito isso desde pelo menos 1996.
GrayOnGray
É verdade. A maior parte do que sei sobre controle industrial vem de um curto estágio na indústria de processamento químico e, ali, o controle preditivo de modelos era uma grande novidade, e acredito que isso foi desenvolvido em algum momento entre meados dos anos 80 e início dos anos 90.
Geoff Oxberry