É sabido que alguns problemas de otimização são equivalentes a intervalos de tempo?

19

Dado um estado desejado e um parâmetro de regularização , considere o problema de encontrar um estado e um controle para minimizar um sujeita à restrição \ begin {equação} Ay = u. \ end {equação} onde, por simplicidade, podemos pensar em y, y_0, u \ in \ mathbb R ^ n e A \ in \ mathbb R ^ {n \ times n} .y0 0βRyvocê

1 12__y-y0 0__2+β2__você__2
UMAy=você.
y,y0 0,vocêRnUMARn×n

Formando o lagrangiano, procurando pontos estacionários, e eliminando o controle você temos as condições de primeira ordem

UMATλ=y0 0-yUMAy=1 1βλ
Pré-multiplicando por UMA na primeira equação e UMAT na segunda, podemos escrever as equações normais
(Eu+βUMAUMAT)λ=βUMAy0 0(Eu+βUMATUMA)y=y0 0
Podemos interpretá-los como etapas simples de aproximações de Euler para trás às equações diferenciais
λb=-UMAUMATλ+UMAy0 0,λ(0 0)=0 0yb=-UMATUMAy,y(0 0)=y0 0
com pseudotimestep β .

Minha pergunta: essa conexão é bem conhecida? É discutido em tratamentos padrão de timestepping ou otimização? (Para mim, parece fornecer algum tipo de conexão intuitiva entre eles.)

A idéia parece simples o suficiente para ser bem conhecida, mas nem pesquisar na literatura ou conversar com pessoas me deu uma boa fonte de discussão. O mais próximo que encontrei é um artigo de O. Scherzer e J. Weichert (J. Math Imaging Vision 12 (2000), pp. 43-63), que afirma a conexão na primeira frase do resumo (!), Mas não forneça referências ou explore a conexão em qualquer profundidade.

Idealmente, estou procurando uma referência que não apenas declare a conexão, mas também explore algumas consequências (por exemplo, é possível imaginar pré-condicionar um problema de otimização com uma etapa Euler direta e barata).

Andrew T. Barker
fonte
11
De um modo geral (e como você provavelmente já sabe), as abordagens passo a passo em pseudo-tempo são métodos bem conhecidos para resolver equações algébricas (como o sistema KKT que você descreve), lançando o problema para encontrar o estado estacionário de um conjunto de EDOs onde a variável time é realmente um pseudo-time. No entanto, não conheço nenhuma conexão específica que relacione uma instância específica das condições KKT a uma única etapa de Euler para trás.
precisa
Como um aparte, você só precisa resolver um dos dois ODEs, pois você pode usar uma das condições necessárias de primeira ordem para calcular, por exemplo, de . λyλ
Christian Clason

Respostas:

17

Como Jed Brown mencionou, a conexão entre a descida do gradiente na otimização não-linear e a escalada no tempo dos sistemas dinâmicos é redescoberta com alguma frequência (compreensivelmente, uma vez que é uma conexão muito satisfatória com a mente matemática, uma vez que vincula dois campos aparentemente diferentes). No entanto, raramente acaba sendo uma conexão útil , especialmente no contexto que você descreve.

Em problemas inversos, as pessoas estão interessadas em resolver a equação operador (mal-posto) com não na faixa de . (Seu problema de controle ideal pode ser visto como uma instância dele com e .) Diversas estratégias de regularização (como Tikhonov ou Landweber) podem ser interpretadas como um único pseudo-tempo passo de uma determinada classe. A idéia é, então, usar a interpretação do parâmetro de regularização como um comprimento de etapa para obter algumas regras de escolha (adaptativas a posteriori) para o parâmetro - um problema fundamental em problemas inversos - e possivelmente fazer várias etapas pseudo-temporais para abordar a solução verdadeira e não regulamentada (semelhante ày δ F F = A - 1 y δ = y 0F(você)=yδyδFF=UMA-1 1yδ=y0 0continuação numérica ). Isso às vezes é chamado de regularização contínua e geralmente é discutido no contexto de métodos de conjunto de níveis; veja, por exemplo, o capítulo 6.1 de Kaltenbacher, Scherzer, Neubauer: métodos de regularização iterativa para problemas não-lineares de posicionamento incorreto (de Gruyter, 2008).

