Pagina 1 di 2

73. Problema di minimo dal sapore ungherese

Inviato: 05 mag 2014, 22:27
da machete
Sia $XYZ$ un triangolo isoscele e rettangolo in $X$ con cateti unitari. Trovare, al variare di $P$ all' interno di esso, il minimo di:
$$
f(P)=14 \cdot PX+13\cdot PY+15\cdot PZ
$$
Ho tratto l' idea per questo problema dal problema 20 della Kavics Kupa 2014. In realtà più che il numero mi interessa il procedimento e se avete un algoritmo per risolverlo (magari con conti arbitrariamente brutti, ma sempre "algebrici") nel caso di tre pesi "generici" (io per il momento credo di averlo solo se i pesi sono lati di un triangolo. . . )

Dunque buon divertimento, o geometri, spero di esser stupito con soluzioni eleganti e concise e profonde :D

Re: 73. Problema di minimo dal sapore ungherese

Inviato: 16 mag 2014, 20:51
da machete
Metto un hint(one?) verso l' idea che ho usato io:
Testo nascosto:
guardate come questo tizio risolve il problema di trovare in un triangolo il punto che minimizza la somma delle distanze dai vertici:
http://www.youtube.com/watch?v=uP8V-O8hncI

Re: 73. Problema di minimo dal sapore ungherese

Inviato: 18 mag 2014, 18:07
da Drago96
Wow, figo il fatto che il gradiente della distanza è un versore radiale! :D
Boh, poi magari tento dei conti, ora purtroppo non posso :(

Re: 73. Problema di minimo dal sapore ungherese

Inviato: 21 mag 2014, 16:14
da machete
Vero? :) E' un fatto semplice ma che porta immediatamente ad una caratterizzazione del minimo! In ogni caso serve dell' altro lavoro per trovare il risultato! (che, grazie ai numeri dati, è bello)

Re: 73. Problema di minimo dal sapore ungherese

