# Maximize scalar product with argument in bounded intersection of half spaces

Given $$a,v_1,\dots,v_n\in \mathbb{R}^d$$, $$n,d\in\mathbb{N}$$, how to compute a maximizer of $$f: \begin{cases} \{x\in\mathbb{R}^d\vert\; \|x\|_2\le1\land \forall i\in \{1,\dots,n\}\;\langle x,v_i\rangle\le 0\}&\to\mathbb{R}\\\\ x&\mapsto \langle x,a\rangle \end{cases}$$ In other words I want to find a direction $$x^*$$ that produces a maximal scalar product with the vector $$a$$ among all directions that lie in the convex region specified by some hyperplane inequalties with hyperplanes that go through the origin $$0\in\mathbb{R}^d$$.

My questions:

1. Does this problem have a specific name?
2. How to solve it algorithmically?
3. What is the complexity of such an algorithm in terms of $$n$$ and $$d$$?
• If you forget the unit ball constraint, then the problem looks a lot like linear programming. – Joppy Oct 24 '19 at 12:51
• @Joppy Yes, it is like checking if a corner of a feasible region is the optimal point in linear programming. If so, then $x^*=0$ otherwise, $x^*$ is the direction with the steepest ascent without leaving the feasible region. – phinz Oct 25 '19 at 16:52

The problem is colloquially written as $$\max_x\left\{a^Tx : v_i^Tx \leq 0 \; \forall i, ||x||\leq1\right\}.$$ This is a second order cone optimization problem. The dual problem is: $$\min_y \left\{ ||a+\sum_i y_i v_i|| : y\geq 0 \right\}.$$ The dual problem is known as nonnegative least squares (the $$a$$ here is $$y$$ on Wikipedia, and the $$v_i$$ here are the columns of $$-A$$ on Wikipedia). That means that there is no closed-form solution.
If you prefer an algorithm tailored to nonnegative least squares, the optimal solution to your original problem is $$x^* = (a+\sum_i y^*_i v_i) / ||a+\sum_i y^*_i v_i||$$ (with $$y^*$$ the optimal dual solution).