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?



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.

  • $\begingroup$ By $||\hat x||$ you mean the $\ell_2$-norm of $\hat x$? $\endgroup$
    – Neal Young
    Dec 26 '20 at 19:24
  • $\begingroup$ Yes. Thank you, I think problem is similar to the problem of Robust Estimator. $\endgroup$ Dec 26 '20 at 19:27
  • $\begingroup$ 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? $\endgroup$ 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.

  • 1
    $\begingroup$ 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.. $\endgroup$
    – Neal Young
    Mar 1 at 21:41
  • $\begingroup$ @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. $\endgroup$ Mar 1 at 22:02
  • $\begingroup$ @NealYoung Should I just delete my answer? I am new, so I am not sure what to do about wrong answers I write. $\endgroup$ Mar 1 at 22:02
  • 1
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Mar 2 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.