3
$\begingroup$

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?
$\endgroup$
0

1 Answer 1

1
$\begingroup$
  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.
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Patricio
    Mar 1 at 13:05
  • $\begingroup$ The new question is or.stackexchange.com/questions/7963/…, in case you care to take a look at it. $\endgroup$
    – Patricio
    Mar 1 at 13:41
  • $\begingroup$ 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 $\endgroup$
    – Patricio
    Mar 11 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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