Plans de collecte de données adaptatifs visant à minimiser les effets du mode d’enquête – étude du cas de l’Enquête sur la population active des Pays‑Bas 3. Un algorithme pour résoudre le problème d’optimisation multimodalPlans de collecte de données adaptatifs visant à minimiser les effets du mode d’enquête – étude du cas de l’Enquête sur la population active des Pays‑Bas 3. Un algorithme pour résoudre le problème d’optimisation multimodal

• Précédent
• Suivant

Dans la section qui précède, nous avons introduit les fonctions de qualité et de coût et construit un problème d’optimisation multimodal. La contrainte de la comparabilité des sous‑populations, c’est‑à‑dire la limite supérieure de la différence absolue maximale entre les effets de méthode de groupe, rend le problème non convexe et difficile à résoudre. En conséquence, lorsqu’ils essaient de résoudre le problème d’optimisation multimodal, la plupart des solveurs de programmation non linéaire à des fins générales ne peuvent pas faire mieux qu’un optimum local. Le choix des points de départ dans les solveurs joue donc un rôle important. C’est pourquoi nous proposons une approche en deux étapes. Dans la première étape, nous résolvons un problème de programmation linéaire (PL) en agissant sur les contraintes linéaires (2.1), (2.5), (2.6) et (2.9) $-$ (2.10). Dans la deuxième étape, nous utilisons la solution optimale obtenue dans la première étape comme point de départ à un algorithme de recherche local pour résoudre le problème non linéaire non convexe.

Nous reformulons le problème d’optimisation afin d’en faciliter le calcul. Étant donné que $\left|f\left(x\right)\right|=\max \left\{f\left(x\right)\mathrm{,}-f\left(x\right)\right\},$ nous pouvons reformuler la fonction d’objectif au moyen d’une variable additionnelle $t$ et imposer les contraintes $f\left(x\right)\le t$ et $-f\left(x\right)\le t.$ De toute évidence, $t$ doit être non négatif. Les contraintes mêmes ne changent pas; elles sont simplement remplacées. Le problème d’optimisation multimodal est donné en (3.2).

Nous pouvons dériver la PL en supprimant les contraintes non linéaires de la comparabilité des effets de méthodes entre les sous‑populations et en remplaçant la fonction d’objectif non linéaire par une des contraintes linéaires. Nous choisissons la minimisation des coûts comme objectif de la PL. Le problème de PL résultant est formulé comme suit :

$$\begin{array}{ll}\underset{p\left(s\mathrm{,}g\right)}{\text{minimiser}}\hfill & {\displaystyle \sum _{s\mathrm{,}g}{N}_g}p\left(s\mathrm{,}g\right)c\left(s\mathrm{,}g\right)\hfill \\ \text{sous les contraintes}\hfill & {\displaystyle \sum _{s\in {\mathcal{S}}^R}{N}_g}p\left(s\mathrm{,}g\right)\rho \left(s\mathrm{,}g\right)\ge R_g\mathrm{,}\forall g\in \mathcal{G}\hfill \\ \hfill & {\displaystyle \sum _{s\mathrm{,}g}{N}_g}p\left(s\mathrm{,}g\right)\le S_{\text{max}}\hfill \\ \hfill & 0\le p\left(s\mathrm{,}g\right)\le \mathrm{1,}\forall s\in \mathcal{S}\mathrm{,}g\in \mathcal{G}\hfill \\ \hfill & {\displaystyle \sum _{s\in \mathcal{S}}p\left(s\mathrm{,}g\right)}=1,\forall g\in \mathcal{G}\hfill \\ \hfill & {\displaystyle \sum _{s\in {\mathcal{S}}^R}p\left(s\mathrm{,}g\right)}\text{>}0,\forall g\in \mathcal{G}\mathrm{.}\hfill \end{array}(3.1)$$

$$\begin{array}{ll}\text{Minimiser}\hfill & t\hfill \\ \text{sous les contraintes}\hfill & {\displaystyle \sum _{s\mathrm{,}g}}\frac{w_{g}p\left(s\mathrm{,}g\right)\rho \left(s\mathrm{,}g\right)D\left(s\mathrm{,}g\right)}{{\displaystyle \sum _{s^{\prime }\in {\mathcal{S}}^R}}p\left(s^{\prime }\mathrm{,}g\right)\rho \left(s^{\prime }\mathrm{,}g\right)}\le t\hfill \\ \hfill & -{\displaystyle \sum _{s\mathrm{,}g}}\frac{w_{g}p\left(s\mathrm{,}g\right)\rho \left(s\mathrm{,}g\right)D\left(s\mathrm{,}g\right)}{{\displaystyle \sum _{s^{\prime }\in {\mathcal{S}}^R}}p\left(s^{\prime }\mathrm{,}g\right)\rho \left(s^{\prime }\mathrm{,}g\right)}\le t\hfill \\ \hfill & {\displaystyle \sum _{s\mathrm{,}g}{N}_g}p\left(s\mathrm{,}g\right)c\left(s\mathrm{,}g\right)\le B\hfill \\ \hfill & {\displaystyle \sum _{s\in {\mathcal{S}}^R}}{N}_{g}p\left(s\mathrm{,}g\right)\rho \left(s\mathrm{,}g\right)\ge R_g\mathrm{,}\forall g\in \mathcal{G}\hfill \\ \hfill & \frac{{\displaystyle \sum _{s\in {\mathcal{S}}^R}}p\left(s\mathrm{,}g\right)\rho \left(s\mathrm{,}g\right)D\left(s\mathrm{,}g\right)}{{\displaystyle \sum _{s\in {\mathcal{S}}^R}}p\left(s\mathrm{,}g\right)\rho \left(s\mathrm{,}g\right)}-\frac{{\displaystyle \sum _{s\in {\mathcal{S}}^R}}p\left(s\mathrm{,}h\right)\rho \left(s\mathrm{,}h\right)D\left(s\mathrm{,}h\right)}{{\displaystyle \sum _{s\in {\mathcal{S}}^R}}p\left(s\mathrm{,}h\right)\rho \left(s\mathrm{,}h\right)}\le M\hfill \\ \hfill & {\displaystyle \sum _{s\mathrm{,}g}{N}_g}p\left(s\mathrm{,}g\right)\le S_{\text{max}}\hfill \\ \hfill & 0\le p\left(s\mathrm{,}g\right)\le \mathrm{1,}\forall s\in \mathcal{S}\mathrm{,}g\in \mathcal{G}\hfill \\ \hfill & {\displaystyle \sum _{s\in \mathcal{S}}p\left(s\mathrm{,}g\right)}=1,\forall g\in \mathcal{G}\hfill \\ \hfill & {\displaystyle \sum _{s\in {\mathcal{S}}^R}}p\left(s\mathrm{,}g\right)\text{>}0,\forall g\in \mathcal{G}\hfill \\ \hfill & 0\le t\mathrm{.}\hfill \end{array}(3.2)$$

