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.
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.