[A] funzioni piu\'-che-convesse

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
sprmnt21
Messaggi: 559
Iscritto il: 01 gen 1970, 01:00

Messaggio da sprmnt21 » 01 gen 1970, 01:33

f: R -> R
<BR>f is very convex if for any two x, y holds: (f (x) + f (y)) / 2 >= f ((x + y) /2) + |y - x|. Prove that no very convex function exists!
<BR>
<BR>PS
<BR>dai miei appunti sembra che la fonte sia una sessione PUTNAM, ma piu\' non so.
<BR>
<BR>e\' corretto il tag [A] per questo tipo di problemi o ce n\'e\' uno piu\' specifico?
<BR>
<BR>

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go » 01 gen 1970, 01:33

uhm.. forse [A+]...
<BR>intanto ci penso <IMG SRC="images/forum/icons/icon_biggrin.gif">

Avatar utente
MASSO
Messaggi: 134
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza\Pisa

Messaggio da MASSO » 01 gen 1970, 01:33

Supponiamo che esista tale funzione,
<BR>sia k=f(0)
<BR>poniamo ora x=x e y=0 nellla relazione di partenza ed avremo:
<BR>(f(x)+k)/2>=f(x)/2 + |x|
<BR>k/2>=x per ogni x incluso a R
<BR>ma per qualsiasi k fissato si può trovare un x che smentisce tale affermazione e perciò le ipotesi sono false<BR><BR>[ Questo Messaggio è stato Modificato da: MASSO il 19-01-2005 13:20 ]

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-19 13:19, MASSO wrote:
<BR>(f(x)+k)/2>=<font color = red>f(x)/2</font> + |x|
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>No, Masso. Leggi meglio la condizione di piuccheconvessità. Avresti dovuto scrivere <!-- BBCode Start --><B>f(x/2)</B><!-- BBCode End -->...
<BR>
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
MASSO
Messaggi: 134
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza\Pisa

Messaggio da MASSO » 01 gen 1970, 01:33

si, hai perfettamente ragione, in effetti mi pareva troppo semplice, va be torno a ragionarci su

santambroeus
Messaggi: 3
Iscritto il: 01 gen 1970, 01:00

Messaggio da santambroeus » 01 gen 1970, 01:33

Non e\' chiaro se la funzione in questione sia convessa o no (nel senso che si impone una disuguaglianza solo sui punti medi e non per ogni punto del tipo $tx+(1-t)y$, con $t\\in [0,1]$). Assumiamo pero\' che lo sia. L\'idea allora e\':
<BR>
<BR>Una funzione convessa ammette in ogni punto $x$ interno al suo dominio derivata destra $f\'_+(x)$ finita. Calcoliamo ora il rapporto incrementale:
<BR>$$\\frac{f(x+\\ve)-f(x)}{\\ve}=\\frac{2\\frac{f(x+\\ve)+f(x)}{2}-2f(x)}{\\ve}\\geq\\frac{2[f(x+\\frac{\\ve}{2})+\\ve]-2f(x)}{\\ve}=2+2\\frac{f(x+\\frac{\\ve}{2})-f(x)}{\\ve}$$
<BR>e passiamo al limite per $\\ve>0$ che tende a $0$: otteniamo
<BR>$$f\'_+(x)\\geq 2+f\'_+(x),$$
<BR>un assurdo.
<BR>
<BR>
<BR>Credo che nel caso che la $f$ non sia a priori convessa si possa ragionare solo sui diadici e ottenere la stessa cosa.
<BR>
<BR>Ciao, Filippo
<BR>

MindFlyer

Messaggio da MindFlyer » 01 gen 1970, 01:33

Ciau Santaclaus, e benvenuto fra noi!
<BR>Dato che il problema dovrebbe essere un Putnam, forse è il caso di trovare una soluzione olimpica, che probabilmente esiste!
<BR>Sarebbe anche il caso di vedere se l\'ipotesi di convessità sia davvero necessaria.

santambroeus
Messaggi: 3
Iscritto il: 01 gen 1970, 01:00

Messaggio da santambroeus » 01 gen 1970, 01:33

