Let $\mathbf{A}=\left(a_{ij}\right)$ be a $n\times J$ matrix with $a_{ij}\geq 0$, $n>J$ and such that no row or column has all its entries equal to zero. Let also $\mathbf{k}=\left(k_j\right)$ be a $J\times 1$ vector of non negative coeficients and $\mathbf{q}=\left(q_i\right)$ a $n\times 1$ vector of variables. Abusing notation, I'll write $\mathbf{q}^{\beta}=\left(q_i^{\beta}\right)$ for some $\beta>1$.

For each $j$, the following problem can be solved

$$\begin{align} \min\limits_{\{q_i\}}& \quad \sum_{i=1}^n q_i^{\beta}a_{ij}\\ \text{s.t.}&\quad \quad \begin{cases} \sum_{i=1}^n q_i=1\\ \mathbf{q}\geq 0. \end{cases} \end{align}$$

Let $\mathbf{q}^j$ denote the minimand, $\mathbf{z}^j=\mathbf{A}^{\top}\left(\mathbf{q}^j\right)^{\beta}$, $\mathbf{Z}=\left(z^j_j\right)$ the matrix resulting from adjoining all the $\mathbf{z}^j$ and $\langle \mathbf{Z}\rangle$ the convex cone spanned by $\mathbf{Z}$. It can be shown that $\langle \mathbf{Z}\rangle\subseteq \langle \mathbf{A}\rangle$. I'd like to prove that for $\mathbf{k}\in\langle \mathbf{Z}\rangle$, problems

$$\begin{align} \max\limits_{\{q_i\}}& \quad \sum_{i=1}^n q_i&\quad &\quad &\quad &\max\limits_{\{q_i\}}&\sum_{i=1}^n q_i\\ \text{s.t.}& \begin{cases} \mathbf{A}^{\top}\mathbf{q}^\beta\leq\mathbf{k}\\ \mathbf{q}\geq 0 \end{cases}&\quad&\quad &\quad &\text{s.t.}& \begin{cases} \mathbf{A}^{\top}\mathbf{q}^\beta=\mathbf{k}\\ \mathbf{q}\geq 0 \end{cases} \end{align}$$

yield the same result, i.e., all the inequality constraints other than the non negativity constraints are binding. I believe this result to be true also for $\beta=1$.


I'm trying to prove this by contradiction. Assume that the minimands are different and denote $\mathbf{\hat q}$ and $\mathbf{\tilde q}$ the solution to the problem with inequality and with equality constraints respectively. If $\mathbf{\hat q}\neq\mathbf{\tilde q}$, then it must happen that

  1. $\hat q=\sum_{i=1}^n \hat q_i>\sum_{i=1}^n \tilde q_i=\tilde q$
  2. $\mathbf{k}^{\prime}=\mathbf{A}^{\top}\mathbf{\hat q}^{\beta}\leq\mathbf{k}$, with strict inequality for some $j$

I think that it suffices to show that $\mathbf{k}^{\prime}\in\langle \mathbf{Z}\rangle$. Note that for $\mathbf{k}^{\prime}$, both problems need to yield $\mathbf{\hat q}$ as the solution and, therefore, the assumption that $\mathbf{k}\in\langle \mathbf{Z}\rangle\implies \mathbf{\hat q}\neq\mathbf{\tilde q}$ cannot be true.

I know that $k_j\geq k^{\prime}_j\geq \hat q^{\beta} z_j^j\;\forall j$, but an example has convinced me that this is not enough to warrant $\mathbf{k}^{\prime}\in\langle \mathbf{Z}\rangle$ when $J>2$ (it is enough for $J=2$, though).

I believe that some "continuity" argument must imply that, given $\mathbf{k}\in\langle \mathbf{Z}\rangle$, there must exist some $\mathbf{k}^{\prime\prime}\in\langle \mathbf{Z}\rangle$ such that $\mathbf{k}^{\prime\prime}\leq\mathbf{k}$ and that the solution to the problem with inequality constraints is unchanged. On the other hand, the solution to the problem with equality constraints would be $\mathbf{\tilde q}^{\prime\prime}$ and $\sum_{i=1}^{n}=\tilde q^{\prime\prime}_i>\tilde q$. Could iterating this procedure yield $\tilde q \rightarrow \hat q$?

