Re: Problema di ottimizzazione

Messaggioda Raptorista » 23/01/2020, 17:01

Bokonon ha scritto:aveva aperto il thread qua e adesso vedo che era un duplicato.
https://www.matematicamente.it/forum/vi ... 0&t=205226

Moderatore: Raptorista

@Pessima_Scelta il crossposting è male!! Cartellino giallo :evil:
Un matematico ha scritto:... come mia nonna che vuole da anni il sistema per vincere al lotto e crede che io, in quanto matematico, sia fallito perché non glielo trovo


Immagine
Avatar utente
Raptorista
Moderatore
Moderatore
 
Messaggio: 5383 di 5403
Iscritto il: 28/09/2008, 19:58

Re: Problema di ottimizzazione

Messaggioda Sergio » 23/01/2020, 19:32

Bokonon ha scritto:Beh dai Sergio, è intuibile che vi siano acque molto simili e acque relativamente diverse.
La cosa importante è non usare due acque del tipo $(1,2,3,4,5,6)$ e $1,2,3,4,5,6.0000001)$
Sono lineamente indipendenti? SI
Sono una scelta subottimale? Assolutamente SI
Il problema che ho posto è stranoto. Mettiamo che alla fine ottenga il vettore $(x_1,x_2,x_3,x_4,x_5,x_6)$
Facendo $100*(x_i)/(sum_0^6 x_i)$ ottiene le percentuali di acqua da impiegare da ogni bottiglia.
Se approssima le percentuali al primo decimale e la scelta delle acque è subottimale, il risultato sarà un'acqua che si discosta assai rispetto a quella voluta.

Sei sicuro?
Se trovo una combinazione di 6 acque linearmente indipendenti quella è chiaramente esatta. Il problema potrebbe porsi se i coefficienti della combinazione richiedessero approssimazioni "pesanti", ma nell'esempio che hai fatto questo potrebbe essere un problema solo per la sesta componente, e come farebbero acque che per quella componente differiscono di $10^{-7}$ a generare un'acqua molto diversa da quella voluta?
Inoltre, capisco che il tuo è un esempio volutamente estremo, ma ppm (parti per milione) equivale a mg/L, che - per quanto ne so - sono indicati con uno o al massimo due decimali. Ad esempio, per l'acqua minerale che ho ora a casa leggo: calcio 60.36, magnesio 3.73, sodio 3.87, cloruri 7.34, solfati 7.54, bicarbonati 185.4. Da una parte sono già numeri approssimati (nessuno - almeno nella mia limitata esperienza - conta il decimilionesimo di milligrammo per litro, ma nemmeno il millesimo), dall'altra non mi sembrano difficili da trattare. O no?

Il problema mi pare piuttosto un altro: non basta trovare una combinazione lineare di 6 acque, se ne deve trovare una combinazione con coefficienti non negativi. E non è scontato...
Peccato che l'autore della doppia richiesta sembri sparito. Tutto sommato, avevo pensato a un altro metodo e mi sarebbe piaciuto verificarlo con 250 acque diverse :D
"Se vuoi un anno di prosperità coltiva del riso. Se vuoi dieci anni di prosperità pianta degli alberi. Se vuoi cento anni di prosperità istruisci degli uomini" (proverbio cinese). E invece... viewtopic.php?p=236293#p236293
Avatar utente
Sergio
Cannot live without
Cannot live without
 
Messaggio: 6398 di 6567
Iscritto il: 26/04/2004, 10:56
Località: Roma

Re: Problema di ottimizzazione

Messaggioda axpgn » 23/01/2020, 20:08

@Sergio
Testo nascosto, perché contrassegnato dall'autore come fuori tema. Fai click in quest'area per vederlo.
Sergio ha scritto:Tutto sommato, avevo pensato a un altro metodo e mi sarebbe piaciuto verificarlo con 250 acque diverse :D

Cosa non si fa per una birra :-D
axpgn
Cannot live without
Cannot live without
 
Messaggio: 14818 di 15013
Iscritto il: 20/11/2013, 22:03

Re: Problema di ottimizzazione

Messaggioda Bokonon » 23/01/2020, 22:45

Sergio ha scritto:Sei sicuro?