Inviato: 21 mag 2014, 16:29
da Drago96
Ehi, idea al volo: i tre vettori devono avere somma 0, ovvero devono formare una spezzata chiusa; ma sono i lati di un triangolo, quindi possiamo ricavare i vari angoli grazie a Carnot. Ovvero, detto $\alpha $ l'angolo tra quello da 13 e quello da 15 abbiamo $14^2=13^2+15^2-2\cdot14\cdot15\cdot\cos (\pi-\alpha) $, da cui ricaviamo i tre angoli e quindi con qualche altro conto si dovrebbe riuscire a determinare il valore della funzione (sempre Carnot, suppongo)
Mi scuso per la soluzione a spezzoni, ma proprio non ho tempo :(

Re: 73. Problema di minimo dal sapore ungherese

Inviato: 21 mag 2014, 18:22
da machete
Bene Drago :D l'idea del triangolo è giusta e proficua, ma ovviamente va sviluppata a modino! Quando hai un po' di tempo butta giù il procedimento fino alla fine e fai il contozzo, uscirne senza morire è (la) parte (facile) dell' esercizio!

p.s. : e ricorda che l' annullarsi del gradiente è necessario, non sufficiente alla minimezza!

p.p.s. : e, IMPORTANTISSIMO, non dimenticare di controllare i bordi dei bordi!

Re: 73. Problema di minimo dal sapore ungherese

Inviato: 21 mag 2014, 20:49
da fph
machete ha scritto: p.s. : e ricorda che l' annullarsi del gradiente è necessario, non sufficiente alla minimezza!

p.p.s. : e, IMPORTANTISSIMO, non dimenticare di controllare i bordi dei bordi!
Sbaglio o anche il tizio del tuo video non si preoccupa troppo dei bordi e della differenza tra "gradiente nullo" e "minimo"?

Re: 73. Problema di minimo dal sapore ungherese

Inviato: 22 mag 2014, 16:37
da Drago96
Orbene, tentiamo quest'arrembaggio all'analisi in più variabili...
Intanto mettiamo questo nostro triangolo, che se non ti dispiace chiamerò $\triangle ABC$, nel piano $Oxy$, in modo che $A=(0,0),B=(1,0),C=(0,1)$.
Prendiamo un generico punto $P$ di coordinate $(x,y)$ e definiamo $$f_A(x,y)=dist(P,A)=\sqrt{x^2+y^2} \\ f_B(x,y)=dist(P,B)=\sqrt{(x-1)^2+y^2} \\ f_C(x,y)=dist(P,C)=\sqrt{x^2+(y-1)^2}$$
Ovviamente quindi $$f(x,y)=14\cdot f_A(x,y)+13\cdot f_B(x,y)+15\cdot f_C(x,y)$$
Sfruttando ora il fatto che la derivata di $g(x)=\sqrt x$ è $g'(x)=\dfrac1{2\sqrt x}$, ci calcoliamo il gradiente delle tre funzioni, che risulta essere (risparmiatemi i passaggi stupidi) $$\nabla f_A(x,y)=\left\langle\dfrac{x}{\sqrt{x^2+y^2}},\dfrac{y}{\sqrt{x^2+y^2}}\right\rangle \\ \nabla f_B(x,y)=\left\langle\dfrac{x-1}{\sqrt{(x-1)^2+y^2}},\dfrac{y}{\sqrt{(x-1)^2+y^2}}\right\rangle \\ \nabla f_C(x,y)=\left\langle\dfrac{x}{\sqrt{x^2+(y-1)^2}},\dfrac{y-1}{\sqrt{x^2+(y-1)^2}}\right\rangle$$
Come ben si nota, ciascuno di essi è un vettore di lunghezza unitaria, la cui direzione è la stessa della retta che collega $P$ al rispettivo vertice e il cui verso è dalla parte opposta del vertice rispetto a $P$.
Il gradiente della somma è ovviamente la somma dei gradienti per la linearità della derivata; per trovare un punto critico -che speriamo vivamente essere il minimo-, dobbiamo imporre $$\nabla f(x,y)=\langle0,0\rangle$$ quindi alla fine ci troviamo a dover sistemare tre vettori di lunghezza $13,14,15$ in modo che sommino $0$.
Allora, notiamo intanto che sono le misure dei lati di un triangolo (per disuguaglianza triangolare -- inoltre $13=6+7,14=6+8,15=7+8$), quindi se li disponiamo a triangolo con i versi tutti nello stesso senso otteniamo una figura chiusa, ovvero la somma vettoriale è nulla. (occhio: in realtà non li possiamo disporre a triangolo, devono avere il punto di applicazione in comune, ma basta traslarli) Ora inizia la parte di conti!
Chiamiamo $\alpha$ l'angolo che c'è tra il vettore di $13$ e quello di $15$, che è uguale all'angolo $\angle BPC$; definiamo similmente $\beta$ e $\gamma$. Ora con un bel disegnino vediamo che se trasliamo i vettori a formare un triangolo, i suoi angoli sono di $\pi-\alpha$ e cicliche; quindi con Carnot ci calcoliamo i coseni: $$14^2=13^2+15^2-2\cdot13\cdot15\cdot\cos(\pi-\alpha) \\ 13^2=14^2+15^2-2\cdot14\cdot15\cdot\cos(\pi-\beta) \\ 15^2=13^2+14^2-2\cdot13\cdot14\cdot\cos(\pi-\gamma)$$ ovvero $$\displaystyle \cos\alpha=-\frac{33}{65},\;\;\cos\beta=-\frac{3}{5},\;\;\cos\gamma=-\frac{5}{13}$$
abbiamo fatto un passettino avanti, ma dobbiamo determinare $AP,BP,CP$... intanto diamogli un nome decente: $AP=a$ e cicliche; dato che mi voglio male, tento di impostare un sistema con Carnot, che alla peggio si risolverà con wolframalpha...
$$\begin{cases}2=b^2+c^2-2bc\cos\alpha \\ 1=c^2+a^2-2ac\cos\beta \\ 1=a^2+b^2-2ab\cos\gamma \end{cases}$$
Ora, WA ci dice che per la soluzione di questo sistema vale $f(P)=\sqrt{730}$, ma sinceramente non saprei risolvere quel sistema, se non provando a sostituire cose (e ciò è molto male in un sistema di secondo grado), quindi potrebbe esserci un metodo più intelligente per trovare il nostro caro $P$.
Bene, abbiamo quindi ricavato (prima o poi tenterò di ricavarlo da me) che in corrispondenza del punto in cui si annulla il gradiente abbiamo $f(P)=\sqrt{730}$; siamo già molto felici che il punto critico sia uno solo, controlliamo solo che sia un minimo e non un massimo (e se così non fosse, uno si arrabbia di brutto): prendiamo ad esempio il circocentro e otteniamo $f(O)=\dfrac{\sqrt2}2(13+14+15)=21\sqrt2$, che è fortunatamente maggiore di $f(P)$. Ora suppongo che questo mi basti a concludere: dovrei controllare sui bordi per vedere se ho un valore più basso, anche se il gradiente non si annulla (cosa che può accadere), ma questo non dovrebbe poter succedere dato che per scendere dovrei risalire, ma non ho un altro punto critico; non so se sia legittimo quello che ho detto, se no mi servirebbe una cosa tipo convessità della funzione, che si dovrebbe fare controllando la positività della derivata rispetto a $x$ dellla componente $x$ del gradiente e la stessa cosa con $y$... (in questo caso effettivamente vengono entrambi positivi)
Qualcuno mi aiuta a formalizzare l'ultima parte? :)

Re: 73. Problema di minimo dal sapore ungherese

Inviato: 22 mag 2014, 17:38
da <enigma>
Prendi $f(x,y)=x^3+y^3$ e un qualsiasi triangolo per cui $(0,0)$ è un punto interno, ripetendo il ragionamento col gradiente: cosa ottieni?
La derivata seconda (più precisamente l'Hessiana di $f$) basta, ma non liquidare con leggerezza quel che succede sul bordo (e finisci i conti) :wink:

Re: 73. Problema di minimo dal sapore ungherese

Inviato: 22 mag 2014, 17:47
da <enigma>
Giusto per tua cultura: $f \in \mathcal C^2(K)$ è convessa in $K$ se e solo se l'Hessiana di $f$ in $K$ è semidefinita positiva. O-equivalenza che torna più utile computazionalmente-se e solo se gli autovalori dell'Hessiana sono non negativi.

Re: 73. Problema di minimo dal sapore ungherese

Inviato: 22 mag 2014, 18:48
da Drago96
<enigma> ha scritto:Prendi $f(x,y)=x^3+y^3$ e un qualsiasi triangolo per cui $(0,0)$ è un punto interno, ripetendo il ragionamento col gradiente: cosa ottieni?
Che l'unico punto critico è $(0,0)$, ma nel primo e nel terzo quadrante cresce e decresce a volontà... il fatto è che appunto non è "convessa"...
<enigma> ha scritto:La derivata seconda (più precisamente l'Hessiana di $f$) basta, ma non liquidare con leggerezza quel che succede sul bordo (e finisci i conti) :wink:
Uhm, vedrò di studiarmelo... però scusa: se io prendo un piano $x=k$ e seziono la funzione, e vedo che per ogni $k$ la mia funzione "sezionata" è convessa (sul piano), e anche per quanto riguarda l'altra variabile prendendo i piani $y=k$ ho tutte funzioni convesse (sul piano), mi basta a poter dire che la funzione nello spazio è convessa? Perché? Perché no?
Per i bordi, cosa intendi? Cosa dovrei controllare bene?

Re: 73. Problema di minimo dal sapore ungherese

Inviato: 22 mag 2014, 21:30
da Kfp
forum ha scritto:Geometria
Drago96 ha scritto: Analisi in più variabili
Non c'è più religione.

Re: 73. Problema di minimo dal sapore ungherese

Inviato: 22 mag 2014, 21:46
da Troleito br00tal
Kfp ha scritto:
forum ha scritto:Geometria
Drago96 ha scritto: Analisi in più variabili
Non c'è più religione.
Più che altro come cazzo faceva sto problema a stare in una gara per liceali...

Re: 73. Problema di minimo dal sapore ungherese

Inviato: 23 mag 2014, 14:30
da <enigma>
Drago96 ha scritto:Uhm, vedrò di studiarmelo... però scusa: se io prendo un piano $x=k$ e seziono la funzione, e vedo che per ogni $k$ la mia funzione "sezionata" è convessa (sul piano), e anche per quanto riguarda l'altra variabile prendendo i piani $y=k$ ho tutte funzioni convesse (sul piano), mi basta a poter dire che la funzione nello spazio è convessa? Perché? Perché no?
Prendi $f(x,y)=x^2y^2$ nel primo quadrante. La restrizione a qualsiasi retta parallela agli assi coordinati è convessa? Ci mancherebbe altro, è una parabola convessa. La funzione è convessa? Come no...

Non bastano le derivate seconde. Volendo proprio riformulare la condizione che ho scritto in termini di derivate seconde, un'equivalenza è:
$f \in \mathcal C^2(K)$ è convessa nel convesso $K$ $\iff$ $\partial_{xx}f \geq 0$, $\partial_{yy}f \geq 0$ e $\partial_{xx}f\ \partial_{yy}f \geq (\partial_{xy}f)^2$ in $K$.

Re: 73. Problema di minimo dal sapore ungherese

Inviato: 23 mag 2014, 23:38
da Gottinger95
Comunque, che la funzione distanza sia convessa lo si può verificare facilmente anche geometricamente: prendiamo un punto \(P\) di riferimento, e due punti \(A,B\) nel piano. Convessità vorrebbe che, detta \( f(\vec{X})\) la funzione distanza da \(P\), per qualsiasi \(t \in [0,1]\) si abbia
\[ f( t \cdot \vec A + (1-t) \cdot \vec B ) \le t \cdot f(\vec A) + (1-t) \cdot f( \vec B) \]
Sia \(C\) il punto sul segmento \(AB\) tale che \(AC = t \cdot AB\). Prendiamo un punto \(A'\) su \(AP\) tale che \(CA'\) sia parallelo a \(BP\): per talete \(PA'\) misura \(t \cdot AP\). Similmente definiamo \(B'\). Allora abbiamo, per disuguaglianza triangolare (e per \( B'P \parallel CA'\) )
\[ t \cdot f (\vec A) + (1-t) \cdot f(\vec B) = t \cdot AP + (1-t) \cdot BP = A'P + B' P = A'P + CA' \ge CP = f( t \cdot \vec A + (1-t) \cdot \vec B )\]