An optimization problem

Question

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.

Answer 1

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 & \sum_{p\in P} t_p\\ \text{subject to }& t_p \geq \langle x, \|p\| p \rangle\\ & t_p \geq -\langle x, \|p\| p\rangle ,\\ & \|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.