Est-il bien connu que certains problèmes d'optimisation équivalent à un pas de temps?

Étant donné un état souhaité et un paramètre de régularisation , considérons le problème de trouver un état et un contrôle pour minimiser une soumis à la contrainte \ begin {equation} Ay = u. \ end {equation} où pour simplifier on peut penser à y, y_0, u \ in \ mathbb R ^ n et 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}$

En formant le lagrangien, en recherchant des points stationnaires et en éliminant le contrôle $u$ nous obtenons les conditions de premier ordre

$$\begin{align*} A^T \lambda &= y_0 - y \\ Ay &= \frac{1}{\beta} \lambda \end{align*}$$ Prémultipliant par $A$ dans la première équation et $A^T$ dans la seconde, nous pouvons écrire les équations normales $$\begin{align} (I + \beta A A^T) \lambda &= \beta A y_0 \\ (I + \beta A^T A) y &= y_0 \end{align}$$ Nous pouvons les interpréter comme des étapes simples d'approximations d'Euler inverses aux équations différentielles $$\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}$$ avec pseudotimestep $\beta$ .

Ma question: ce lien est-il bien connu? Est-il discuté dans les traitements standards de timestapse ou d'optimisation? (Pour moi, cela semble fournir une sorte de connexion intuitive entre eux.)

L'idée semble assez simple pour qu'elle soit bien connue, mais ni chercher dans la littérature ni parler aux gens ne m'a donné une bonne source où cela est discuté. Le plus proche que j'ai trouvé est un article de O. Scherzer et J. Weichert (J. Math Imaging Vision 12 (2000) pp. 43-63) qui énonce le lien dans la première phrase du résumé (!) Mais ne dit pas fournir des références ou explorer la connexion en profondeur.

Idéalement, je recherche une référence qui non seulement énonce la connexion mais explore également certaines conséquences (par exemple, on pourrait imaginer préconditionner un problème d'optimisation avec une étape Euler pas chère).

Comme l'a mentionné Jed Brown, le lien entre la descente de gradient dans l'optimisation non linéaire et le pas de temps des systèmes dynamiques est redécouvert avec une certaine fréquence (ce qui est compréhensible, car il s'agit d'un lien très satisfaisant avec l'esprit mathématique car il relie deux champs apparemment différents). Cependant, il s'avère rarement être une connexion utile , surtout dans le contexte que vous décrivez.

Dans les problèmes inverses, les gens sont intéressés par la résolution de l'équation de l' opérateur (mal posé) avec pas dans la plage de . (Votre problème de contrôle optimal peut être vu comme une instance de celui-ci avec et .) Plusieurs stratégies de régularisation (telles que Tikhonov ou Landweber) peuvent être interprétées comme un seul pseudo-temps étape d'une certaine classe. L'idée est alors d'utiliser l'interprétation du paramètre de régularisation comme longueur de pas pour obtenir des règles de choix (adaptatif, a posteriori) du paramètre - un problème fondamental dans les problèmes inverses - et éventuellement de faire plusieurs pseudo-temps pour approche la vraie solution non régularisée (comme pour$F(u)=y^\delta$$y^\delta$$F$$F=A^{-1}$$y^\delta = y_0$suite numérique ). Ceci est parfois appelé régularisation continue , et est généralement discuté dans le contexte des méthodes de level set; voir, par exemple, le chapitre 6.1 de Kaltenbacher, Scherzer, Neubauer: Méthodes de régularisation itérative pour les problèmes non linéaires mal posés (de Gruyter, 2008).

Un deuxième contexte dans cette idée apparaît à plusieurs reprises est l'optimisation non linéaire: si vous regardez une étape de descente de gradient pour , vous pouvez alors l'interpréter comme une étape d'Euler vers l'avant pour le système dynamique Comme l'a souligné Jed Brown, cela ne donne à première vue que l'observation peu surprenante que cette méthode converge, à condition que les pseudo-pas de temps soient suffisamment petits. La partie intéressante survient lorsque vous regardez le système dynamique et que vous vous demandez quelles sont les propriétés de la solution continue du flux dit de gradient$\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)$a (ou devrait avoir), indépendamment de la descente du gradient, et si cela ne pourrait pas conduire à des méthodes de pas de temps (et donc d'optimisation) plus appropriées que Euler standard. Quelques exemples du haut de ma tête:

1. Existe-t-il un espace de fonction naturel dans lequel vit le flux de gradient? Si c'est le cas, votre pas de gradient doit être pris à partir du même espace (c'est-à-dire que la discrétisation doit être conforme). Cela conduit, par exemple, au calcul des représentations Riesz du gradient par rapport à différents produits internes (parfois appelés gradients de Sobolev ) et, en pratique, à des itérations préconditionnées qui convergent beaucoup plus rapidement.

2. Peut-être que ne devrait pas appartenir à un espace vectoriel, mais à une variété (par exemple, des matrices définies positives symétriques), ou le flux de gradient devrait conserver une certaine norme de . Dans ce cas, vous pouvez essayer d'appliquer des schémas de pas de temps préservant la structure (par exemple, impliquant un retrait par rapport à un groupe de Lie approprié ou à un intégrateur géométrique).$x$$x$

3. Si n'est pas différenciable mais convexe, le pas d'Euler vers l'avant correspond à une méthode de descente de sous-gradient qui peut être très lente en raison des restrictions de taille de pas. D'un autre côté, une étape d'Euler implicite correspond à une méthode de point proximal , pour laquelle aucune restriction de ce type ne s'applique (et qui est ainsi devenue très populaire, par exemple, dans le traitement d'image).$f$

4. Dans la même veine, ces méthodes peuvent être considérablement accélérées par des étapes d'extrapolation. Une façon de les motiver est d'observer que les méthodes de premier ordre standard souffrent d'avoir à faire de nombreux petits pas près des minimiseurs, parce que les directions du gradient "oscillent" (pensez à l'illustration standard pour laquelle les gradients conjugués surclassent la descente la plus raide). Pour y remédier, on peut "amortir" l'itération en ne résolvant pas un système dynamique du premier ordre, mais un système du second ordre amorti : pour convenablement choisi . Avec une discrétisation appropriée, cela conduit à une itération (connue sous le nom de méthode de balle lourde de Polyak ) de la forme

   $$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})$$ (avec selon ). Des idées similaires existent pour les méthodes du point proximal, voir, par exemple, l'article http://arxiv.org/pdf/1403.3522.pdf de Dirk Lorenz et Thomas Pock.$\gamma_k,\alpha_k$$a_1,a_2$

