2. L’approche d’ajustement minimal

Jeroen Pannekoek et Li-Chun Zhang

Précédent | Suivant

2.1 Le problème d’optimisation

Nous proposons de résoudre le problème de cohérence décrit plus haut en ajustant les variables libres simultanément et aussi peu que possible, de manière à ce que toutes les règles de vérification soient satisfaites. Représentons la partie ajustable de l’enregistrement avant l’ajustement par le vecteur $x_0$ de dimension $J$ et après l’ajustement, par le vecteur $\tilde{x}$ de dimension $J$ correspondant. Le problème d’optimisation peut être formulé comme suit :

$$\begin{array}{lll}\tilde{x}\hfill & =\hfill & \arg \underset{x}{\min }D\left(x,x_0\right)\hfill \\ \text{s}\text{.c}\text{.}\hfill & \hfill & A\tilde{x}\le b,\hfill \end{array}(2.1)$$

où $D\left(x\mathrm{,}{x}_0\right)$ est une fonction mesurant la distance (ou divergence) entre $x$ et $x_0,$ et $A$ est la matrice comptable de dimensions $K\times J$ associée aux $K$ contraintes sur $\tilde{x}$ données en (1.1). Nous considérerons différentes fonctions $D$ à la section 2.2.

Les conditions pour une solution du problème de minimisation (2.1) peuvent être trouvées en inspectant le lagrangien pour ce problème, lequel peut s’écrire sous la forme

$$L\left(x\mathrm{,}\alpha \right)=D\left(x\mathrm{,}{x}_0\right)+{\alpha }^T\left(Ax-b\right)(2.2)$$

où $\alpha$ est un vecteur de dimension $K$ de multiplicateurs de Lagrange, ou variables duales, avec composantes ${\alpha }_k,$ une pour chacune des $K$ contraintes, et $a_k$ est la $k^{\text{e}}$ ligne (correspondant à la contrainte  $k)$ de la matrice comptable $A_{K\times J}.$ Notons qu’une contrainte de non-négativité additionnelle doit être appliquée à chaque ${\alpha }_k$ correspondant à une contrainte d’inégalité, mais non aux ${\alpha }_k$ des contraintes d’égalité.

La théorie de l’optimisation montre bien que, pour une fonction convexe $D\left(x\mathrm{,}{x}_0\right)$ et des contraintes linéaires, la solution de (2.1) est donnée par les vecteurs $\tilde{x}\mathrm{,}\tilde{\alpha }$ qui satisfont ce qu’il est convenu d’appeler les conditions de Karush-Kuhn-Tucker (KKT) (voir, par exemple, Luenberger 1984; Boyd et Vandenberghe 2004). L’une d’elles est que le gradient du lagrangien en ce qui concerne $x$ est nul quand il est évalué à $\tilde{x}\mathrm{,}\tilde{\alpha },$ c’est-à-dire

$${L^{\prime }}_{x_j}\left(\tilde{x}\mathrm{,}\tilde{\alpha }\right)={D^{\prime }}_{x_j}\left(\tilde{x}\mathrm{,}{x}_0\right)+{\displaystyle \sum _k{a}_{kj}{\tilde{\alpha }}_k}=0,(2.3)$$

où $a_{kj}$ est l’élément $\left(k\mathrm{,}j\right)$ de $A,$ et ${L^{\prime }}_{x_j}\left(\tilde{x}\mathrm{,}\tilde{\alpha }\right),$ le gradient de $L$ en ce qui concerne $x_j$ évalué à $\tilde{x}$ et $\tilde{\alpha },$ et ${D^{\prime }}_{x_j},$ celui de $D.$ L’examen de (2.3) montre comment divers choix de $D$ mènent à différentes solutions du problème d’ajustement, auxquelles nous donnons le nom de modèles d’ajustement.

2.2 Fonctions de distance et modèles d’ajustement

Une fonction de distance d’usage très répandu dans de nombreux domaines de la statistique est la fonction des moindres carrés pondérés (MCP) donnée par $D\left(x\mathrm{,}{x}_0\right)=1/2{\left(x-x_0\right)}^{T}W\left(x-x_0\right),$ où $W$ est une matrice diagonale dont les éléments diagonaux sont $w_j,$ pour $j=1,\mathrm{...},J.$ Nous obtenons alors, à partir de (2.3), le modèle d’ajustement

