0
$\begingroup$

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)

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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