Si, Sergio. E l'errore si amplia all'aumentare del numero di "assi".
Ne parla Strang ma ovviamente ci sono diversi video e lezioni online che trattano l'argomento della scelta delle basi (che ovviamente diventa essenziale quando si trattano matrici immense).
Per il resto, direi che fare 4 operazioni (roba da 3 minuti scarsi) con excel per selezionare un campione di acque, non merita approfondimenti particolari.

Sergio ha scritto:Il problema mi pare piuttosto un altro: non basta trovare una combinazione lineare di 6 acque, se ne deve trovare una combinazione con coefficienti non negativi. E non è scontato...

Vero, meglio avere una ventina di acque diverse e sperare per il meglio.
Avatar utente
Bokonon
Advanced Member
Advanced Member
 
Messaggio: 1979 di 2089
Iscritto il: 25/05/2018, 20:22

Re: Problema di ottimizzazione

Messaggioda Sergio » 23/01/2020, 23:59

Bokonon ha scritto:Si, Sergio. E l'errore si amplia all'aumentare del numero di "assi".
Ne parla Strang [ecc.]

Sì, ho capito quello a cui ti riferisci, ma non riesco a trarne le tue conclusioni.
Prendiamo un esempio di Strang (p. 62) e interpretiamolo come se si trattasse di acque. Hai una matrice con due colonne-acqua, $A=((1,1),(1,1.0001))$, e diciamo che vuoi trovare come usare le due acque per produrre una tua acqua $b=(2,2)$, usando $u$ della prima colonna e $v$ della seconda. Ottieni $u=2$, $v=0$.
Poi invece vuoi produrre $(2,2.0001)$ e ottieni $u=1$, $v=1$.
La conclusione di Strang: un cambiamento nella quinta cifra di $b$ si amplifica fino a diventare un cambiamento della prima cifra della soluzione. Ha ragione? Sicuramente sì.
C'entra qualcosa? Mi pare proprio di no, per due motivi:
1) Una volta che si è deciso di produrre un $b$, non vedo perché dovrei considerare altri possibili $b$.
2) Soprattutto, ammettiamo che una delle due soluzioni di Strang sia per qualche misterioso motivo quella ottimale, l'altra subottimale. Sono davvero così vistosamente diverse?
Mica tanto...
Prima soluzione: ottengo $2(1,1)+0(1,1.0001)=(2,2)$.
Seconda soluzione: ottengo $1(1,1)+1(1,1.0001)=(2,2.0001)$.
La differenza che mi interessa, quella tra le acque che otterrei, è ancora nella quinta cifra.
Non si è amplificata nemmeno un po' (e il motivo è evidente...)

Direi che la situazione è simile a quella che si verifica in statistica con la multicollinearità. Mi viene in mente un esempio che avevo proposto qui: un modello in cui sono possibili infinite stime diverse - e non poco - dei coefficienti, in cui quindi non è possibile ottenere stime credibili dei singoli coefficienti, ma quali che siano le stime che scegli i valori teorici \(\hat y\) rimangono sempre gli stessi.
In altri termini, anche se non succede sempre, puoi ottenere una combinazione lineare di colonne non unica, ma efficace, pure se le colonne non sono linearmente indipendenti. La condizione è che $b$ appartenga a \(\text{Im}(A)\).
"Se vuoi un anno di prosperità coltiva del riso. Se vuoi dieci anni di prosperità pianta degli alberi. Se vuoi cento anni di prosperità istruisci degli uomini" (proverbio cinese). E invece... viewtopic.php?p=236293#p236293
Avatar utente
Sergio
Cannot live without
Cannot live without
 
Messaggio: 6401 di 6567
Iscritto il: 26/04/2004, 10:56
Località: Roma

Sì, è un problema di ottimizzazione

Messaggioda Sergio » 24/01/2020, 16:44

