Consider the following simple linear program with one equality constraint and a simple set of inequalities bounding the variables:
\begin{align}
\max_{x_1,\dots,x_K} & \sum_{k=1}^K a_kx_k \\
\text{subject to:} \; & \sum_{k=1}^K p_kx_k = b \\
& x_k \in [0,1] \; \forall \; k
\end{align}
My goal is to characterize the set of $\{(x^*_1,\dots,x^*_K)\}$ that achieve the maximum of this program, and I am struggling to do this. In case it helps, $a_k$ are all distinct and $\sum p_k =1, p_k \geq 0$ (all of these constants are known). I'm not interested in numerically solving this, and was wondering if there is a way to analytically identify the set that achieves the max.
Attempt:
I remember from first year of college the lagrangian method, which I believe involves considering
$$\mathcal{L}(x_1,\dots,x_K,\lambda) = \sum_{k=1}^K a_kx_k – \lambda(\sum_{k=1}^K p_kx_k – b)$$
but the gradient is simply
$$a_k – \lambda(b-p_k) = 0 \; \forall \; k$$
which implies that
$$\lambda = \frac{a_k}{b-p_k}$$
and I don't see how that can hold for all $k$ so I must be doing something wrong?
Could someone please advise on how I could go about analytically characterizing the set $\{(x^*_1,\dots,x^*_K)\}$ that achieve the max in this linear objective function/single linear equality constraint setting? I can do this for simple examples, but don't understand how to generalize.
Best Answer
Presumably $0 \le b \le \sum_i p_i$ (otherwise there is no feasible solution).
We may assume the indices $1, \ldots, K$ are sorted in order of decreasing $a_k/p_k$ (where this is taken as $+\infty$ if $p_k = 0$ and $a_k > 0$, and $-\infty$ if $p_k = 0$ and $a_k < 0$). The point is that if you think of $p_k$ as the cost per unit of variable $x_k$ and $a_k$ as the return per unit, $a_k/p_k$ is the return per unit spent on $x_k$. The optimal solution is to spend as much as possible on the items that give you the best return per unit spent. Thus if $\sum_{i=1}^{k-1} p_i \le b < \sum_{i=1}^{k} p_i$, you take $x_i = 1$ for $i \le k-1$, $x_i = 0$ for $i > k$, and $x_k = \left(b - \sum_{i=1}^{k-1} p_i\right)/p_k$.
EDIT: The problem with your "lagrangian method" is that it doesn't take into account the bounds $0 \le x_i \le 1$. If you take those bounds into account, you essentially have the dual linear programming problem.
The dual linear programming problem here is $$ \eqalign{\text{minimize}\ & b y + \sum_{i=1}^k \xi_k\cr \text{subject to}\ & p_i y + \xi_i \ge a_i \ \forall i\cr & \xi_i \ge 0 \ \forall i}$$ The optimal solution should have $\xi_i = 0$ for $i \ge k$ with $p_i y + \xi_i = a_i$ for $i \le k$, thus $y = a_k/p_k$. Showing that this gives you a feasible solution of the dual problem, and satisfies complementary slackness with my solution of the original problem, you can conclude that these solutions are optimal.