The default M in KKT operator

[asxadf]

Hi Dr. Johan,

I am working with the KKT operator under the @lmi folder of YALMIP-master. kkt.txt

If I get it correctly, the KKT operator uses a default M value 1e+4 to reformulate the complementaries as long as I turn off the dual bound derivation.

In my case, I think the default M value 1e+4 is somehow small, so I want to change the 1e+4 to 1e+6. Maybe I can do this by slightly adjusting the code of the KKT operator?

I have gone through the code of the KKT operator. I think the target codes are at lines 209-218 of kkt.m.

   if ops.kkt.minnormdual;
        MinNorm = [0 <= Lambda <= 10000*s_,s == 0];
        ops.kkt.minnormdual = ops.kkt.minnormdual-1;
        parametricInMinNorm = recover(setdiff(depends(MinNorm),depends(Lambda)));
        [kkt2,info2] = kkt(MinNorm,Lambda'*Lambda,parametricInMinNorm,ops);
        kkt2 = [kkt2, [indicators(kkt2(1)) <= 1-[s_;s_]]];
        kkt2 = [kkt2, info2.dual <= 10000];
        KKTConstraints = [KKTConstraints, kkt2];
        details.info2 = info2;
    end

Maybe I can replace 10000 with 1000000 to achieve my goal?

COuld you please share your ideas or suggestions with me?

Best regards,
Xianbang

[johanlofberg]

Those lines of code are related to some weird experimental feature minnormdual (turned off) which I have no memory of what it does, and you shouldn't bother with

There is no big-M constant in the KKT code. The big-M modelling is done before solver call when the complementarity condition in the KKT model is modelled, and the big-M constant used there is automatically derived as tight as possible, based on the bounds available on primal and dual variables (which you add to the model, either by your own knowledge and/or using the bounds computed in KKT and returned in the details.primalbounds and details.dualbounds. If those bound derivations have failed, you simply add your own magic bounds on those). The lowest level resort to a magic bound is in derivebounds, where a arbitrary constant of 10^4 is used, when it fails to derive anything based on propagating suplied variable bounds to the involved operator. Change at your own risk, I hope you know that using huge constants is a recipe for poor models...

[asxadf]

Thank you for your mention, Dr. Johan.

Yes, I understand that a huge M may lead to a weak relaxation. But I still want to try.

Because I want to take advantage of the automatic KKT operator (Handy coding is easy to wrong), also get some control over the M value.

I revisited the KKT code (I have turned off the derivation of the dual bound cause it is difficult in my big model). If I want to set a magic M for the Big-M, seems like I should replace the inf with a magic 8000 for the dual bounds, and then the Big-M modeling will use the 8000 to relax the complementary constraints. Is that right?

details.dual = Lambda;
details.dualeq = mu;
details.primal = x;
if length(b)>0
    details.inequalities = A*x <= b;
else
    details.inequalities = [];
end
if length(f)>0
    details.equalities = E*x == f;
else
    details.equalities = [];
end
if isempty(U)
    U = repmat(8000,length(b),1);
    %     U = repmat(inf,length(b),1);
end
details.dualbounds = U;

Best regards,
Xianbang

[johanlofberg]

No reason to edit the kkt operator, just add the constraint details.dual<=8000 to your model

The number 8000 will then be used in the bound propagation when the big-M constant is derived for the complementarity slackness model (which effectively will be 8000 for the MILP-constraint related to the dual in {dual==0 or b-Ax== 0})

[asxadf]

Got it!

Thank you so much, Dr. Johan!