the uncertain wrong of minimizing Topic is solved

[Jim3361]

Hello,everyone! I have a question that I am trying to balance the SAM table using the cross entropy method, but the corresponding command cannot achieve the minimization of the objective function Z, but I really can't find out where the problem is.
This is the command.
*********************
set ac /sec1,sec2,lab,hh,total/;
set i(ac) /sec1,sec2,lab,hh/;

alias (ac,acp);
alias (i,j);

table sam(*,*)
sec1 sec2 lab hh total
sec1 52 45 150 247
sec2 95 48 90 233
lab 120 89 209
hh 192 192
total 267 182 192 240
;

parameters
Q0(i,j) initial value of SAM
H0 sum of all transaction flows ;

*Assignment for parameters
Q0(i,j)=sam(i,j);
H0=sum((i,j),sam(i,j));

display H0,sam;

Variables
Q(i,j) the target values of SAM
H the adjust sum of all transaction flows(total)
Hratio the ratio of Initial and adjusted total
z Expected entropy value;

*nonneg values must be non-negative
Positive variable Q(i,j);

equations
totalsum adjusted total
directentropy objective function
balance Balancing restrictions for each account
Hratiodef the ratio of Initial and adjusted total;

totalsum.. H =e= sum((i,j),Q(i,j));
Hratiodef.. Hratio =e= H/H0;
directentropy.. z=e=sum((i,j)$sam(i,j),(1/H)*Q(i,j)*log(Q(i,j)/sam(i,j)))-log(Hratio);
balance(i).. sum(j$sam(i,j),Q(i,j)) =e= sum(j,Q(j,i));


*Assign values to the initial values of variables.
*There are special limitations on the scope of Hratio here. Because without limitation, when the objective function is minimized,
*H will tend towards infinity, and the true result cannot be obtained
Q.l(i,j)=Q0(i,j);
H.l=H0;
Hratio.lo=0.5;
Hratio.up=2.0;

model sambal /all/;
solve sambal using dnlp minimizing z;


display Q.l,z.l,H.l,H0,Hratio.l;
*end
**********************
This is the corresponding result.
“Hratio.lo=0.5;
Hratio.up=2.0”
‘balance(i).. sum(j$sam(i,j),Q(i,j)) =e= sum(j,Q(j,i));
’
---- 60 VARIABLE Q.L the target values of SAM

sec1 sec2 lab hh

sec1 96.000 119.000
sec2 95.000 48.000 90.000
lab 120.000 89.000
hh 209.000


---- 60 VARIABLE z.L = 0.754 Expected entropy value
VARIABLE H.L = 866.000 the adjust sum of all transaction flows(total)
PARAMETER H0 = 881.000 sum of all transaction flows
VARIABLE Hratio.L = 0.983 the ratio of Initial and adjusted total

“ Hratio.fx=0.984”
---- 59 VARIABLE Q.L the target values of SAM

sec1 sec2 lab hh

sec1 51.515 52.535 140.353
sec2 79.862 47.552 71.460
lab 113.026 98.787
hh 2.96948E-19 211.813


---- 59 VARIABLE z.L = 0.007 Expected entropy value
VARIABLE H.L = 866.904 the adjust sum of all transaction flows(total)
PARAMETER H0 = 881.000 sum of all transaction flows
VARIABLE Hratio.L = 0.984 the ratio of Initial and adjusted total
It can be seen that when the Hratio ratio is between 0.5 and 2, a program value of 0.983 cannot achieve the minimum z. As I fx it 0.984,the Z is 0.007,much less than 0.983, and the 0.984 is also not the real solution.
And there is a weird thing that in logical, whither I add the ' $sam(i,j)' of the definition 'balance(i).. ' will not influence the result as that all Q(i,j) is positive, but the result shows that if I delete this, the Z is ZERO, but the table is totally not changed.
“balance(i).. sum(j ,Q(i,j)) =e= sum(j,Q(j,i));”

---- 60 VARIABLE Q.L the target values of SAM

sec1 sec2 lab hh

sec1 96.000 119.000
sec2 95.000 48.000 90.000
lab 120.000 89.000
hh 209.000


---- 60 VARIABLE z.L = 0.000 Expected entropy value
VARIABLE H.L = 866.000 the adjust sum of all transaction flows(total)
PARAMETER H0 = 881.000 sum of all transaction flows
VARIABLE Hratio.L = 0.983 the ratio of Initial and adjusted total

Thanks a lot

[bussieck]