Vuoi dire niente derivate? OK, però i rapporti incrementali sì, quelli si possono fare, sono solo divisioni!
<BR>il conto che ho fatto prima dice che il rapporto incrementale di $f$ fatto in $x$ rispetto ad altri punti, nel passare da $x+\\epsilon$ (scusate, nell\'altra mail ho scritto $\\ve$ per mia abbreviazione) a $x+\\epsilon / 2$ diminuisce di almeno 2. Facendo i conti in modo analogo sui rapporti incrementali a sinistra di $x$ si ottiene che lì nel passare da $x-\\epsilon$ a $x-\\epsilon / 2$ aumenta di almeno 2. Questo in pratica vuol dire che le pendenze di $f$ vicino a $x$ diventano sempre più \"decrescenti\" da entrambi i lati di $x$. In particolare, se prendo punti del tipo $x-epsilon / 2^k$ e $x+epsilon / 2^k$ con $x$ in mezzo, per $k$ sufficientemente grande avrò una situazione in cui per passare dal primo di questi tre punti a $x$ e poi all\'altro, la $f$ prima sale e poi scende. Questo non succede nemmeno in una funzione convessa, figuriamoci in queste piucheconvesse! intendo dire che realmente questo farebbe venir meno la disuguaglianze richiesta per la piucheconvessità. siccome in questo si usano solo punti medi e non si usa la vera convessità di $f$, direi che anche la questione se serve aggiungere convessità o continuità o altro è forse risolta.
<BR>
<BR>spero di avere soddisfatto almeno parzialmente il tuo desiderio di soluzioni olimpiche; quanto ai tuoi desideri natalizi (da come mi hai chiamato nel messaggio scorso), mi spiace, ma al posto di un molto nordico santaclaus ti dovrai accontentare di un un po\' meno nordico santambroeus !
<BR>
<BR>CiaoCiao

MindFlyer

Messaggio da MindFlyer » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-02-09 00:32, santambroeus wrote:
<BR>direi che anche la questione se serve aggiungere convessità o continuità o altro è forse risolta.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Senza forse, il tuo metodo funziona perfettamente!
<BR>Prima non ti volevo contraddire, ma solo invitarti (ed invitare tutti) a produrre una dimostrazione elementare, ricordando che questo forum è popolato da gente (la cosiddetta maggioranza silenziosa) che non ha mai sentito parlare di rapporti incrementali, etc.
<BR>
<BR>Ti sarai accorto che il forum non interpreta le formule scritte in LaTeX: questo è sempre stato un problema. Ma le nostre pene stanno per finire, perché nel nuovo forum (online tra breve) ci sarà auspicabilmente anche il supporto LaTeX!! Mai più formule incomprensibili (speriamo...)!
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>spero di avere soddisfatto almeno parzialmente il tuo desiderio di soluzioni olimpiche
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Altroché! Ti ricordi quella pubblicità?
<BR>- santambroeus, avverto un leggero languorino...
<BR>- Gradisce una dimostrazione con derivate e passaggi al limite?
<BR>- Ma la mia non è proprio fame: è più... voglia di qualcosa di buono!
<BR>- Capisco, MindFlyer.
<BR>Così santambroeus preme un pulsante e parte la dimostrazione olimpica.
<BR>- santambroeus, sai sempre stupirmi!
<BR>- Grazie, MindFlyer.

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 01 gen 1970, 01:33

Ciao.
<BR>
<BR>Eh, eh, eh, finalmente qualcun altro si è lanciato a risolverlo.
<BR>
<BR>Anch\'io ho la mia soluzione a questo problema graziosissimo, che tenevo in serbo da un po\'...
<BR>
<BR>----------------------------------------
<BR>
<BR>Sia k un reale positivo. Definisco f come <!-- BBCode Start --><B>k-piuccheconvessa</B><!-- BBCode End --> se succede che, per ogni x e y,
<BR>
<BR>[f(x) + f(y)]/2 >= f( (x+y)/2 ) + <!-- BBCode Start --><B>k</B><!-- BBCode End --> |x-y|.
<BR>
<BR>Dimostrerò che una fz. k-p.c.c. è anche 2k-p.c.c.
<BR>
<BR>Infatti:
<BR>
<BR>Sia f k-p.c.c. Fisso x_0 e x_4 distinti. Sia x_i = [ (4-i)x_0 + i x_4 ]/4, per i = 1,2,3. Sia D = |x-y|.
<BR>
<BR>Applico la condizione di piuccheconvessità alle coppie di p.ti ( x_0, x_2), ( x_1, x_3 ), ( x_2, x_4 )
<BR>
<BR>Ricavo rispettivamente:
<BR>
<BR>f(x_1) =< [ f(x_0) + f(x_2) ] / 2 - k D/2.
<BR>f(x_2) =< [ f(x_1) + f(x_3) ] / 2 - k D/2.
<BR>f(x_3) =< [ f(x_2) + f(x_4) ] / 2 - k D/2.
<BR>
<BR>Da cui, sostituendo f(x_1) e f(x_3) in quella centrale,
<BR>
<BR>f(x_2) =< [ f(x_0) + f(x_4) ] / 4 + f(x_2)/2 - k D,
<BR>
<BR>che si semplifica
<BR>
<BR>f(x_2) =<[ f(x_0) + f(x_4) ] / 2 - 2k D.
<BR>
<BR>Che, facendo variare x_0 e x_4 su tutto R, è precisamente la condizione di 2k-p.c.c.
<BR>
<BR>Se esistesse una fz. p.c.c., allora sarebbe M-p.c.c. per ogni M arbitrariamente grande. [mi risparmio di dimostrare che M-p.c.c. è via via più forte al crescere di M...]
<BR>
<BR>Ma allora f(x_2) =< [costante] - M D per ogni M, e questo è assurdo. []
<BR>
<BR>Ciao. M.
<BR>
<BR>[addsig]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

santambroeus
Messaggi: 3
Iscritto il: 01 gen 1970, 01:00

Messaggio da santambroeus » 01 gen 1970, 01:33

</BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Altroché! Ti ricordi quella pubblicità?
<BR>- santambroeus, avverto un leggero languorino...
<BR>- Gradisce una dimostrazione con derivate e passaggi al limite?
<BR>- Ma la mia non è proprio fame: è più... voglia di qualcosa di buono!
<BR>- Capisco, MindFlyer.
<BR>Così santambroeus preme un pulsante e parte la dimostrazione olimpica.
<BR>- santambroeus, sai sempre stupirmi!
<BR>- Grazie, MindFlyer.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Oh, se la ricordo! fra l\'altro, da una rapida occhiata a quello che c\'è scritto sulla mia carta d\'identità, direi che puoi proprio mettere l\'originale Ambrogio al posto del nick santambroeus.
<BR>Comunque mi sono sbellicato a leggere questo dialogo, grazie!
<BR>Vabbé, ora smetto che se no si esce dal tema matematico e si entra nel tema idiozie.
<BR>quanto invece alla dimostrazione di Marco, quella è ancora più olimpica, no?

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 01 gen 1970, 01:33

[OT]
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-02-09 03:11, MindFlyer wrote:
<BR>Ma le nostre pene stanno per finire, perché nel nuovo forum (online tra breve) ci sarà auspicabilmente anche il supporto LaTeX!! Mai più formule incomprensibili (speriamo...)!
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>..No!! Giüra!
<BR>
<BR>Peccato che la comprensibilità grafica non implichi la comprensibilità concettuale...
<BR>
<BR>EDIT: Boh, io ci ho provato a ribilanciare i quotes nel messaggio di S.Ambrogio, ma e che è, mica sono MindDrake...
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: marco il 09-02-2005 14:37 ]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

