<p>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</p>
<p><span class="math-container">$\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}$</span></p>
<p>This is a second-order cone program, which can be solved by standard methods.</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2021-03-01T21:41:29.130Z
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..
Neal Young
CC BY-SA 4.0
2021-03-01T22:02:06.777Z
@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.
walkerbacker
CC BY-SA 4.0
2021-03-01T22:02:47.237Z
@NealYoung Should I just delete my answer? I am new, so I am not sure what to do about wrong answers I write.
walkerbacker
CC BY-SA 4.0
2021-03-02T16:23:07.680Z
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.
Neal Young
CC BY-SA 4.0
2021-02-28T07:13:39.867Z
2021-03-03T11:07:09.390Z
2021-03-03T11:07:09.390Z
walkerbacker
<p>I am considering the following optimization problem. Let <span class="math-container">$P$</span> be a set of <span class="math-container">$n$</span> points in <span class="math-container">$\mathbb{R}^d$</span></p>
<p><strong>maximize <span class="math-container">$\sum_{p\in P}\vert\langle \Vert p\Vert p, \hat{x}\rangle\vert$</span> subject to <span class="math-container">$\Vert\hat{x}\Vert^2=1, \hat{x}\in \mathbb{R}^d$</span>.</strong></p>
<p>Without the absolute value inside the summand, the solution is easy, the optimal solution is achived by the unit vector along the vector <span class="math-container">$\sum_{p\in P}\Vert p\Vert p$</span>. But with the absolute value in the picture, I failed to find a solution. Can this problem be solved by techniques of optimization literature?</p>
<p>Thanks</p>
<p>p.s.</p>
<p>This problem has some superficial similarities with <em>Chebyshev approximation problem:</em></p>
<p><span class="math-container">$minimize \max_i \vert a_i^Tx-b_i\vert$</span>. The aforementioned problem involves <span class="math-container">$l_\infty$</span> norm, whereas the original problem deals with <span class="math-container">$l_1$</span> norm.</p>

CC BY-SA 4.0
2020-12-26T19:24:24.040Z
By $||\hat x||$ you mean the $\ell_2$-norm of $\hat x$?
Neal Young
CC BY-SA 4.0
2020-12-26T19:27:35.033Z
Yes. Thank you, I think problem is similar to the problem of Robust Estimator.
Sudipta Roy
CC BY-SA 4.0
2021-03-05T22:51:35.680Z
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?
Thomas Ahle
<ds.algorithms><optimization><linear-algebra><convex-optimization>
An optimization problem
Sudipta Roy
# An optimization problem

(Asked by: username_0 on 2020-12-26)

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.

**Tags:** ds.algorithms, optimization, linear-algebra, convex-optimization
> **Comments:**
> **username_1**: By $||\hat x||$ you mean the $\ell_2$-norm of $\hat x$?  
> **username_0**: Yes. Thank you, I think problem is similar to the problem of Robust Estimator.  
> **username_2**: 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?  

---

## 1 answers

### Answer by username_3 on 2021-02-28. Score: 2

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.

> **Comments:**
> **username_1**: 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..  
> **username_3**: @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.  
> **username_3**: @NealYoung Should I just delete my answer? I am new, so I am not sure what to do about wrong answers I write.  
> **username_1**: 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.  

---