Edit 2: Two other approaches, both of them incomplete:

  1. An alternative is trying to prove the contrapositive, i.e., \begin{equation*} \hat{\mathbf{q}}\neq\tilde{\mathbf{q}}\implies\mathbf{k}\not\in\langle \mathbf{Z}\rangle. \end{equation*}

    There are two cases:

  • $\nexists \tilde{\mathbf{q}}$. This can only happen if the feasible set is empty (if it is not empty, it is compact and convex, and since the objective function is continuous, it will reach a maximum). Let $\mathbf{w}=\left(w_{i}\right)_{1\leq i\leq n}$ with $w_{i}=q_{i}^{\beta}\geq 0$. The feasible set being empty implies that $\nexists \mathbf{q}\geq 0$ such that $\mathbf{A}^{\top}\mathbf{q}^{\beta}=\mathbf{k}$ and, therefore, $\nexists \mathbf{w}\geq 0$ such that $\mathbf{A}^{\top}\mathbf{w}=\mathbf{k}$. This means $\mathbf{k}\not\in\langle \mathbf{A}\rangle$ and, hence, $\mathbf{k}\not\in\langle \mathbf{Z}\rangle$.
  • $\exists \tilde{\mathbf{q}}$ but $\tilde{\mathbf{q}}\neq\hat{\mathbf{q}}$. The fact that they are different implies (a) $\sum \hat q_i>\sum\tilde q_i$ and (b) $\mathbf{k}^{\prime}\leq\mathbf{k}$ and $\exists j^*$ such that $k^{\prime}_{j^{*}}<k_{j^*}$. Let $\mathbf{w}=\left(w_{j}\right)_{1\leq j\leq J}$. If $\mathbf{Z}$ is full rank, the system $\mathbf{Z}\mathbf{w}=\mathbf{k}^{\prime}$ has a solution. If the solution was such that $\mathbf{w}\geq 0$ we'd have that $\mathbf{k}^{\prime}\in\langle \mathbf{Z}\rangle$. However, I don't know how to prove that indeed $\mathbf{w}\geq 0$. In addition, this leaves out the case of a singular $\mathbf{Z}$.
  1. Let $\mathbf{w}=\left(w_{j}\right)_{1\leq j\leq J}$ be a vector that (a) is a linear combination of $\mathbf{Z}$ and (b) is orthogonal to those $\mathbf{z}^j$ such that $k_{j}=k_{j}^{\prime}$. It should be the case that $\mathbf{w}^{\top}\mathbf{k}>\mathbf{w}^{\top}\mathbf{k}^{\prime}$. In fact, what needs to happen is that $\mathbf{w}$ separates $\langle \mathbf{Z}\rangle$ from the part of $\langle \mathbf{A}\rangle$ where $\mathbf{k}$ lies. The underlying rationale is that if the solutions to (I) and (II) are different, $\mathbf{k}\not\in\langle \mathbf{Z}\rangle$, while $\mathbf{k}^{\prime}\in\langle \mathbf{Z}\rangle$. As $\langle\mathbf{Z}\rangle$ is convex, we use a separating hyperplane, which is just the specific side of the cone on which $\mathbf{k}^{\prime}$ sits. The problem is that I don't know how to implement this approach.

Edit 3:

All three approaches boil down to proving that $\mathbf{k}^{\prime}=\mathbf{A}^{\top}\mathbf{\hat q}^{\beta}\in\langle \mathbf{Z}\rangle$.

Edit 4:

It can be shown that the two problems having different solutions implies that some of the Lagrange multipliers in the problem with equality constraints need to be negative. If it's possible to show that those multipliers are non-negative $\forall\mathbf{k}\in\langle\mathbf{Z}\rangle$ then we'll have completed the proof. I think the following proves that the Lagrange multipliers are indeed non-negative for each of the $\mathbf{z}^{j}$. However, I still need to extend the proof to the rest of $\langle\mathbf{Z}\rangle$.

Choose an input, say $j^{*}$. Solving the problem with inequality constraints with $\mathbf{k}=\mathbf{z}^{j^{*}}$ results in $\mathbf{q}^{j^{*}}$ and, therefore, a maximum production of 1, because $z_{j^{*}}^{j^{*}}$ is the minimum quantity of $j^{*}$ needed to produce one unit of output and, on the other hand, $\mathbf{q}^{j^{*}}$ is feasible and results in precisely in $\sum q_{i}^{j^{*}}=1$. Note that increasing marginally the available amount of any input except the $j^{*th}$ has no effect on the maximum production (because, again, it is limited by the fact that $z_{j^{*}}^{j^{*}}$ is the minimum needed for a production of one unit), and, therefore the corresponding KKT multipliers (denoted $\lambda_j$) need to be zero. On the other hand, we can obtain from the FOCs wrt $q_i\,\forall i$ of either problem
\begin{equation*} \sum_{i=1}^n q_i=\beta\sum_{j=1}^{J} \lambda_{j} \sum_{i=1}^{n} q_{i}^{\beta}x_{ij}. \end{equation*} As $\mathbf{q}^{j^{*}}$ satisfies the FOCs of both problems and $\lambda_{j}=0\;\forall j\neq j^{*}$, we have that $\lambda_{j^{*}}=\frac{1}{\beta z_{j^{*}}^{j^{*}}}>0$.

  • 2
    $\begingroup$ Given a solution that satisfies the inequalities, show that you can perturb it to satisfy at least one more equality without decreasing the objective. $\endgroup$ – RobPratt Oct 22 '20 at 13:07
  • $\begingroup$ @RobPratt, I think I'd need to know in what direction to perturb it, i.e., which $q_i$'s to increase and which to decrease, and I believe that this depends on the specific $\mathbf{A}$ and $\mathbf{k}$ $\endgroup$ – Patricio Oct 22 '20 at 14:10
  • $\begingroup$ @RobPratt, Hi, I added a few ideas, in case you want to take a look. $\endgroup$ – Patricio Nov 15 '20 at 10:09

Your Answer

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

Browse other questions tagged or ask your own question.