Minimizing L_infty Norm: Finding Closest Points to b on x-axis and y=x

[Mindscrape]

This is a routine minimization problem, find the closest point or points to b = (-1,2)^T that lie on (a) the x-axis and (b) the line y=x.

First I am supposed to solve it with the Euclidian norm, which is no problem, but then we are supposed to solve with the L_\infty norm. I am a little confused because the L_\infty is the max of all points, so it is asking to minimize the maximum point??

 

[ZioX]

You just take the maximum absolte value over all of your coordinates.

It's just another way to conceptualize space in R^n.

 

[Mindscrape]

I know what the L_\infty norm is. I am confused because the closest point will be when ||Ax-b|| is minimized, but the norm of ||Ax-b||_\infty finds the maximum absolute value, which means that either the minimum must be less than zero for the two to agree, or if the minimum distance is greater than zero the problem doesn't make sense because the maximum value won't be the minimum.

To me there seems to be a contradiction.

 

[ZioX]

No, no. The infinity norm is the absolute value of the coordinate with the largest absolute value. Find x that minimizes this.

Consider the first problem.

You want to minimize ||(-1,2)-(x,0)||_\infty=||(-1-x,2)||_\infty. What is this if x is between 1 and 3? What is it otherwise? How can you minimize it? Is the x that minimizes the norm unique?

 

[Mindscrape]

Oh, right, this actually does make sense - just really strange to think about. So then the idea is to minimize ||(-1-x,2)||_\infty which would be minimum of |-1-x|, and |2|. So then the minimum infinity norm would be whenever 1+x < 2 or x < 1.

Then for the line y = x the idea will be to minimize |-1-x| and |2-y|. So it would be a minimum where the two intersect.