3
$\begingroup$

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.

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • 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
    Commented Mar 1, 2021 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$ Commented Mar 1, 2021 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$ Commented Mar 1, 2021 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
    Commented Mar 2, 2021 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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