Okay, I'm not really sure whether the title is good. Consider
\begin{align*} \min\{ 5x_1 + \frac{5}{2}x_2 + \frac{5}{3}x_3 + \frac{5}{4}x_4, \\ x_1 + \frac{6}{2}x_2 + \frac{6}{3}x_3 + \frac{6}{4}x_4, \\ x_1 + x_2 + \frac{7}{3}x_3 + \frac{7}{4}x_4, \\ x_1 + x_2 + x_3 + 2x_4\}. \end{align*}
Moreover, I have the restrictions $0 \le x_i \le 1$ and $\sum x_i = 1$. I want to maximize the above term by choosing the $x_i$ appropriately. How can I show that the optimal choice is the one that sets the four terms equal (i.e., $x_1 = 25 / 369, x_2 = 40 / 369, x_3 = 48 / 369, x_4 = 256 / 369$)?
I have read about linear programming, the lower envelope, convex optimization, piecewise-linear functions—but I cannot quite put all of this together. Can anyone give me a hint in the right direction?
Since you just want a hint, I'll just walk through how you can reformulate this an LP. First note that the constraints $x_i \le 1$ are redundant, since nonnegative numbers which sum to 1 cannot be greater than 1. Then using vector notation the problem can be stated as: $$ \begin{gathered} \max_{\mathbf{x}} \ \min_i \mathbf{a}_i^T \mathbf{x} \\ \text{s.t.: } \mathbf{x}^T \mathbf{1} = 1 \\ \mathbf{x} \ge 0 \end{gathered} $$ Then we can introduce another variable $y$ without changing the problem: $$ \begin{gathered} \max_{\mathbf{x}, y} \ y \\ \text{s.t.: } \min_i \mathbf{a}_i^T \mathbf{x} \ge y\\ \mathbf{x}^T \mathbf{1} = 1 \\ \mathbf{x} \ge 0 \end{gathered} $$ Then this is equivalent to the LP: $$ \begin{gathered} \max_{\mathbf{x}, y} y \\ \text{s.t.: } \mathbf{a}_i^T \mathbf{x} \ge y \text{ for } i=1\ldots4\\ \mathbf{x}^T \mathbf{1} = 1 \\ \mathbf{x} \ge 0 \end{gathered} $$ In matrix notation this is: $$ \begin{gathered} \max_{\mathbf{x}, y} y \\ \text{s.t.: } \mathbf{Ax} \ge y \mathbf{1}\\ \mathbf{x}^T \mathbf{1} = 1 \\ \mathbf{x} \ge 0 \end{gathered} $$ Lastly, if you want to put this in standard form, you can introduce a slack variable. Also, it doesn't hurt to assume $y \ge 0$. $$ \begin{gathered} \max_{\mathbf{x}, y, \mathbf{z}} y \\ \text{s.t.: } \mathbf{Ax} = y \mathbf{1} + \mathbf{z}\\ \mathbf{x}^T \mathbf{1} = 1 \\ \mathbf{x}\ge 0, y\ge0, \mathbf{z} \ge 0 \end{gathered} $$ Finally, expressed in standard form with block matrices we have: $$ \begin{gathered} \max_{\mathbf{x}, y, \mathbf{z}} \ \begin{bmatrix} \mathbf{0} \\ 1 \\\mathbf{0}\end{bmatrix}^T \begin{bmatrix} \mathbf{x} \\ y \\\mathbf{z}\end{bmatrix} \\ \text{s.t.: } \begin{bmatrix} A & -\mathbf{1} & -\mathbf{I} \\ \mathbf{1}^T & 0 & \mathbf{0}^T \end{bmatrix} \begin{bmatrix} \mathbf{x} \\ y \\\mathbf{z}\end{bmatrix} = \begin{bmatrix} \mathbf{0} \\ 1 \end{bmatrix}\\ \begin{bmatrix} \mathbf{x} \\ y \\\mathbf{z} \end{bmatrix} \ge 0 \end{gathered} $$ Your problem is then reduced to showing that the optimal solution to this LP has $\mathbf{z}=0$.