# 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.

• By $||\hat x||$ you mean the $\ell_2$-norm of $\hat x$? Dec 26 '20 at 19:24
• Yes. Thank you, I think problem is similar to the problem of Robust Estimator. Dec 26 '20 at 19:27
• What's the point of multiplying $p$ by its own norm? Could you not just make $P$ the set of points already scaled the way you want them? Mar 5 at 22:51

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.

• Your proposed problem has constraints "$t_p \ge \cdots$" (two times), and objective $\max \sum_p t_p$, so the problem is unbounded (take $t_p$ arbitrarily large). You could try "$t_p \le \cdots$", but then you would have $t_p = -|\langle x, \|p\|p\rangle|$ and taking $x = \overline 0$ would be optimal.. Mar 1 at 21:41
• @NealYoung Thank you for pointing out that error! I am just realizing that the problem stated in the original post is itself nonconvex, since it asks about maximizing a sum of absolute values. So perhaps my approach is totally wrong, since it would be too much to expect to have a convex program so close to a nonconvex problem. Mar 1 at 22:02
• @NealYoung Should I just delete my answer? I am new, so I am not sure what to do about wrong answers I write. Mar 1 at 22:02
• I'm not sure if there is a standard practice for this. Sometimes people leave the answer, but edit it to add a comment to the top noting that it's wrong. I guess people do that if they think the answer, though wrong, still contains information that other readers will find useful. Mar 2 at 16:23