Optimizing Numerical Analysis: Finding the Smallest Maximum of g(x) on [-1,1]

[buzzmath]

Let g(x)=(x-x1)(x-x2)(x-x3) -1<=x1<x2<x3<=1 find the points x1,x2,x3 so that
max |g(x)| for x an element of [-1,1] is as small as possible.

This is the only problem I have left and I have no idea how to do it. We've been covering Newtons method and rootfinding but I don't think it relates and I don't know of a method to solve this problem. Any suggestions?

Thanks

 

[D H]

First thing to do is get rid of that nasty absolute value. You want to minimize the maximum of |g(x)|. You should be able to convince yourself that this is the same as minimizing the maximum of g(x)^2.

 

[buzzmath]

But how would you go about minimizing a function for 3 unknown constants and and variable between -1 and 1. If I take g(x)^2 and then take the derivative of that I get
2(x^3-x^2x3-x^2x2+xx2x3-x^2+xx3+xx1x2-x1x2x3)(3x^2-2xx3-2xx2+x2x3-2x+x3+x1x2) and then set the equal to zero but that won't tell me the x1 x2 x3 values but the x value for specif x1 x2 x3 points. This is the way I've minimized functions in the past. How would you minimize a function for x in an interval for many unknown constants where what your minimizing is also a max? It doesn't really make that much sense to me to minimize a maximum value?

 

[D H]

A couple of pointers. First, don't call it just g(x). Better would be g(x;x1,x2,x3). You have four parameters here.

Second, don't be so quick to expand. For example, instead of expanding $g(x;x1,x2,x3)^2$ first and then differentiating, do it the other way around:

$$\frac{\partial}{\partial x} g(x;x1,x2,x3)^2 = 2g(x;x1,x2,x3)\;\frac{\partial}{\partial x} (g(x;x1,x2,x3))$$

Setting this to zero yields

$$g(x;x1,x2,x3) \;\frac{\partial}{\partial x} (g(x;x1,x2,x3)) = 0$$

The points $x$ at which $g(x;x1,x2,x3)=0$ represent the local minima in $g(x;x1,x2,x3)^2$. You want the local maxima, not the local minima. You can ignore the solutions $g(x;x1,x2,x3)=0$. The local maxima are the solutions to

$$\frac{\partial}{\partial x} g(x;x1,x2,x3) = 0$$

This is a quadratic function with potentially two solutions. Find these. This will give you the points at which $|g(x)|$ reaches local minimum. The function $|g(x)|$ might also reach a maximum at the boundary points (0 and 1). The function will reach its maximum value over [0,1] at one these four points.

Now you want the partial derivatives of $g(x;x1,x2,x3)^2$ wrt each of the x_i evaluated at this maximal x to be zero. That's three simultaneous equations in three variables.

Minimizing the maximum (or maximizing the minimum) is used in many places in mathematics. One area is game theory. Here the goal is to find the move that maximizes the "me versus the other guy" score even if the other guy finds the move that minimizes this same score.

Another area is function design. Suppose you are asked to design an approximation g(x) to some hard-to-calculate function f(x) over some range. Most people will use a least squares approximation. This minimizes the root mean square error. A user of this function is more likely concerned with the worst case error, not the root mean square error. The worst case error is max(|f(x)-g(x)|). This is exactly what you are asked to do in this problem.

 

[D H]

Another hint: You should be able to show the graph of g(x)^2 needs to be symmetric about x=1/2. This simplifies the problem immensely.

 

[D H]

Just one more note (I promise!) ...

This problem is a nice introduction to the concept of a minimax polynomial. One way to solve for such a beast is the Remez exchange algorithm. The wikipedia article is pretty good, the mathworld article is mediocre. There is no need to use the Remez algorithm on this problem. Exploiting the symmetry makes the answer fall out.