Um segundo contexto em que essa idéia surge repetidamente é a otimização não-linear: se você observar um passo de descida de gradiente para , é possível interpretar isso como uma etapa de Euler direta para o sistema dinâmico Como Jed Brown apontou, isso à primeira vista produz apenas a observação não muito surpreendente de que esse método converge, desde que os passos do pseudo-tempo sejam pequenos o suficiente. A parte interessante vem quando você olha para o sistema dinâmico e se pergunta quais propriedades a solução contínua do chamado fluxo gradientex k + 1 = x k - γ kf ( x k ) , ˙ x ( t ) = - f ( x ( t ) ) ,minxf(x)

xk+1 1=xk-γkf(xk),
x˙(t)=-f(x(t)),x(0 0)=x0 0.
γkx(t)possui (ou deveria ter), independentemente da descida do gradiente, e se isso pode não levar a métodos de escalonamento de tempo mais apropriados (e, portanto, otimização) do que o Euler padrão. Alguns exemplos em cima da minha cabeça:
  1. Existe um espaço funcional natural no qual o fluxo de gradiente vive? Nesse caso, sua etapa de gradiente deve ser realizada no mesmo espaço (ou seja, a discretização deve estar em conformidade). Isso leva, por exemplo, ao cálculo das representações de Riesz do gradiente em relação a diferentes produtos internos (às vezes chamados de gradientes de Sobolev ) e, na prática, a iterações pré-condicionadas que convergem muito mais rapidamente.

  2. Talvez deva pertencer não a um espaço vetorial, mas a uma variedade (por exemplo, matrizes definidas positivas simétricas), ou o fluxo gradiente deve conservar uma certa norma de . Nesse caso, você pode tentar aplicar esquemas de escalonamento que preservam a estrutura (por exemplo, envolvendo um retrocesso em relação a um grupo de Lie apropriado ou a um integrador geométrico).xx

  3. Se não for diferenciável, mas convexo, a etapa de Euler direta corresponde a um método de descida de subgradiente que pode ser muito lento devido a restrições de tamanho de etapa. Por outro lado, um passo implícito de Euler corresponde a um método de ponto proximal , para o qual essas restrições não se aplicam (e que assim se tornaram muito populares no processo de imagem, por exemplo).f

  4. De maneira semelhante, esses métodos podem ser significativamente acelerados por etapas de extrapolação. Uma maneira de motivá-las é observar que os métodos padrão de primeira ordem sofrem com a necessidade de dar muitos pequenos passos próximos aos minimizadores, porque as direções do gradiente "oscilam" (pense na ilustração padrão para saber por que os gradientes conjugados superam a descida mais íngreme). Para remediar isso, pode-se "amortecer" a iteração não resolvendo um sistema dinâmico de primeira ordem, mas um sistema de segunda ordem amortecido : para escolhido adequadamente . Com a discretização adequada, isso leva a uma iteração (conhecida como método de bola pesada de Polyak ) da forma

    uma1 1x¨(t)+uma2x˙(t)=-f(x(t))
    uma1 1,uma2
    xk+1 1=xk-γkf(xk)+αk(xk-xk-1 1)
    (com dependendo de ) Idéias semelhantes existem para métodos de pontos proximais, veja, por exemplo, o artigo http://arxiv.org/pdf/1403.3522.pdf de Dirk Lorenz e Thomas Pock.γk,αkuma1 1,uma2

(Devo acrescentar que, na minha opinião, na maioria desses casos a interpretação como um sistema dinâmico não era estritamente necessária para a derivação ou a prova de convergência do algoritmo; alguém poderia argumentar que idéias como "implícito vs. explícito" ou derivado de Lie são realmente mais fundamentais do que os sistemas dinâmicos ou os métodos de descida de gradiente. Ainda assim, nunca é demais ter outro ponto de vista para analisar um problema.)


Edição: Acabei de encontrar um excelente exemplo do segundo contexto, em que a interpretação ODE é usada para deduzir propriedades do método extragradiente de Nesterov e sugerir melhorias: http://arxiv.org/pdf/1503.01243.pdf (Observe que isso também é um exemplo do argumento de Jed Brown, no qual os autores redescobrem essencialmente o ponto 4 acima, sem aparentemente conhecer o algoritmo de Polyak.)

