I got a resource allocation problem as follows: \begin{eqnarray} \min &\sum_{i=1}^M \frac{1}{1 + \text{exp}(C_i + \frac{r_i}{1+r_i})} ;\\ &\sum_{i=1}^M r_i \le R;\\ &r_i \ge 0 \,\,\,\text{for}\,\,\, i = 1,2,...,M. \end{eqnarray} The objective function is convex and the constraints are linear. For simplicity, assume $C_i = 1$ for $i = 1,2,...,M$. When I tried to use CVX to solve the problem, I rewrite the problem as follows:
cvx_begin
variable x(M) nonnegative
minimize( sum(inv_pos(1 + exp(x))) )
subject to
sum(inv_pos(2-x)) <= R + M
x >= 1
x < 2
cvx_end
where $x_i = 1 + \frac{r_i}{1+r_i}$. However, CVX cannot solve it, since 1/(1 +exp(x)), x>0 is not thought to be convex.
Is there any other way to rewrite the problem, such that CVX can solve it? Or is there any other good tool to use? Thx :)
I am assuming you have checked that the cost $f$ is convex. Note that if $\Pi$ is a permutation matrix, then $f(x) = f(\Pi x)$ and if $x$ satisfies the constraints then so does $\Pi x$.
Let $\Pi$ be the permutation that just shifts 'left', that is, $\Pi (x_1,...,x_n)^T = (x_2,x_3,...,x_n,x_1)^T$. Then we see that $f({1 \over n}(x+\Pi x+\cdots+ \Pi^{n-1} x)) \le f(x)$ since $f$ is convex.
Note that all components of ${1 \over n}(x+\Pi x+\cdots+ \Pi^{n-1} x)$ are the same.
Hence we need only consider the function $\phi(\lambda) = f(\lambda e)$, where $e=(1,1,...,1)^T$ and the problem reduces to solving $\min \{ \frac{M}{1 + \text{exp}(1 + \frac{\lambda}{1+\lambda})} | \lambda \ge 0, M \lambda \le R\}$. The cost function is strictly decreasing (look at the derivative), hence a minimizer is at $\lambda = {R \over M}$, hence $x={R \over M} e$ solves the original problem.