Avevo detto che più che un problema di ottimizzazione è un problema di algebra lineare. Guardando meglio, però, sotto sotto c'è un vero problema di ottimizzazione.
Il motivo è che non basta trovare una combinazione lineare di $n$ acque minerali, con $n\le 6$, perché ne serve una combinazione conica, cioè lineare non negativa. E così si entra nel mondo dell'ottimizzazione.
Il dato nuovo, che era stato comunicato solo nell'altro thread, è che le acque minerali da scegliere vanno scelte da 250 acque diverse. Il problema è quindi: dati una matrice \(A\in M_{6,250}\), \(a_{ij}\ge 0\) per ogni $i,j$, e un vettore \(b\ge 0\) (l'acqua da generare), esiste un vettore \(x\ge 0\) tale che $Ax=b$?
Il problema non è di facile soluzione.
In teoria, l'esistenza o meno di una soluzione può essere accertata ricorrendo al lemma di Farkas, ma in pratica questa non sarebbe certo una scorciatoia. Non con una matrice di 250 colonne.
Da un punto di vista più pragmatico si potrebbe ricorrere alla regressione ristretta, in particolare a una regressione in cui si impone che i coefficienti stimati siano tutti non negativi (v. qui). Con R si può usare la libreria nnls (non-negative least squares), che può essere installata con:
Codice:
> install.packages("nnls")

Le ppm di ioni che caratterizzano un'acqua minerale sono numeri con uno o due cifre decimali, quindi razionali, che vanno grosso modo da $40/10$ a $1800/10$. Una matrice $A$ può quindi essere costruita più o meno così:
Codice:
> set.seed(1234)                          # per poter riprodurre l'esempio
> A <- round(matrix(runif(6*250, 40, 1800) / 10, 6, 250), 2)

Proviamo ora a definire un vettore $b$ con componenti nello stesso range:
Codice:
> b <- round(runif(6, 40, 1800) / 10, 2)
> b
[1]  85.06 115.89  99.27 148.92 160.04 138.17

E proviamo ora a eseguire una regressione ristretta:
Codice:
> library(nnls)
> mod1 <- nnls(A, b)
> x <- mod1$x                             # i coefficienti trovati

In questo caso (e non stupisce) solo 6 coefficienti sono positivi, gli altri tutti nulli. Possiamo estrarre sia i coefficienti non nulli, sia le corrispondenti colonne di $A$:
Codice:
> pos <- which(x > 0)                     # indici dei coefficienti positivi
> pos
[1]  61 131 156 234 236 241
> A_pos <- A[,pos]
> A_pos
       [,1]   [,2]   [,3]   [,4]   [,5]   [,6]
[1,]   4.55 170.30  29.66 149.04  55.41   8.05
[2,] 102.20  13.95 178.34 139.16  51.62  62.72
[3,]  85.00   4.06   8.59 122.87 114.62  48.69
[4,]  62.03  55.04 110.79 108.43 124.81 169.31
[5,] 151.04  42.24  21.97 166.44  34.86 146.66
[6,] 176.08 125.19  93.66 145.11 179.45  56.41
> x_pos <- x[pos]
> x_pos
[1] 0.10768263 0.03297067 0.04979047 0.45401592 0.11597716 0.42056228
> A_pos %*% x_pos
       [,1]
[1,]  85.06
[2,] 115.89
[3,]  99.27
[4,] 148.92
[5,] 160.04
[6,] 138.17

Come si vede, prendendo le acque alle colonne 61, 131, 156, 234, 236 e 241 e combinandole secondo i coefficienti x_pos si ottiene l'acqua desiderata (il vettore $b$).
NB: Non funziona sempre! È evidente, e si può facilmente verificare usando diversi vettori $b$, che a volte si ottiene solo una rozza approssimazione. D'altra parte, questo vorrebbe semplicemente dire che l'acqua $b$ non può essere generata combinando le 250 acque disponibili con coefficienti tutti non negativi.
"Se vuoi un anno di prosperità coltiva del riso. Se vuoi dieci anni di prosperità pianta degli alberi. Se vuoi cento anni di prosperità istruisci degli uomini" (proverbio cinese). E invece... viewtopic.php?p=236293#p236293
Avatar utente
Sergio
Cannot live without
Cannot live without
 
Messaggio: 6403 di 6567
Iscritto il: 26/04/2004, 10:56
Località: Roma

Precedente

Torna a Analisi Numerica e Ricerca Operativa

Chi c’è in linea

Visitano il forum: Nessuno e 3 ospiti