Minimizing the maximal residual in mathematica

Question

With this:

d1 = 10; d2 = 4;
mat = RandomReal[{-1, 1}, {d1, d2}];
vec = RandomReal[{-1, 1}, d1];

LeastSquares[mat, vec] returns the x, that minimizes Plus @@ ((mat.x-vec)^2)

What is the best way to make mathematica return the x that minimizes Max @@ ((mat.x-vec)^2)

I ended up with this, thank you Daniel ;)

With[{L = Length[First[mat]]},
LinearProgramming[Prepend[ConstantArray[0, L], 1],
Prepend[#, 1] & /@ Riffle[mat, -mat], Riffle[vec, -vec],
Prepend[ConstantArray[-\[Infinity], L], 0]]]

Answer 1

It is equivalent to minimize the absolute values. This can be set up as an explicit linear programming problem. The advantage over the approach of @bobthechemist (which is good, and I voted up) is that the problem can then be shipped to special case LP code.

vars = Array[x, d2];
linearexprs = mat.vars - vec;
constraints = 
  Join[Thread[max >= linearexprs], Thread[max >= -linearexprs]];
NMinimize[{max, constraints}, Join[{max}, vars]]

(* Out[790]= {0.634141, {max -> 0.634141, x[1] -> 0.679669, 
  x[2] -> 0.244346, x[3] -> -0.539059, x[4] -> -1.09431}} *)

Answer 2

Since LeastSquares can be written as

NMinimize[Plus @@ ((mat.{x1, x2, x3, x4} - vec)^2), {x1, x2, x3, x4}]

Then you can use a similar approach to minimizing your desired function:

NMinimize[Max @@ ((mat.{x1, x2, x3, x4} - vec)^2), {x1, x2, x3, x4}]

Although whether or not this is the "best" way is likely up for debate.