Determining the optimal solution for a given function I have a function that I aim to minimize, however, I could not figure out the rule to reach the optimal. I am first sharing the function below and then providing a small example.
$\min_{\alpha \geq 0} f(\alpha) = [  z \alpha + \sum_{i=1}^{n} c_i \max\{ d_i - \alpha, 0 \}] $ where $z, c _i,  d_i $ are non-negative constant numbers.
For instance, if I try to find the optimal solution for the example shown below,
$\min_{ \alpha \geq 0} f(\alpha) = 0.95\alpha + 0.9 \max\{ 0.6 - \alpha, 0 \} + 0.4 \max\{ 0.11 - \alpha, 0 \} + 0.5 \max\{ 0.25 - \alpha, 0 \} $
The optimal solution is obtained when $\alpha = 0.25$. I am 100% sure that the optimal is attained whenever $\alpha$ is equal to one of given $d_i$, however, I sort of got stuck how to determine the index $i$. I was wondering if someone could provide me a hint.
Also, please note that I do no want to use a solver to reach the optimal.
 A: You can solve the problem via linear programming (LP) as follows.  Let $y_i$ represent $\max\{ d_i - \alpha, 0 \}$.  The problem is to minimize
$$z \alpha + \sum_{i=1}^n c_i y_i$$
subject to
\begin{align}
\alpha + y_i &\ge d_i &&\text{for all $i$} &&(\pi_i \ge 0)\\
\alpha &\ge 0 \\
y_i &\ge 0 &&\text{for all $i$} \\
\end{align}
The dual LP is to maximize
$$\sum_{i=1}^n d_i \pi_i$$
subject to
\begin{align}
\sum_i \pi_i &\le z &&&&(\alpha \ge 0)\\
\pi_i &\le c_i &&\text{for all $i$} &&(y_i \ge 0)\\
\pi_i &\ge 0 &&\text{for all $i$} \\
\end{align}
Without loss of generality, assume $d_1 \ge d_2 \ge \dots \ge d_n$ and $c_i>0$ for all $i$. Then an optimal dual solution is to take
\begin{align}
\pi_1^* &= \min\{z, c_1\}\\
\pi_2^* &= \min\{z - \pi_1^*, c_2\}\\
\pi_3^* &= \min\{z - \pi_1^* - \pi_2^*, c_3\}\\
\vdots \\
\pi_n^* &= \min\left\{z - \sum_{i=1}^{n-1} \pi_i^*, c_n\right\}
\end{align}
In particular, note that $\pi_i^* = 0$ implies $\pi_{i+1}^* = 0$.  Let
$$i^* = \min\left\{i: \sum_{j=1}^i c_j > z\right\}$$
be the smallest index for which $\pi_i^* = 0$.  Because $c_i > 0 = \pi_i^*$ for $i \ge i^*$, complementary slackness implies that $y_i^*=0$ for $i \ge i^*$, which suggests taking $\alpha^* = d_{i^*}$ and $y_i^* = \max\{ d_i - \alpha^*, 0 \}$, which is clearly primal feasible.
Now to certify optimality of this primal-dual pair $(\alpha^*,y^*)$ and $\pi^*$, compare the objective values.
For your example, $z=0.95$ and
\begin{matrix}
i & c_i & d_i & \pi_i^* & y_i^* \\
\hline
1 & 0.9 & 0.6  & 0.9  & 0.35 \\
2 & 0.5 & 0.25 & 0.05 & 0 \\
3 & 0.4 & 0.11 & 0    & 0 \\
\end{matrix}
So we have $i^* = 2$, with $\alpha^* = d_{i^*} = d_2 = 0.25$, as you claimed.
