Discussion :

[MPEG4]

Bonjour tout le monde
J'ai cherche sur la toile du web des schema numeriques de l'algorithme "interior point", mais sans succes

Le probleme que je dois resoudre est de la forme:
minimiser f(X) tel que Ax=y
x dans R^n, y dans R^m, m<<n

Quelqu'un pourrait-il me donner l'algorithme ou m'expliquer en quoi consiste la methode de Newton pour determiner la direction de descente dans l'algorithme.
Merci d'avance

[Zavonen]

Et f c'est quoi dans tout ça ???

[MPEG4]

Bonjour
f est la fonction norme
f(x)=||x||_p avec 0<p<=1
||x||_p=\sqrt( \sum (x_i)^p, p)

Dans le cas le plus simple p=1; Chercher à minimiser la norme l1 du vecteur X, ce qui revient à approcher la solution parcimonieuse du problème Ax=y par un programme convexe.

Merci d'avance

[Zavonen]

Les solutions de AX=Y forment une variété linéaire.
Le vecteur X cherché est tel que X=OM est orthogonal à cette variété. (projection orthogonale).

[MPEG4]

Les solutions de AX=Y forment une variété linéaire.
Le vecteur X cherché est tel que X=OM est orthogonal à cette variété. (projection orthogonale).

Le X que je cherche doit être la solution parcimonieuse "sparse" du problème Ax=y

Par parcimonieux, j'entends comme dans la littérature, que la majorité des coefficients de la solution deviennent insignifiants, voire nuls
En ce qui concerne la projection, elle n'est pas forcement orthogonale.
Un dictionnaire A= (A_1, A_2,..., A_n), A_i dans R^m où les fonctions de base A_i sont orthogonales entre elles est l'idéal, mais l'on peut avoir des dictionnaires sur-complets

Le problème à résoudre se formule comme suit
minimiser ||x||_p sous la contrainte Ax=y

Des suggestions d'algorithmes?

Merci d'avance

[pseudocode]

En ce qui concerne la projection, elle n'est pas forcement orthogonale.

C'est Lagrange qui va être déçu...

[MPEG4]

C'est Lagrange qui va être déçu...

Effectivement, reecrivant le probleme sous cette forme peut changer la done
mais vu du point de vu "Compressed sensing", le dictionnaire de representation (en effet, on utilise plutot dictionnaire que base pour eviter cette nuance d'orthogonalite) peut etre l'uninion de plusieurs bases, et ainsi, faillir a la condition d'orthogonalite. le plus important que que les fonctions de base soient incoherentes.

Quelqu'un pourrait en quoi consiste la methode de descnete de Newton et comment l'utiliser dans un algorithme de "interior point" pour resoudre un probleme linaire (ou convexe)?