1
$\begingroup$

Say $\mathbf{X}$ is a $n\times m$ matrix with no negative entries. Assume further that every row and every column have at least a non zero element. 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?

$\endgroup$

1 Answer 1

3
$\begingroup$

No, it is not true. Consider $$X^{T}=\left[\begin{array}{cc} 1 & 6\\ 1 & 3 \end{array}\right],\ k=\left[\begin{array}{c} 7\\ 4 \end{array}\right].$$

$\endgroup$
1

Your Answer

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

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