4
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ actually your function is concave... $\endgroup$ May 29, 2014 at 20:25
  • $\begingroup$ you're right, but we can consider its negative which is convex and then minimize that. $\endgroup$
    – HHH
    May 29, 2014 at 20:27
  • $\begingroup$ Suggestion: write the Kuhn-Tucker conditions by hand first. $\endgroup$ May 29, 2014 at 20:38
  • $\begingroup$ 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. $\endgroup$ May 29, 2014 at 20:49

2 Answers 2

2
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ May 29, 2014 at 21:26
  • $\begingroup$ 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. $\endgroup$ May 29, 2014 at 21:39
  • $\begingroup$ So are you aware of any other solver considering the problem size if CVX is not working? $\endgroup$
    – HHH
    May 29, 2014 at 21:45
  • $\begingroup$ Well, good old fmincon from MATLAB's optimization toolbox might do the trick here. YALMIP provides a convenient interface to fmincon, I believe. $\endgroup$ May 29, 2014 at 22:11
2
$\begingroup$

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.
$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – HHH
    May 30, 2014 at 22:42
  • $\begingroup$ 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. $\endgroup$ May 31, 2014 at 21:01
  • $\begingroup$ 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$. $\endgroup$
    – HHH
    Jun 1, 2014 at 20:04
  • $\begingroup$ Well yes, I made a mistake above. But that is, unfortunately, not convex. $\endgroup$ Jun 1, 2014 at 20:12
  • $\begingroup$ I don't really understand why! Entropy function is a concave function and its negative is convex, why you're saying it's not? $\endgroup$
    – HHH
    Jun 1, 2014 at 21:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .