Esistenza soluzione problema Weber-Fermat
Ciao a tutti,
sto seguendo un corso di ottimizzazione ed uno degli esami precedenti verteva sul problema di Fermat-Weber.
Dati m punti $y_i$ in un piano, si tratta di trovare il punto $x$ per cui la somma delle distanze (pesate, con peso variabile) dai punti fissi $y_i$ è minima.
In altre parole, si tratta di minimizzare la funzione $$\sum_{i=1}^mw_i||x-y_i||$$ rispetto a $x$ con $x \in R^2$.
Ora, la soluzione non si può trovare in forma chiusa in generale, però la domanda del problema è solo dimostrare che
esista una soluzione.
Io ho un'idea, ma poiché mi sembra troppo semplice temo di dimenticare qualcosa. Quindi vorrei sottoporvela.
Supponiamo che i punti non siano collineari.
1-La funzione è una somma di funzioni convesse e continue su $R^2$, quindi è convessa e continua
su $R^2$.
2-Essendo definita su tutto il piano, la si può definire su un arbitrario insieme chiuso e limitato. Quindi, una volta definita su un insieme chiuso e limitato sappiamo che ammette un minimo su tale insieme in base al teorema di Weierstrass.
3-Dimostrare unicità : work in progress.
I miei dubbi sono sui casi limite, cioè il minimo potrebbe essere uno dei punti $y_i$? Direi di no, ma come si può provare?
Inoltre, secondo voi si può provare che il minimo è all'interno del poligono formato dai punti $y_i$?
Grazie in anticipo
Iorfus
sto seguendo un corso di ottimizzazione ed uno degli esami precedenti verteva sul problema di Fermat-Weber.
Dati m punti $y_i$ in un piano, si tratta di trovare il punto $x$ per cui la somma delle distanze (pesate, con peso variabile) dai punti fissi $y_i$ è minima.
In altre parole, si tratta di minimizzare la funzione $$\sum_{i=1}^mw_i||x-y_i||$$ rispetto a $x$ con $x \in R^2$.
Ora, la soluzione non si può trovare in forma chiusa in generale, però la domanda del problema è solo dimostrare che
esista una soluzione.
Io ho un'idea, ma poiché mi sembra troppo semplice temo di dimenticare qualcosa. Quindi vorrei sottoporvela.
Supponiamo che i punti non siano collineari.
1-La funzione è una somma di funzioni convesse e continue su $R^2$, quindi è convessa e continua
su $R^2$.
2-Essendo definita su tutto il piano, la si può definire su un arbitrario insieme chiuso e limitato. Quindi, una volta definita su un insieme chiuso e limitato sappiamo che ammette un minimo su tale insieme in base al teorema di Weierstrass.
3-Dimostrare unicità : work in progress.
I miei dubbi sono sui casi limite, cioè il minimo potrebbe essere uno dei punti $y_i$? Direi di no, ma come si può provare?
Inoltre, secondo voi si può provare che il minimo è all'interno del poligono formato dai punti $y_i$?
Grazie in anticipo
Iorfus
Risposte
Il punto 2 non è corretto.
Basta però osservare che, se \(R > \max\{|y_1|, \ldots, |y_m|\}\), si ha che
\[
f(x) \geq \sum w_i (R - |y_i|) \qquad \forall |x| \geq R.
\]
Ti basta a questo punto scegliere \(R\) abbastanza grande tale che
\[
f(x) > f(0) \qquad \forall |x| \geq R.
\]
Il teorema di Weierstrass ti garantisce l'esistenza di un minimo nel compatto \(K := \overline{B}_R(0)\) che, grazie alla relazione precedente, è necessariamente minimo assoluto su tutto \(\mathbb{R}^2\).
Basta però osservare che, se \(R > \max\{|y_1|, \ldots, |y_m|\}\), si ha che
\[
f(x) \geq \sum w_i (R - |y_i|) \qquad \forall |x| \geq R.
\]
Ti basta a questo punto scegliere \(R\) abbastanza grande tale che
\[
f(x) > f(0) \qquad \forall |x| \geq R.
\]
Il teorema di Weierstrass ti garantisce l'esistenza di un minimo nel compatto \(K := \overline{B}_R(0)\) che, grazie alla relazione precedente, è necessariamente minimo assoluto su tutto \(\mathbb{R}^2\).
"iorfus":
Inoltre, secondo voi si può provare che il minimo è all'interno del poligono formato dai punti $y_i$?
Se con questo intendi dire che il minimo si trova nel convessificato \(K\) dei punti \(\{y_1,\ldots, y_m\}\), mi sembra che sia vero.
Infatti, se \(x\not\in K\), direi che la proiezione di \(x\) su \(K\) abbassi strettamente il valore di \(f\).
Intendevo dire che, fermo restando che dobbiamo essere nel piano, il punto sia appunto all'interno di questo convessificato.
Cioè che non si può uscire dal "recinto" formato dagli N punti.
Cioè che non si può uscire dal "recinto" formato dagli N punti.
Ora mi rendo conto che non avevo letto la prima risposta.
Puoi dirmi come si definisce l'insieme $K$ che menzioni? È la palla chiusa di raggio R e centro 0?
Comunque grazie, il punto 2 mi sembrava poco "matematico".
Puoi dirmi come si definisce l'insieme $K$ che menzioni? È la palla chiusa di raggio R e centro 0?
Comunque grazie, il punto 2 mi sembrava poco "matematico".
"iorfus":
Ora mi rendo conto che non avevo letto la prima risposta.
Puoi dirmi come si definisce l'insieme $K$ che menzioni? È la palla chiusa di raggio R e centro 0?
Sì.
Grazie, capisco il tuo ragionamento che ho trovato molto ingegnoso.
Nel punto 1 del mio ragionamento avevo scritto che ho una somma di funzioni strettamente convesse. In realtà sono solo convesse, devo trovare un altro modo per dimostrare l'unicità del minimo.
Nel punto 1 del mio ragionamento avevo scritto che ho una somma di funzioni strettamente convesse. In realtà sono solo convesse, devo trovare un altro modo per dimostrare l'unicità del minimo.
"iorfus":
Nel punto 1 del mio ragionamento avevo scritto che ho una somma di funzioni strettamente convesse. In realtà sono solo convesse, devo trovare un altro modo per dimostrare l'unicità del minimo.
Temo che, in generale, il minimo non sia unico.
Considera, ad esempio, il caso \(m=2\), con \(w_1=w_2=1\).
La funzione assume minimo su tutto il segmento che congiunge i due punti \(y_1\) e \(y_2\) (dove è costante).
Prova ad esempio a vedere cosa succede con \(y_1=(-1,0)\), \(y_2 = (1,0)\).
Hai ragione al 100%!
Infatti avrei dovuto scrivere che il minimo è unico se e solo se i punti non sono collineari.
È questo che ora (o meglio domani) cercherò di dimostrare.
Infatti avrei dovuto scrivere che il minimo è unico se e solo se i punti non sono collineari.
È questo che ora (o meglio domani) cercherò di dimostrare.
In effetti se i punti \(y_i\) non sono collineari, allora la somma \(f\) è strettamente convessa (quindi il punto di minimo è unico).
Per dimostrarlo puoi tenere conto di questa osservazione: supponiamo per assurdo che \(f\) non sia strettamente convessa, cioè che esistano \(x_0, x_1\) e \(\lambda\in (0,1)\) tali che
\[
f(x_\lambda) = (1-\lambda) f(x_0) + \lambda f(x_1), \qquad x_\lambda := (1-\lambda) x_0 + \lambda f(x_1).
\]
Allora
\[
|x_\lambda - y_i| = (1-\lambda) |x_0 -y_i| + \lambda |x_1 - y_i|, \qquad \forall i=1,\ldots,m.
\]
Per dimostrarlo puoi tenere conto di questa osservazione: supponiamo per assurdo che \(f\) non sia strettamente convessa, cioè che esistano \(x_0, x_1\) e \(\lambda\in (0,1)\) tali che
\[
f(x_\lambda) = (1-\lambda) f(x_0) + \lambda f(x_1), \qquad x_\lambda := (1-\lambda) x_0 + \lambda f(x_1).
\]
Allora
\[
|x_\lambda - y_i| = (1-\lambda) |x_0 -y_i| + \lambda |x_1 - y_i|, \qquad \forall i=1,\ldots,m.
\]
Sì, c'ero !
In effetti, una volta che abbiamo la disuguaglianza triangolare saturata, concludiamo che i punti sono collineari ... arriviamo ad una contraddizione, e quindi la tesi (cioè che la funzione non è strettamente convessa) non può essere negata.
Sei davvero gentile e d'aiuto ...
visto che sei così gentile, secondo te si può dimostrare che questo famoso minimo non coincide con nessuno dei punti?
Perché un'altro punto del problema richiede di dimostrare che il minimo è realizzato dal punto in cui la risultante delle forze è nulla, e io volevo fare con il gradiente nullo (condizione necessaria e sufficiente per il minimo dato che la funzione è strettamente convessa).
Però, se il minimo coincide con uno dei punti il gradiente esplode ...
Scusa eh, ma sei così gentile e d'aiuto che ne approfitto!
In effetti, una volta che abbiamo la disuguaglianza triangolare saturata, concludiamo che i punti sono collineari ... arriviamo ad una contraddizione, e quindi la tesi (cioè che la funzione non è strettamente convessa) non può essere negata.
Sei davvero gentile e d'aiuto ...
visto che sei così gentile, secondo te si può dimostrare che questo famoso minimo non coincide con nessuno dei punti?
Perché un'altro punto del problema richiede di dimostrare che il minimo è realizzato dal punto in cui la risultante delle forze è nulla, e io volevo fare con il gradiente nullo (condizione necessaria e sufficiente per il minimo dato che la funzione è strettamente convessa).
Però, se il minimo coincide con uno dei punti il gradiente esplode ...
Scusa eh, ma sei così gentile e d'aiuto che ne approfitto!
Mah, non sono così sicuro che il minimo non possa coincidere con uno degli \(y_i\).
Ad esempio, con \(m=3\) e pesi unitari, se \(y_1=(-R,0)\), \(y_2 = (R, 0)\), \(y_3=(0,1)\), per \(R\) abbastanza grande mi aspetterei il minimo in \(y_3\) (ma forse mi sbaglio).
Ad ogni modo, con un po' di pazienza si può provare a fare i conti.
Assumiamo che gli \(y_i\) siano distinti. Se \(x\) non coincide con alcuno degli \(y_i\) allora, come osservavi, è facile calcolare il gradiente di \(f\).
D'altra parte, se \(x = y_j\), allora il sottodifferenziale di \(f\) vale
\[
\partial f(y_j) = w_j \overline{B}_1(0) + \sum_{i\neq j} w_i \frac{y_j - y_i}{|y_j - y_i|}.
\]
Condizione necessaria e sufficiente affinché un punto \(x\) sia di minimo per la funzione (strettamente) convessa \(f\) è che \(0 \in \partial f(x)\). A questo punto basta considerare tutti i casi possibili...
Ad esempio, con \(m=3\) e pesi unitari, se \(y_1=(-R,0)\), \(y_2 = (R, 0)\), \(y_3=(0,1)\), per \(R\) abbastanza grande mi aspetterei il minimo in \(y_3\) (ma forse mi sbaglio).
Ad ogni modo, con un po' di pazienza si può provare a fare i conti.
Assumiamo che gli \(y_i\) siano distinti. Se \(x\) non coincide con alcuno degli \(y_i\) allora, come osservavi, è facile calcolare il gradiente di \(f\).
D'altra parte, se \(x = y_j\), allora il sottodifferenziale di \(f\) vale
\[
\partial f(y_j) = w_j \overline{B}_1(0) + \sum_{i\neq j} w_i \frac{y_j - y_i}{|y_j - y_i|}.
\]
Condizione necessaria e sufficiente affinché un punto \(x\) sia di minimo per la funzione (strettamente) convessa \(f\) è che \(0 \in \partial f(x)\). A questo punto basta considerare tutti i casi possibili...
Penso che il minimo in $y_3$ si abbia per $R$ tendente all'infito, il che non troverebbe riscontro in una situazione "fisica". Credo ...
Però forse hai ragione, basta immaginare tre punti non allineati. Trovato il minimo, possiamo sempre aggiungere un altro punto coincidente col minimo ... ed ecco 4 punti di cui uno coincide col minimo.
È la prima volta che sento parlare di subdifferenziale ... cerco di informarmi e di tornare su questo canale con un opinione riguardo il tuo ultimo ragionamento.
Ciao!
Però forse hai ragione, basta immaginare tre punti non allineati. Trovato il minimo, possiamo sempre aggiungere un altro punto coincidente col minimo ... ed ecco 4 punti di cui uno coincide col minimo.
È la prima volta che sento parlare di subdifferenziale ... cerco di informarmi e di tornare su questo canale con un opinione riguardo il tuo ultimo ragionamento.
Ciao!
"iorfus":
Penso che il minimo in $y_3$ si abbia per $R$ tendente all'infito, il che non troverebbe riscontro in una situazione "fisica".
No, intendo proprio per \(R\) finito; se non sbaglio, il minimo finisce in \(y_3\) non appena \(R > \sqrt{3}\).
In una configurazione simile, ponendo che il minimo sia in $y_3$, la forza agente su tale punto non sarebbe nulla.
Due sono i casi :
O il minimo non è in quella posizione, oppure c'è qualcosa che non quadra ... forse l'interpretazione del minimo come punto in cui la risultante è nulla non vale nel caso in cui il minimo coincida con uno dei punti fissi $y_i$.
Non ho fatto le derivate perché dovrei mettermi a lavorare con i valori assoluti, e penso mi rimbambirei molto presto.
Farò il grafico con qualche software, nel frattempo volevo chiederti da cosa deduci che il minimo è in quella posizione.
Due sono i casi :
O il minimo non è in quella posizione, oppure c'è qualcosa che non quadra ... forse l'interpretazione del minimo come punto in cui la risultante è nulla non vale nel caso in cui il minimo coincida con uno dei punti fissi $y_i$.
Non ho fatto le derivate perché dovrei mettermi a lavorare con i valori assoluti, e penso mi rimbambirei molto presto.
Farò il grafico con qualche software, nel frattempo volevo chiederti da cosa deduci che il minimo è in quella posizione.
"iorfus":
Farò il grafico con qualche software, nel frattempo volevo chiederti da cosa deduci che il minimo è in quella posizione.
Per simmetria il minimo (che abbiamo detto essere unico) deve stare sull'asse \(x_2\).
Abbiamo che
\[
f(x_1, x_2) = \sqrt{(x_1-R)^2+x_2^2} + \sqrt{(x_1+R)^2+x_2^2} +\sqrt{x_1^2+(x_2-1)^2}.
\]
Calcoliamo la restrizione sull'asse \(x_2\):
\[
\phi(t) := f(0, t) = 2 \sqrt{R^2+t^2} + |t-1|.
\]
Senza tirare in ballo il sottodifferenziale in \(t=1\), questa funzione (convessa) è derivabile per \(t\neq 1\) e si ha
\[
\phi'(t) = \frac{2t}{\sqrt{R^2+t^2}} + \text{sign}(t-1), \qquad \forall t\neq 1.
\]
Banalmente (cioè semplicemente guardando i segni degli addendi), hai che \(\phi'(t) < 0\) per \(t\leq 0\) e \(\phi'(t) > 0\) per \(t > 1\).
D'altra parte, con un semplice conto scopri che, se \(R\geq \sqrt{3}\), hai anche che \(\phi'(t) < 0\) per \(t\in (0,1)\).
Di conseguenza, se \(R\geq\sqrt{3}\) il punto \(t=1\) è di minimo per \(\phi\).
Vista la simmetria di \(f\) (\(f(-x_1, x_2) = f(x_1, x_2)\)) e la sua convessità, il punto \((0,1)\) è di minimo per \(f\).
Giusto per completezza, se \(R < \sqrt{3}\) allora \(t=1\) non è di minimo per \(\phi\), dunque non lo è nemmeno per \(f\).
Grazie mille,
capisco il tuo ragionamento (chiarissimo) e mi hai convinto.
Però sono quasi sicuro che adesso, se calcolo la risultante delle forze sul minimo, non è nulla.
Poniamo che sia $R=\sqrt{3}$, sempre pesi tutti unitari.
I due pesi sull'asse $X$ tirano verso il basso con un forza di 1+1=2 (le loro due trazioni lungo l'asse $X$ si bilanciano).
Ora, il peso attaccato al minimo in $(0,1)$ si opporrà allo spostamento, ma con una forza uguale a 1 ...
Ho l'impressione che sia come avere una massa appesa ad un tavolo, con peso di 1 Newton, e tirarlo verso l'alto con una forza di 2 Newton ...
Cosa mi perdo?
capisco il tuo ragionamento (chiarissimo) e mi hai convinto.
Però sono quasi sicuro che adesso, se calcolo la risultante delle forze sul minimo, non è nulla.
Poniamo che sia $R=\sqrt{3}$, sempre pesi tutti unitari.
I due pesi sull'asse $X$ tirano verso il basso con un forza di 1+1=2 (le loro due trazioni lungo l'asse $X$ si bilanciano).
Ora, il peso attaccato al minimo in $(0,1)$ si opporrà allo spostamento, ma con una forza uguale a 1 ...
Ho l'impressione che sia come avere una massa appesa ad un tavolo, con peso di 1 Newton, e tirarlo verso l'alto con una forza di 2 Newton ...
Cosa mi perdo?
Se il minimo sta in uno dei punti \(y_i\), dal punto di vista dell'interpretazione fisica è come avere una reazione vincolare in \(y_i\); quando la risultante vince la reazione vincolare massima, il minimo si "schioda" da \(y_i\).
In pratica, se la risultante \(R\) delle (altre) forze in \(y_i\) ha intensità che non supera \(w_i\), in \(y_i\) hai una reazione vincolare uguale e contraria a \(R\), e \(y_i\) è il minimo.
In pratica, se la risultante \(R\) delle (altre) forze in \(y_i\) ha intensità che non supera \(w_i\), in \(y_i\) hai una reazione vincolare uguale e contraria a \(R\), e \(y_i\) è il minimo.
Capisco, e sono persuaso di quello che dici.
Quello che mi crea problemi, è che nell'esempio che mi hai fatto:
con $R=\sqrt{3}$, il minimo è in $y_3$, come tu mi hai dimostrato. (ho visto poi che questo è uno dei casi dimostrati geometricamente da Torricelli),
A me sembra che la risultante su $y_3$ sia di intensità 2, mentre la reazione vincolare massima è il peso, cioè 1.
Allora, questo punto $y_3$ non dovrebbe spostarsi in queste condizioni?
Sto prendendo un granchio colossale?
Tu che risultante vedi?
Quello che mi crea problemi, è che nell'esempio che mi hai fatto:
"Rigel":
\(m=3\) e pesi unitari, se \(y_1=(-R,0)\), \(y_2 = (R, 0)\), \(y_3=(0,1)\)
con $R=\sqrt{3}$, il minimo è in $y_3$, come tu mi hai dimostrato. (ho visto poi che questo è uno dei casi dimostrati geometricamente da Torricelli),
A me sembra che la risultante su $y_3$ sia di intensità 2, mentre la reazione vincolare massima è il peso, cioè 1.
Allora, questo punto $y_3$ non dovrebbe spostarsi in queste condizioni?
Sto prendendo un granchio colossale?
Tu che risultante vedi?
"iorfus":
Capisco, e sono persuaso di quello che dici.
Quello che mi crea problemi, è che nell'esempio che mi hai fatto:
[quote="Rigel"] \(m=3\) e pesi unitari, se \(y_1=(-R,0)\), \(y_2 = (R, 0)\), \(y_3=(0,1)\)
con $R=\sqrt{3}$, il minimo è in $y_3$, come tu mi hai dimostrato. (ho visto poi che questo è uno dei casi dimostrati geometricamente da Torricelli),
A me sembra che la risultante su $y_3$ sia di intensità 2, mentre la reazione vincolare massima è il peso, cioè 1.
Allora, questo punto $y_3$ non dovrebbe spostarsi in queste condizioni?
Sto prendendo un granchio colossale?
Tu che risultante vedi?[/quote]
In \(y_1\) e \(y_2\) le "forze" agenti sono rispettivamente \(F_1 = (-\sqrt{3}/2, -1/2)\) ed \(F_2 = (\sqrt{3}/2, -1/2)\), la cui somma è \((0, -1)\), che viene compensata dalla "reazione vincolare" \(R = (0,1)\) in \(y_3\).
Ok prendevo un granchio, confondevo il peso w=1 con il modulo del vettore, che è 2. Questo perché quando dieci anni fa studiavo i doagrammi delle forze, disegnavo i vettori proporzionali al loro modulo.
Grazie
Grazie
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo