An optimization problem I am considering the following optimization problem. Let $P$ be a set of $n$ points in $\mathbb{R}^d$
maximize $\sum_{p\in P}\vert\langle \Vert p\Vert p, \hat{x}\rangle\vert$ subject to $\Vert\hat{x}\Vert^2=1, \hat{x}\in \mathbb{R}^d$.
Without the absolute value inside the summand, the solution is easy, the optimal solution is achived by the unit vector along the vector $\sum_{p\in P}\Vert p\Vert p$. But with the absolute value in the picture, I failed to find a solution. Can this problem be solved by techniques of optimization literature?
Thanks
p.s.
This problem has some superficial similarities with Chebyshev approximation problem:
$minimize \max_i \vert a_i^Tx-b_i\vert$. The aforementioned problem involves $l_\infty$ norm, whereas the original problem deals with $l_1$ norm.
The problem as described is not convex, due to the nonconvexity of the constraint set. However, if you were to permit a relaxation, we could write your problem as
$\begin{array}{ll}
\max &amp; \sum_{p\in P} t_p\\
\text{subject to }&amp; t_p \geq \langle x, \|p\| p \rangle\\
&amp; t_p \geq -\langle x, \|p\| p\rangle ,\\
&amp;  \|x\|_2 \leq 1. 
\end{array}$
This is a second-order cone program, which can be solved by standard methods.
It is probably not trivial to recover a solution to your original problem from this relaxation (for instance, Goemans-Williamson wrote a breakthrough paper describing the rounding algorithm for a similar relaxation). But maybe this is helpful in some way.
edit -- As pointed out by Neal Young, there is an error in the above answer. The question in the original post is a maximization of absolute value function, which isn't a convex objective; so, my reduction is incorrect. I am leaving the incorrect answer here in case someone finds any information in it useful, but please see Neal Young's comments below for more comprehensive (and correct) observations about the problem.