Will all constraints in this LP be binding?

Question

This is a follow up to my previous questions here and here . I've added the assumption that $m=2$.

Say $\mathbf{X}$ is a $n\times 2$ matrix with no negative entries and such that every row and every column have at least a non zero element.

Let $\mathbf{x}^i$ be the $i$-th row of $\mathbf{X}$ and assume further that $\mathbf{x}^i\not\leq\mathbf{x}^j$ and $\mathbf{x}^j\not\leq\mathbf{x}^i\;\forall i,j$.

Denote $\langle\mathbf{X}\rangle$ the cone spanned by $\mathbf{X}$. Let $\mathbf{q},\mathbf{k}, 1$, and $0$ be vectors of the suitable dimension. In the following LP $$ \begin{array}{ll} \text{maximize} &\quad \mathbf{q}\cdot 1\\ \text{subject to} & \quad \mathbf{X}^{\top}\mathbf{q}\leq\mathbf{k}\\ &\quad\mathbf{q}\geq 0, \end{array}$$

let $\mathbf{q}^*$ be its solution. I see that $\mathbf{k}\not\in\langle\mathbf{X}\rangle\implies \mathbf{X}^{\top}\mathbf{q}^*\leq\mathbf{k}$ (with $\mathbf{X}^{\top}\mathbf{q}^*\ne\mathbf{k}$), because $\mathbf{k}\not\in\langle\mathbf{X}\rangle$ implies that there does not exist a set of positive weights satisfying $\mathbf{X}^{\top}\mathbf{q}=\mathbf{k}$.

However, I believe that $\mathbf{k}\in\langle\mathbf{X}\rangle\implies \mathbf{X}^{\top}\mathbf{q}^*=\mathbf{k}$. Is this true? Why?

Edit For my purposes, it would be enough to show that this is true for the $n=2$ case. I'm trying to understand the linear case in the hope of being able to generalize the result to

$$ \begin{array}{ll} \text{maximize} &\quad \mathbf{q}\cdot 1\\ \text{subject to} & \quad \mathbf{X}^{\top}\mathbf{q}^{\beta}\leq\mathbf{k}\\ &\quad\mathbf{q}\geq 0, \end{array}$$

with $\beta>1$ and where $\mathbf{q}^{\beta}=(q_1^\beta,\dots,q_n^\beta)$. I believe this to be true for $\mathbf{k}\in\langle\mathbf{Z}\rangle\subseteq\langle\mathbf{X}\rangle$.

Also, ideas about why this does not hold for $n\times m$ matrices (with $m>2$) would be appreciated.

Edit 2: For the $n=2$ case, let $\mathbf{X}$ be such that $0\leq x_{11}<x_{21}$ and $0\leq x_{22}<x_{12}$ and proceed by contradiction. Suppose without loss of generality that $q^*_1 x_{11}+q^*_2 x_{21}=c<k_1$ while $q^*_1 x_{12}+q^*_2 x_{22}=k_2$. Consider $\mathbf{\bar q}=(q^*_1-\delta_1,q^*_2+\delta_2)$ for some $\delta_1,\delta_2>0$ such that $(q^*_1-\delta_1) x_{12}+(q^*_2 +\delta_2) x_{22}=k_2$. Clearly this implies that $$\delta_1=\frac{x_{22}}{x_{12}}\delta_2.$$ We now have \begin{align} (q^*_1-\delta_1) x_{11}+(q^*_2+\delta_2) x_{21}&=\left(q^*_1-\frac{x_{22}}{x_{12}}\delta_2\right) x_{11}+(q^*_2+\delta_2) x_{21}\\ &=c+\delta_2\left(x_{21}-\frac{x_{22}}{x_{12}}x_{11}\right). \end{align}

The term in parenthesis is positive and we can choose $$\delta_2=\frac{k_1-c}{x_{21}x_{12}-x_{22}x_{11}}x_{12}>0.$$

The change in the objective is $$\delta_2-\delta_1=\delta_2\left(1-\frac{x_{22}}{x_{12}}\right)>0,$$

because of the assumption $x_{22}<x_{12}.$ Hence, $\mathbf{q}^*$ is not a maximum.

I believe this shows that indeed $\mathbf{k}\in\langle\mathbf{X}\rangle\implies \mathbf{X}^{\top}\mathbf{q}^*=\mathbf{k}$. My questions are now

1. Is my proof correct?
2. Why can't this be generalized to $n\times m$ matrices when $m>2$? In the $2\times 2$ case it was easy to identify the direction in which to perturb the claimed solution to show that it did not lead to a maximum, but the fact that this doesn't hold for $3\times 3$ matrices suggests that in higher dimensions this direction may not exist altogether and I cannot see why.
3. How should I proceed in order to extend this result to the non-linear constraints in the second program above?

Answer 1

1. Yes, your proof is correct.
2. I don't think there is an easy answer to this.
3. The result does not extend to the nonlinear version. Let $\beta=2$. Set $$ \mathbf{X}^{\top}=\left[\begin{array}{cc} 1 & 2\\ 2 & 1 \end{array}\right] $$and $$\mathbf{k}=\left[\begin{array}{c} 2\frac{1}{9}\\ 1\frac{2}{9} \end{array}\right].$$The vector $\mathbf{\bar{q}} = (\frac{1}{3}, 1)$ is the unique solution to $$\mathbf{X}^\top \mathbf{q}^\beta = \mathbf{k}$$and has sum $1\frac{1}{3}.$ Now consider $\mathbf{\hat{q}}=(0.4594683, 0.8944272),$ for which $\mathbf{\hat{q}}^\beta = (0.2111111, 0.8).$ $$\mathbf{X}^\top \mathbf{\hat{q}}^\beta = \left[\begin{array}{c} 1.811\\ 1.222 \end{array}\right],$$ so $\mathbf{\hat{q}}$ is feasible (with some slack in the first constraint). The sum of the elements of $\mathbf{\hat{q}}$ is approximately 1.35386 > 1.33333, proving that $\mathbf{\bar{q}}$ is not optimal.