# Relationship between two minimization problems

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.

• Could you link to the suggestion of @MikeY? Also, how is $\underline{k}$ defined? – Kevin Dalmeijer Nov 17 '19 at 7:48
• @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. – Patricio Nov 18 '19 at 8:13
• @KevinDalmeijer, Do you have any hint as to how to proceed? – Patricio Nov 19 '19 at 14:17
• @KevinDalmeijer, I see my mistake, I hadn't defined $k_j$. I've corrected that and added some further info. – Patricio Nov 20 '19 at 9:35
• 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. – Kevin Dalmeijer Nov 20 '19 at 11:38