Given a linearly independent set, $\{a_i\}_{i=1}^n$, where $a_i\in\mathbb{R}^m$ and $m\gg n$. How to find a solution to the following optimization problem?
$$\begin{array}{ll} \underset{a \in \mathbb{R}^m}{\text{minimize}} & \displaystyle\left\langle a, \sum_{i=1}^{n} \frac{a_i}{\left\Vert a_i\right\Vert}\right\rangle\\ \text{subject to} & \langle a, a_i\rangle>0 \quad\forall i\in\{1,2,\dots,n\}\\ & \left\Vert a\right\Vert=1\end{array}$$
Please, note that:
-
$\langle\cdot,\cdot\rangle$ denotes the inner product.
-
I would prefer to understand how to solve this for strict inequalities constraints, but it is ok anyway.
The problem is a good fit for LP but, unfortunately I can't find a work around the unit norm constraint. To get around the strict inequalities, I was thinking maybe I can use $\langle a,a_i\rangle\ge e^{-t}$ inequalities for some big value of $t$. I want to use scipy.optimize.linprog to solve this, but don't know how to incorporate the unit norm constraint.
Best Answer
The answer to this problem is ill-posed, the solution can be arbitrarily small and close to zero. Consider $A$ be the subspace formed by $\{a_i\}_{i=1}^{n}$. Then the solution for the problem, we call it $a^*$, can be written as $a^* = \bar{a}^* + a^{\bot}$ where $\bar{a}^* \in A$ and $a^{\bot}$ is in the null-space of $A$, i.e. $A^{\bot}$ .
Because there is the constraint $\langle a, a_i\rangle>0$, therefore the trivial solution $a = a^{\bot}, \lVert a^{\bot}\rVert = 1$ is not valid, however we can have a solution of the form $a = \epsilon_1 \frac{a_1}{\left\Vert a_1\right\Vert} +\epsilon_2 \frac{a_2}{\left\Vert a_2\right\Vert} + \cdots + \epsilon_n \frac{a_n}{\left\Vert a_n\right\Vert} + \sqrt{1-\epsilon_1^2-\epsilon_2^2-\cdots-\epsilon_n^2}a',a'\in A^{\bot}$, where $\forall i: \epsilon_i >0$ can be arbitrarily small.