La méthode du G.R.G, en Anglais Generalized Reduced Gradient est une méthode employée par le solveur d’excel dans le cas ou les contraintes ne sont pas linéaires.

Commençons par expliquer comment fonctionne l’algorithme du Gradient Réduit à travers un exemple linéaire pour ensuite ébaucher la méthode suivie dans le cas non linéaire.

Tout d’abord nous considérons un problème dont les contraintes sont des égalités.

La résolution numérique des problèmes d’optimisation à n variables sans contraintes nous a logiquement conduit à développer des algorithmes dans  ⁿ. Les méthodes employées étaient, pou la plupart, fondées sur la notion de direction admissible, ce qui leur conférait une certaine unité, aussi bien pour l’étude de la convergence que pour la mise en oeuvre. Il n’en est pas de même quand on aborde la résolution numérique des problèmes à n variables et à m contraintes(égalité ou inégalité). En effet, pour atteindre un point d’une variété à partir d’un point de départ quelconque, on peut soit essayer de rester tout le temps sur la variété à partir, de dimension n-m (méthode que l’on appellera méthodes admissibles), soit se déplacer dans l’espace de dimension n tout entier en direction du point cherché.

Intéressons nous à la méthode du gradient réduit à proprement parler :

Il s’agit d’une généralisation de la méthode qui consiste à utiliser les contraintes (linéaires) égalité pour éliminer les variables. Cette méthode s’apparente à l’algorithme du simplexe, car elle utilise les notions de variables de base et variables hors-base d’une façon analogue à ce dernier. Nous ne la présenterons brièvement que dans le cas de contraintes linéaires, la généralisation aux contraintes non-linéaires étant assez délicate dans sa mise en oeuvre.

On considère le problème :

Min_{u³ 0}(J(u)) sous la contrainte Au=b,

avec uÎ Â ⁿ, AÎ Â ^{n* m}, bÎ Â ^m , et J une fonctionnelle deux fois continûment différenciable. Les contraintes, ainsi formulées sont analogues à celle de la programmation linéaire. Nous ferons une hypothèse dite de non-dégénérescence : toute famille de m colonnes de A est linéairement indépendante et aucune solution admissible de m composantes n’a plus de n-m composantes nulles. Etant donné une solution admissible u, on décompose u en deux sous-vecteurs v et w de telle manière que v contienne m composantes strictement positives et w contiennent les autres composantes (positives ou nulles). On dira que v représente en fait les variables de base, et w les variables hors-base. Pour simplifier, on supposera que v contient en fait les m premières composantes de u. Avec ces conventions et hypothèses, on peut écrire le problème sous la forme :

Min_u³ 0,v³ 0(J(u,v)) sous Bv + Nw = b,

Avec la définition A = [Bê N]. L’équation admissible Bv + Nw = b permet d’écrire :

v = v(w) = B^-1(b-Nw)>0, ce qui donne l’idée de reformuler le problème sous la forme

Min_{w³ 0} J(B^-1(b-Nw),w) sous v(w) = B^-1(b-Nw)³ 0.

Introduisons maintenant le gradient (dit " réduit ")associé à ce nouveau problème. Il a pour expression :

Grad_rJ = Grad_wJ(v(w),w) - Grad_vJ(v(w),w) B^-1N.

La direction admissible que l’on utilise pour se déplacer est l’opposé de ce gradient réduit. On descend le long de cette direction (w® w-a .grad_rJ) en préservant la positivité de v(w), jusqu’à ce qu’une composante de v(w) devienne nulle. Cette composante quittera alors v et rejoindra w à l’itération suivante. De même, d’après l’hypothèse de non-dégénérescence, une composante strictement positive de w-a .grad_rJ pourra rejoindre les variables de base(c’est-à-dire les composantes de v).

Notons qu’il est impossible d’adapter des algorithmes de type gradient conjugué au gradient réduit, ce qui rend cette méthode très performante.