min linear over sum=1 constraint

Dependencies: None

$$ Let $a_1,a_2,\dots ,a_n$ be real numbers. Let $a_k\le a_i$ for all $i$. The optimization program $$\underset{x\in {\mathbb{R}}^n}{min}\sum _{i=1}^n{a}_i{x}_i\text{ where }\sum _{i=1}^n{x}_i=1\text{ and }{x}_i\ge 0\mathrm{\forall }i$$ has $x^{\ast }$ as an optimal solution, where $$x_i^{\ast }=\{\begin{array}{ll}1& \text{ if }i=k\\ 0& \text{ otherwise}\end{array},$$ and thus the optimal value is $a_k$.

Similarly, if $a_r\ge a_i$ for all $i$, then the optimal solution to the maximization problem is where the $r^{\text{th}}$ coordinate is 1 and all other coordinates are 0.

Proof

Let $\hat{x}$ be a feasible solution to the optimization program. Then $\sum _{i=1}^n{\hat{x}}_i=1$ and ${\hat{x}}_i\ge 0$ for all $i$.

$$\begin{array}{rl}& \sum _{i=1}^n{a}_i{\hat{x}}_i-\sum _{i=1}^n{a}_i{x}_i^{\ast }\\ & =\sum _{i=1}^n{a}_i{\hat{x}}_i-a_k\\ & =\sum _{i=1}^n{a}_i{\hat{x}}_i-a_k\left(\sum _{i=1}^n{\hat{x}}_i\right)\\ & =\sum _{i=1}^n(a_i-a_k){\hat{x}}_i\\ & \ge 0.\end{array}$$ Hence, $\sum _{i=1}^n{a}_i^T{x}_i^{\ast }\le \sum _{i=1}^n{a}_i^T{\hat{x}}_i$. Hence, $x^{\ast }$ is an optimal solution.

Dependency for:

1. LP is optimized at BFS

Info:

• Depth: 0
• Number of transitive dependencies: 0

Transitive dependencies: None