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)

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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.