Chemical potential of noninteracting bosons is known to be negative because the Bose-Einstein distribution $[e^{(\epsilon-\mu)/T}-1]^{-1}$ should be free of singularities. However, I don't fully understand how it is connected with the thermodynamic definition $\mu=\partial E/\partial N$ of chemical potential as the minimal energy required to add an extra particle to the system. Consider the mean occupation numbers $\{n_i\}$, then $$ N=\sum_i n_i,\qquad E=\sum_i \epsilon_in_i\quad\mbox{and}\quad N'=\sum_i n'_i,\qquad E'=\sum_i \epsilon_in'_i $$ before and after adding an extra particle. If $\Delta n_i=n_i'-n_i$, then $$ \Delta N\equiv N'-N=\sum_i\Delta n_i,\qquad\Delta E\equiv E'-E=\sum_i \epsilon_i\Delta n_i. $$ Since $\Delta N=1$, we have $$ \Delta E\geqslant\min(\epsilon_i)\sum_i\Delta n_i=\min(\epsilon_i)\geqslant0. $$ So we obtain $\Delta E\geqslant0$ hence $\mu$ should not be negative.
One might argue that we should work in canonical ensemble where $\mu=\partial F/\partial N$, $F$ is the free energy. However we can consider, for example, the $(N,V,S)$ ensemble, where $dE=TdS-pdV+\mu dN$, so $\mu$ is still $\partial E/\partial N$. I suppose it is possible to add an extra particle in such a way that $S$ will not change.
So why the chemical potential of noninteracting bosons is negative despite the fact that nonnegative energy is needed to add a particle to the system?