How to maximize an entropy function?

Question

I'm very novice in optimization and have a convex optimization function of form $\sum_{i,k} p_{k,i}*\log{p_{k,i}} $ to minimize with the following constraints:

$\forall i, a_i = \sum_{k=1}^{m} b_k. p_{k,i}$

$\forall k, k=\sum_{i=1}^{m} p_{k,i}$

$0\leq p_{k,i} \leq 1$

$1\leq i,k \leq m$

$0\leq a_i \leq 1$'s and $0 \leq b_k \leq 1$'s are known and $m=160$.

Could someone help me in transforming this optimization problem to a solver, preferably matlab or cvxopt. If having $1\leq i,k \leq 160$, which results in 160*160 variables $p_{k,i}$, makes the problem unsolvable (or hard to solve), we can change $k$ to something like $1\leq k \leq 20$.

My other question is whether we can consider this problem as the entropy maximization problem considering the fact that condition $\sum_{i,k} p_{k,i} = 1$ does not hold?

Answer 1

There is a quick solution to your problem. If you use cvx, you can directly apply the entropy function to formulate your target function $\sum_{i,k}-p_{k,i}*\log{p_{k,i}}$ as

sum(entr( p )), where p is the vector which contains all the variables $p_{i,k}$.

For further reading and how to formulate your problem in matlab see the user's guide http://cvxr.com/cvx/doc/CVX.pdf

Answer 2

If a and b are stored in MATLAB as column vectors, then this is the CVX model:

cvx_begin
    variable p(m,m)
    maximize(sum(entr(p(:)))
    subject to
        b' * p == a';
        sum( p, 2 ) == ( 1 : k )';
        p <= 1;
cvx_end

A couple of comments.

• The solvers that CVX currently targets cannot handle the entropy term "natively". CVX implements a successive approximation approach to solve these problems. It's a heuristic, and doesn't always work. But I've found that for entropy problems it's reliable---if the problem isn't too large.
• I don't know if 160x160 will be too large or not. I tried a test problem, and it seemed to handle it, but 1) I have 16GB of RAM, and 2) my test problem was infeasible, so I didn't get to see it go to convergence.
• It doesn't seem easy to build a feasible problem here, so I assume that your a and b matrices are built from some known physical application.
• You do not need to add a constraint p >= 0; the domain of the entropy function itself ensures that p will stay nonnegative.
• The default solver that CVX uses, SDPT3, will be particularly slow for this problem. SeDuMi will be a bit better (cvx_solver sedumi), but MOSEK would really work best for this one (cvx_solver mosek). You'll need an academic license key to unlock MOSEK though. ECOS is an open-source alternative that would likely be very fast as well; it has CVX support, but it doesn't ship with CVX, so you have to manage that separately.