Timeline for Greatest function satisfying some convexity requirements
Current License: CC BY-SA 3.0
27 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 29, 2013 at 5:25 | comment | added | fedja | Just confirming reading the comment to free up your hands :) | |
| Jul 25, 2013 at 14:36 | comment | added | Sune Jakobsen | @fedja: We are now writing a paper about the problem that inspired this question. Your example is still the best we have, and we would like to mention you in the paper. At the moment we only know that you are "fedja from mathoverflow". If you want your real name in the paper, you can send me an email (to the address in my profile), and we can discuss how to do it. Even if you prefer "fedja from mathoverflow", please say so in a comment bellow, so we know that you have read this comment. Thanks for the example! | |
| Aug 20, 2012 at 22:13 | comment | added | Sune Jakobsen | By planes I mean 2-dimensional planes. | |
| Aug 20, 2012 at 20:34 | comment | added | Gerhard Paseman | Since the entire simplex (domain of f) lies on a (hyper-)plane, it seems to me that f(1/4,1/4,1/4,1/4) is at most 1/2, so I must be doing something wrong. For the constraints involving planes, are the planes 2-dim. or 3-dim.? Gerhard "Which Way To The Universe?" Paseman, 2012.08.20 | |
| Aug 20, 2012 at 19:22 | history | edited | Sune Jakobsen | CC BY-SA 3.0 |
added 193 characters in body
|
| Jan 29, 2012 at 19:37 | answer | added | Aaron Meyerowitz | timeline score: 0 | |
| Jan 29, 2012 at 19:22 | vote | accept | CommunityBot | ||
| Jan 29, 2012 at 19:22 | history | bounty ended | Sune Jakobsen | ||
| Jan 25, 2012 at 9:22 | history | edited | Sune Jakobsen | CC BY-SA 3.0 |
added 232 characters in body
|
| Jan 24, 2012 at 2:39 | answer | added | David E Speyer | timeline score: 1 | |
| Jan 23, 2012 at 9:12 | comment | added | Wadim Zudilin | Continuity isn't a point: the max of two convex functions is convex. Fedja's example $g(x_1,\dots,x_4)=x_1^2+\dots+x_4^2-2a(x_1x_3+x_2x_4)$ is "biconvex" for $-1\le a\le3$, because of the positivity of $g(x_1,x_2,x_3,1-x_1-x_2-x_3)$ for any fixed $x_3$; then $f=\max(0,(a+g)/(a+1))$ satisfies the constraints and $f(1/4,1/4,1/4,1/4)=(1+3a)/(4+4a)$ is maximal possible, 5/8 (for $a$ in the range), when $a=3$. A next step would be to search for a suitable biquadratic (biconvex) $g$, two many bi's though... | |
| Jan 22, 2012 at 23:00 | answer | added | David E Speyer | timeline score: 4 | |
| Jan 22, 2012 at 22:55 | comment | added | David E Speyer | Nevermind, I found the $2/3$. I'll write it up below in case it helps someone. | |
| Jan 22, 2012 at 22:34 | comment | added | David E Speyer | Would you mind writing up the proof of the $2/3$ bound? The best bound I can get is $3/4$, and I think seeing why that isn't tight would give me insight. | |
| Jan 22, 2012 at 19:15 | history | bounty started | Sune Jakobsen | ||
| Nov 24, 2011 at 20:23 | history | edited | Sune Jakobsen | CC BY-SA 3.0 |
Trying to fix the "{" in LaTeX
|
| Nov 24, 2011 at 20:01 | comment | added | Sune Jakobsen | @fedja how do you get continuity at the boundary? | |
| Nov 24, 2011 at 15:09 | comment | added | fedja | Yes, continuity is easy (the convexity directions are "spanning"). The function is even Lipschitz (though not better than that in general). But how does that help? | |
| Nov 24, 2011 at 9:05 | comment | added | Dima Pasechnik | can you at least show that your greatest function is continuous? | |
| Nov 24, 2011 at 7:53 | comment | added | Sune Jakobsen | I know that the value at the center is at most 2/3 and fedjas comment proves that it is at least 7/12. | |
| Nov 24, 2011 at 2:10 | comment | added | fedja | We can certainly do better. $g(x)=x_1^2+x_2^2+x_3^2+x_4^2-4(x_1x_3+x_2x_4)$ is "biconvex" in your sense, bounded by $1$ from above and has value $-1/4$ at the center of the simplex and the value $-1/2$ at your edge midpoints. Now just put $f=\max(0,(2+g)/3)$. It is far from optimal but it already shows that the life is not simple. | |
| Nov 23, 2011 at 22:48 | comment | added | Sune Jakobsen | Remember that the function is to [0,1]. It is not allowed to take values above 1. I think I once checked that the above function (which can also be written as $\max(x_1,x_3)+\max(x_2,x_4)$) is the greatest convex function that satisfy $f(½,0,½,0)=f(0,½,0,½)=½$. However, it could be that some greater function is convex only when restricted to the relevant planes. | |
| Nov 23, 2011 at 22:26 | comment | added | Suvrit | Sorry somehow I forgot the summation constraint; however, even the function that you mention achieves only a value of $1/2$ for the desired point $(1/4,1/4,1/4,1/4)$. | |
| Nov 23, 2011 at 22:13 | comment | added | Sune Jakobsen | $x_1+x_2+x_3+x_4=1$ so the function you mention is constantly 1/2. We can do better than that, $max(x_1+x_2,x_3+x_4,x_1+x_4,x_2+x_3)$, but I don't know if we can do even better. | |
| Nov 23, 2011 at 22:01 | comment | added | Suvrit | So basically, we are searching for something better than $(x_1+x_2+x_3+x_4)/2$. | |
| Nov 23, 2011 at 21:20 | history | edited | Sune Jakobsen | CC BY-SA 3.0 |
typo: I-> Is
|
| Nov 23, 2011 at 20:34 | history | asked | Sune Jakobsen | CC BY-SA 3.0 |