# Find an optimal solution formula from multiple variables analytically

If I have an optimization problem as follows: \label{eqn:for3b} \begin{aligned} (\mathbf{P}_1) \phantom{10} & \max_{\boldsymbol{\pi}} \phantom{5} \sum_{i=1}^I\pi_i(a_i - b_i). \end{aligned} $$\begin{eqnarray} \text{ s.t. } \quad \sum_{i=1}^I \pi_i a_i \leq S, \label{eqn:for3c} \\ 0 \leq \pi_i \leq 1, \forall i \in [1, I] \end{eqnarray}$$ how to find the optimal solution formula of $$\pi_i, \forall i \in [1,I]$$? As far as I understand the optimal solution occurs if $$\frac{\partial(\sum_{i=1}^I\pi_i(a_i - b_i))}{\partial\pi}= 0$$. In this way I can obtain Lagrangian expression: \label{eqn:for3a} \begin{aligned} L(\pi,\lambda,\sigma) &= \sum_{i=1}^I\pi_i(a_i - b_i) - \lambda_1(S - \sum_{i=1}^I \pi_i a_i - \sigma_1) + \lambda_2(\pi_1 - \sigma_2) \\ &+ \lambda_3(1 - \pi_1 - \sigma_3) + ... + \lambda_{I+1}(\pi_I - \sigma_{I+1}) + \lambda_{I+2}(1 - \pi_I - \sigma_{I+2}). \end{aligned} However, since it has many $$\pi$$'s, how can I obtain the general optimal $$\pi^*_i, \forall i \in [1,I]$$ formula? Is there any suggestion using KKT conditions?

This problem is the linear programming (LP) relaxation of a 0-1 knapsack problem, and an optimal solution is obtained by sorting in descending order the ratio $$(a_i-b_i)/a_i$$ and setting $$\pi_i$$ according to this order. This greedy algorithm is optimal for the LP relaxation but only a heuristic if you require $$\pi_i \in \{0,1\}$$.
• It would be easy to solve using optimization solver. However, is there any way to find $\pi_i^*, \forall i \in [1,I]$ analytically, i.e., $\pi_i^* = ...$, for example using KKT conditions? Sep 14 '19 at 1:58
• I didn't mean to use an optimization solver. The optimal solution is to reindex so that $(a_i-b_i)/a_i \ge (a_{i+1}-b_{i+1})/a_{i+1}$ and then set $\pi_1 = \pi_2 = \dots = \pi_{j-1} = 1$ until $\sum_{i=1}^{j-1} a_i \le S < \sum_{i=1}^j a_i$, $\pi_j = (S - \sum_{i=1}^{j-1} a_i)/a_j$, and $\pi_{j+1} = \dots = \pi_I = 0$. Sep 14 '19 at 2:36
• At the end, is it correct that $\pi_i^* = \sum_{i=1}^{j-1}(a_i - b_i) + (a_j - b_j)\frac{S - \sum_{i=1}^{j-1}a_i}{a_j}$? In this case, how to find the correct $j$? Sep 14 '19 at 3:25
• No, after reindexing in descending order of $(a_i-b_i)/a_i$, the optimal solution looks like $\pi^*=(1,\dots,1,\pi^*_j,0,\dots,0)$, where $j$ is the smallest index such that $\sum_{i=1}^j a_i > S$. Sep 14 '19 at 3:31