On Tue, 16 Apr 2013 13:06:48 -0600, Markus <firstname.lastname@example.org> wrote:
> >Hello everyone, > >last week I found a question during my seminar work and couldn't solve >it. I'm wondering if anybody else wants to work on this since the >question is pretty easy but a solution turns out to be (at least) not >as easy as the question. So, > >Given function values y_i for finite x_i's in the interval (0,1) such >that the frequency polygon can be convex. What is the convex function >with the least area connecting the points (0,0) and the (x_i,y_i)'s?
I assume you mean by the frequency polygon simply the line segments connecting (0,0) and the (x_i,y_i).
I assume by convex you mean this polygon is the graph of a convex function and that this means the region above the graph is convex.
If the function you seek must be continuous and there are no other restrictions, then no such function exists unless all the points lie on a straight line through (0,0).
> >I had different ideas, the most important (and somewhat only useful) is >that I can look in the class of piecewise linear functions for the >'solution'. Furthermore, I should have n pieces and the pieces are >somehow centered at (x_i,y_i).
But if we add an additional requirement: there is an upper bound given on the slope of the function, then your idea is correct. To see why an additional requirement is needed, consider the following counter-example: the points are (0,0), (.5,0) and (1,1). For any number b in (.5,1) the polygon connecting (0,0), (b,0) and (1,1) is convex and the area below it is (1-b)/2. This can be made arbitrarily close to 0, but an area of 0 cannot be achieved with a continuous function.
But if the slope is required to be at most M, then that forces 1/(1-b) <= M and so the minimum area is 1/(2M), achieved with b = 1 - 1/M.
Assuming an upper limit on the slope it can be shown that any convex function lies above some piecewise linear one such as you describe. Thus, the minimum area over all functions is the same as the minimum area over the piecewise linear functions. Since the set of such piecewise linear functions is finite dimensional and parametrised by a compact set of parameters (the slopes of the segments) it will contain a minimizing function.
An actual computation using this idea is beyond me at the moment, but it should be feasible.
Dan To reply by email, change LookInSig to luecking