$${\tilde{x}}_j=x_{\mathrm{0,}j}-\frac{1}{w_j}{\displaystyle \sum _k{a}_{kj}{\tilde{\alpha }}_k}\mathrm{.}(2.4)$$

Le critère MCP aboutit donc à des ajustements additifs : l’ajustement total de la valeur initiale $x_{\mathrm{0,}j}$ est égal à la somme pondérée des ajustements qui correspondent à chacune des $K$ contraintes. L’ajustement dû à la $k^{\text{e}}$ contrainte dépend des éléments suivants :

• le paramètre d’ajustement (c’est-à-dire la variable duale) ${\tilde{\alpha }}_k$ qui décrit la grandeur de l’ajustement. Une plus petite valeur de ${\tilde{\alpha }}_k$ (en valeur absolue si $k$ désigne une contrainte d’égalité) correspond à un plus petit ajustement; une valeur nulle de ${\tilde{\alpha }}_k$ signifie qu’aucun ajustement dû à la contrainte en question n’a lieu;

• la constante $a_{kj}$ (c’est-à-dire un élément de la matrice comptable) qui décrit la direction et la grandeur de l’ajustement de la variable $j.$ Souvent, $a_{kj}$ vaut 1, -1 ou 0 et décrit alors si $x_{\mathrm{0,}j}$ est ajustée par ${\tilde{\alpha }}_k,-{\tilde{\alpha }}_k$ ou ne l’est pas du tout;

• le poids $w_j:$ les variables dont les poids sont élevés sont moins ajustées que celles dont les poids sont faibles. Le cas particulier de $w_j\equiv 1$ donne le critère des moindres carrés ordinaires (MCO), où la quantité d’ajustement due à chaque contrainte est la même pour toutes les variables pertinentes.

Un choix particulier des poids est $w_j=1/x_{\mathrm{0,}j},$ pour $j=1,\mathrm{...},J,$ auquel cas les carrés des ajustements relatifs sont minimisés, et une grande valeur initiale (c’est-à-dire $x_{\mathrm{0,}j})$ fait l’objet d’un plus grand ajustement qu’une valeur plus petite en valeur absolue. En divisant (2.4) par $x_{\mathrm{0,}j},$ nous obtenons

$$\frac{{\tilde{x}}_j}{x_{\mathrm{0,}j}}=1-{\displaystyle \sum _k{a}_{kj}{\tilde{\alpha }}_k}\mathrm{,}(2.5)$$

qui est un modèle d’ajustement additif pour le ratio entre les valeurs ajustée et non ajustée. On notera qu’il s’agit du développement en série de Taylor d’ordre un (c’est-à-dire autour de 0 pour tous les ${\tilde{\alpha }}_k)$ de l’ajustement multiplicatif donné par

$$\frac{{\tilde{x}}_j}{x_{\mathrm{0,}j}}={\displaystyle \prod _k}\left(1-a_{kj}{\tilde{\alpha }}_k\right).(2.6)$$

Partant de (2.5) nous voyons que ${\tilde{\alpha }}_k$ détermine la variation relative de la valeur initiale $x_{\mathrm{0,}j}$ à la valeur ajustée ${\tilde{x}}_j,$ qui en valeur absolue est habituellement beaucoup plus petite que l’unité. Par exemple, ${\tilde{\alpha }}_k=\pm \text{0,2}$ implique un ajustement de $\left|20\%\right|$ de $x_{\mathrm{0,}j}$ si $a_{kj}=\pm 1,$ ce qui est grand en pratique. Les produits des ${\tilde{\alpha }}_k$ sont par conséquent souvent beaucoup plus petits que les ${\alpha }_k$ proprement dits, auquel cas (2.5) devient une bonne approximation de (2.6), et l’on peut considérer l’ajustement MCP comme étant donné approximativement par le produit de tous les ajustements multiplicatifs propres aux contraintes.

