How can the l1 norm of a linear function be maximized?

[humbug]

Hi all,

Sorry if this is in the wrong section...first time and i couldn't see a convex analysis section.

I'm trying to find a good algorithm/theorem that will maximise the l1 norm (sum of absolute values) of a linear function. Namely, given a function z = c + Ax where z is (nx1), A is (nxm) and x is (mx1), what is the optimal way to choose x such that the sum of the absolute values of z are maximised (obviously x is bounded).

My problem scales really badly so its not feasible to just compute at the bounds of x and choose the biggest outcome. I've also found that the simplex algorithm cannot do it (it only works for minimising the l1 norm). I think the separating hyperplane theorem might be able to help but i can't really see how.

Any help/ideas would be greatly appreciated

 

[uart]

I think this will work - just make all but one element of x equal to zero. With the position of the one nonzero element corresponding to the column of A which has the maximum L1 norm.

Edit : Ok scrub that, it's only correct for c=0.

BTW c is a vector (nx1) isn't it?

 

[humbug]

In general c is a vector (nx1), however one of my cases deals with c being a constant vector so any thoughts on how to deal with that would also be helpful. As I understand it, if each element of x is in the interval [a,b], then shouldn't x be populated with a and b only? I thought that since the abs function is convex then its maximum will lie at the bounds always (or in other words, the solution lies at the corner of some hypercube). You can use this argument to turn the problem into a binomial choice problem if that makes things easier (thats what I'm playing with at the moment but it hasn't made it easier for me yet)