How to maximize an entropy function?

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?

• actually your function is concave... May 29, 2014 at 20:25
• you're right, but we can consider its negative which is convex and then minimize that.
– HHH
May 29, 2014 at 20:27
• Suggestion: write the Kuhn-Tucker conditions by hand first. May 29, 2014 at 20:38
• ok so either you say that you maximize that concave function that you wrote, or you say you minimze a convex function but you change the function accordingly. Just to be precise. May 29, 2014 at 20:49

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

• Thanks for recommending CVX! It's certainly worth a try for a scaled down version of the problem. I'm not as optimistic about the full $160\times 160$ model, though. The solvers that CVX currently connects to don't handle the entropy function natively, so it employs a successive approximation method that's a bit inefficient and expensive. For a problem this large it might not work as well, and it will certainly be slow. May 29, 2014 at 21:26
• You are right with your concerns about the problem size. I'm not sure if the choice of the solver could speed up the optimization process. I have good experience by using the Mosek solver within the cvx-Matlab interface. May 29, 2014 at 21:39
• So are you aware of any other solver considering the problem size if CVX is not working?
– HHH
May 29, 2014 at 21:45
• Well, good old fmincon from MATLAB's optimization toolbox might do the trick here. YALMIP provides a convenient interface to fmincon, I believe. May 29, 2014 at 22:11

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


• 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.
• Thanks Michael. I ran it using my real data and it seems like that it converges after 5,6 iterations. Does it make sense? Besides, as my problem is entropy maximization I need to divide the entropy argument by a constant value that they add up to 1 and this change causes the solver to fail! What can be the reason?
– HHH
May 30, 2014 at 22:42
• Well, you did not include this rather important detail in your original question. The normalized entropy function $(\sum_{i=1}^k p_i\log p_i)/\sum_i p_i$ is neither convex nor concave. And if you instead add the normalization sum(p,1)==1 or sum(p,2)==1, to your model, then you've changed the relationship between $p$ and the constraints. I'm surprised you could build a feasible model that satisfies those constraints, frankly. In particular, you have a constraint $\sum_i p_{m,i}=m$, which is either impossible to satisfy or forces all of the other $p$'s to zero. May 31, 2014 at 21:01
• Actually what I mean is $maximize(\sum_{k,i} \frac{p_{k,i}}{V} \log \frac{p_{k,i}}{V})$ in which $\sum_{k,i} \frac{p_{k,i}}{V}=1$.
– HHH
Jun 1, 2014 at 20:04
• Well yes, I made a mistake above. But that is, unfortunately, not convex. Jun 1, 2014 at 20:12
• I don't really understand why! Entropy function is a concave function and its negative is convex, why you're saying it's not?
– HHH
Jun 1, 2014 at 21:32