L’ajustement multiplicatif par (2.6) peut changer le signe de $x_{\mathrm{0,}j}$ si $a_{kj}{\tilde{\alpha }}_k>1$ pour une certaine unité $k.$ Les ajustements multiplicatifs qui préservent le signe de la valeur initiale $x_{\mathrm{0,}j}$ peuvent être obtenus en utilisant la mesure de divergence de Kullback-Leibler (KL) (qui n’est pas formellement une fonction de distance) donnée par $D_{KL}={\displaystyle {\sum }_j{x}_j\left(\ln x_j-\ln x_{\mathrm{0,}j}-1\right)}.$ Nous avons alors, à partir de (2.3), le modèle d’ajustement

$${\tilde{x}}_j=x_{\mathrm{0,}j}{\displaystyle \prod _k}\exp \left(-a_{kj}{\tilde{\alpha }}_k\right)\mathrm{.}(2.7)$$

L’ajustement dû à la contrainte $k$ est égal à $1$ si $a_{kj}$ vaut $0$ (c’est-à-dire aucun ajustement), il est égal à $\exp \left({\tilde{\alpha }}_k\right)$ si $a_{kj}$ vaut $1$, et il est égal à $1/\exp \left({\tilde{\alpha }}_k\right)$ si $a_{ik}$ vaut $-1.$ Puisque $1-a_{kj}{\tilde{\alpha }}_k$ est l’approximation d’ordre un de $\exp \left(-a_{kj}{\tilde{\alpha }}_k\right)$ autour de ${\tilde{\alpha }}_k=0$ si $a_{kj}\pm 1,$ on peut s’attendre à ce que les critères MCP et KL donnent des ajustements similaires à condition que ceux-ci soient petits ou moyens.

2.3 Méthodes de résolution du problème d’ajustement minimal

Le problème général d’optimisation convexe (2.1) peut être résolu explicitement si la fonction d’objectif est celle des moindres carrés pondérés et qu’il existe seulement des contraintes d’égalité. Dans ce cas, le lagrangien est $L\left(x\mathrm{,}\alpha \right)=1/2{\left(x-x_0\right)}^{T}W\left(x-x_0\right)+{\alpha }^T\left(Ax-b\right),$ et les équations qu’il faut résoudre sont

$${L^{\prime }}_x\left(x\mathrm{,}\alpha \right)=W\left(x-x_0\right)+A^T\alpha =0(2.8)$$

$${L^{\prime }}_{\alpha }\left(x\mathrm{,}\alpha \right)=Ax-b=0.(2.9)$$

En résolvant (2.8) pour trouver $x$ et en substituant le résultat dans (2.9), nous obtenons

$$\tilde{\alpha }={\left(A{W}^{-1}{A}^T\right)}^{-1}\left(A{x}_0-b\right)$$

et alors, par substitution inverse dans (2.8), nous obtenons explicitement

$$\tilde{x}=x_0-W^{-1}{A}^T{\left(A{W}^{-1}{A}^T\right)}^{-1}\left(A{x}_0-b\right).(2.10)$$

Pour d’autres fonctions d’objectif et avec des contraintes d’inégalité en général, il n’existe pas de solution explicite du problème (2.1). Cependant, de nombreux algorithmes en accès libre ou commerciaux sont disponibles pour résoudre le problème d’optimisation convexe. Pour l’application décrite dans le présent article, nous avons utilisé le langage de programmation R et appliqué le Successive Projection Algorithm (SPA) (ou row action algorithm) $–$ voir par exemple, Censor et Zenios (1997). Le SPA est un algorithme itératif qui utilise les contraintes (lignes de la matrice comptable) une à une. En une itération, le vecteur $\text{x}$ est ajusté séquentiellement à chacune des contraintes. L’opération d’ajustement avec une seule contrainte requiert uniquement la mise à jour des éléments du vecteur $\text{x}$ qui interviennent dans cette contrainte (correspondant aux éléments non nuls de la ligne traitée de la matrice comptable). Une fois que toutes les contraintes ont été traitées, l’itération s’achève et la suivante commence. Pour le critère MCP, il existe un module (ou package) R qui met en œuvre l’algorithme SPA et est conçu spécialement pour le problème d’ajustement (van der Loo 2012).

2.4 Retour à l’exemple

