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

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.