Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: convex function through finite points with minimal area
Replies: 1   Last Post: May 3, 2013 9:31 PM

 Dan Luecking Posts: 26 Registered: 11/12/08
Re: convex function through finite points with minimal area
Posted: May 3, 2013 9:31 PM

On Tue, 16 Apr 2013 13:06:48 -0600, Markus
<markus.ausserhofer@hotmail.com> 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