Aiuto problema ottimizzazione
Salve
vorrei un vostro aiuto per risolvere un problema di matematica forse per voi banale
partendo da una espressione $y-X*b=e^2$
dove $X$ è una matrice ($n\times k$)
$b$ è un vettore ($k\times 1$)
$y$ è un vettore ($n\times 1$)
$e^2$ è un vettore ($n\times 1$) intendo un vettore che contiene solo valori positivi
esempio:
$((y_1),(y_2),(y_3),(y_4))-((x_(11),x_(12),x_(13)),(x_(21),x_(22),x_(23)),(x_(31),x_(32),x_(33)),(x_(41),x_(42),x_(43)))*((b_1),(b_2),(b_3))=((e_1^2),(e_2^2),(e_3^2),(e_4^2))$
per $n=4$ e $k=3$.
ponendo come vettore incognita la $b$ il mio obiettivo è trovare il vettore ($b$) minimizzando ($e$) ovvero (credo) ponendo uguale a zero la derivata prima di $e=(y-X*b)^(1/2)$
come si fa?
quali saranno gli elementi che compongono $b$?
Spero possiate spiegarmi il procedimento che porta al risultato, vi ringrazio anticipatamente
vorrei un vostro aiuto per risolvere un problema di matematica forse per voi banale
partendo da una espressione $y-X*b=e^2$
dove $X$ è una matrice ($n\times k$)
$b$ è un vettore ($k\times 1$)
$y$ è un vettore ($n\times 1$)
$e^2$ è un vettore ($n\times 1$) intendo un vettore che contiene solo valori positivi
esempio:
$((y_1),(y_2),(y_3),(y_4))-((x_(11),x_(12),x_(13)),(x_(21),x_(22),x_(23)),(x_(31),x_(32),x_(33)),(x_(41),x_(42),x_(43)))*((b_1),(b_2),(b_3))=((e_1^2),(e_2^2),(e_3^2),(e_4^2))$
per $n=4$ e $k=3$.
ponendo come vettore incognita la $b$ il mio obiettivo è trovare il vettore ($b$) minimizzando ($e$) ovvero (credo) ponendo uguale a zero la derivata prima di $e=(y-X*b)^(1/2)$
come si fa?
quali saranno gli elementi che compongono $b$?
Spero possiate spiegarmi il procedimento che porta al risultato, vi ringrazio anticipatamente
Risposte
Ti consiglio di consultare questo link:
https://www.matematicamente.it/forum/com ... 26179.html
e di usare questa sintassi per scrivere le formule. Il post guadagna molto in leggibilità.
https://www.matematicamente.it/forum/com ... 26179.html
e di usare questa sintassi per scrivere le formule. Il post guadagna molto in leggibilità.
Detto in termini un po' più "raffinati", vuoi trovare la migliore approssimazione di $y$ sul sottospazio di $RR^n$ generato dalle $k$ colonne di $X$ sotto il vincolo che gli scarti tra le componenti di $y$ e le componenti del vettore (incognito) approssimante $X*b$ siano positivi...
In generale il problema di migliore approssimazione si risolve molto facilmente col metodo dei minimi quadrati: infatti, sfruttando le proprietà di spazio euclideo (cioè dotato di prodotto scalare) di $RR^n$, si stabilisce facilmente che il vettore $b$ ha come componenti i prodotti scalari di $y$ per i vettori colonna di $X$ è la migliore approssimazione di $y$ sul sottospazio generato dalle colonne di $X$.
Però quando si applica un procedimento di questo tipo si sta rendendo minima la lunghezza del vettore degli scarti $y-X*b$, ossia la norma $||y-X*b||$, e non è detto che ogni componente di tale vettore risulti $>=0$.
Valga un esempio banale in $RR^2$; prendiamo:
$n=2$, $k=1$, $y=((-1),(-1))$, $X=((1),(0))$;
per quanto detto prima, la migliore approssimazione di $y$ sul sottospazio generato dalla colonna di $X$ (che poi è il primo asse del riferimento cartesiano canonico di $RR^2$) nel senso dei minimi quadrati viene ad essere il vettore individuato dallo scalare:
$b=y\circ X^1=(-1)*1+(-1)*0=-1$ (prodotto scalare tra $y$ è la prima colonna $X^1$ di $X$)
ossia $X*b=((-1),(0))$; si vede che il vettore degli scarti è $y-X*b=((0),(-1))$ quindi non verifica la condizione che tu richiedi.
Allora la domanda è: sei sicuro che è proprio necessario rispettare il vincolo $y-X*b>=0$ (intendendo che tutte le componenti di $y-X*b$ sono non negative)?
P.S.: Per curiosità, ma che roba è? Ricerca operativa?
In generale il problema di migliore approssimazione si risolve molto facilmente col metodo dei minimi quadrati: infatti, sfruttando le proprietà di spazio euclideo (cioè dotato di prodotto scalare) di $RR^n$, si stabilisce facilmente che il vettore $b$ ha come componenti i prodotti scalari di $y$ per i vettori colonna di $X$ è la migliore approssimazione di $y$ sul sottospazio generato dalle colonne di $X$.
Però quando si applica un procedimento di questo tipo si sta rendendo minima la lunghezza del vettore degli scarti $y-X*b$, ossia la norma $||y-X*b||$, e non è detto che ogni componente di tale vettore risulti $>=0$.
Valga un esempio banale in $RR^2$; prendiamo:
$n=2$, $k=1$, $y=((-1),(-1))$, $X=((1),(0))$;
per quanto detto prima, la migliore approssimazione di $y$ sul sottospazio generato dalla colonna di $X$ (che poi è il primo asse del riferimento cartesiano canonico di $RR^2$) nel senso dei minimi quadrati viene ad essere il vettore individuato dallo scalare:
$b=y\circ X^1=(-1)*1+(-1)*0=-1$ (prodotto scalare tra $y$ è la prima colonna $X^1$ di $X$)
ossia $X*b=((-1),(0))$; si vede che il vettore degli scarti è $y-X*b=((0),(-1))$ quindi non verifica la condizione che tu richiedi.
Allora la domanda è: sei sicuro che è proprio necessario rispettare il vincolo $y-X*b>=0$ (intendendo che tutte le componenti di $y-X*b$ sono non negative)?
P.S.: Per curiosità, ma che roba è? Ricerca operativa?
Ciao Gugo82, innanzitutto vorre ringraziarti per aver ragionato sul mio quesito, devo rispondere alla tua domanda con un si, è proprio questa la restrizione da rispettare, qualcuno ha la minima idea di come almeno impostare la soluzione?
P.S e un "semplice" problema di ottimo
P.S e un "semplice" problema di ottimo
Allora vorresti risolvere un problema con un vincolo del genere:
$X*b<=y$
con $X\in M_(n,k)(RR)$ di rango $k<=n$ ed $y\in RR^n$.
Un po' d'intuizione geometrica ci dice che l'insieme $T:=\{ z\in RR^n: z<=y\}$ è lo $n$-edro (ossia "angolo di $RR^n$") che ha per $i$-esima faccia (per $i=1,\ldots ,n$) il semi-iperpiano:
$\{(z_i<=y_i),(z_j<=y_j " per ogni " j!=i):}$
mentre l'insieme $S:=\{ z \in RR^n: (exists b\in RR^k:z=X*b)\}$ è il sottospazio, di dimensione $k$ evidentemente, generato dalle colonne di $X$.
Il tuo vincolo ti impone di cercare le soluzioni al problema in $T\cap S$.
Si vede subito che l'insieme $T\cap S$ può essere vuoto, limitato o non limitato.
Ad esempio si veda il disegno che segue:
[asvg]xmin=-3; xmax=3; ymin=-3; ymax=3;
axes("labels", "grid");
marker="arrow";
line([0,0],[-1,1]);
text([-0.5,0.5],"y", aboveright);
marker="none";
fill="lightyellow";
rect([-4,-4],[-1,1]);
text([-2,0],"T");
stroke="blue";
plot("-0.33*x",-4,4);
text([3,-1],"S2", belowleft);
stroke="red";
plot("x",-4,4);
text([2,2],"S3", belowright);
stroke="green";
plot("-2*x",-4,4);
text([1,-2],"S1", belowleft);[/asvg]
in cui $T\cap S_1$, $T\cap S_2$ e $T\cap S_3$ sono rispettivamente vuoto, limitato e illimitato.
Si capisce che se $T\cap S$ è vuoto, il problema (qualunque esso sia) non ha soluzione.
Ora, dopo l'analisi del vincolo, viene il bello...
In effetti, caro gabriele, non è chiara quale sia la tua funzione obiettivo.
Mi spiego.
Tu chiedi di minimizzare gli scarti, ossia le componenti del vettore $y-X*b$, però ciò significa che hai $n$ funzioni obiettivo da minimizzare, ossia le tue $e_i^2:=y_i-X^i*b$; quindi dovresti trovare un $b\in RR^k$ tale che dia il minimo contemporaneamente a tutte le $e_i^2$.
Questo non si può sempre fare, come mostra il seguente esempio: consideriamo le situazione in figura:
[asvg]xmin=-3; xmax=3; ymin=-3; ymax=3;
axes("labels", "grid");
marker="arrow";
line([0,0],[-1,1]);
text([-0.5,0.5],"y", aboveright);
marker="none";
fill="lightyellow";
rect([-4,-4],[-1,1]);
text([-2,0],"T");
stroke="blue";
plot("-0.33*x",-4,4);
text([3,-1],"S", below);
dot([-3,1]);
text([-3,1],"B",above);
dot([-1,0.33]);
text([-1,0.33],"A",belowleft);[/asvg]
Volendo minimizzare solo lo scarto sulle ascisse, ossia $e_1^2$, si vede che il minimo è preso nel punto $A$; invece, volendo minimizzare solo lo scarto sulle ordinate, cioè $e_2^2$, si vede che il minimo è preso in $B$.
Quindi, visto che $A!=B$ non hai una soluzione del problema di minimo (perchè tu vuoi che $e_1^2,e_2^2$ assumano minimo nello stesso punto!).
A mio parere, devi capire bene qual è la tua "funzione obiettivo" (terminologia da ingegnere...), perchè così com'è posto il problema non si trova sempre una soluzione (cosa auspicabile quando l'insieme determinato dai vincoli è non vuoto).
Ad esempio una buona funzione obiettivo sarebbe $F(e_1^2,\ldots ,e_n^2)=\sum_(i=1)^n e_i^2$ che ingloba tutte le informazioni sugli scarti.
Con tale scelta di $F$, il problema diventa:
$\{(min_(b\in RR^k) F(y-X*b)),("sotto vincolo: " X*b<=y):}$
e, se consideriamo la situazione rappresentata nella figura precedente, la soluzione è $A$.
Spero d'esserti stato d'aiuto.
Buono studio.
$X*b<=y$
con $X\in M_(n,k)(RR)$ di rango $k<=n$ ed $y\in RR^n$.
Un po' d'intuizione geometrica ci dice che l'insieme $T:=\{ z\in RR^n: z<=y\}$ è lo $n$-edro (ossia "angolo di $RR^n$") che ha per $i$-esima faccia (per $i=1,\ldots ,n$) il semi-iperpiano:
$\{(z_i<=y_i),(z_j<=y_j " per ogni " j!=i):}$
mentre l'insieme $S:=\{ z \in RR^n: (exists b\in RR^k:z=X*b)\}$ è il sottospazio, di dimensione $k$ evidentemente, generato dalle colonne di $X$.
Il tuo vincolo ti impone di cercare le soluzioni al problema in $T\cap S$.
Si vede subito che l'insieme $T\cap S$ può essere vuoto, limitato o non limitato.
Ad esempio si veda il disegno che segue:
[asvg]xmin=-3; xmax=3; ymin=-3; ymax=3;
axes("labels", "grid");
marker="arrow";
line([0,0],[-1,1]);
text([-0.5,0.5],"y", aboveright);
marker="none";
fill="lightyellow";
rect([-4,-4],[-1,1]);
text([-2,0],"T");
stroke="blue";
plot("-0.33*x",-4,4);
text([3,-1],"S2", belowleft);
stroke="red";
plot("x",-4,4);
text([2,2],"S3", belowright);
stroke="green";
plot("-2*x",-4,4);
text([1,-2],"S1", belowleft);[/asvg]
in cui $T\cap S_1$, $T\cap S_2$ e $T\cap S_3$ sono rispettivamente vuoto, limitato e illimitato.
Si capisce che se $T\cap S$ è vuoto, il problema (qualunque esso sia) non ha soluzione.
Ora, dopo l'analisi del vincolo, viene il bello...
In effetti, caro gabriele, non è chiara quale sia la tua funzione obiettivo.
Mi spiego.
Tu chiedi di minimizzare gli scarti, ossia le componenti del vettore $y-X*b$, però ciò significa che hai $n$ funzioni obiettivo da minimizzare, ossia le tue $e_i^2:=y_i-X^i*b$; quindi dovresti trovare un $b\in RR^k$ tale che dia il minimo contemporaneamente a tutte le $e_i^2$.
Questo non si può sempre fare, come mostra il seguente esempio: consideriamo le situazione in figura:
[asvg]xmin=-3; xmax=3; ymin=-3; ymax=3;
axes("labels", "grid");
marker="arrow";
line([0,0],[-1,1]);
text([-0.5,0.5],"y", aboveright);
marker="none";
fill="lightyellow";
rect([-4,-4],[-1,1]);
text([-2,0],"T");
stroke="blue";
plot("-0.33*x",-4,4);
text([3,-1],"S", below);
dot([-3,1]);
text([-3,1],"B",above);
dot([-1,0.33]);
text([-1,0.33],"A",belowleft);[/asvg]
Volendo minimizzare solo lo scarto sulle ascisse, ossia $e_1^2$, si vede che il minimo è preso nel punto $A$; invece, volendo minimizzare solo lo scarto sulle ordinate, cioè $e_2^2$, si vede che il minimo è preso in $B$.
Quindi, visto che $A!=B$ non hai una soluzione del problema di minimo (perchè tu vuoi che $e_1^2,e_2^2$ assumano minimo nello stesso punto!).
A mio parere, devi capire bene qual è la tua "funzione obiettivo" (terminologia da ingegnere...), perchè così com'è posto il problema non si trova sempre una soluzione (cosa auspicabile quando l'insieme determinato dai vincoli è non vuoto).
Ad esempio una buona funzione obiettivo sarebbe $F(e_1^2,\ldots ,e_n^2)=\sum_(i=1)^n e_i^2$ che ingloba tutte le informazioni sugli scarti.
Con tale scelta di $F$, il problema diventa:
$\{(min_(b\in RR^k) F(y-X*b)),("sotto vincolo: " X*b<=y):}$
e, se consideriamo la situazione rappresentata nella figura precedente, la soluzione è $A$.
Spero d'esserti stato d'aiuto.
Buono studio.
Gugo82 sei stato gentilissimo!!! ti ringrazio ancora e spero tu possa aiutarmi ancora semmai dovesse venirmi qualche altro dubbio circa lo stesso problema. Saluti
Prego.
Ad ogni modo cambio un po' il titolo e sposto il thread in Analisi Numerica e Ricerca Operativa, che mi pare la sezione più adatta.
Ad ogni modo cambio un po' il titolo e sposto il thread in Analisi Numerica e Ricerca Operativa, che mi pare la sezione più adatta.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo