# An efficient algorithm to solve this convex optimization problem

I have a convex optimization problem as follows:

\begin{align*} maximize_{x\in R^n} &\sum_{i=1}^n a_i log(x_i)\\ st\quad & \sum_{i=1}^n p_{ij} (x_i-1) = 0 \quad \forall j\\ & x_i \geq 0 \end{align*} where, $a_i \geq 0$ and $P$ is an $n\times m$ probability matrix with rows sum up to 1. Is there any efficient and fast algorithm to solve it? (I suppose it doesn't have a closed-form solution)

• Yes, I had included the non-negativity constraint. – ie86 Oct 19 '16 at 15:33

## 1 Answer

If you flip the sign of the objective function and find the minimum, you have a smooth, linearly constrained, convex optimization problem. Newton's method will rapidly converge to the solution for this problem.

For the equality constraints, you can either work with Lagrange multipliers, or you can eliminate the constraint by only working on the null space of the matrix $P$, assuming that it is easy to compute.

For the inequality constraints, you will have to use something like an active set method, or a penalty approach. Since these are only linear box constraints, there should be no difficulty here.