Algorithm to maximize sum of absolute dot products over the unit sphere

Question

Given vectors $x_1, \dots, x_n \in \mathbb{R}^d$, I am seeking a solution to the following optimization problem:

$$ \underset{v \in \mathbb{R}^d}{\arg\max} \sum_{i=1}^n \left| \langle v, x_i \rangle \right| \quad\text{subject to}\quad \lVert v \rVert = 1 $$

So, I'm trying to find a vector $v$ of unit length that maximizes the sum of absolute dot products. I thought about solving this with Lagrange multipliers, but I don't think that's the way to go. Anyways, here's the derivative:

$$\frac{\partial}{\partial v} \sum_{i=1}^n |\langle v, x_i \rangle| = \sum_{i=1}^n \text{sgn}(\langle v, x_i \rangle) \cdot x_i$$

Root finding turns out to be a combinatorial problem where $v$ has to be chosen so that it assigns positive or negative sign to $x_i$ making the sum yield zero. So very possibly a root does not even exist. On second thought, the problem is a piecewise linear function, so it didn't make sense to try gradient-based methods in the first place.

So what class of optimization problems does this fall into? And are there related problems with known solutions?

I could think of a heuristic approach that sorts all $x_i$ by their lengths (assume $x_i$ are sorted length descending), then initializes $v=\frac{x_1}{\lVert x_1 \rVert}$ and then lets each subsequent $x_i$ turn $v$ a little bit into its direction according to their 'importance', i.e., their length. Something like this: $$ v^{(i)} := v^{(i-1)} + \text{sgn}(\langle v^{(i-1)}, x_i \rangle) \cdot \frac{x_i}{\lVert x_i \rVert} \cdot w(\lVert x_i \rVert) \quad \text{with some appropriate weight function $w$}$$ $$ v^{(i)} := \frac{v^{(i)}}{\lVert v^{(i)} \rVert} \quad \text{(normalize $v$)}$$

---

Considering D.W.'s pointer to a similar problem, there may be a connection to support vector machines. Or maybe a connection to solving the dual problem, so the objective and constraints need to be rewritten.

Or maybe minimizing $\lVert v \rVert$ could be done while constraining $|\langle v,x_i \rangle| \geq 1$. Not sure how this relates to the original problem though, and whether it is equivalent.

• D.W.: Are the vectors 2-dimensional? Or arbitrary dimensional?
• D.W.: Loosely related (but definitely different): cs.stackexchange.com/q/163397/755
• hageldave: vectors are arbitrary dimensional, I updated the question accordingly

Answer 1

Assuming $| \langle v,w \rangle| = v_1 w_1 + \ldots v_d w_d$ for $v, w \in \mathbb{R}^d$ and $\| v \| = \sqrt{v_1^2 + \ldots v_d^2}$, we can reformulate your problem as $$ \arg \min \sum_{i=1}^n w_i \qquad \text{subject to } \\ w_i \geq \langle v, x_i \rangle\\ w_i \geq -\langle v, x_i \rangle \\ \| v \|^2 = 1. $$ Now the objective function and the inequality constraints are linear constraints, while the last constraint is a quadratic constraint. This is an instance of what is known as quadratically constrained linear program (QCLP), a subfield of convex programming. There exist general-purpose algorithms that can solve such problems, including the ellipsoid method and interior-point methods. A few quick comments on this:

1. Important: These algorithms do not return an exact solution, but rather return a solution within a certain (arbitrary) accuracy of the optimum ($\min$). However, they do not necessarily return a point that is close (in Euclidean distance) to the true optimizer unless additional conditions (like strong convexity) are met. In this, such conditions are not met.
2. Less important: The computational complexity of such algorithms for QCLP is a bit of a thorny issue. Here's a few references that should be useful: (1) Bienstock, D., Pia, A.D. & Hildebrand, R. Complexity, exactness, and rationality in polynomial optimization. Math. Program. 197, 661–692 (2023).(2) Vavasis, Stephen A.. "Quadratic Programming is in NP." Inf. Process. Lett. 36 (1990): 73-77.

I know it's a partial answer, but I hope it helps!

• NaturalLogZ: Your formulation of the problem is actually incorrect. Note that what you have written allows $w_i$ to be arbitrarily large. It would work if we were trying to minimize the sum, but since we are maximizing it, it doesn't.
• hageldave: Thanks for your answer Alakaei. As NaturalLogZ pointed out, w_i need to be minimized so that w_i does not simply become the largest dot product of an arbitrary v. What I do not understand, however, is how minimizing w_i yields an appropriate v. v needs to be variable, but how is it varied? Varying v changes the boundary of the feasible region. What mechanism determines how v is changed?
• Alakaei: I don't understand entirely your questions. However: 1. The minimum of the sum of w_i coincides with the max of the sum of | < v_i, x_i> | . 2. In my formulation both w_i and v_i are variables, and so the feasibility region is both in terms of w_i and v_i. So what I mean by argmin is to find w_i and the v_i such that the min of the sum of w_i is attained.