Closed form solution of the following linear programming question

Question

I want to ask whether the following question has a closed form solution: $$ \begin{cases} \displaystyle\min_{x} c^T x \\ \mbox{ s.t. } \\ \mathbf{1}^Tx = b \\ \quad x \geq 0 \end{cases} $$

We can write down the kkt condition as: $$ \begin{aligned} L &= c^T x - \langle \lambda_1,\mathbf{1}^Tx-b\rangle - \langle \lambda_2,x\rangle\\ \partial L/\partial x &= c - \mathbf{1}\lambda_1 - \lambda_2 = 0\\ [\lambda_2]_i\cdot x_i &= 0\\ [\lambda_2]_i &\geq 0 \end{aligned} $$

Denote ith component of $c$ as $c_i$. Now we can see that when $(c_i-\lambda_1) \geq 0$, then we must have $x_i = 0$ and $(c_i-\lambda_1) = 0$, we also must have $x_i > 0$. But I am not sure how to proceed to the next.

Answer 1

You are almost there. First, notice that $c - \lambda_1 \mathbf{1} - \lambda_2 = \mathbf{0} \implies \lambda_2 = c - \lambda_1 \mathbf{1}$. Plugging this back into $L$ we get that, \begin{aligned} L &= c^{\mathsf{T}} x - \langle \lambda_1,\mathbf{1}^{\mathsf{T}}x-b\rangle - \langle \lambda_2,x\rangle\\ &= c^{\mathsf{T}} x - \langle \lambda_1,\mathbf{1}^{\mathsf{T}}x-b\rangle - \langle c-\lambda_1\mathbf{1},x\rangle \\ &= \lambda_{1}b \end{aligned} Second, you are technically missing the condition that $\mathbf{1}^{\mathsf{T}}x=b$ and $x\geq 0$ in your KKT conditions.

Lastly, you found that for all $i$ that $c_i \geq \lambda_1$. There are two cases you need to check, $\lambda_1 = \min_i c_i$ or $\lambda_1 < \min_i c_i$. If $\lambda_1 < \min_i c_i$ then $[\lambda_2]_i > 0$ for all $i$, which implies that $x_i = 0$ for all $i$. This can only occur if $b=0$ and is a kind of a degenerate case since the constraint $\mathbf{1}^{\mathsf{T}}x = 0$ plus $x\geq 0$ implies $x = 0$. If $b>0$ then it must be the case that $\lambda_1 = \min_i c_i$. From here it should be straightforward to determine what $\lambda_2$ is and also what $x_i$ is.

Answer 2

Your primal problem is to minimize $\sum_j c_j x_j$ subject to $\sum_j x_j=b$ and $x_j \ge 0$ for all $j$. Assuming $c_j \ge 0$ and $b \ge 0$, it is clearly optimal to take $x_j = b$ for the smallest $c_j$, yielding optimal objective value $b \min_j c_j$. To formally prove the optimality, consider the dual problem, which is to maximize $b y$ subject to $y \le c_j$ for all $j$. Now note that $y = \min_j c_j$ is dual feasible and has objective value $b \min_j c_j$. Because these primal and dual objective values agree, weak duality implies that both solutions are optimal, even without any assumptions on $c_j$ and $b$.