4

Minimise $\displaystyle \sum_{i=1}^n \frac{1}{a_i + x_i}$ subject to $\displaystyle \sum_{i=1}^n x_i =b$, $x_i\geq 0$ for $i=1,\cdots , n$, where $a_i >0$ for $i=1,\cdots , n$ and $b>0$.

I know I need to use Lagrange multipliers to do this, but I'm having difficulty getting the calculation to work. In particular, I am confused about what the set $Y=\{\lambda: inf_{x\geq 0}L(x, \lambda)>-\infty\}$ is. Many thanks for your help.

1 Answers1

3

Your problem reads: \begin{align} \min_{x_i,~i=1,\ldots,n}~& \sum_{i=1}^n \frac{1}{a_i+x_i}\\ s.t.~& \sum_{i=1}^n x_i=b\\ & x_i\geq 0,~\forall i\in\{1,\ldots,n\} \end{align}

Let $\lambda$ be the Lagrange multiplier associated with the equality constraint and $\mu_i\leq 0,~i=1,\ldots,n$ be the Lagrange multipliers associated with the inequality constraints. The Lagrangian of the problem reads: \begin{equation} \mathcal{L}(\mathbf{x},\lambda,\mathbf{\mu})=\sum_{i=1}^n \frac{1}{a_i+x_i}+\lambda \left(\sum_{i=1}^n x_i-b\right)+\sum_{i=1}^n\mu_i x_i \end{equation} The KKT conditions are: \begin{align} \mu_i&=\frac{1}{(a_i+x_i)^2}-\lambda,~\forall i\\ \sum_{i=1}^nx_i&=b\\ x_i&\geq 0,~\forall i\\ \mu_i&\leq 0,~\forall i\\ \mu_ix_i&=0,~\forall i \end{align} The first condition corresponds to $\frac{\partial \mathcal{L}}{\partial x_i}=0,~\forall i$, the second and third to the primal feasibility, the fourth to dual feasibility and the fifth is the complementary slackness condition. Substituting the first condition in the last yields: \begin{equation} x_i\left(\frac{1}{(a_i+x_i)^2}-\lambda\right)=0 \end{equation}

Consider a fixed index $k$:

  • If $a_k<\frac{1}{\sqrt{\lambda}}$, then the condition that $\mu_k\leq 0$ implies that we must have $x_k>0$ in order to satisfy the first condition, which in turn implies that we must have $x_k=\frac{1}{\sqrt{\lambda}}-a_k$ in order to satisfy the complementary slackness condition.
  • If $a_k\geq \frac{1}{\sqrt{\lambda}}$, then the complementary slackness condition can only be satisfied if $x_k=0$

We have thus shown that: $$ x_k= \begin{cases} 0 & a_k\geq \frac{1}{\sqrt{\lambda}},\\ \frac{1}{\sqrt{\lambda}}-a_k & a_k<\frac{1}{\sqrt{\lambda}} \end{cases} $$

Finally, you can find $\lambda$ by using the second KKT condition, which reads: $$ \sum_{i=1}^n \max\left(0,\frac{1}{\sqrt{\lambda}}-a_k\right)=b $$ The sum on the left is a continuous and piecewise differentiable function with break-points at the $1/a_k^2$.

This problem is very closely related to the Water-filling problem, which you can find for instance in Stephen Boyd's Convex Optimization book, page 245.

The interpretation of the problem is that you start allocating your budget to the indices of lower $a_k$, and that all indices to which some of the budget has been allocated have a common $a_k+x_k$ value. Whenever this common level reaches a new value $a_{k'}$, you also start allocating budget to the index $k'$ and so on, until you run out of budget.

Edit

As an illustration, I have let $n=20$ and generated random values for the $a_i$ in the interval $[1,50]$. I have let $b=150$ and solved the problem as described above. The following graph sums up the results:

enter image description here

You can observe that the indices are filled up to the level $\frac{1}{\sqrt{\lambda}}$ (whenever that makes sense). You can play with the following code that I used to generate the picture.

M=50;
n=20;
a=randi(M,1,n);
b=150;
g=@(lam) sum(max(0,1./sqrt(lam)-a))-b;
lambda=fzero(g,0.001);
x=max(0,1./sqrt(lambda)-a);

bar(a+x)
hold on
bar(a,'green')
Alvaro Maggiar
  • 1,028