Given constants $c>0$ and $\beta_i \in [0, \infty)^d$, for $i=1,..,n$, I want to (numerically?) solve the following problem:
$\max_{x \in [0, \infty)^d} \sum_{i=1}^n \log(\beta_i^T x), \text{ subject to } ||x||_1=c.$
My attempt:
1 – By definition of the problem, $x \in [0, \infty)^d$, so the constraint is equivalent to $\sum_{j=1}^d x_j = c$.
2 – $\log(\cdot)$ is strictly concave, $\beta_i^T x$ are linear functions, and the constraint is also linear, so the objective is concave. Thus, any local maximum is a global maximum.
3 – Our constrained objective yields the following Lagrangian:
$L(x, \lambda, \mu) = \sum_{i=1}^n \log(\beta_i^T x) + \lambda(c-\sum_{j=1}^d x_j) + \sum_{j=1}^d\mu_jx_j$
4 – From KKT conditions, the optimal solution $x^*$ and suitable parameters $\lambda^*$ and $\mu^*$ satisfy:
$\nabla_x L(x^*, \lambda^*, \mu^*) = 0, \,\,\, \lambda^*(c-\sum_{j=1}^d x_j^*)=0, \,\,\, \mu_j^*x_j^*=0, \text{ and } \mu_j^* \geq 0, \text{ for } j=1,…,d.$
However, except for some simple particular cases (e.g., $n=d=2$), I am not being able to solve this problem analytically… Questions:
Q1 – Is it possible to solve the problem analytically in the general case? (I suppose it is not.)
Q2 – Assuming the answer to Q1 is 'No', what would be a suitable numerical optimization algorithm to solve it?
Best Answer
The KKT conditions (which necessarily hold at an optimal solution since the feasible region is polyhedral) that you've written out yield $\lambda^* - \mu^*_j = \displaystyle\sum_{i=1}^{n}\dfrac{\beta_{ij}}{\beta^{T}_i x^*}, \:\: \forall j \in \{1,\cdots,d\}$. Multiplying each of these equations by $x^*_j$, using complementary slackness conditions, and summing up yields $\sum_{j=1}^{d} \lambda^* x^*_j = 1$, which along with the equality constraint implies $\lambda^* = \frac{1}{c}$.
The conditions we are left with are: \begin{align*} &\mu^*_j + \displaystyle\sum_{i=1}^{n}\dfrac{\beta_{ij}}{\beta^{T}_i x^*} = \frac{1}{c}, \:\: \forall j \in \{1,\cdots,d\}, \\ &\sum_{j} x^*_j = c, \:\: x^* \geq 0, \\ &\mu^*_j x_j = 0, \:\: \forall j \in \{1,\cdots,d\}, \:\: \text{and}\\ &\mu^*_j \geq 0, \:\: \forall j \in \{1,\cdots,d\}. \end{align*}
It doesn't seem to me like there's a closed form solution to this system in general.
A numerical option for solving your problem directly (without going through KKT conditions) is mirror descent, see Example 4.2 here. This should be particularly effective for your problem.