sprmnt21
Messaggi: 559
Iscritto il: 01 gen 1970, 01:00

Messaggio da sprmnt21 » 01 gen 1970, 01:33

Se sostituiamo x con (x+y)/2 nella dieguaglianza data, otteniamo che : f(x)+3f(y))/4>=f((x+3y)/4)+|y-x|.
<BR>Piu\' generalmente se consideriamo l\'ennesimo mezzo-intervallo di [x,y] cioe\' [(x+(2^n-1)y)/2^n, y], per ogni n e per ogni x, y risulta che :
<BR>
<BR>f(x)/2^n+(2^n-1)/2^n f(y) >= f((x+(2^n-1)y)/2^n)+|y-x|.
<BR>
<BR>
<BR>Per x=y-e ed x=y+e, si ha che
<BR>
<BR>f(y)>= f(y-e/2^n)+e+[f(y)-f(x-e)]/2^n
<BR>
<BR>f(y)>= f(y+e/2^n)+e+[f(y)-f(x+e)]/2^n
<BR>
<BR>
<BR>Sommando membro a membro
<BR>
<BR>
<BR>2f(y)>= f(y-e/2^n)+f(y+e/2^n)+2e+F(x,y,e,n) dove e chiaro cosa intendo con F \"grande\".
<BR>
<BR>Ma da questultima, applicando la definizione, segue che
<BR>
<BR>
<BR>2f(y)>= f(y-e/2^n)+f(y+e/2^n)+2e+F(x,y,e,n)>= 2f(y)+e/2^(n-1)+2e+F(x,y,e,n), cioe\' che
<BR>
<BR>
<BR>0 >= e/2^(n-1)+2e+F(x,y,e,n) , ma quest\'ultima per il principio di Archimede non puo\' essere perche\' fissati x ed y, per n sufficientemente grande |F| < e.
<BR>

lordgauss
Messaggi: 478
Iscritto il: 01 gen 1970, 01:00
Località: Brunswick

Messaggio da lordgauss » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>f is very convex if for any two x, y holds: (f (x) + f (y)) / 2 >= f ((x + y) /2) + |y - x|. Prove that no very convex function exists!
<BR>
<BR>PS
<BR>dai miei appunti sembra che la fonte sia una sessione PUTNAM, ma piu\' non so.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>E\' l\'esercizio 1 delle USAMO 2000

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>ora va meglio anche se la pagina in alto è spostata gli altri messaggi si capiscono tutti<BR><BR>[ Questo Messaggio è stato Modificato da: Boll il 09-02-2005 17:34 ]
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)

Bloccato

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti