Maximisation d'une fonction non-linéaire
Répondre à la discussion
Affichage des résultats 1 à 10 sur 10

Maximisation d'une fonction non-linéaire



  1. #1
    invitebba29e66

    Maximisation d'une fonction non-linéaire


    ------

    [modif]
    à cause du mauvais affichage du latex, je vous envoie sur le site [url]http://les-mathematiques.u-strasbg.fr/phorum/read.php?f=2&i=317703&t=317703[\url] où j'ai aussi posté le problème.
    [\modif]

    Bonjour,

    j'ai un problème assez simple à poser mais je pense qu'il n'a pas de solution en algèbre linéaire. Et j'aimerais

    avoir des idées ou des algorithmes pour le résoudre.

    Je travaille avec des signaux à temps discret (des vecteurs horizontaux)

    Mon problème est le suivant:

    Un vecteur [TEX] \underline{m}[\TEX] de taille [TEX] L[\TEX], de norme unité, est utilisé pour créer un vecteur [TEX] \underline{r}[\TEX] de

    taille [TEX] L+R[\TEX] de la façon suivante :
    [TEX] \underline{r}[\TEX] est la somme pondérée de [TEX] \underline{m}[\TEX] et de sa version translatée de [TEX] R[\TEX] échantillons,

    soit:
    [TEX] \underline{r}[t] = \left\{ \begin{array}{l} c_1 \cdot \underline{m}[t] \mbox{ si } t < R \\ c_1 \cdot

    \underline{m}[t] + c_2 \cdot \underline{m}[t-R] \mbox{ si } R \le t \le L \\c_2\cdot \underline{m}[t-R] \mbox{ si

    } L < t \\ \end{array} \right. [\TEX]

    Je veux retrouver [TEX] \underline{m}[\TEX] à partir de la seule connaissance de [TEX] \underline{r}[\TEX] et des tailles [TEX] L[\TEX] et [TEX]

    R[\TEX].


    Où j'en suis dans le problème:

    J'étais parti sur la piste suivante: minimiser le critère d'erreur quadratique [TEX] \arg

    \min_{\underline{m},\underline {c}} \Vert\underline{r} - \underline{c} \cdot \underline{F}[\underline{m}] \Vert

    _2^2[\TEX], où [TEX] \underline{c} = [c1 c2][\TEX] et [TEX] \underline{F}[\underline{m}] = \left[ \begin{array}{l}

    T_0[\underline{m}]\\ T_R[\underline{m}] \end{array} \right][\TEX], avec [TEX] T_\tau[\TEX] la fonction de translation d'une

    paramètre [TEX] \tau[\TEX].

    En minimisant par rapport à [TEX] \underline{c}[\TEX], à [TEX] \underline{m}[\TEX] fixé, on arrive à [TEX] \underline{c} =

    \underline{r} \cdot \underline{F}^+[\underline{m}] = \underline{r} \cdot \cdot

    \underline{F}^T[\underline{m}](\underline{F}[\underline{m}] \cdot \underline{F}^T[\underline{m}])^{-1}[\TEX].


    Le critère à minimiser devient, à cet optimum pour [TEX] \underline{c}[\TEX]:
    [TEX] \arg \min_{\underline{m}} \Vert r\Vert _2^2 - \Vert\underline{c}\cdot \underline{F}[\underline{m}]\Vert _2^2[\TEX]
    soit
    [TEX] \arg \max_{\underline{m}} \underline{r} \cdot \underline{F}^T[\underline{m}] (\underline{F}[\underline{m}]

    \cdot \underline{F}^T[\underline{m}])^{-1} \cdot \underline{F}[\underline{m}] \cdot \underline{r}^T[\TEX]


    Comme [TEX] \underline{F}[\TEX] est une fonction linéaire, elle admet un adjoint et donc [TEX] \underline{r} \cdot

    \underline{F}^T[\underline{m}] = \underline{m} \cdot \underline{F}^{*T}[\underline{r}][\TEX].


    Si les lignes de [TEX] \underline{F}[\TEX] étaient orthogonales, le résultat est direct: [TEX] \underline{m}[\TEX] est un vecteur

    propre associé à la plus grande valeur propre de la matrice [TEX] \underline{F}^{*T}[\underline{r}] \cdot

    \underline{F}^{*}[\underline{r}][\TEX].

    Or ce n'est pas le cas, et on peut écrire le critère comme [TEX] \arg \max_{\underline{m}} \underline{m} \cdot

    \underline{F}^{*T}[\underline{r}] \cdot (\underline{F}[\underline{m}] \cdot \underline{F}^T[\underline{m}])^{-1}

    \cdot \underline{F}^*[\underline{r}] \cdot \underline{m}^T[\TEX], mais il reste toujours la matrice inverse, au

    milieu, qui dépend de [TEX] \underline{m}[\TEX]. J'ai essayé d'initialiser [TEX] \underline{m}[\TEX] aléatoirement, de fixer [TEX]

    (\underline{F}[\underline{m}] \cdot \underline{F}^T[\underline{m}])^{-1}[\TEX], et de mettre à jour [TEX] \underline{m}[\TEX],

    et on réitère, mais ça ne converge pas vers l'optimum.

    Une autre piste était d'orthogonaliser [TEX] \underline{F}[\underline{m}][\TEX], pour donner [TEX]

    \underline{G}[\underline{m}][\TEX]. Il s'agit alors de résoudre:
    [TEX] \arg \max_{\underline{m}} \underline{r} \cdot\underline{G}^T[\underline{m}] \cdot \underline{G}[\underline{m}]

    \cdot \underline{r}^T[\TEX].
    Le problème est que [TEX] \underline{G}[\underline{m}][\TEX] n'est pas linéaire, donc pas d'ajoint, donc pas de résolution

    par les valeurs propres.


    Merci beaucoup si vous avez une idée sur:
    - l'existence d'une solution analytique
    - une façon de converger vers l'optimum.

    -----

  2. #2
    Sylvestre

    Re : Maximisation d'une fonction non-linéaire

    Citation Envoyé par Gnouf Voir le message
    [modif]
    à cause du mauvais affichage du latex, je vous envoie sur le site [url]http://les-mathematiques.u-strasbg.fr/phorum/read.php?f=2&i=317703&t=317703[\url] où j'ai aussi posté le problème.
    [\modif]
    Salut
    Les balises latex sont à fermer par un / et non par un \.

  3. #3
    Gwyddon

    Re : Maximisation d'une fonction non-linéaire

    Salut,

    Je te conseille d'aller voir sur le forum test pour t'entraîner aux balises tex de ce forum

    Pour info, la fermeture d'une balise c'est [/tex], pas [\tex]

    EDIT: grillé par Sylvestre
    A quitté FuturaSciences. Merci de ne PAS me contacter par MP.

  4. #4
    invitebba29e66

    Re : Maximisation d'une fonction non-linéaire

    Quel âne...

    voilà le message bien écrit:


    Bonjour,

    j'ai un problème assez simple à poser mais je pense qu'il n'a pas de solution en algèbre linéaire. Et j'aimerais

    avoir des idées ou des algorithmes pour le résoudre.

    Je travaille avec des signaux à temps discret (des vecteurs horizontaux)

    Mon problème est le suivant:

    Un vecteur de taille , de norme unité, est utilisé pour créer un vecteur de

    taille de la façon suivante :
    est la somme pondérée de et de sa version translatée de échantillons,

    soit:


    Je veux retrouver à partir de la seule connaissance de et des tailles et .


    Où j'en suis dans le problème:

    J'étais parti sur la piste suivante: minimiser le critère d'erreur quadratique , où et , avec la fonction de translation d'un paramètre .

    En minimisant par rapport à , à fixé, on arrive à .

    Le critère à minimiser devient, à cet optimum pour :

    soit



    Comme est une fonction linéaire, elle admet un adjoint et donc .


    Si les lignes de étaient orthogonales, le résultat est direct: est un vecteur propre associé à la plus grande valeur propre de la matrice .

    Or ce n'est pas le cas, et on peut écrire le critère comme , mais il reste toujours la matrice inverse, au milieu, qui dépend de . J'ai essayé d'initialiser aléatoirement, de fixer , et de mettre à jour ,

    et on réitère, mais ça ne converge pas vers l'optimum.

    Une autre piste était d'orthogonaliser , pour donner . Il s'agit alors de résoudre:
    .
    Le problème est que n'est pas linéaire, donc pas d'ajoint, donc pas de résolution par les valeurs propres.


    Merci beaucoup si vous avez une idée sur:
    - l'existence d'une solution analytique
    - une façon de converger vers l'optimum.

  5. A voir en vidéo sur Futura
  6. #5
    Sylvestre

    Re : Maximisation d'une fonction non-linéaire

    Citation Envoyé par Gnouf Voir le message
    soit:


    Je veux retrouver à partir de la seule connaissance de et des tailles et .
    Je traduirais cela matriciellement de cette manière :


    où A est une matrice (L+R) par L. est la matrice identité de taille n par n et est la matrice nulle de taille n par m.

    La méthode des moindres carrés que tu as mis en place devrait te donner :


  7. #6
    invitebba29e66

    Re : Maximisation d'une fonction non-linéaire

    Eh oui, on est d'accord, si on connait et . Le problème est que je veux maximiser aussi par rapport à ces deux coefficients. Est en maximisant par rapport aux coefficients et au vecteur , à mon avis, c'est non-linéaire et ça ne peut pas se résoudre par une méthode linéaire comme les moindres carrés.

  8. #7
    Sylvestre

    Re : Maximisation d'une fonction non-linéaire

    Citation Envoyé par Gnouf Voir le message
    à mon avis, c'est non-linéaire et ça ne peut pas se résoudre par une méthode linéaire comme les moindres carrés.
    Ok, j'ai compris. J'ai fais quelques calculs et effectivement, c'est non linéaire. J'ai trouvé que les équations à résoudre sont :






    avec
    et .

    Les inconnues sont les composantes de m ainsi que c_1 et c_2. Nous exactement le bon nombre d'équations pour ce nombre d'inconnues. Il s'agit maintenant d'un problème quadratique dans , cela devrait être faisable (au moins numériquement).

  9. #8
    invitebba29e66

    Re : Maximisation d'une fonction non-linéaire

    OK on est d'accord.

    Est-ce que quelqu'un sait comment résoudre ce problème ?

    Merci beaucoup

  10. #9
    GrisBleu

    Re : Maximisation d'une fonction non-linéaire

    Salut

    si j en crois Sylvestre, les equations sont quadratiques en les inconnues. Si tu veux une solution exacte, je ne la connais pas, mais sinon, essaie d exprimer tes inconnues X=(m,c1,c2) sous la forme
    0.5 X^T QX +P^TX=0
    et la, il n y a plus qu a lancer un progrqamme d optimisation QP - sans contraintes. essaie la librairie GNU GSL CQP si tu veux du libre, sinon Matlab dois pouvoir faire ca

    ++

  11. #10
    invitebba29e66

    Re : Maximisation d'une fonction non-linéaire

    A mon avis, en fait, ça n'a rien de quadratique...

    car par exemple et les deux derniers termes incluent la multiplication de trois termes du "supervecteur" .

    Par contre, ça risque de pouvoir s'écrire comme un produit tensoriel, si je ne dis pas trop de bétises. Je regarde ça...

Discussions similaires

  1. Matrice d'une application linéaire
    Par invite962bb108 dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 10/09/2007, 20h18
  2. [Analyse] Continuité d'une fonction linéaire
    Par indian58 dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 14/05/2007, 11h11
  3. fonction linéaire et affine
    Par invite975d9f0f dans le forum Mathématiques du collège et du lycée
    Réponses: 1
    Dernier message: 26/04/2006, 18h50
  4. Fonction additive ou linéaire ?
    Par ericcc dans le forum Mathématiques du supérieur
    Réponses: 35
    Dernier message: 28/11/2005, 10h25
  5. Regression non-linéaire d'une fonction discrète
    Par Evil.Saien dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 15/12/2004, 15h37