# Will all constraints in this LP be binding?

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} and $$0\leq x_{22} and proceed by contradiction. Suppose without loss of generality that $$q^*_1 x_{11}+q^*_2 x_{21}=c 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} 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?

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.
• Thanks. As noted in the question, for the $\beta>1$ case I believe this to be true for the subset of $\langle \mathbf{X}\rangle$ $\left(\langle \mathbf{Z}\rangle\right)$ of which I didn't offer any specifics. Your $\mathbf{k}$ falls outside of $\langle \mathbf{Z}\rangle$. I'll post a new question with its full definition. Mar 1 at 13:05
• I've written a new question in which I hope to have proved that all rows $i$ for which $\exists\,j\mid\mathbf{x}^j\leq\mathbf{x}^i$ will have $q_i^*=0$. If I'm correct I don't need the assumption I've used in this question. If you want to look into it, it's or.stackexchange.com/questions/8040/are-these-lp-equivalent Mar 11 at 11:44