Problème d'optimisation niveau L3

Posté par Alexandroff Alexandroff

Bonjour,

Je me permets d'écrire N(x) pour la norme euclidienne d'un vecteur (je ne suis pas un champion de LaTeX...)

On considère le problème :

(P) Min ( 1/2*N(w)² + 1/(2h)*N(x)² )
    sous contraintes : Aw + x e

où : w est un vecteur de R^(m+1) ; A est une matrice n "croix" m+1 de réels donnée ; x un vecteur de R^n ; h un paramètre réel non nul donné ; et e un vecteur de "uns" de dimension n.

Ce programme fait l'objet d'un projet avec implémentation d'un algorithme d'activation de contraintes qui etc... je ne vous en demande pas tant. Mais on nous demande en préalable de montrer que w = A'z (où A' est la transposée de A) est solution de (P) si z est solution de :

(P') Min ( 1/2*N(A'z)² + h/2*N(z)² - z'e )
     s.c : z 0

Et là je sèche littéralement. Ne perd-on pas de l'information en trouvant une solution qui n'est pas fonction du vecteur x, alors que le critère à minimiser dans (P) est bien fonction de w ET x ?? D'autre part les KKT dans (P') nécessitent que la condition k (k= 1...n) soit saturée, donc que z_k = 0 et en les écrivant je n'arrive à rien de fameux...

Merci d'avance pour vos éventuels éclaircissements, et navré si ce problème est un peu pointu, et pour cette présentation barbare...

Posté par Tigweg Tigweg

Bonjour,

1) je ne suis pas sûr de bien saisir tes formules, en particulier les dénominateurs.As-tu bien parenthésé, ou bien

  est-il entièrement au dénominateur par exemple?



2) De plus, de quel ordre munis-tu ?

Est-ce l'ordre lexicographique, l'ordre-produit, ou autre?



3) Enfin, dans le cas où il s'agirait de l'ordre-produit, soit minimisant (P').


Pour vérifier que minimise (P), il faudrait déjà être certain qu'on a ce qui me fait penser que tu as peut-être oublié d'écrire l'une des hypothèses; en tout cas il me semble que sans hypothèse supplémentaire, on peut trouver une foule de contre-exemples.



Merci de préciser ces différents points.

Posté par Alexandroff Alexandroff

Bonsoir,

1. Normalement c'est bien parenthésé, 1/2 et 1/(2h) sont des facteurs que multiplient respectivement N²(w) et N²(x). Donc le gradient du critère a une forme assez simple normalement. Idem pour P'.

2. Ici l'équation Aw + x e est un système de n équations dans R, ie pour tout i = 1...n,

   a_i*w + x_i 1

où a_i est la ligne i de la matrice A et x_i la i-ème coordonnée de x. Donc pas besoin d'ordre sur ^n

3. Enfin, oui, j'ai peur qu'il manque une hypothèse, mais d'un autre côté le fait de réduire le problème à (P') présente un sérieux intérêt algorithmique. Ne peut-on pas montrer que si z est solution de (P'), alors à x vérifiant la contrainte de (P) fixé, w minimise (P)?
   Le vecteur x est en fait un vecteur d'erreurs (l'algorithme retourne une valeur approchée de la solution finale qui est un problème de clasification automatique), et on prendra en paramètre un petit "tol" en exigeant N²(x) < tol. Dans cette optique, ne peut-on pas minimiser "en deux fois", résolvant P' pour trouver w, puis P à w fixé pour minimiser x?

Vu la tête de notre cours l'implication z minimise P' implique w minimise P commence forcément par écrire les KKt de P'. On trouve que les multiplicateurs des conditions d'inégalité saturées (actives) sont égaux à 1, ce qui ne m'avance pas des masses, et pour les conditions non saturées j'arrive à une expression salasse qui ne me permet pas de généraliser.

Merci beaucoup pour ton aide, je continue à chercher...