Jim,

Don't put your code in a regular text. The topic editor gives you code markdown to put code in mono-spaced font. This way, the formatting of table sam survives and we know where what number goes. BTW, this might all be related to non-convexity. But without running the model it's hard to say.

-Michael

[Jim3361]

Jim,

Don't put your code in a regular text. The topic editor gives you code markdown to put code in mono-spaced font. This way, the formatting of table sam survives and we know where what number goes. BTW, this might all be related to non-convexity. But without running the model it's hard to say.

-Michael

Michael,
Thanks for your suggestion, Michael!
This time, I upload my code file and try to describe my confuse again to make it easy to read.
Here is my question.

That I am trying to balance the SAM table using the cross entropy method, but the corresponding command cannot achieve the minimization of the objective function Z, but I really can't find out where the problem is.
“ Hratio.lo=0.5; Hratio.up=2.0;”→“Hratio.fx=0.984”,Z from 0.754 to 0.007
It can be seen that when set the" Hratio " ratio between 0.5 and 2, the value of it is auto chosen as 0.983 which cannot achieve the minimum of Z(0.754). As I Hratio.fx it to 0.984, the Z is 0.007, much less than 0.754, and the " Hratio =0.984" is also not the real solution.
"balance(i).. sum(j$sam(i,j),Q(i,j)) =e= sum(j,Q(j,i));"
And there is a weird thing that in logical, regularly whither I add the ' $sam(i,j)' of the definition 'balance(i).. ' will not influence the result as that all Q(i,j) are positive, but the result shows that if I delete this, the Z is ZERO, but the Q table is totally not changed. I'm so confuse about it.
Thanks for your reply.
--Jim.

[bussieck]

The model is indeed nonconvex and depending on the starting point (set by bounds) you can get better solutions even if you make the feasible space smaller. Better is to use a global solver, e.g. BARON. In order to make it work okay I had to percolate the bounds of Hratio to H. With that BARON proves in 15 minutes that 0.006752 is the global optimal solution:

Code: Select all

Solution      = 0.00675199048637898  found at node 1132
Best possible = 0.00675131528913
Absolute gap  = 6.75197248977896E-7  optca = 1E-9
Relative gap  = 9.99997334623019E-5  optcr = 0.0001

Please find attached gms, lst, and log.

-Michael

[Jim3361]

The model is indeed nonconvex and depending on the starting point (set by bounds) you can get better solutions even if you make the feasible space smaller. Better is to use a global solver, e.g. BARON. In order to make it work okay I had to percolate the bounds of Hratio to H. With that BARON proves in 15 minutes that 0.006752 is the global optimal solution:

Code: Select all

Solution      = 0.00675199048637898  found at node 1132
Best possible = 0.00675131528913
Absolute gap  = 6.75197248977896E-7  optca = 1E-9
Relative gap  = 9.99997334623019E-5  optcr = 0.0001

Please find attached gms, lst, and log.

-Michael

Michael,
Thank you very much!!!
After add "H.lo = H0*Hratio.lo; H.up = H0*Hratio.up;", the result seems right as I could get a ratio of 1.072 and Z is equal to 0.007, and as I tight the space smaller as 0.7~1.5, the result is stable. However, as I make it smaller as 0.7~1.3 or 0.9~1.5, the ratio is not stable any more.
Then I add "option dnlp=baron;" and run the model when the space is 0.5~2.0, the ratio is 1.524 and Z is 0.007. And again, as I small the space to 0.9~1.7, the ratio is not 1.524 but 1.353, Z is still 0.007.
In these attempts, the Z is all 0.006752 just as you calculated, I just can't understand why the ratio is not stable when the changed space actually covers the previously calculated ratio.
Grateful for your reply!!!
--Jim

[bussieck]

Why do you expect the ratio to be stable? Many optimization problems are degenerate, i.e. with the same objective function you have many solutions. Which one the solver spits out is a matter of chance. So if you change the input (e.g. different bounds) the solver takes a slightly different path and you end up with a different solution of the same quality (subject to tolerances).

-Michael

[Jim3361]

Why do you expect the ratio to be stable? Many optimization problems are degenerate, i.e. with the same objective function you have many solutions. Which one the solver spits out is a matter of chance. So if you change the input (e.g. different bounds) the solver takes a slightly different path and you end up with a different solution of the same quality (subject to tolerances).

-Michael

Thank you very much for explaining my confusions!!!!!
Wish you a wonderful day!!
-Jim