Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 07-06-2018 01:49:37

cossin
Membre
Inscription : 07-06-2018
Messages : 4

d'un problème d'optimisation standard à un problème de EIGENVALUES

Bonjour les mathématiciens,

Je suis en plein apprentissage des méthodes d'optimisation, je bloque dans la reformulation d'un simple problème d'optimisation standard en un problème de calcul de eigenvalue.

si seulement je trouve l’explication du passage de la formule 2 à la formule 3 puis 4!! tout est ici

Je vous remercie pour votre aide.

Hors ligne

#2 07-06-2018 12:47:20

D_john
Invité

Re : d'un problème d'optimisation standard à un problème de EIGENVALUES

Salut,

Je ne comprends pas vraiment ce qui te bloque car ce n’est qu’une suite de définitions et de changements de variables jusqu’à (4), après je n’ai pas lu...
Donc, au risque de répondre à côté, je détaille le seul point qui me semble nécessiter une petite attention : le passage W → Z avec :
[tex]W = \left[w_{1}, \cdots , w_{m} \right]^{T}\qquad
et
\qquad Z = \left[z_{1}, \cdots , z_{m} \right]^{T}[/tex]

Pour des scalaires z et w, on a :
[tex]z = 2.w - 1\quad\Longrightarrow\quad w = \frac{z+1}{2}[/tex]
et
[tex] w\in\left\{0,1 \right\}\quad\Longrightarrow\quad z \in\left\{-1,1 \right\}[/tex]

Concernant la contraint, si on note le vecteur colonne de m composantes égales à 1 :
[tex]I_{m} = \left[ 1,\cdots, 1\right]^{T}[/tex]
on obtient la contrainte par projection :
[tex] W^{T}. I_{m} = k \qquad \left( k \le m\right)[/tex]
et de même :
[tex]Z = 2.W - I_{m}\qquad\Longrightarrow\qquad Z^{T}.I_{m} = 2.W^{T}.I_{m} - \left[ I_{m}\right]^{T}.I_{m}[/tex]
et finalement :
[tex] W^{T}. I_{m} = k \qquad\Longleftrightarrow\qquad Z^{T}. I_{m} = 2.k – m[/tex]

Je ne crois pas utile de réécrire les formules à minimiser en W et Z...

Pour obtenir (4), on ajoute une composante 1 en tête de Z, etc.

A+ si d'autres questions.

#3 07-06-2018 23:12:25

cossin
Membre
Inscription : 07-06-2018
Messages : 4

Re : d'un problème d'optimisation standard à un problème de EIGENVALUES

Mercii bcp @D_john pour ta réponse, au fait j'avais déjà compris ce que tu viens de m'expliquer. Donc je tiens à m'excuser je viens de me rendre compte que je me suis très mal exprimé par rapport à ce que je n'ai pas compris.

