8
$\begingroup$

Let $\mathbf{A}$ be a ${n\times J}$ matrix with $A_{ij}\geq0$ (and $A_{ij}>0$ for most $ij$, there cannot be any rows or columns that consist only of $0$s), $Q=\left\{\mathbf{q}\mid \mathbf{q}\in\Bbb R^n_+\land\sum\limits_{i=1}^n q_i=1\right\}$ and an $0<\alpha<1$. Abusing notation, let $\mathbf{q}^{\frac{1}{\alpha}}=\bigl(q_1^\frac{1}{{\alpha}},\dots,q_n^\frac{1}{{\alpha}}\bigr).$

Consider the set $K=\{\mathbf{k}\in\Bbb R^J_+\mid \mathbf{k}=\mathbf{A}^{\top}\mathbf{q}^\frac{1}{{\alpha}}\land \mathbf{q}\in Q\}.$ There exist $J$ members of $K$ such that the $j$-th component of $\underline{\mathbf{k}}^j$ is lower than the $j$-th component of any other $\mathbf{k}\in K$. These can be easily identified using calculus.

The $\mathbf{k}\in K$ that I'm interested in can be found as follows

  1. Choose some $\beta \in\Bbb R^J_+$ such that $\sum\limits_{j=1}^J b_j=1,$
  2. Compute $\widehat{\mathbf{k}} =\sum\limits_{j=1}^J\beta_j\underline{\mathbf{k}}^j,$
  3. Determine the proportions $\mathbf{r}=\frac{1}{\hat k_1}\widehat{\mathbf{k}}$
  4. Let $k_j=\sum\limits_{i=1}^nA_{ij}q_i^{\frac{1}{\alpha}}$ and minimize $k_1$ subject to $\mathbf{k}\in K$ and $k_j=r_j k_1 \quad \forall j=\{2,\dots,J\}.$ If $k^*_1$ is the minimum of this problem, then $\mathbf{k}^*=(k^*_1,r_2 k^*_1,\dots,r_J k^*_1)$ lies on the frontier.

@MikeY suggested that I could solve instead the following problem:

$$\begin{align} \min\limits_{\{q_i\}}&\quad \delta^{\top}\mathbf{A}^{\top}\mathbf{q}^\frac{1}{{\alpha}}\\ \text{s.t.}&\quad\begin{cases} \sum\limits_{i=1}^n q_i=1 \\ q_i \geq 0 & i=\{1,\dots,n\} \\ \end{cases} \end{align}$$

for some $\delta \in \Bbb R_+^J$ such that $\sum\limits_{j=1}^J \delta_j=1$. If $\mathbf{q}^*$ is the minimand of this problem, then $\mathbf{k}^*=\mathbf{A}^{\top}\left(\mathbf{q}^*\right)^\frac{1}{{\alpha}}$ lies on the frontier. I've tried this approach, that is computationally much more efficient, and it works fine in the sense that it results in a frontier that is indistinguishable from the one obtained with my approach.

My questions are:

  1. Why is this second approach equivalent to mine? I can see that if $\delta^j$ is a vector of zeroes except for the $j-th$ component that is a $1$, @MikeY's approach yields $\underline{\mathbf{k}}^j$, but I don't see why this is also the case for other points in the frontier.
  2. What is the relationship between $\beta$ and $\delta$? For $J=2$, @MikeY suggests that $\delta=(\beta,1-\beta)$. My exploration of a $J=3$ case, indicates that the relationship is not so obvious.
  3. Ideally, I'd like to be able to determine the $\delta$ that corresponds to any $\widehat{\mathbf{k}}$ that is a convex combination of the $\underline{\mathbf{k}}^j$s.

Edit: @MikeY's suggestion is the third answer to my question in Stack Exchange Mathematica site.

Edit 2: We can write the Lagrangian of the first problem to ressemble that of the second (ommiting the non-negativity constraints is of no consequence): $$\begin{align}\mathcal L &=k_1+\sum\limits_{j=2}^J \lambda_j (k_j -k_1 r_j) +\gamma \left(1-\sum\limits_{i=1}^nq_i\right)\\ & =\left(1-\sum\limits_{j=2}^J \lambda_j r_j\right)k_1 + \sum\limits_{j=2}^J \lambda_j k_j+\gamma \left(1-\sum\limits_{i=1}^nq_i\right)\end{align}.$$ One could set $\rho_1=1-\sum\limits_{j=2}^J \lambda_j r_j$ and $\rho_j=\lambda_j \quad j=\{2,\dots,J\},$ observe that $$\sum\limits_{j=1}^J\rho_j=1-\sum\limits_{j=2}^J\lambda_j(r_j-1),$$ and write $\delta_j=\frac{\rho_j}{\sum\limits_{j=1}^J\rho_j}$ which would result in an equivalent lagrangian (in the sense that the minimand is the same)

$$ \mathcal L' =\sum\limits_{j=1}^J \delta_j k_j+\gamma' \left(1-\sum\limits_{i=1}^nq_i\right)$$ The problem is that, although these deltas do add up to one, $\delta_1$ can be negative, in which case (some) $\delta_j$s can be larger than one. Further, I'd like to be able to obtain $\delta$ without having to compute the $\lambda_j$s first.

$\endgroup$
  • $\begingroup$ Could you link to the suggestion of @MikeY? Also, how is $\underline{k}$ defined? $\endgroup$ – Kevin Dalmeijer Nov 17 '19 at 7:48
  • $\begingroup$ @KevinDalmeijer, I've added the link. I don't think I've used any $\underline{k}$. If you mean $\underline{\mathbf{k}}^j,$ it's the member of $\mathbf{K}$ whose $j$-th component is the lowest. $\endgroup$ – Patricio Nov 18 '19 at 8:13
  • $\begingroup$ @KevinDalmeijer, Do you have any hint as to how to proceed? $\endgroup$ – Patricio Nov 19 '19 at 14:17
  • $\begingroup$ @KevinDalmeijer, I see my mistake, I hadn't defined $k_j$. I've corrected that and added some further info. $\endgroup$ – Patricio Nov 20 '19 at 9:35
  • $\begingroup$ Thank you for clearing this up. I won't be able to answer this question, but I am sure the edits make it easier for others to help you. $\endgroup$ – Kevin Dalmeijer Nov 20 '19 at 11:38

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.