Fmincon / Multistart: Local minimum found, but one nonlinear constraint is violated

Hi,

i am trying to find an optimal point with multistart / fmincon. Matlab finds a local minima, for which the following message is given in the output struct:

Local minimum found that satisfies the constraints.
Optimization completed because the objective function is non-decreasing in feasible directions, 
to within the value of the optimality tolerance,and constraints are satisfied to within the value of the 
constraint tolerance.<stopping criteria details>
Optimization completed: The relative first-order optimality measure, 7.337955e-07,
is less than options.OptimalityTolerance = 1.000000e-06, and the relative maximum constraintviolation, 7.082693e-07,
is less than options.ConstraintTolerance = 1.000000e-06.

i have 13 nonlinear constraints, of which one is violated.

This is the constraint:

ceq(10) = (L_1 - (L_2 - L_3)) - 0.001;

I want to achieve:

abs(L_1 - (L_2 - L_3)) <= 0.001;

If i check this constraint by hand, I get

abs(L_1 - (L_2 - L_3)) = 0.0011;

which is larger than the desired value 0.001

The constraint tolerance in optimoptions is set to 1e-6 by default.

How can this happen? The output clearly says, that all the constraints are met, but in reality this one is not.

[Shashank Gupta]

Hi,

Would you share your code and all the necessary files required for me to investigate?

Cheers.

[e_frog]

Hi, I am sorry, but I must not share the whole code due to confidentiality reasons, but I can provide a minimalized version of the definition of the nonlinear constraints. I hope you can help me nonetheless. Also I can provide you with further information:

• the exitflag when it happens are 1 and 2
• in fmincon the input is: fmincon(objective,x_0,[ ],[ ],[ ],[ ],lb,ub,nlcon,options)

Did I misunderstand the functionality of fmincon? My assumption based on the documentation is, that fmincon may violate the nonlinear constraints for intermediate iterations, but not the the last / solution iteration. Is that correct? Is fmincon supposed to be able to breach nonlinear constraints in the solution?

My second assumption is, that the constraint violations appear because of the definition of the nonlinear constraints. I try to constrain outputs of differential equations (X_ode), which get calculated for every iteration using the optimization vector x_opt.

function [c,ceq] = nlcon(x_opt)
L_1 = 500;
[X_ode] = solveODEs(x_opt,% calculations of ODEs with ode45())

L_2 = X_ode(end,1)
L_3 = X_ode(end,3)

c(1) = ...;
    ...

ceq(1) = L_1 - (L_2 - L_3); % this constraint is violated
ceq(2) = ...;
    ...

end

[Matt J]

I can't be sure what is going on without code that can actually be executed, but just as a a remark, fmincon expects the constraints to be differentiable, so it may be better to avoid abs,

ceq(10) = (L_1 - (L_2 - L_3)) - 0.001;
ceq(11) =  0.001 - (L_1 - (L_2 - L_3)) ;

[e_frog]

@matt yes, that's definitely right. I read that in the documentation. That's why I stopped using abs() in the comment. The problem still occurs. Should I edit the question?

[Matt J]

The best would be to provide an example which we can use to reproduce what you are seeing.

[e_frog]

I know, but unfortunately I can't provide that because of confidentiality reasons and I am really sorry about that. Also the structure of my scripts is too complex, to easily get a minimal example. I understand, that it is hard to help me on this situation.

Nevertheless it would help me a lot, if I could at least get help with these questions:

• Did I misunderstand the functionality of fmincon?
• My assumption based on the documentation is, that fmincon may violate the nonlinear constraints for intermediate iterations, but not the the last / solution iteration. Is that correct?
• Is fmincon supposed to be able to breach nonlinear constraints in the solution?

The deviation form the limit value is always so small, that it could be negligible, but it would greatly help me to basically just understand what fmincon does with nonlinear constraints in general.

Answer 1

[Matt J]

If the exit message says constraints were satisfied within tolerance, then that is what should have happened. However, the tolerance is relative for all fmincon algorithms except 'active-set'. Relative to what, the documentaiton does not seem to say, but it might be relative to the initial point. This means that if your initial point violated one of the constraints by say, 8000, then 0.0011 would be within the 1e-6 tolerance, because 0.0011/8000 < 1e-6.

A simple solution might be to reduce the ConstraintToleance to say, 1e-12. Or, use the active-set algorithm, if it applies to your problem.

[e_frog]

Thank you, I will test both options later today!

Your suggestions however gave me an idea for a third possible solution to my problem:

Maybe my testing method is just mathematically wrong. Would you be willing to check that?

The constraint itself is defined as in my above comment (keep in mind that I ditched the fixed value of 0.001):

function [c,ceq] = nlcon(x_opt)
L_1 = x_opt(1);
[X_ode] = solveODEs(x_opt,% calculations of ODEs with ode45())
L_2 = X_ode(end,1)
L_3 = X_ode(end,3)
c(1) = ...;
    ...
