Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 LInfinitySolve

Source Notebook

Solve the linear minimax problem

Contributed by: Jan Mangaldan

ResourceFunction["LInfinitySolve"][m,b]

finds an x that solves the linear minimax problem for the matrix equation m.x==b.

Details

The linear minimax problem is also referred to as linear ℓ∞ norm minimization or Chebyshev norm minimization.
ResourceFunction["LInfinitySolve"][m,b] gives a vector x that minimizes Norm[m.x-b,∞].
All entries in the matrix m and the vector b must be real numbers.
SparseArray objects can be used in ResourceFunction["LInfinitySolve"].
ResourceFunction["LInfinitySolve"] takes the same options as LinearProgramming.

Examples

Basic Examples (1) 

Solve a simple minimax problem:

In[1]:=
ResourceFunction[ "LInfinitySolve"][{{1, 1}, {1, 2}, {1, 3}}, {7, 7, 8}]
Out[1]=

Scope (2) 

Create a 4×3 matrix, and b is a length-4 vector:

In[2]:=
m = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}}; b = {1, 2, 4, 8};

Use exact arithmetic to find a vector x that minimizes :

In[3]:=
ResourceFunction["LInfinitySolve"][m, b]
Out[3]=

Use machine arithmetic:

In[4]:=
ResourceFunction["LInfinitySolve"][N[m], b]
Out[4]=

Use 20-digit-precision arithmetic:

In[5]:=
ResourceFunction["LInfinitySolve"][N[m, 20], b]
Out[5]=

Use a sparse matrix:

In[6]:=
s = SparseArray[{{i_, j_} /; j == i + 1 -> N[i]}, {10, 10}]; ResourceFunction["LInfinitySolve"][ N[s], {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}]
Out[7]=

Applications (4) 

Here is some data:

In[8]:=
data = {{0, 1}, {1, 0}, {3, 2}, {5, 4}};

Find the line that best fits the data in the minimax sense:

In[9]:=
line = ResourceFunction["LInfinitySolve"][ DesignMatrix[data, {1, x}, x], data[[All, -1]]] . {1, x}
Out[9]=

Find the quadratic that best fits the data in the minimax sense:

In[10]:=
parabola = ResourceFunction["LInfinitySolve"][ DesignMatrix[data, {1, x, x^2}, x], data[[All, -1]]] . {1, x, x^2}
Out[10]=

Show the data with the two curves:

In[11]:=
Show[ListPlot[data, PlotStyle -> Red], Plot[{line, parabola}, {x, 0, 5}]]
Out[12]=

Properties and Relations (2) 

For a vector b, LInfinitySolve is equivalent to ArgMin[Norm[m.x-b,∞],x]:

In[13]:=
m = {{1, 2}, {3, 4}, {1, 1}}; x = {x1, x2}; b = {1, 2, 3};
In[14]:=
ResourceFunction["LInfinitySolve"][m, b] == ArgMin[Norm[m . x - b, \[Infinity]], x]
Out[14]=

Create a 5×2 matrix, and b is a length-5 vector:

In[15]:=
m = {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}}; b = {1, 2, 4, 3, 5};

Solve the minimax problem:

In[16]:=
a = ResourceFunction["LInfinitySolve"][m, b]
Out[16]=

This is the minimizer of :

In[17]:=
Show[Plot3D[Norm[m . {x, y} - b, \[Infinity]], {x, -2, 2}, {y, 0, 2}, MeshFunctions -> {#3 &}, ColorFunction -> (Hue[.65 (1 - #3)] &)], Graphics3D[{Red, PointSize[0.05], Point[{a[[1]], a[[2]], Norm[m . a - b]}]}]]
Out[17]=

It also gives the coefficients for the line with minimax absolute deviation from the points:

In[18]:=
Show[ListPlot[{{1, 1}, {2, 2}, {3, 4}, {4, 3}, {5, 5}}], Plot[a . {1, x}, {x, 1, 5}]]
Out[19]=

Version History

  • 1.0.0 – 06 January 2021

Source Metadata

  • Citation:
    • Barrodale, I., Young, A., "Algorithms for Best L^1 and L^∞ Linear Approximations on a Discrete Set." Numerische Mathematik, vol. 8, 295–306, 1966.
      DOI: 10.1007/BF02162565
    • Watson G.A., "Approximation in normed linear spaces." Journal of Computational and Applied Mathematics, vol. 121, 1-36, 2000.
      DOI: 10.1016/S0377-0427(00)00333-2

Related Resources

License Information