|
Pour
modéliser les stratégies mises en œuvre par un ensemble
d'entreprises en situation de concurrence, on peut tout
d'abord envisager le cas de la concurrence "parfaite",
où les acteurs sont nombreux et de même envergure. La
résolution repose sur le formalisme de base des jeux sans
coopération (équilibre de Nash). Dans la réalité, cette
représentation est souvent peu adaptée, en particulier
dans le cas d'un processus de libéralisation, où généralement
les différents acteurs ne sont pas de même nature et sont
peu nombreux. Typiquement, l'un d'entre eux dispose d'une
avance substantielle (avance technologique, capacité de
production, clientèle héritée d'une position de monopole,
etc.) et ses choix modifient les possibilités des autres
acteurs.
On
est donc en présence d'un leader ou pionnier et de suiveurs,
c'est-à-dire dans le cadre d'un jeu de type Stackelberg
(ou leader-follower), dont la résolution reflète l'aspect
asymétrique et séquentiel du modèle : à décision du pionnier
fixée, les suiveurs optimisent leurs décisions, puis la
décision optimale du pionnier est déduite d'un programme
d'optimisation avec contraintes pour les réponses des
suiveurs. D'un point de vue d'optimisation, on a donc
a priori affaire à un problème bi-niveaux. Sous des hypothèses
assez faibles, il est cependant possible de se ramener
à une classe de problèmes dits à contraintes de complémentarité
(ou d'équilibre), en remplaçant les problèmes du niveau
bas (ceux des suiveurs) par leurs conditions d'optimalité.
On nomme ces problèmes "Mathematical Problems with Equilibrium
Constraints" ou encore MPEC.
Le
terme de complémentarité qualifie la nature de ces contraintes
qui imposent qu’une décision des suiveurs n’est prise
que pour un prix marginal inférieur à une certaine valeur.
Si on considère le cas où le problème de plus bas niveau
est un problème de production, cette complémentarité correspond
au fait que l’un des suiveurs ne produit que si le prix
marginal de production est inférieur à un certain plafond
et modélise le choix offert au suiveur (produire ou non).
De façon générique, ces contraintes sont de la forme :
La
contrainte de complémentarité cristallise la difficulté,
tant théorique (modéliser un choix) que numérique du problème.
Ce type de contrainte conduit en effet à un problème où
la qualification "classique" des contraintes (Mangasarian-Fromovitz)
n'est assurée en aucun point réalisable. Ceci conduit
les linéarisations issues du lagrangien à approcher de
façon inappropriée le problème initial. En particulier
pour les méthodes de type programmation quadratique successive,
les sous-problèmes quadratiques peuvent être inadéquats
face au problème initial, même lorsqu'on est proche d'un
point stationnaire. Une autre source de difficultés numériques
provient des gradients des contraintes, dont l'indépendance
linéaire n'est pas vérifiée.
Les
conditions favorables de qualification des contraintes
n'étant pas respectées, le fonctionnement même des algorithmes
standards d'optimisation non linéaire est remis en cause.
Cependant, la structure particulière des problèmes permet
de formuler des conditions de qualification spécifiques
et de modifier les algorithmes pour la prise en compte
explicite et adaptée de ces contraintes de complémentarité.
Pour les méthodes de points intérieurs deux optiques sont
envisageables : relâcher la contrainte de complémentarité
(1) en introduisant, par exemple, un paramètre ε
que l’on fait tendre vers 0 :
ou
bien employer une technique de pénalisation exacte qui
intègre cette contrainte à la fonction objectif (cf. [2]).
Certains solveurs de programmation non linéaire et certains
modeleurs intègrent de tels traitements. C'est notamment
le cas de Knitro, qui offre depuis sa version 5 cette
fonctionnalité à la fois à travers son interface Ampl
et son interface C.
Vous
trouverez ici un exemple de
problème de fiscalité qui illustre le comportement
de l’algorithme de points intérieurs de Knitro avec et
sans l’option MPEC. Cet
exemple simple illustre une forme de concurrence entre
un Etat (pionnier) qui choisit un niveau de fiscalité
pour assurer un revenu minimum et des consommateurs (suiveurs)
dont le comportement est modifié par le niveau de fiscalité.
Les suiveurs cherchent un équilibre entre leurs différents
loisirs et consommations et leur coût. Il s’agit d’un
exemple académique avec deux consommateurs. Voici les
résultats
obtenus par les deux versions de l’algorithme de points
intérieurs de Knitro.
[1]
Leader-Follower Equilibria for Electric Power and NOx
Allowances Markets, Y. Chen, B. Hobbs, S. Leyffer,
and T. Munson, ANL/MCS-P1191-0804, August 2004.
[2] Interior Methods for Mathematical Programs with
Complementarity Constraints, S. Leyffer, G. Lopez-Calva
and J. Nocedal, Report OTC 2004-10, July 2005.
|
