11.1 Méthodes rapides pour les grands systèmes
301
Soulignons cependant que les méthodes décrites ci-dessous ne sont pas complètement satisfaisantes pour les systèmes isolants (et sont vraisemblablement
largement perfectibles), et qu’elles ne fonctionnent pas pour des systèmes
métalliques (pour lesquels le gap γ est nul). La construction d’algorithmes
de complexité linéaire véritablement efficaces demeure donc un sujet de
recherche actif.
11.1.1 Méthodes de pénalisation
Les méthodes de pénalisation consistent à éliminer les contraintes d’orthonormalité (dans (11.2)) ou d’idempotence (dans (11.1)) en construisant des
fonctions de pénalisation exacte de ces contraintes. Cette technique consiste
à remplacer le problème d’optimisation sous contraintes générique
inf {f (x), x ∈ IR
n , c(x) = 0}
(11.3)
par un problème d’optimisation sans contrainte
inf {h(x), x ∈ IR
n
}
(11.4)
tel que tout minimiseur local de (11.3) soit un minimiseur local de (11.4)
(la réciproque étant rarement vérifiée). On utilise ensuite un algorithme de
minimisation sans contrainte standard (cf. section 6.3.1) pour résoudre (11.4).
Ainsi, la méthode OM (Orbital Minimization [174]) consiste à remplacer (11.2)
par
inf
Tr
F C(2 − C
T SC)C
T
, C ∈ M(N b , N)
(11.5)
et la méthode DMM (Density Matrix Minimization [145]) à remplacer (11.1)
par
inf {Tr (F µ (3DSD − 2DSDSD)) , D ∈ M S (N b ), Tr(SD) = N } (11.6)
où F µ = F − µI, µ désignant le niveau de Fermi, c’est-à-dire un nombre de
l’intervalle ] − N , , N +1 [. On pourra vérifier en exercice que dans les deux cas,
il s’agit bien de méthodes de pénalisation exacte. Notons qu’utiliser (11.6)
nécessite de connaître le niveau de Fermi. Comme c’est une inconnue du problème, il faut coupler la résolution de (11.6) avec un algorithme itératif de
calcul de µ. C’est un problème beaucoup plus facile que celui dont on discute.
L’analyse numérique des algorithmes de descente associés aux problèmes
(11.5) et (11.6) est facile si l’on suppose que toutes les opérations sont effectuées en arithmétique exacte. Or en pratique, ces algorithmes font appel à
des produits matrice-matrice (pour calculer le gradient) qui ne sont effectués
que de façon approchée : les deux matrices qu’on cherche à multiplier sont
creuses et on cherche à conserver ce caractère creux au cours des itérations
en ne stockant que les termes des produits matrice-matrice qui dépassent un
certain seuil. En pratique, on constate que les formulations (11.5) et (11.6)
fournissent des algorithmes relativement efficaces lorsqu’on démarre au voisinage de la solution, mais très mauvais lorsque ce n’est pas le cas.
301
Soulignons cependant que les méthodes décrites ci-dessous ne sont pas complètement satisfaisantes pour les systèmes isolants (et sont vraisemblablement
largement perfectibles), et qu’elles ne fonctionnent pas pour des systèmes
métalliques (pour lesquels le gap γ est nul). La construction d’algorithmes
de complexité linéaire véritablement efficaces demeure donc un sujet de
recherche actif.
11.1.1 Méthodes de pénalisation
Les méthodes de pénalisation consistent à éliminer les contraintes d’orthonormalité (dans (11.2)) ou d’idempotence (dans (11.1)) en construisant des
fonctions de pénalisation exacte de ces contraintes. Cette technique consiste
à remplacer le problème d’optimisation sous contraintes générique
inf {f (x), x ∈ IR
n , c(x) = 0}
(11.3)
par un problème d’optimisation sans contrainte
inf {h(x), x ∈ IR
n
}
(11.4)
tel que tout minimiseur local de (11.3) soit un minimiseur local de (11.4)
(la réciproque étant rarement vérifiée). On utilise ensuite un algorithme de
minimisation sans contrainte standard (cf. section 6.3.1) pour résoudre (11.4).
Ainsi, la méthode OM (Orbital Minimization [174]) consiste à remplacer (11.2)
par
inf
Tr
F C(2 − C
T SC)C
T
, C ∈ M(N b , N)
(11.5)
et la méthode DMM (Density Matrix Minimization [145]) à remplacer (11.1)
par
inf {Tr (F µ (3DSD − 2DSDSD)) , D ∈ M S (N b ), Tr(SD) = N } (11.6)
où F µ = F − µI, µ désignant le niveau de Fermi, c’est-à-dire un nombre de
l’intervalle ] − N , , N +1 [. On pourra vérifier en exercice que dans les deux cas,
il s’agit bien de méthodes de pénalisation exacte. Notons qu’utiliser (11.6)
nécessite de connaître le niveau de Fermi. Comme c’est une inconnue du problème, il faut coupler la résolution de (11.6) avec un algorithme itératif de
calcul de µ. C’est un problème beaucoup plus facile que celui dont on discute.
L’analyse numérique des algorithmes de descente associés aux problèmes
(11.5) et (11.6) est facile si l’on suppose que toutes les opérations sont effectuées en arithmétique exacte. Or en pratique, ces algorithmes font appel à
des produits matrice-matrice (pour calculer le gradient) qui ne sont effectués
que de façon approchée : les deux matrices qu’on cherche à multiplier sont
creuses et on cherche à conserver ce caractère creux au cours des itérations
en ne stockant que les termes des produits matrice-matrice qui dépassent un
certain seuil. En pratique, on constate que les formulations (11.5) et (11.6)
fournissent des algorithmes relativement efficaces lorsqu’on démarre au voisinage de la solution, mais très mauvais lorsque ce n’est pas le cas.