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

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} .$y_0$$\beta \in \mathbb R$$y$$u$

$$\begin{equation} \frac{1}{2} \| y - y_0 \|^2 + \frac{\beta}{2} \| u \|^2 \end{equation}$$ $$\begin{equation} Ay = u. \end{equation}$$ $y, y_0, u \in \mathbb R^n$$A \in \mathbb R^{n \times n}$

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

$$\begin{align*} A^T \lambda &= y_0 - y \\ Ay &= \frac{1}{\beta} \lambda \end{align*}$$ Pré-multiplicando por $A$ na primeira equação e $A^T$ na segunda, podemos escrever as equações normais $$\begin{align} (I + \beta A A^T) \lambda &= \beta A y_0 \\ (I + \beta A^T A) y &= y_0 \end{align}$$ Podemos interpretá-los como etapas simples de aproximações de Euler para trás às equações diferenciais $$\begin{align} \frac{\partial \lambda}{\partial b} &= -A A^T \lambda + A y_0, \quad \lambda(0) = 0 \\ \frac{\partial y}{\partial b} &= -A^T A y, \quad y(0) = y_0 \end{align}$$ com pseudotimestep $\beta$ .

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).

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 $F(u)=y^\delta$$y^\delta$$F$$F=A^{-1}$$y^\delta = y_0$continuaçã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 - γ k ∇ f ( x k ) , ˙ x ( t ) = - ∇ f ( x ( t ) ) $\min_x f(x)$

$$x^{k+1} = x^k - \gamma_k \nabla f(x^k),$$ $$\dot x(t) = -\nabla f(x(t)),\qquad x(0) = x^0.$$ $\gamma_k$$x(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).$x$$x$

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

   $$a_1 \ddot x(t) + a_2 \dot x(t) = -\nabla f(x(t))$$ $a_1,a_2$ $$x^{k+1} = x^k - \gamma_k \nabla f(x^k) + \alpha_k (x^k - x^{k-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.$\gamma_k,\alpha_k$$a_1,a_2$

---

(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 .

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

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.)
$\qquad \dot{ x } = - \nabla f( x )$
$\quad \ddot{ x } = \beta \dot{ x } - \alpha \nabla 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.