[algoritmo] calcolare minimo di una funzione da Rn a R con un computer

[mamo139]

sia dato il vettore x e il vettore x trasposto xt contenente n incognite x1,x2,...,xn
sia definita la matrice Y di grandezza n*n (di cui conosciamo tutti i valori)
sia e un vettore che ha tutti gli elementi di valore 1.

quale puo essere un algoritmo efficiente per il seguente problema??

min xt*Y*x
sub x*e = 1

anzi... ancor meglio mi piacerebbe sapere come risolvereste con il computer semplicemente questo problema:
min xt*Y*x
al vincolo poi ci penso io!!

grazie

ps: mi piacerebbe un modo piu sofisticato della forza bruta... io stavo pensando magari di utilizzare i differenziali, posizionarmi in un punto e scorrere "giu per le conche" () fino a raggiungere un minimo, ma magari potrei finire intrappolato in un minimo locale...

[mamo139]

up...

ho gia predisposto il codice per moltiplicare le matrici!

#include <stdio.h>
#include <stdlib.h>

struct matrice {
   int r;
   int c;
   long ** m;
};


struct matrice crea_matrice(int r, int c); // r = righe, c = colonne
bool moltiplica_matrici(struct matrice * c, struct matrice a, struct matrice b);

int main (){
   
    struct matrice x,y,z;
    x = crea_matrice(2,3);
    y = crea_matrice(3,2);
    z = crea_matrice(x.r,y.c);
   
    if(!moltiplica_matrici(&z,x,y))
        printf("errore...");
       
    getchar();
    return 1;
}

struct matrice crea_matrice(int r, int c){ // r = righe, c = colonne

     int x,y;
     struct matrice matrice;
     
     matrice.r = r;
     matrice.c = c;
     matrice.m = (long **) malloc(r * sizeof(long *));
     
     for(x=0;x<r;x++)
          matrice.m[x] = (long *) malloc(c * sizeof(long));
         
     for(x=0;x<r;x++)
          for(y=0;y<c;y++)   
               matrice.m[x][y] = 0;
     
     return matrice;
}

bool moltiplica_matrici(struct matrice * c, struct matrice a, struct matrice b){
     
     int x,y,i;
     
     if(a.c != b.r)
          return 0;
     if(c->r != a.r || c->c != b.c)
          return 0;
     
     for(x=0;x<c->r;x++)
          for(y=0;y<c->c;y++)
               for(i=0;i<a.c;i++)
                    c->m[x][y] = c->m[x][y] + a.m[x][i]*b.m[i][y];
     
     return 1;
}

[Furla]

simplesso?
comunque si risolve esattamente come si risolve a mano, devi solo procedere a piccoli passi trasformando i procedimenti "manuali" in funzioni che lavorano sulla struttura e si passano informazioni.

[mamo139]

Originariamente inviato da Furla

simplesso?
comunque si risolve esattamente come si risolve a mano, devi solo procedere a piccoli passi trasformando i procedimenti "manuali" in funzioni che lavorano sulla struttura e si passano informazioni.

il simplesso funziona solo con problemi lineari... quindi temo non vada bene!

[krogy80]

Originariamente inviato da mamo139

sia dato il vettore x e il vettore x trasposto xt contenente n incognite x1,x2,...,xn
sia definita la matrice Y di grandezza n*n (di cui conosciamo tutti i valori)
sia e un vettore che ha tutti gli elementi di valore 1.

quale puo essere un algoritmo efficiente per il seguente problema??

min xt*Y*x
sub x*e = 1

anzi... ancor meglio mi piacerebbe sapere come risolvereste con il computer semplicemente questo problema:
min xt*Y*x
al vincolo poi ci penso io!!

grazie

ps: mi piacerebbe un modo piu sofisticato della forza bruta... io stavo pensando magari di utilizzare i differenziali, posizionarmi in un punto e scorrere "giu per le conche" () fino a raggiungere un minimo, ma magari potrei finire intrappolato in un minimo locale...

in questo caso dipende dalle caratteristiche di Y. se Y é semi-definita positiva, ovvero xt*Y*x>=0 per ogni x!=0, allora il problema é convesso e ogni minimo locale é anche globale, quindi puoi usare i differenziali.
i problemi non-convessi, a parte poche eccezzioni, non sono risolvibili efficacemente.
comunque ottimizzazzione é un'argomento piuttosto complesso, non posso certo tenerti una lezione via forum
se ti interessa questo libro é ottimo.

[edit] fatto due calcoli, se Y é semidefinita positiva il minimo dovrebbe essere
x_min = (invY*e) / ( et * invY * e)
dove invY é l'inversa di Y se esiste o la pseudo inversa altrimenti.

[mamo139]

Originariamente inviato da krogy80

in questo caso dipende dalle caratteristiche di Y. se Y é semi-definita positiva, ovvero xt*Y*x>=0 per ogni x!=0, allora il problema é convesso e ogni minimo locale é anche globale, quindi puoi usare i differenziali.
i problemi non-convessi, a parte poche eccezzioni, non sono risolvibili efficacemente.
comunque ottimizzazzione é un'argomento piuttosto complesso, non posso certo tenerti una lezione via forum
se ti interessa questo libro é ottimo.

[edit] fatto due calcoli, se Y é semidefinita positiva il minimo dovrebbe essere
x_min = (invY*e) / ( et * invY * e)
dove invY é l'inversa di Y se esiste o la pseudo inversa altrimenti.

capito, grazie...
alla fine il metodo piu rapido e quello di calcolare il gradiente della lagrangiana del caso generico, risolverlo e poi utilizzare la soluzione nel programma
io volevo fargli fare i calcoli, però è meno efficiente!!!

cmq il tuo risultato è giustissimo, anche a me con il metodo che ho detto viene:
xt = et*invY / (et*invY*e)

[krogy80]

Originariamente inviato da mamo139

capito, grazie...
alla fine il metodo piu rapido e quello di calcolare il gradiente della lagrangiana del caso generico, risolverlo e poi utilizzare la soluzione nel programma
io volevo fargli fare i calcoli, però è meno efficiente!!!

il tuo problema é un caso particolare in cui si riesce a ricavare la soluzione in forma chiusa. in generale peró non si puó, e bisogna utilizzare metodi iterativi.

[edit] tra l'altro la formula sopra é valida solo se Y é anche simmetrica. altrimenti basta usare al posto di invY l'inversa di Y+Yt.

[mamo139]

ok, ora vorrei utilizzare un metodo iterativo per trovare i punti stazionari (quindi non solo quelli di massimo o di minimo) di una funzione da Rn a R...

che metodi ci sono?