11
$\begingroup$

Edit: Even though there is an accepted answer, the problem isn't solved. I only accepted the answer, because there was a bounty on the question so I had to accept an incomplete answer.

I was working on a problem in discrete matematics, and reduced it to a more analytical problem. I was hoping that we could use some analytical tecniques to solve it, but I don't know of any.

A special case of the reduced problem is: Consider the 3-simplex

$\Delta^3= \{ (x_1,x_2,x_3,x_4)|0\leq x_1,x_2,x_3,x_4\leq 1, x_1+x_2+x_3+x_4=1\}$
and functions $f:\Delta^3\to [0,1]$. We want to find the greatest such function satisfying

  • $f(½,0,½,0)=f(0,½,0,½)=½$
  • If we restrict $f$ to any plane that contains both $(1,0,0,0)$ and $(0,1,0,0)$ we get a convex function
  • If we restrict $f$ to any plane that contains both $(0,0,1,0)$ and $(0,0,0,1)$ we get a convex function

Here we say that $f$ is greater than $g$ if $f(x)\geq g(x)$ for all $x\in\Delta^3$. It is clear that there exists a greatest function satisfying the above since it is just the supremum of all functions satisfying the above. In particular, I would like to know if $f$ had to be convex on all of $\Delta^3$ and to know the value of $f(1/4,1/4,1/4,1/4)$.

Is there a known theory for solving this kind of problems?

Edit: I would also be interested to know a proof or disproof that the algorithm described in David Speyers community wiki-answer give the function we are looking for in a finite number number of steps (in the limit it does).

$\endgroup$
16
  • $\begingroup$ So basically, we are searching for something better than $(x_1+x_2+x_3+x_4)/2$. $\endgroup$
    – Suvrit
    Commented Nov 23, 2011 at 22:01
  • 1
    $\begingroup$ $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. $\endgroup$ Commented Nov 23, 2011 at 22:13
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Nov 23, 2011 at 22:48
  • 2
    $\begingroup$ 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. $\endgroup$
    – fedja
    Commented Nov 24, 2011 at 2:10
  • 1
    $\begingroup$ 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... $\endgroup$ Commented Jan 23, 2012 at 9:12

3 Answers 3

4
$\begingroup$

Just writing down for the record why the best answer can't beat $2/3$.

Look at the plane $z=0$. From $f(0,1,0,0) \leq 1$ and $f(1/2, 0, 1/2, 0) \leq 1/2$, we see that $f(1/3,1/3,1/3,0) \leq 2/3$. Similar arguments show that all cyclic permutations of $(1/3,1/3,1/3,0)$ also have $f \leq 2/3$.

Look at the plane $y=z$. From the known bounds for $f(0,1/3,1/3,1/3)$ and $f(1/3,0,1/3,1/3)$ we deduce that $f(1/6,1/6,1/3,1/3) \leq 2/3$. Similarly $f(1/3,1/3,1/6,1/6) \leq 2/3$.

Now the line segment from $(1/3, 1/3, 1/6, 1/6)$ to $(1/6, 1/6, 1/3, 1/3)$ lies in the plane $y=z$, so $f \leq 2/3$ everywhere on this segment. In particular, $f(1/4, 1/4, 1/4, 1/4) \leq 2/3$.

$\endgroup$
1
  • $\begingroup$ I'm pretty sure that this has most of the solution in it. The maximum should be piece-wise linear. Perhaps a constant 2/3 if the maximum entry is no larger than 1/3 and outside there shrinking to 1/2 in some places and increasing to 1 in others. I suspect it will be (for me) messy intermediate formulas leading to a less messy final description. I'll post it if I work it out. $\endgroup$ Commented Jan 26, 2012 at 18:33
1
$\begingroup$

This answer is to record a sequence of upper bounds which I have been building. I am coming to believe that the correct answer is $2/3$, but I don't have a construction which achieves it.

Looking at the line segment from $(1,0,0,0)$ to $(0,1/2,0,1/2)$, at a point of the form $(u,v,0,v)$ with $u+2v=1$, the function $f$ is at most $u+v$. The same is true for points of the form $(v,u,v,0)$, $(0,v,u,v)$ and $(v,0,v,u)$.

Look at the convex hull of $(0,0,a,b)/(a+b)$, $(a,0,a,b)/(2a+b)$ and $(0,b,a,b)/(a+2b)$. At the first vertex, $f \leq 1$. From the previous paragraph, $f$ is bounded by $(a+b)/(2a+b)$ and $(a+b)/(a+2b)$ at the second and third vertices. In short, at all three vertices of this triangle, $f(w,x,y,z) \leq y+z$. Since this triangle is contained in the plane $by=az$, which contains $(\ast, \ast, 0,0)$, we conclude that we have the bound $f(w,x,y,z) \leq y+z$ throughout this triangle.

After some algebra, one works out that, whenever $wz+xy \leq yz$ we have the bound $f(w,x,y,z) \leq y+z$.

Symmetrically, if $wz+xy \leq wx$, then $f(w,x,y,z) \leq w+x$.

That was the pain-free part.


Let's restrict our attention to the plane $qy = pz$, where $p+q=1$. This meets $\Delta$ in a triangle whose corners are $(0,0,p,q)$, $(1,0,0,0)$ and $(0,1,0,0)$. We can parameterize it as $(w,x,p(1-w-x), q(1-w-x))$, subject to the inequalities $w \geq 0$, $x \geq 0$, $w+x \leq 1$.