EDIÇÃO 2: E como uma indicação de quão longe você pode levar isso, consulte a página 5 de http://arxiv.org/pdf/1509.03616v1.pdf .

Christian Clason
fonte
Estou aceitando esta resposta porque o segundo parágrafo responde mais diretamente à pergunta que eu estava tentando fazer, mas também gostei da resposta de Jed Brown.
Andrew T. Barker
13

Embora eu não tenha visto a formulação exata que você escreveu aqui, continuo vendo palestras nas quais as pessoas "redescobrem" uma conexão para integrar algum sistema transitório e passam a escrever um algoritmo que é algebricamente-equilibrado para uma forma ou outro de uma descida de gradiente existente ou método semelhante a Newton, e falha em citar qualquer outra pessoa. Eu acho que não é muito útil porque a conclusão é basicamente que "contanto que você dê passos pequenos o suficiente, o método eventualmente convergirá para um mínimo local". Bem, 2014 marca o 45º aniversário do artigo de Philip Wolfe, mostrando como fazer isso de uma maneira baseada em princípios. Também há uma boa teoria para obter convergência q quadrática ou q superlinear a partir da continuação pseudotransiente e métodos relacionados, como Levenberg-Marquardt.

Se você deseja obter um exemplo dessa redescoberta usando uma formulação semelhante a Newton para resolver equações algébricas (por exemplo, continuação pseudotransiente clássica) de um matemático com mais de 600 artigos (talvez ele prove coisas que você acha interessantes), veja " Método de Sistemas Dinâmicos "por AG Ramm [1].

Se a intuição adquirida ao considerar um sistema transitório levasse a algoritmos práticos que eram mais rápidos ou mais confiáveis, acho que veríamos artigos altamente citados sobre esse assunto. Eu acho que não é nenhum mistério que Nocedal e Wright tenham mais de 13.000 citações, enquanto o livro de Ramm tem cerca de 80 (principalmente autocitações).

[1] Eu posso aconselhá-lo a não informar ao Prof. Ramm que seu DSM é algebricamente equivalente a algo que está em incontáveis ​​pacotes de engenharia há décadas ou você pode ser gritado para fora da sala. #gradstudentmemories

Jed Brown
fonte
3
Pode ser mais interessante ver você dizer isso a ele agora, Jed!
Bill Barth
0

Se os métodos ODE podem contribuir para a otimização, existe um problema de exemplo realmente simples para mostrar isso?
Um homem de palhaço: existe um solucionador de ODE que faça um trabalho razoável em ou como Christian Clason sugere para digamos a função de Rosenbrock, em 2d ou 10d? Se isso é bobagem, alguém tem um homem de palha melhor? (Observe "razoável", não "competitivo com otimizadores de última geração". Imagino que seja necessário diminuir o tamanho / tolerância das etapas e talvez um solucionador rígido.)
x˙=-f(x)
x¨=βx˙-αf(x)  
f

Na prática, etapas "grandes demais" são muito mais problemáticas do que "pequenas demais" - as oscilações são confusas.
Eu teria pensado ingenuamente que a teoria do controle poderia ajudar. Receitas Numéricas p. 915 descreve o
controle de tamanho de etapa adaptável do PI para ODEs, mas não sei se isso é usado na prática.

denis
fonte
Parece que você está postando uma nova pergunta como resposta ... Perguntas tangencialmente relacionadas devem ser postadas em perguntas ou comentários separados para as respostas dadas.
Paul
@Paul, isso faz algum sentido? Em caso afirmativo, você poderia sugerir um título para uma nova pergunta?
Denis
Estou confuso ... Posso estar errado, mas parece que sua resposta não é realmente a pergunta do OP. Qual é exatamente a mensagem que você está tentando transmitir e como ela se relaciona com a pergunta original?
Paul
@ Paul, desculpe, eu não estou claro. A pergunta que eu entendo pede uma relação entre um problema de otimização específico e o tempo, também conhecido como solucionadores de ODE. Christian Clason aponta a relação direta entre a descida do gradiente e um solucionador de EDO específico (Euler-dianteiro). Comento, o que é uma função de teste simples f () que mostra um solucionador de ODE se movendo em direção a um mínimo de f ()?
Denis