Bounding \(D_\Phi (\mathbf {x}_*, \mathbf {x}_1)\) : The minimum value of \(\Phi (x)\)  over \(\mathcal {X}\)  is achieved when we spread the capacity mass \(k\)  over the decision variable, giving \(x_i = \frac{k}{N}, i \in \mathcal {N}\) . If we select \(\mathbf {x}_1\)  to be the minimizer of \(\Phi (\mathbf {x})\) , then we have \(\nabla \Phi ^T(\mathbf {x}_1) (\mathbf {x} - \mathbf {x}_1) \ge 0 , \forall \mathbf {x} \in \mathcal {X}\)  [1]}.
\(D_\Phi (\mathbf {x}_*, \mathbf {x}_1) &= \Phi (\mathbf {x}_*) - \Phi (\mathbf {x}_1) - \nabla {\Phi (\mathbf {x}_1)}^T (\mathbf {x}_* - \mathbf {x}_1) \le \Phi (\mathbf {x}_*) - \Phi (\mathbf {x}_1)\) 
