Closed form solution of the following linear programming question

convex optimizationduality-theoremskarush kuhn tuckerlinear programmingoptimization

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.

Best Answer

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.

Related Question