Alors, je reformule: pourquoi il a fallut la reformulation et la relaxation pour diminuer la complexité du calcule? (au contraire dans mon cas de la formule 2 à 4 je suis passée d'une matrice m x m  a une matrice m+1 x m+1), donc qu'est ce qui permet la réduction de la complexité? pourquoi le changement de variable est t-il fait?

autre chose, c'est remarquable que de 6 à 7 on est passé d'un problème de minimisation à un problème de maximisation!! comment cela est t-il fait?

je te remercie d'avance pour ton attention et ta réponse.

au plaisir de te relire.

D_john a écrit :

Salut,

Je ne comprends pas vraiment ce qui te bloque car ce n’est qu’une suite de définitions et de changements de variables jusqu’à (4), après je n’ai pas lu...
Donc, au risque de répondre à côté, je détaille le seul point qui me semble nécessiter une petite attention : le passage W → Z avec :
[tex]W = \left[w_{1}, \cdots , w_{m} \right]^{T}\qquad
et
\qquad Z = \left[z_{1}, \cdots , z_{m} \right]^{T}[/tex]

Pour des scalaires z et w, on a :
[tex]z = 2.w - 1\quad\Longrightarrow\quad w = \frac{z+1}{2}[/tex]
et
[tex] w\in\left\{0,1 \right\}\quad\Longrightarrow\quad z \in\left\{-1,1 \right\}[/tex]

Concernant la contraint, si on note le vecteur colonne de m composantes égales à 1 :
[tex]I_{m} = \left[ 1,\cdots, 1\right]^{T}[/tex]
on obtient la contrainte par projection :
[tex] W^{T}. I_{m} = k \qquad \left( k \le m\right)[/tex]
et de même :
[tex]Z = 2.W - I_{m}\qquad\Longrightarrow\qquad Z^{T}.I_{m} = 2.W^{T}.I_{m} - \left[ I_{m}\right]^{T}.I_{m}[/tex]
et finalement :
[tex] W^{T}. I_{m} = k \qquad\Longleftrightarrow\qquad Z^{T}. I_{m} = 2.k – m[/tex]

Je ne crois pas utile de réécrire les formules à minimiser en W et Z...

Pour obtenir (4), on ajoute une composante 1 en tête de Z, etc.

A+ si d'autres questions.

Dernière modification par cossin (08-06-2018 00:15:49)

Hors ligne

#4 17-06-2018 23:00:59

D_john
Invité

Re : d'un problème d'optimisation standard à un problème de EIGENVALUES

Salut,

Bon, je déterre... pour te proposer ce raccoucis qui va peut-être t’éclairer si c’est encore nécessaire.
Mais c’est au feeling, donc sans garantie.

Comme écrit dans la publication, la seule astuce de relaxation est de passer d’un domaine discret (à explorer en combinatoire par la force brute !) à un domaine continu. Sur ce dernier domaine, hypersphérique, la recherche d’une seule valeur propre (la plus grande) + la direction propre associée, suffit à réduire la complexité du problème. Si j’ai bien compris, c’est le but des reformulations successives mentionné aussi dans le titre.

Le passage de (6) à (7) est assez évident. Dans (6), on cherche l’argument du minimum d’une fonction objectif F(v) réelle. On passe à (7) par ‘compactage matriciel’ des contraintes linéaires mais surtout, on retranche F(v) d’une constante alpha supérieure aux valeurs propres de G. Le changement de signe de F(v) pour reformuler une nouvelle fonction objectif H(v) conduit alors à rechercher l’argument du maximum de H(v). Si je passe les contraintes à la trappe, cet argument du max correspond forcément à la plus grande des valeurs propres de la matrice de la forme quadratique H(v).
Or il existe justement un algorithme (voir réf. [20]) qui sait résoudre par approximations successives...
A toi de voir.

#5 22-06-2018 21:47:55

cossin
Membre
Inscription : 07-06-2018
Messages : 4

Re : d'un problème d'optimisation standard à un problème de EIGENVALUES

Je vous remercie pour votre réponse. Je vois claire le choses et j'ai même bien compris pourquoi le changement de variable.

cependant, je n'arrive pas à trouver une explication de :  pourquoi la contrainte discrète fait que le problème soit NP-hard??

D_john a écrit :

Salut,

Bon, je déterre... pour te proposer ce raccoucis qui va peut-être t’éclairer si c’est encore nécessaire.
Mais c’est au feeling, donc sans garantie.

Comme écrit dans la publication, la seule astuce de relaxation est de passer d’un domaine discret (à explorer en combinatoire par la force brute !) à un domaine continu. Sur ce dernier domaine, hypersphérique, la recherche d’une seule valeur propre (la plus grande) + la direction propre associée, suffit à réduire la complexité du problème. Si j’ai bien compris, c’est le but des reformulations successives mentionné aussi dans le titre.

Le passage de (6) à (7) est assez évident. Dans (6), on cherche l’argument du minimum d’une fonction objectif F(v) réelle. On passe à (7) par ‘compactage matriciel’ des contraintes linéaires mais surtout, on retranche F(v) d’une constante alpha supérieure aux valeurs propres de G. Le changement de signe de F(v) pour reformuler une nouvelle fonction objectif H(v) conduit alors à rechercher l’argument du maximum de H(v). Si je passe les contraintes à la trappe, cet argument du max correspond forcément à la plus grande des valeurs propres de la matrice de la forme quadratique H(v).
Or il existe justement un algorithme (voir réf. [20]) qui sait résoudre par approximations successives...
A toi de voir.

Hors ligne

#6 23-06-2018 13:13:48

D_john
Invité

Re : d'un problème d'optimisation standard à un problème de EIGENVALUES

Hello,

Impossible de t'aider sur ce langage d'informatique théorique qui dépasse largement mes connaissances.
J'imagine que le temps nécessaire pour sélectionner un jeu optimal de k algorithmes de classification (parmi un ensemble de m algo. très grand) doit être énorme en raison des factorielles. Je fais donc confiance à la publication...
Maintenant, si tu veux vraiment des explications, il "suffit" de remonter à la source des publications par les références pertinentes des références pertinentes des références pertinentes... Oui, comme sur les wiki !
On appelait ça l'histoire du paquet de trombones autrefois... (Tu veux en prendre un et c'est tout le paquet qui vient !).

Alors bon courage.

#7 23-06-2018 18:21:37

cossin
Membre
Inscription : 07-06-2018
Messages : 4

Re : d'un problème d'optimisation standard à un problème de EIGENVALUES

Je te remercie infiniment pour ton temps et ton attention.

D_john a écrit :

Hello,

Impossible de t'aider sur ce langage d'informatique théorique qui dépasse largement mes connaissances.
J'imagine que le temps nécessaire pour sélectionner un jeu optimal de k algorithmes de classification (parmi un ensemble de m algo. très grand) doit être énorme en raison des factorielles. Je fais donc confiance à la publication...
Maintenant, si tu veux vraiment des explications, il "suffit" de remonter à la source des publications par les références pertinentes des références pertinentes des références pertinentes... Oui, comme sur les wiki !
On appelait ça l'histoire du paquet de trombones autrefois... (Tu veux en prendre un et c'est tout le paquet qui vient !).

Alors bon courage.

Hors ligne

Pied de page des forums