Solve $\min_{\|w\|=1} \max_i w^Tx_i$

Question

Given $n$ points $x_1,\cdots,x_n$, how can I find a lower bound $c$ such that for any unit vector $w$ ($\|w\|=1$), $\max_i w^Tx_i\ge c$? This is a non-convex problem since the constraint $\|w\|=1$ is non-convex. But the problem is extremely concise. Is there an efficient algorithm to solve the problem? If this is impossibe, can we approximate $c$ using algorithms? Thank you!

Note that the problem is equivalent to finding a point in a polyhedron with the largest norm.

Answer 1

Partial answer:

I am assuming the Euclidean norm here.

Let $C= \operatorname{co} \{ x_k \}_k$. Let $\Sigma = \{ \mu| \sum_k \mu_k = 1, \mu_j \ge 0 \}$.

If $0 \notin C^\circ$, then it is straightforward to show that $\min_{|w\| = 1} \max_k w^T x_k = \min_{|w\| \le 1} \max_k w^T x_k$.

Then $\min_{|w\| \le 1} \max_k w^T x_k = \min_{|w\| \le 1} \max_{\mu \in \Sigma} w^T (\sum_k \mu_k x_k )$.

Apply the Von Neumann minimax theorem we get the dual $\min_{|w\| \le 1} \max_{\mu \in \Sigma} w^T (\sum_k \mu_k x_k ) = \max_{\mu \in \Sigma} \min_{|w\| \le 1} w^T (\sum_k \mu_k x_k ) = \max_{\mu \in \Sigma} (- \|\sum_k \mu_k x_k\| ) = - \min _{\mu \in \Sigma} \|\sum_k \mu_k x_k\| $.

Hence the solution can be found by finding the minimum distance to the convex hull of the $x_k$.

Answer 2

How about introducing an optimization variable $t \in \mathbb R$ and solving the following optimization problem in $\mathrm w \in \mathbb R^d$ and $t \in \mathbb R$?

$$\boxed{\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & \mathrm x_1^\top \mathrm w \leq t\\ & \quad\vdots\\ & \mathrm x_n^\top \mathrm w \leq t\\ & \| \mathrm w \|_2 = 1\end{array}}$$