1
$\begingroup$

Suppose it is given that there exists a ‘strictly positive’ vector $\vec x \in (0,1)^k$, which lies on the probability simplex $\sum_i x_i = 1$. What is the least number of inequalities of the form $\vec g_i^T \vec x \geq 0$ required to ensure that the solution set is a singleton vector? Note that there is no restriction on $\{\vec g_i \}$ so one can pick the ‘best’ possible vectors (it should be consistent in the sense that there must exist one solution on the simplex with positive components).

I believe the answer would be $2(k-1)$ — I know it definitely is sufficient but can't seem to be able to show that it is necessary as well. Construction for sufficiency — take pairs of $\vec g_i, - \vec g_i$ so essentially you would have $k-1$ equations of form $\vec x^T \vec g_i = 0$ and $\sum_i x_i = 1$. We have $k$ equations so this has a unique solution and it's not hard to see that by suitable choice of $\vec g_i$, we can make the solution have positive components.

$\endgroup$

1 Answer 1

4
$\begingroup$

$\newcommand\v\vec\newcommand\R{\mathbb R}$For any natural $k\ge2$, $k$ inequalities (but not fewer than $k$) will suffice.

Indeed, take any vector $\v a\in(0,\infty)^k$ such that $\v1\cdot\v a=1$, where $\v1:=(1,\dots,1)\in\R^k$ and $\cdot$ denotes the dot product. Take any linearly independent vectors $\v g_1,\dots,\v g_{k-1}$ in $\R^k$ that are orthogonal to $\v a$, and then let $\v g_k:=-\v g_1-\dots-\v g_{k-1}$. Then, for each $\v x\in\R^k$, the inequalities \begin{equation} \v g_1\cdot\v x\ge0,\ \dots,\ \v g_{k-1}\cdot\v x\ge0,\ \v g_k\cdot\v x\ge0 \tag{0} \end{equation} imply the equalities \begin{equation} \v g_1\cdot\v x=\dots=\v g_{k-1}\cdot\v x=0. \tag{1} \end{equation} Also, the vector $\v1$ is linearly independent of $\v g_1,\dots,\v g_{k-1}$ -- otherwise, we would have $1=\v1\cdot\v a=0$, since (1) holds for $\v x=\v a$. So, the system of equalities (1) together with the equality \begin{equation} \v1\cdot\v x=1 \tag{2} \end{equation} has a unique solution.

Moreover, equalities (1) and (2) do hold for $\v x=\v a$.

Thus, $\v x=\v a$ is the unique solution of the system of inequalities (0) and equality (2),
as desired.


Also, for any natural $k\ge2$, any $k-1$ inequalities of the form \begin{equation} \v g_1\cdot\v x\ge0,\dots,\v g_{k-1}\cdot\v x\ge0 \tag{0a} \end{equation} will not suffice to identify $\v a$, even together with the equality (2).

Indeed, suppose the contrary, so that $\v a$ is the only solution in $(0,\infty)^k$ of the system (0a)--(2).

Consider first the case when $\v a$ is not orthogonal to \begin{equation*} V:=\text{span}(\v g_1,\dots,\v g_{k-1}). \end{equation*} Take any nonzero vector $\v h\in\R^k$ orthogonal to $V$ and such that $\v1\cdot\v h\ge0$, so that $\v1\cdot(\v a+\v h)\ge1>0$, and also short enough so that $\v a+\v h\in(0,\infty)^k$. Let
\begin{equation} \v b:=\frac{\v a+\v h}{\v1\cdot(\v a+\v h)}\in(0,\infty)^k. \tag{3} \end{equation} Then $\v b\ne \v a$, while (0a) and (2) hold with $\v x=\v b$. This contradicts $\v a$ being the only solution in $(0,\infty)^k$ of the system (0a)--(2).

Next, consider the case when $\v a$ is orthogonal to $V$ and $\v g_1,\dots,\v g_{k-1}$ are linearly dependent, so that there is a nonzero vector $\v h\in\R^k$ orthogonal to $V$ and to $\v a$ and such that $\v1\cdot\v h\ge0$, which also is short enough so that $\v a+\v h\in(0,\infty)^k$. Then again, for $\v b$ as in (3), we have $\v b\ne \v a$, while (0a) and (2) hold with $\v x=\v b$. This contradicts $\v a$ being the only solution in $(0,\infty)^k$ of the system (0a)--(2). Again, a contradiction.

Finally, consider the case when $\v a$ is orthogonal to $V$ and $\v g_1,\dots,\v g_{k-1}$ are linearly independent. Then there is a vector $\v h_1\in V$ such that $\v g_1\cdot\v h_1=1$ and $\v g_j\cdot\v h_1=0$ for $j=2,\dots,k-1$. Letting now $\v h:=t\,\v h_1$ for a small enough $t>0$ so that $\v1\cdot\v h\ge-1/2$ and $\v a+\v h\in(0,\infty)^k$, we get $\v1\cdot(\v a+\v h)\ge1/2>0$. So, again for $\v b$ as in (3), we have $\v b\ne \v a$, while (0a) and (2) hold with $\v x=\v b$. This contradicts $\v a$ being the only solution in $(0,\infty)^k$ of the system (0a)--(2). Once again, a contradiction.

Thus, $k$ is the smallest number of inequalities of the form $\v g_j\cdot\v x\ge0$ that will suffice.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.