NonLinear Constraint not verified, although fmincon says it is

Hi everyone,

I come to you with an constrainted optimization problem to which I cannot find a satisfying solution.

The problem consists of linear equality constraints, linear inequality constraints and nonlinear constraints. To solve this, I use fmincon and the sqp algorithm. My issue is the following : the optimization stops because the step size is too small and moreover the constraints are satisfied.

It is true that the constraints are satisfied, but only the linear ones : in fmincon nomencalture, my x_out satisfies c(x_out) > 0 ! Which is paradoxical with the definition of the nonlinear constraint c(x) <= 0. In addition, c(x_out) is bigger than my ConstraintTolerance of 10^-4.

% Linear Constraints and bounds
load('Optim_Vars.mat'); % Contains A,b_optim,Aeq,beq,ub_optim,lb_optim,targetfun

% Non Linear Constraint definition
Target_thresh = 0.4;
non_lin_buffzone = 10^-2; % A parameter to satisfy "more sharply" the condition, but bigger than the constraint tolerance,
%                         so that constraint_violation < buffzone => c(x) + constraint_violation <= 0                          
nonlcon = @(x)the_non_linear_con(x,Target_thresh,non_lin_buffzone);
function [c,ceq] = the_non_linear_con(x,threshhold,buffzone)
    ceq = [];
    Idx = and(x <= 0.1, x >= 0.05);
    c = sum(x(Idx)) - threshhold + buffzone; % Sum of elements of x within range [0.05,0.1] has to be lower than threshhold
end

% Ignore this part as is it only suited to build a good
% initial point for a the more constrained latter optimization
options_x0 = optimoptions(@fmincon,'Algorithm','sqp','MaxFunctionEvaluations',10^5,'ConstraintTolerance',10^-8,'StepTolerance',10^-8);%'sqp','active-set'                        
x0_g = fmincon(funobj,x0,A(1:end-1,:),b_optim(1:end-1,:),Aeq,beq,lb,ub,nonlcon,options_x0);

% Optimization - Core problem
@(x) 0.5*x'*H*x + x'*f; % Some target function
options = optimoptions(@fmincon,'Algorithm','sqp','MaxFunctionEvaluations',10^5,'ConstraintTolerance',10^-4,...
    'StepTolerance',10^-10);               
[x_out,fval,exitflag,output] = fmincon(funobj,x0_g,A,b_optim,Aeq,beq,lb_optim,ub_optim,nonlcon,options);

After the optimization, I check the constraints. As you can see, Ax <= b is satisfied, Aeq * x = beq is satisfied, but c(x) <= 0 is not satisfied :

Local minimum possible. Constraints satisfied.

fmincon stopped because the size of the current step is less than
the value of the step size tolerance and constraints are 
satisfied to within the value of the constraint tolerance.

<stopping criteria details>
K>> [c,~] = nonlcon(x_out)

c =

    0.0729
K>> sum(A*x_out > b_optim)

ans =

     0

K>> sum(Aeq *x_out ~= beq)

ans =

     0

Could someone enlighten me please ? I would like the optimization to stop if all constraints are satisfied, including the non linear one...

Answer 1

[Matt J]

For the sqp algorithm, the ConstraintTolerance is relative, not absolute. See the table here,

https://www.mathworks.com/help/optim/ug/tolerance-details.html

[Matt J]

I would also point out that your nonlinear constraint is discontinuous and non-differentiable. It is therefore not in the theoretical scope of a derivative-based solver like fmincon.

[Karen Bozanian]

Hi Matt J,

Thank you for the clarification. However, I don't understand which quantity the ConstrainteTolerance is relative to. The constraint value ? The vector x magnitude ?

[Matt J]

I don't think that's documented. I would guess it is a fraction of the maximum constraint violation at x0.

In any case, you will have a hard time satisfying those constraints, for reasons mentioned above.

[Karen Bozanian]

I see. Thank you, I am now looking in the documentation for a better-suited algorithm for non differentiable nonlinear constraints.

[Matt J]

You're welcome, but if this answer resolves your question, please Accept-click it.

[Bruno Luong]

+1 to Matt comment: You cannot hope fmincon woud respect the constraints if your constraints do not respect what fmincon requires.

[Bruno Luong]

Found an old message from @Alan Weiss here on relative constraint tolerance. His answer is a little bit evasive at the time.

[Karen Bozanian]

For completion, here is the solution I ended up using :

• Replaced nonlcon by a differentiable enough approximation : replaced by where
• Randomized and scaled shifts on the initial point to avoid traps

Fmincon now founds the target solution.