closed-form on linear programming optimization

68 Views Asked by At

I am interested in the following linear programming optimization problem.

\begin{align} O: \max_{E_k}\sum_{k=1}^{K} E_k P_k,\\ {\rm{subject\; to:}} \sum_{k=1}^{K} E_k\le E, \end{align} where $E_k$, $P_k$, $K$, and $E$ are all real constant. Is there a general closed-form expression of $P_k, k\in 1,\dots, K$ for the solution rather than using software to solve it, especially when $K$ turn to be large?

2

There are 2 best solutions below

0
On

The problem you state has no optimal solutions (is unbounded) unless $P_1=P_2=\cdots=P_K\geq 0$.

Indeed, since the problem is convex and the constraint qualifications are satisfied (we have a single linear constraint) the KKT conditions are both necessary and sufficient for optimality. In the present case they amount to the existence of the Lagrange multiplier $\lambda \geq 0$ such that $P_k = \lambda$, $\sum_{k=1}^K E_k \leq E$, and $\lambda[\sum_{k=1}^K E_k - E] = 0$. Thus when the solution exists, you can e.g. take $E_1 = E$, $E_2=\cdots=E_K=0$ as the desired closed form, among infinitely many other possibilities when $K>1$.

0
On

Assuming $P_k\ge 0$ and $E_k \ge 0$, this is a special case of the continuous knapsack problem, and greedy is known to be optimal. Explicitly, take $E_k=E$ for the $k$ that corresponds to the largest $P_k$.