KKT optimisation problem

Question

I want to find the minimum of the following function

$$\min \limits_{x}c^{T}x$$ $$\sum_{i=1}^nx_i=1$$ $$x_i \geq 0$$

Let's define Lagrangian function:

$$L(x,\lambda,\mu) = \sum_{i=1}^nc_ix_i - \sum_{i=1}^{n} \lambda_ix_i + \mu\sum_{i=1}^{n} x_i - \mu $$

Now, we can have KKT conditions:

$$ c_i - \lambda_i + \mu = 0 \\ \lambda_i x_i = 0 \\ \lambda_i \geq 0 $$

And now I'm stack and not sure how to proceed further. Any hint?

Answer 1

This is a linear programming problem on a simplex which is compact, there is an optimal solution at one of the vertices.

The vertices are the standard unit vector.

Let $j$ be an index corresponding to the smallest value of $c$. Then $e_j$ is one of the optimal solution. If there are multiple such $j$'s, then their convex combination are optimal as well.

---

$$(\mu + c_i)x_i = 0$$

If $x_i \ne 0 $ and $x_j \ne 0$, then we must have $c_i = c_j$. Hence if $c_i \ne c_j$, then $x_ix_j=0$. Hence the optimal solution must take one of the $c_i$'s value, we pick the smallest such value.

Answer 2

For the sake of future readers:

Let $c_\mathrm{min}$ be the smallest element of $c$ and let $i_\mathrm{min}$ be the index of this element. We have: \begin{align} c_1x_1&\ge c_\mathrm{min} x_1\\ c_2x_2&\ge c_\mathrm{min} x_2\\ &\dots\\ c_nx_n&\ge c_\mathrm{min} x_n. \end{align} Summing up the above, we obtain $c^Tx\ge c_\mathrm{min}(x_1+x_2+\dots+x_n) = c_\mathrm{min}$.

On the other hand, if $x_{i_\mathrm{min}} = 1$ and $x_i = 0 \ \forall i\neq i_\mathrm{min}$ then equality occurs: $c^Tx = c_\mathrm{min}$. We conclude that the minimum is $c_\mathrm{min}$.