---

(Je dois ajouter qu'à ma connaissance, dans la plupart de ces cas, l'interprétation en tant que système dynamique n'était pas strictement nécessaire pour la dérivation ou la preuve de convergence de l'algorithme; on pourrait soutenir que des idées comme «implicites vs explicites» ou dérivées de Lie sont en fait plus fondamentaux que les systèmes dynamiques ou les méthodes de descente de gradient. Pourtant, cela ne fait jamais de mal d'avoir un autre point de vue pour regarder un problème.)

---

EDIT: Je suis juste tombé sur un excellent exemple du deuxième contexte, où l'interprétation ODE est utilisée pour déduire les propriétés de la méthode extragradient de Nesterov et suggérer des améliorations: http://arxiv.org/pdf/1503.01243.pdf (Notez que c'est aussi un exemple du point de Jed Brown, en ce sens que les auteurs redécouvrent essentiellement le point 4 ci-dessus sans avoir apparemment connaissance de l'algorithme de Polyak.)

EDIT 2: Et pour vous indiquer jusqu'où vous pouvez aller, voir page 5 de http://arxiv.org/pdf/1509.03616v1.pdf .

Bien que je n'aie pas vu la formulation exacte que vous avez écrite ici, je continue de voir des discussions dans lesquelles les gens "redécouvrent" une connexion à l'intégration d'un système transitoire, et continuent à écrire un algorithme qui est algébriquement équilavent à une forme ou une autre d'une descente de gradient existante ou d'une méthode de type Newton, et ne citer personne d'autre. Je pense que ce n'est pas très utile parce que la conclusion est fondamentalement que "tant que vous faites assez peu de pas, la méthode finit par converger vers un minimum local". Eh bien, 2014 marque le 45e anniversaire de l'article de Philip Wolfe montrant comment le faire de manière raisonnée. Il existe également une bonne théorie pour obtenir une convergence q-quadratique ou q-super-linéaire à partir de la continuation pseudotransitoire et de méthodes connexes comme Levenberg-Marquardt.

Si vous voulez un exemple de cette redécouverte en utilisant une formulation de type Newton pour résoudre des équations algébriques (c.-à-d., Continuation pseudotransitoire classique) d'un mathématicien avec plus de 600 articles (alors peut-être qu'il prouvera des choses que vous trouvez intéressantes), regardez le " Méthode des systèmes dynamiques "par AG Ramm [1].

Si l'intuition acquise en considérant un système transitoire conduisait à des algorithmes pratiques qui étaient soit plus rapides soit plus fiables, je pense que nous verrions des articles très cités sur ce sujet. Je pense que ce n'est pas un mystère que Nocedal et Wright ont plus de 13 000 citations alors que le livre de Ramm en a environ 80 (principalement des auto-citations).

[1] Je peux vous conseiller de ne pas informer le professeur Ramm que son DSM est algébriquement équivalent à quelque chose qui a été dans d'innombrables packages d'ingénierie pendant des décennies ou vous pourriez vous faire hurler hors de la pièce. #gradstudentmemories

Si les méthodes ODE peuvent contribuer à l'optimisation, y a-t-il un exemple de problème très simple pour le montrer?
Un homme de paille: existe-t-il un solveur ODE qui fait un travail raisonnable sur ou comme Christian Clason le suggère pour dire la fonction de Rosenbrock, en 2d ou 10d? Si c'est idiot, quelqu'un a-t-il un meilleur homme de paille? (Notez "raisonnable", pas "compétitif avec les optimiseurs de pointe". J'imagine que l'on a besoin de diminuer la taille / tolérance des pas, et peut-être un solveur rigide.)
$\qquad \dot{ x } = - \nabla f( x )$
$\quad \ddot{ x } = \beta \dot{ x } - \alpha \nabla f( x ) \ \ $
$f$

En pratique, les étapes "trop ​​grandes" sont beaucoup plus problématiques que "trop ​​petites" - les oscillations sont désordonnées.
J'aurais pensé naïvement que la théorie du contrôle pouvait aider. Recettes numériques p. 915 décrit
le contrôle de taille adaptative PI pour les ODE, mais je ne sais pas si cela est utilisé dans la pratique.