Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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]]]
share|improve this question
    
Nice. I might "borrow" (okay, steal) this next time I want to use LinearProgramming directly and avoid NMinimize overhead. I'd give it an upvote but I notice I already did that. –  Daniel Lichtblau Feb 28 at 19:14

2 Answers 2

up vote 3 down vote accepted

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}} *)
share|improve this answer
    
Amazing, thank you, I tried to set this up with LinearProgramming[], but I think it's not possible, do you think I'm wrong? –  Coolwater Feb 26 at 19:35
    
It can be set up to use LinearProgramming directly, but that's usually more work than I'm willing to do. Maybe someone out there has a program to convert an LP in NMinimize format to one directly usable by LinearProgramming? Of course then you'd be essentially replicating work that NMinimize does in coming up with that conversion itself. –  Daniel Lichtblau Feb 26 at 20:15

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.