[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" (:D) fino a raggiungere un minimo, ma magari potrei finire intrappolato in un minimo locale... :rolleyes:

[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]

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]

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" (:D) fino a raggiungere un minimo, ma magari potrei finire intrappolato in un minimo locale... :rolleyes:

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 (http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf) é 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]

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 (http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf) é 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) :mano:

[krogy80]

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?