ceq(1) = L_1 - (L_2 - L_3); % this constraint is violated
% I want to achieve: L_1 == (L_2 - L_3) is true within ConstraintTolerance = 1e-6 
ceq(2) = ...;
    ...
    end

And the test after multistart has finished calculating goes as follows with the output vector x_opt_out:

function [checked_nlcons] = nlconCheck(x_opt_out,options) % options from fmincon for ConstraintTolerance
L_1 = x_opt_out(1);
[X_ode] = solveODEs(x_opt_out,% calculations of ODEs with ode45())
L_2 = X_ode(end,1)
L_3 = X_ode(end,3)

% I want to achieve: L_1 == (L_2 - L_3) is true within ConstraintTolerance = 1e-6 
checked_nlcons(1,1) = num2cell(le(L_1 - (L_2 - L_3),ConstraintTolerance)); % would result in 1 if constraint is met
end

Your answer gave me the impression, that the last line could be wrong.

[Matt J]

I don't see why nlconCheck doesn't just call nlcon.

[e_frog]

that's because of dependencies of variables that are not shown in these minimal pieces of code. All that nlconCheck does is to generate a cell with zeros and ones for the constraints that are violated and not violated. That's for the user to see which constraint is violated. It just checks the constriants outside of fmincon and multistart again manually.

[Matt J]

If nlconCheck does not measure the constraints by calling the same function as fmincon does, I would worry about inconsistencies creeping in.

[e_frog]

That's why I am concerned, if the last line as shown is mathematically testing the same as fmincon does. Can you please help me with that?

[e_frog]

assuming fmincon checks:

c(1) = A - B % A <=B with ConstraintTolerance 1e-06

How would I check this constraint manually afterards?

% Like so?
checked_nlcon(1) = A + A * ConstraintTolerance <= B;

% Or like this?
checked_nlcon(1) = A <= B + B * ConstraintTolerance;

[Matt J]

We won't be able to determine what test fmincon does since, as I said, it is undocumented. However, I think it would be instructive to measure both relative and absolute constraint violation, like in the following.

function [cTest,ceqTest] = nlconCheck(xFinal,xInitial)
%
%  [cAbsolute,ceqAbsolute] = nlconCheck(xFinal)
%  [cRelative,ceqRelative] = nlconCheck(xFinal,xInitial)

  doRelative=nargin>1;

  fv=@(z) max(-z,0); %measure violation
  fvEq=@(z) abs(z);

  [cFinal,ceqFinal]=nlcon(xFinal);
  cFinal=fv(cFinal);
  ceqFinal=fvEq(ceqFinal); 
  
  if doRelative 
      
      [cInitial,ceqInitial]=nlcon(xInitial);
       cInitial=fv(cInitial);
       ceqInitial=fvEq(ceqInitial);
       
       cTest=cFinal/(1+max(cInitial)); ceqTest=ceqFinal/(1+max( ceqInitial ));
       
  else
      
      cTest=cFinal; ceqTest=ceqFinal;
       
  end

[e_frog]

Thanks for your effort so far, but that does not help me further with my constraint

ceq(1) = L_1 - (L_2 - L_3);

because i want to achieve L1 = (L2-L3) the target value would be 0. Thats why no relative violation can be calculated

[Matt J]

I may have lost track of what we're trying to deduce ... but the code I gave you above will compute the relative constraint violationmetric that I think fmincon might be using. There's no way to confirm that without MathWorks staff's input, but this 2014 post

https://www.mathworks.com/matlabcentral/answers/142427-what-is-the-difference-between-relative-max-constraint-violation-and-constraint-violation?s_tid=srchtitle

seems to support my theory, at least for Matlab versions circa 2014.

[e_frog]

No worries. With your code i get some NaNs because it divides by 0 for some constraints.

Thank you for your help so far. I now think my problem is selfmade, because if it is not documented how fmincon checks the constraints, then I clearly did not check them as fmincon did and then there might actually be no constraint violations.

Yet the code you gave me helped me to narrow down my code! Also thanks for that!

[Matt J]

No worries. With your code i get some NaNs because it divides by 0 for some constraints.

No, I updated the code with Alan's formula from the link I gave you. There shouldn't be any divisions by zero with that.

then I clearly did not check them as fmincon did and then there might actually be no constraint violations.

I'm pretty sure you don't have to worry about fmincon lying to you about whether you satisfied fmincon's own stopping criterion. The question is whether that criterion is practically meaningful for you :-)

[e_frog]

sorry, i didn't see that you updated the code! Calculationg the relative violations now work for me too! Why exactly is your code using the initial values for the relative violation? Wouldn't it be more logical to use the limit values?

[Matt J]

That's what Alan (a MathWorks employee) said they do...