Maximum entropy optimisation with equality constraints only

1

Hey there I am trying to minimise the objective (sum_{i}p_{i}\log(p_{i})) given moment constraints ((sum_{i}p_{i}x^{j}).

I have taken and adapted code from here

n = 200;
a = linspace(0,1,n);
a2 = a .^ 2;
a3 = a .^ 3;

A = [ a ; a2 ; a3];
b = [ 0.7 ; 0.5 ; 0.2];

%
% Compute the maximum entropy distribution
%

cvx_expert true
cvx_begin
variables pent(n)
maximize( sum(entr(pent)) )
sum(pent) == 1;
A * pent == b;
cvx_end

figure( 1 )
plot( a, pent );
xlabel( ‘x’ );
ylabel( ‘PDF( x )’ );

but this breaks down and fails to give a solution when I add the third moment constraint (a3). I know that a solution exists and have calculated it with other methods, could anyone advise me as to what is going on? I get the status infeasible and that the optimal value is -Inf.

thank-you

2

I believe that is because with the inclusion of the a3,b(3) constraint, there is no value of pent which is >= 0. So CVX is scoring the objective function as -Inf, and apparently declaring it to be infeasible. So in effect, CVX is adding the constraint pent >= 0, which results in an infeasible problem.

My technical description as to what CVX is doing internally might not be quite right, but I think I have described the essence of the situation.

3

Could you explain why it is doing this? clearly the exponential distribution of the form \frac{1}{Z}\exp(-\alpha x -beta x^{2} - \gamma x^{3}) fits the constraints. This is from solving the equation of maximum entropy and the lagrange multipliers explicitly.

4

Per the documentation, entr returns -Inf when its argument is negative. Given your full set of constraints, there is no feasible solution which does not have at least one negative component - you can verify that yourself. Therefore, the objective value equals -Inf for any feasible value of pent.

5

I’m super confused here. Why is there no feasible solution with a negative p(x)? the exponential of a negative is still positive? my solution is non negative on the whole domain. Explain how in the set of 0-1 having 3 decreasing moment constraints has no solution?

6

What I’m trying to say is that clearly something is going wrong here, maybe my code is a problem? why are we setting a moment constraint as A * pent, should it not be sum(a*pent), I have tried this but get no solution

7

I analyzed what happened with the problem you provided. I will leave it to you whether that is the “right” problem to solve.

8

O.k then, how can I solve a problem of finding the pent that maximises the entropy in the space of 0-1 with 3 moment constraints? so mean of x is some value, the mean of x^2 is another and the mean of x^3 is another value (all positive) is there anything wrong with my code so far to do this simple problem?

thank-you @Mark_L_Stone I appreciate your input

9

I just looked at the full example. It has A * pent <= b . You have A * pent == b . Changing it to A * pent <= b , the problem solves to reported optimality.

And I think perhaps you in general need 0<= pent <= 1, even though you may get away without having this in some circumstances. (Actually pent <= 1 is redundant given 0 <= pent and sum(pent) == 1.) That would make the feasibility situation more explicitly evident.

Using equality instead of inequality constraint, you are overconstraining.