Minimize maximum error

[Joshua2]

I reduced my problem to this almost linear program:
minimize
max (
abs(a*1+b*3-c),
abs(a*2+b*5-c),
abs(a*3+b*7-c),
abs(a*5+b*11-c),
abs(a*7+b*14-c),
abs(a*8+b*15-c),
abs(a*10+b*19-c)
)
on
ax + by = c

I can get rid of the abs,

minimize
max (
a*1+b*3-c, -a-3b+c
a*2+b*5-c, -2a-5b+c
a*3+b*7-c, -3a-7b+c
a*5+b*11-c, -5a-11b+c
a*7+b*14-c, -7a+14b+c
a*8+b*15-c, -8a-15b+c
a*10+b*19-c, -10a-19b+c
)
on
ax + by = c

How do I get rid of the max?
Someone said the answer is:
min z
s.t. z >= a*x_i + b*y_i - c, 1<=i<=T
z >= c - a*x_i + b*y_i, 1<=i<=T

Thanks!

[cheesehead]

I don't see how you can get rid of the max function, or something functionally equal to it, as long as your goal is, as your title says, "minimize maximum error". How else is the "maximum error" to be determined?

You can use some algorithm that avoids using "max" by using comparisons and conditional branches ... but that's just what the max function does, so all you accomplish that way is to pretend that you're not using a "max" function just because the character string ("m", "a", "x") doesn't appear in your code.

Inside the max function, what goes on is just comparisons and conditional branches to assignment statements.

function max(a,b);

if a > b then return a else return b;

function max(a,b,c);

if a > b then {if a > c then return a else return c}
else {if b > c return b else return c};

. . .

Originally Posted by Joshua2

Someone said the answer is:
min z
s.t. z >= a*x_i + b*y_i - c, 1<=i<=T
z >= c - a*x_i + b*y_i, 1<=i<=T

All that's doing is hiding ("m", "a", "x") while doing just the same comparisons and conditionals.

z
s.t. z >= a*x_i + b*y_i - c, 1<=i<=T
z >= c - (a*x_i + b*y_i), 1<=i<=T

is just

z = -infinity;

for i = 1 to T by 1;
m = a*x_i + b*y_i - c;
if m > z then z = m;
if -m > z then z = -m;
end for;

return z;

[xilman]

Originally Posted by cheesehead

Inside the max function, what goes on is just comparisons and conditional branches to assignment statements.

function max(a,b);

if a > b then return a else return b;

Unless you write it something like this:

#include <stdint.h>

int32_t max (int32_t a, int32_t b)
{
   return b - (a-b) * ((a-b) >> 31);
}

I think that's right --- I typed it in without compiling and testing.

Moral 1: there is more than one way to skin a cat.
Moral 2: there is a long history behind writing straight-line code to be found within the SIMD machine community, which is where I learned this kind of trick. CUDA coders aiming to squeeze every drop of performance try really hard to have uniform program flow and uniform memory accesses in their kernels.

Paul

[lavalamp]

Shouldn't that be (a-b) for the first bracket?

Nice trick btw.

Edit: Or add it rather than subtract it to keep both brackets the same.

[cheesehead]

Originally Posted by xilman

Unless you write it something like this:

#include <stdint.h>

int32_t max (int32_t a, int32_t b)
{
   return b - (a-b) * ((a-b) >> 31);
}

So, if a = 56 and b = 2, it returns

2 - (56-2)*((56-2)>>31)

= 2 - (54)*((54)>>31)

= 2 - (54)*(0)

= 2

?

Moral 3: One of us has failed to either compile or test correctly before publishing our result. If >> is not a right shift, it's me.

[lavalamp]

Ah, maybe it was meant to be a at the start then.

All equivalent:

   return b - (b-a) * ((a-b) >> 31);

   return b + (a-b) * ((a-b) >> 31);

   return a - (a-b) * ((a-b) >> 31);

The last two being probably being a bit quicker because (a-b) can be stored in a register and used again.

[xilman]

Originally Posted by cheesehead

Moral 3: One of us has failed to either compile or test correctly before publishing our result. If >> is not a right shift, it's me.

That's exactly how I documented it.

I typed it in without compiling and testing.

As lavalamp noted, the first '-' should be a '+'.

Still, at least two of us think it's a nice trick.

At least one of us (me) thinks its a lousy way to write code unless you really need that last drop of performance. Almost all the time it takes longer to write, test and debug the code in the first place than you ever get back at runtime.

Paul

[cheesehead]

If I hadn't tested, I wouldn't have moralized about it. :-)

[CRGreathouse]

Originally Posted by xilman

At least one of us (me) thinks its a lousy way to write code unless you really need that last drop of performance. Almost all the time it takes longer to write, test and debug the code in the first place than you ever get back at runtime.

It's a good way to write library code. It's a bad way, generally, to write most anything else.

[R.D. Silverman]

Originally Posted by xilman

Unless you write it something like this:

#include <stdint.h>

int32_t max (int32_t a, int32_t b)
{
   return b - (a-b) * ((a-b) >> 31);
}

I think that's right --- I typed it in without compiling and testing.

Moral 1: there is more than one way to skin a cat.
Moral 2: there is a long history behind writing straight-line code to be found within the SIMD machine community, which is where I learned this kind of trick. CUDA coders aiming to squeeze every drop of performance try really hard to have uniform program flow and uniform memory accesses in their kernels.

Paul

Note also:

max(a,b) = [abs(a+b) + abs(a-b)]/2
min (a,b) = [abs(a+b) - abs(a-b)]/2

[ppo]

Originally Posted by R.D. Silverman

Note also:

max(a,b) = [abs(a+b) + abs(a-b)]/2
min (a,b) = [abs(a+b) - abs(a-b)]/2

This is working only for non-negative values for a and b.
To allow also negative values:

max(a,b) = (a+b+abs(a-b))/2
min (a,b) = (a+b-abs(a-b))/2