Solving an optimization problem with lower computational complexity

Question

Given $$n, C, r_i, p_i, \quad∀ i={1,2,...,n} $$ I want to solve this optimization problem: $$maximize \quad f(x_1,x_2,...,x_n)=\prod_{i=1}^n {{(x_i/r_i)}^{p_i}} $$ $$s.t \quad {(x_i/r_i)≤1}, \quad {(\sum_{i=1}^n x_i)}/C ≤1$$ where $$0≤p_i≤1 \quad\quad, \sum_{i=0}^n p_i =1\quad \quad\quad, ∀x_i,r_i∈R,\quad x_i,r_i>0,\quad C>0 $$ To solve this problem, I use primal-dual interior-point method. I don't need accuracy more than 3 digits. But, I need to use a way to solve it much faster. I wonder if I can approximate this problem to another one that can be solved faster or I can use another way to solve it. Thank you for your help.

Answer 1

By using the transformation $y_{i}=\log(x_{i})$, $i=1, 2, \ldots, n$, and maximizing the logarithm of the original objective and dropping constant terms, you end up with the problem

$\max \sum_{i=1}^{n} p_{i} y_{i}$

subject to

$y_{i} \leq \log(r_{i})$, $i=1, 2, \ldots, n$

$\mbox{logsumexp}(y_{1},y_{2},\ldots,y_{n}) \leq \log(C)$

This is an exponential cone programming problem that can be solved with the ECOS interior-point solver or the SCS first order solver. You could also just hand it to a conventional nonlinear programming solver.

I went ahead and implemented this in MATLAB/ECOS. For the $n=2$ case given in the question the solution time on my desktop machine was consistently about 10 ms. For randomly generated problems with $n=100$, I loosened the optimality tolerances in ECOS a bit and got solutions good to about 4 digits in 25 ms or less. This compares with about 1 second for these problems using CVX.