Cas d’application

Résoudre des modèles de politique fiscale grâce à Julia avec Artelys Knitro
Les économistes travaillent régulièrement avec des modèles de politique fiscale sous forme de problèmes d’optimisation non convexes avec contraintes d’inégalités. Ils présentent une dégénérescence : le nombre de contraintes d’inégalité actives pour une solution est généralement plusieurs fois supérieur au nombre de variables du problème, ce qui les rend particulièrement difficiles à résoudre.

Enjeux

  • Algorithme NLC
  • Des milliers de variables et des demi-millions de contraintes

Résultats

  • Résultats chiffrés sur des problèmes réalistes
  • Calcul primal et dual

L’algorithme NCL, conçu par Kenneth Judd, Ding Ma, Michael Saunders et Dominique Orban dans le cadre de la thèse de doctorat de Ding Ma à Stanford, traite de la difficulté à résoudre de tels modèles. L’idée est d’approcher un problème mal posé avec une séquence de sous-problèmes bien posés sans la caractéristique de dégénérescence. On peut alors trouver une solution approchée aux premiers sous-problèmes. La précision n’est nécessaire que lorsque l’on s’approche de la solution du modèle original.

La première version de la NCL est entièrement implémentée en AMPL et appelle le solveur non-linéaire Artelys Knitro avec son algorithme barrière et les options appropriées. On peut ainsi résoudre les sous-problèmes correspondant aux modèles de politique fiscale avec des milliers de variables et un demi-million de contraintes.

Le succès du NCL sur les modèles fiscaux a incité à étudier une généralisation pour tout modèle d’optimisation. Le langage Julia offre les outils nécessaires à cette généralisation, notamment via l’interface Julia avec KNITRO et l’infrastructure JuliaSmoothOptimizers (JSO) pour l’optimisation. En particulier, les fonctionnalités de modélisation génériques de JSO donnent accès à d’importantes données de tests par l’interface Julia à la collection CUTEst et aux modèles AMPL.

Grâce aux travaux de Pierre-Élie Personnaz lors de son stage au GERAD, des résultats numériques sur des problèmes fiscaux réalistes ont été présentés à la conférence ICCOPT 2019 à Berlin. Ces résultats dépassaient tous les résultats précédents. Le solveur NCL montre à quel point la combinaison de Julia, JSO et Artelys Knitro peut être puissante pour l’optimisation. Les améliorations en cours comprennent les démarrages à chaud en primal et dual, les tolérances progressives et l’ajustement des paramètres.

© ARTELYS • All rights reserved • Legal mentions

Pin It on Pinterest

Share This