Le tableau 2.1 montre les ajustements minimaux apportés à l’enregistrement du tableau 1.1 en utilisant les critères MCO, MCP et KL, respectivement. Les valeurs observées sont traitées comme fixes et inscrites en caractères gras, et les valeurs imputées sont ajustables. Pour la méthode MCP, nous utilisons $w_j=1/x_{0,j},$ ce qui donne des résultats égaux à ceux produits par le critère KL jusqu’à la première décimale.

Pour les deux schémas de réponse, la procédure d’ajustement MCO donne pour la variable Autre chiffre d’affaires une valeur négative qui n’est pas acceptable (tableau 2.1). Quand la procédure MCO est réexécutée avec une contrainte de non-négativité pour la variable Autre chiffre d’affaires, le résultat est simplement zéro pour cette variable et 950 pour la variable Chiffre d’affaires principal en raison de la contrainte $a2.$ Sans la contrainte de non-négativité, les ajustements MCO sont de -40 pour $x_3$ et $x_4,$ et de -16 pour $x_6$ et $x_7,$ c’est-à-dire le même ajustement pour chaque paire de variables figurant dans la même contrainte. La variable Total des coûts $\left(x_8\right)$ fait partie de deux contraintes et son ajustement total comprend deux composantes additives. Une composante est due à la contrainte $a1,$ et l’autre, à $a3.$ Pour le schéma de réponse (I), la première composante est -48 et la deuxième composante est 16, et leur somme est égale à -32 dans le tableau 2.1.

Tableau 2.1
Imputation et ajustement de l’enregistrement d’entreprise du tableau 1.1. ID : Imputation partielle par donneur sans ajustement; MCO : distance selon les moindres carrés ordinaires; MCP : distance selon les moindres carrés pondérés; KL : mesure de divergence de Kullback-Leibler; RG : ajustement par le ratio généralisé
Sommaire du tableau
Le tableau montre les résultats de Imputation et ajustement de l’enregistrement d’entreprise du tableau 1.1. ID : Imputation partielle par donneur sans ajustement; MCO : distance selon les moindres carrés ordinaires; MCP : distance selon les moindres carrés pondérés; KL : mesure de divergence de Kullback-Leibler; RG : ajustement par le ratio généralisé. Les données sont présentées selon Variable (titres de rangée) et Nom, Réponse (I) et Réponse (II)(figurant comme en-tête de colonne).

Variable	Nom	Réponse (I)				Réponse (II)
		ID	MCO	MCP/KL	RG	ID	MCO	MCP/KL	RG
${\text{x}}_1$	Profit	330	282	291	304	330	260	249	239
${\text{x}}_2$	Effectif	20	20	20	18	25	25	25	25
${\text{x}}_3$	Chiffre d’affaires principal	1 000	960	922	922	1 000	960	922	921
${\text{x}}_4$	Autre chiffre d’affaires	30	-10	28	28	30	-10	28	29
${\text{x}}_5$	Chiffre d’affaires	950	950	950	950	950	950	950	950
${\text{x}}_6$	Rémunération	500	484	470	461	550	550	550	550
${\text{x}}_7$	Autres coûts	200	184	188	184	200	140	151	161
${\text{x}}_8$	Total des coûts	700	668	658	646	700	690	701	711

Les ajustements MCP/KL sont plus grands, en valeur absolue, pour les grandes valeurs imputées que pour les valeurs plus petites. En particulier, l’ajustement pour Autre chiffre d’affaires n’est que de -2,3, de sorte qu’aucune valeur ajustée négative n’est produite dans ce cas, tandis que l’ajustement pour Chiffre d’affaires principal est de -77,7. On peut observer la nature multiplicative de ces ajustements car le facteur d’ajustement pour ces variables est égal à 0,92 (pour les deux schémas de réponse). Le facteur d’ajustement pour les variables Rémunération et Autres coûts sous le schéma de réponse (I) est égal à 0,94 dans les deux cas parce que ces variables figurent dans la même contrainte $a3,$ de sorte que le ratio de leurs valeurs initiales n’est pas modifié par cet ajustement. Cependant, le ratio initial de chacune de ces variables à la variable Total des coûts n’est pas préservé, parce que le total des coûts possède un signe différent dans la contrainte $a3$ et, de surcroît, il fait aussi partie de la contrainte $a1,$ si bien qu’il est sujet à deux facteurs d’ajustement.

Précédent | Suivant