Pour résoudre le problème linéaire, nous utilisons la méthode du simplexe disponible en R dans le module $boot.$ Notre algorithme proposé en deux étapes traite donc (3.1) dans la première étape. $x_{\text{LP}}^{*}$ dénote la solution optimale obtenue dans la PL. Dans la deuxième étape, la solution  $x_{\text{LP}}^{*}$ est soumise à un algorithme d’optimisation non linéaire comme point de départ afin de résoudre (3.2). À cette étape, nous utilisons les algorithmes non linéaires disponibles dans NLOPT (voir Johnson 2013 ), une bibliothèque de source ouverte pour l’optimisation non linéaire qui peut être appelée à partir de R dans le module  $nloptr.$ La deuxième étape du problème non linéaire non convexe de l’algorithme est exécutée seulement si le budget minimal requis trouvé à la première étape de la PL est plus petit ou égal au budget  $B$ disponible. Si le budget minimal est plus grand, il n’y a pas de solution possible au problème d’optimisation.

Étant donné que la performance de ces algorithmes dépend du problème, nous avons choisi de combiner deux algorithmes locaux de recherche afin d’accroître la vitesse de convergence. Des algorithmes d’optimisation globale sont disponibles dans la bibliothèque NLOPT, mais leur performance dans la résolution de notre problème était considérablement inférieure à celle des algorithmes d’optimisation locale sélectionnés. Les deux algorithmes de recherche locale sélectionnés sont COBYLA (Constrained Optimization by Linear Approximations), proposé par Powell (1998) (voir Roy 2007 pour une mise en œuvre en $\mathcal{C})$ et l’algorithme lagrangien augmenté AUGLAG, décrit dans Conn, Gould et Toint (1991) et Birgin et Martinez (2008) . La méthode COBYLA construit des approximations linéaires successives de la fonction d’objectif et des contraintes au moyen d’un simplexe de $n+1$  points (en $n$  dimensions), et optimise ces approximations dans une région de confiance à chaque étape. La méthode AUGLAG combine la fonction d’objectif et les contraintes non linéaires en une seule fonction, c’est‑à‑dire l’objectif en plus d’une pénalité pour toute contrainte non respectée. La fonction résultante est ensuite transférée à un autre algorithme d’optimisation en tant que problème sans contrainte. Si la solution de ce sous‑problème enfreint les contraintes, les pénalités sont accrues et le processus est répété. Le processus finit par converger vers la solution souhaitée, si elle existe.

Nous avons choisi d’utiliser la méthode MMA (Method of Moving Asymptotes, introduite dans Svanberg 2002), comme optimiseur local pour la méthode AUGLAG, en raison de sa performance dans nos expériences numériques. La stratégie sous‑tendant la méthode MMA est expliquée ci‑après. À chaque point $x_k,$ MMA forme une approximation locale à la fois convexe et séparable en utilisant le gradient de $f\left(x_k\right)$ et les fonctions de contrainte, ainsi qu’un terme de pénalité quadratique pour rendre les approximations prudentes, par exemple des limites supérieures pour les fonctions exactes. L’optimisation de l’approximation mène à un nouveau point candidat $x_{k+1}.$ Si les contraintes sont respectées, le processus continue à partir du nouveau point $x_{k+1}.$ Sinon, le terme de pénalité est accru et le processus est répété.

Nous utilisons deux algorithmes de recherche locaux, parce que la méthode AUGLAG est plus efficace pour trouver le voisinage de l’optimum global, tandis que la méthode COBYLA offre une plus grande exactitude dans la recherche de l’optimum. En conséquence, la solution optimale de la PL est d’abord soumise à AUGLAG, puis, après un certain nombre d’itérations, lorsque l’amélioration de la valeur objective est inférieure à un seuil spécifié, la solution de la méthode AUGLAG est traitée par la méthode COBYLA pour une plus grande exactitude. Pour notre étude de cas, étant donné les exigences en matière de précision des statistiques obtenues dans le cadre de l’enquête (0,5 %), les résultats sont considérés comme suffisamment exacts si la valeur objective obtenue se situe à moins de ${10}^{-4}$ de l’optimum global. Tout autre gain d’exactitude est complètement éliminé par la variation d’échantillonnage et l’exactitude des paramètres d’entrée mêmes. Les calculs peuvent prendre jusqu’à quelques heures. Comme il n’est pas nécessaire de résoudre le problème d’optimisation durant la collecte des données, cela ne posera pas de problèmes dans la pratique.

• Précédent
• Suivant