The inequality $wz+xy \leq yz$ turns into $(1-p^2) w + (1-q^2) x \leq pq$, a line cutting off one corner of the triangle. Let $r$ and $s$ be the end points of this line segment. The inequality $wz+xy \leq wx$ turns into a hyperbola, passing through the two corners $(w,x)=(1,0)$ and $(w,x)=(0,1)$ and through the centroid $(w,x) = (1/3, 1/3)$. The equation in $w$ and $x$ coordinates should be something like $px(1-2w-x) + qw(1-w-2x)=0$. Let $C$ be portion of the hyperbola which lies inside the triangle.

So, on two regions of the triangle we have bounds. Those bounds then imply, by convexity, bounds on the rest of the triangle. Here is what those bounds are.

Let $t$ be the point on $C$ where $(w+x-y-z)/(wz+xy-yz)$ is minimized.

On $\mathrm{Hull}(r,s,t)$, we know that $f$ is bounded by the linear function which is equal to $y+z$ on the line $rs$ and equal to $w+x$ at $t$. Of course, this would be true for any $t$ on the curve $C$, but we get the best bounds by choosing $t$ as above. I have not worked out explicit formulas for this, but I will report that, in the special case $(p,q) = (1/2, 1/2)$, it gives the upper bound of $2/3$ through the triangle $$\mathrm{Hull}( (0,1/3,1/3,1/3,), (1/3,0,1/3,1/3), (1/3,1/3,1/6,1/6) ),$$ which includes the point $(1/4, 1/4, 1/4, 1/4)$.

We have so far given bounds on the triangle $\mathrm{Hull}( (0,0,p,q), r, s)$; on the triangle $\mathrm{Hull}(r,s,t)$, and on one side of the hyperbola $C$. This leaves two regions left over. One is bounded by a portion of $C$, the line segment $rt$, and the line segment from $r$ to $(1,0,0,0)$. For $(w,x,y,z)$ in this region, one gets the best bound by drawing the line segment from $r$ to $(w,x,y,z)$, extending it until it meets $C$, and bounding $f$ by the function which linearly interpolates between the known bounds at $r$ and at $C$.

Similarly, on the region which is bounded by the line segment $st$, the line segment from $s$ to $(0,1,0,0)$ and a portion of $C$, the best bound is interpolating linearly on each line segment from $s$ to $C$.


Now, we could play the game again. We just got bounds throughout the simplex, using planes which contain $(\ast, \ast, 0,0)$. We could restrict those bounds to triangles containing $(0,0,\ast, \ast)$. The resulting function probably would not be convex, so we could take its lower convex hull, getting better bounds. But this computation was too painful for me to want to attempt it.

$\endgroup$
3
  • $\begingroup$ @David: Thanks for thinking about the problem. Did you receive my email yesterday? $\endgroup$ Commented Jan 24, 2012 at 13:09
  • $\begingroup$ Yup, I got it. Doesn't give me any more ideas. $\endgroup$ Commented Jan 24, 2012 at 13:56
  • $\begingroup$ Yes sounds right, unpleasant calculations with coefficients like x3/(x3+2x4) and fractions, possibly leading to the conclusion that f is either 2/3 or $1-x_i$ for a certain $i$. $\endgroup$ Commented Jan 26, 2012 at 19:24
0
$\begingroup$

Here is my progress report, much of which was anticipated by earlier answers. I will look for $g=1-f.$ We want $g$ to be as small as possible subject to the constraint that on each interval $g \ge g*$ where $g*$ is the linear function taking the same value at the endpoints. Then at each point there is an explicit constraint which forces the value, otherwise we could slightly decrease the value of $g$ without resulting in an increase elsewhere. On the 4 vertices of the domain we can thus have $g=0.$ Then we can also have $g=0$ on 4 of the 6 edges while $g([a,0,b,0])=\min(a,b)$ and, in general, on the boundary $g([a,0,b,d])=g([a,b,c,0])=\min(a,c)$ and $g([0,b,c,d])=g([a,b,0,d])=\min(a,d).$ Consider now a point$[a,b,c,d]$ with $\min(a,b,c,d) \gt 0.$ It is in two triangles where the constraints must hold. One has vertices $P=[1,0,0,0]$,$Q=[0,1,0,0]$,$R=[0,0,\frac{c}{c+d},\frac{d}{c+d}].$ We have already determined that $g$ is $0$ on $PQ.$ Consider the $S=[\frac{c}{2c+d},0,\frac{c}{2c+d},\frac{d}{2c+d}]$ on $PR.$ We know that $g([x,0,z,w])$ increases linearly from $0$ at $P$ to $\frac{c}{2c+d}$ at $S$ and then decreases linearly to $0$ at $R.$ Similarly, $g$ increases along $QR$ to $\frac{d}{c+2d}$ at $T=[0,\frac{d}{c+2d},\frac{c}{c+2d},\frac{d}{c+2d}]$ starting with $0$ at $Q$ and then decreases to $0$ again at $R$. Assume that $c \ge d.$ Then in the triangle $PQS$ we have $g([x,y,z,w])\ge x$ as this holds at the 3 vertices. And in triangle $SRT$ we have $g([x,y,z,w]) \ge x+y.$ This leaves the triangle $SQT$ where we have $g([x,y,z,w]) \ge \frac{c-d}{c}x+\frac{d}{c}z$ (note that $\frac{d}{c}z=w$ holds in this entire triangle so the bounds can the written in various ways.) So looking at this triangle we know that (assuming $c \ge d$) $g([a,b,c,d])$ is at least $c$, $\frac{c-d}{c}a+\frac{d}{c}c=(1-\frac{d}{c})a+d$ or $a+b$ according as $c \le a$ or $a \le c$ but $d(c-a) \le b$ or $d(c-a) \ge b.$ The points $abcd,adcb,cbad,cdab,dcba,bcda,dabc,badc$ should all have equal $g$ values so we can combine all these constraints. I can't quite see yet what all these constraints give nor if further steps are needed.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .