1
$\begingroup$

This is a follow up of my previous question. I repeat it below with an additional condition (in italics).

Say $\mathbf{X}$ is a $n\times m$ 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?

$\endgroup$

1 Answer 1

5
$\begingroup$

Counterexample:

$$X^{T}=\left[\begin{array}{cc} 1 & 5 & 6\\ 0 & 1 & 0\\ 6 & 5 & 1 \end{array}\right],\ k=\left[\begin{array}{c} 12\\ 1\\ 12 \end{array}\right].$$

$\endgroup$
1
  • $\begingroup$ Thanks. I believe that it is only true for $m=2$ $\endgroup$
    – Patricio
    Commented Feb 16, 2022 at 19:18

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.