What happens if the termination condition is satisfied before the constraint in matlab's fmincon?

I'm doing optimization using fmincon.

I used ObjectiveLimit to terminate the optimization when the size of the objective function is less than 0.2,

As I was writing the code, it seems that if the nonlinear constraints are satisfied, the termination condition is also satisfied.

However, when I run the code, the optimization is performed several times and then the code terminates.

I don't understand this part.

Doesn't fmincon perform optimization for cases that satisfy the constraints?

What happens if the termination condition is satisfied before the constraint in matlab's fmincon?

Below is the output when optimization is finished.

fmincon stopped because the objective function value 6.018404e-04 is less than options.ObjectiveLimit = 2.000000e-01 and the relative maximum constraint violation 2.039171e-13 is less than options.ConstraintTolerance = 1.000000e-06

Thank you.

[Torsten]

This question is too specific to be answered in the forum. You should address it directly to the developers:

https://uk.mathworks.com/support/contact_us.html

Most probably it's necessary to have direct access to the source code to answer without speculating.

[재현]

Thank you.

I will contact the developer.

Answer 1

[Matt J]

The only time fmincon will stop without satisfying the constraints (within ConstraintTolerance) is if the MaxItertions or MaxFunctionEvaluations limits are exceeded.

[Torsten]

As I was writing the code, it seems that if the nonlinear constraints are satisfied, the termination condition is also satisfied.

However, when I run the code, the optimization is performed several times and then the code terminates.

As far as I understand, OP thinks that constraints and termination condition are satisfied right at the start, but nonetheless, "fmincon" starts iterating.

But the following "fmincon" behaviour may mean that constraints and objective function are only evaluated - I don't know:

However, when I run the code, the optimization is performed several times and then the code terminates.

[재현]

Thank you for your reply.

However, I made the other termination conditions except "ObjectiveLimit" very large so that they would not be triggered.

options = optimoptions('fmincon', 'Display', 'iter-detailed', 'Algorithm', 'sqp', ...

'ObjectiveLimit', (Tolerance^2)*2, 'MaxFunctionEvaluations', 1e10, 'MaxIterations', 1e5, 'OptimalityTolerance', 1e-100, 'FunctionTolerance', 1e-100, 'StepTolerance', 1e-100);

I still did not understand, so I sent a contact email to the developer. :*(

[Torsten]

This is not large, it is unreasonably small:

'OptimalityTolerance', 1e-100, 'FunctionTolerance', 1e-100, 'StepTolerance', 1e-100

[재현]

Sorry, I misspoke.

I made the conditions small so that the optimization would not terminate because of those conditions.

and made the optimization end with objectiveLimit

[Torsten]

You must make "the conditions large" for that the optimization ends fast. If a larger error is accepted, the optimizer will finish early.

[Matt J]

However, I made the other termination conditions except "ObjectiveLimit" very large so that they would not be triggered.

And that is what the exit message you showed us confirms. The ObjectiveLimit criterion did stop the optimization. Soif that was what you were trying to do, you succeeded, and I don't know what you see as a problem.

Is it that you think the constraints are not satisified upon termination? They are satisfied, according to the exit message.

[재현]

Iterations end in about 20 times.

The time taken is about 1 second.

In my code, if the nonlinear constraint is satisfied, the termination condition (objectLimit) should be satisfied.

However, I am curious as to why several repetitions are performed because the termination condition is not satisfied in the early part of the iteration.

Thank you for your hard work.

[재현]

@Matt J

What I'm curious about is whether fmincon performs optimization at a solution that satisfies nonlinear constraints.

I guess that fmincon performs optimization at a solution that satisfies nonlinear constraints.

And in my code, if the nonlinear constraints are satisfied, the termination condition(objectiveLimit) is also satisfied.

However, when I run the code and look at the display, it does not satisfy the termination condition and after a few iterations, it satisfies the termination condition and terminates.

To summarize, I want to know whether fmincon performs optimization at a solution that satisfies nonlinear constraints.

[Torsten]

Before calling "fmincon", call your objective function and your constraint function with your initial guesses for the solution variables. Are the constraints satisfied ? Is your objective function below "objectiveLimit" ?

[Matt J]

And in my code, if the nonlinear constraints are satisfied, the termination condition(objectiveLimit) is also satisfied.

It is not enough that the nonlinear constraints be satisfied for the optimization to stop. The linear ones need to be satisfied as well.

But if you have an initial point that satisfies all the contraints and the objective limit, the optimization should not progress, as the following example shows:

nonlcon=@(x) deal(x.^2-1,[]);

opts = optimoptions('fmincon' , ObjectiveLimit=1,Display='iter');

x=fmincon(@(x)x,0.5, [],[],[],[],[],[],nonlcon,opts )

                                            First-order      Norm of
 Iter F-count            f(x)  Feasibility   optimality         step
    0       2    5.000000e-01    0.000e+00    1.000e+00

Problem appears unbounded.

fmincon stopped because the objective function value is less than
the value of the objective function limit and constraints 
are satisfied to within the value of the constraint tolerance.

x = 0.5000

Conversely, here is a case where the nonlinear constraints are satisfied, but not the linear ones. So, the optimziation can continue,

x=fmincon(@(x)x,-0.5, -1,0,[],[],[],[],nonlcon,opts )

                                            First-order      Norm of
 Iter F-count            f(x)  Feasibility   optimality         step
    0       2   -5.000000e-01    5.000e-01    4.351e-01
    1       5   -2.289291e-01    2.289e-01    1.992e-01    2.711e-01
    2       7    9.409174e-02    0.000e+00    9.409e-02    3.230e-01

Problem appears unbounded.

fmincon stopped because the objective function value is less than
the value of the objective function limit and constraints 
are satisfied to within the value of the constraint tolerance.

x = 0.0941

[Walter Roberson]

How many variables are you optimizing over? fmincon() typically starts by evaluating at a series of points, with there being (N+1) evaluations for N variables. (One evaluation is at the original point; the other evaluations are at the original point plus a delta at each component in turn.)

[재현]

@Torsten

I can't check the results right now because I'm running other code.

However, I guess the initial conditions will not satisfy the constraints.

@Matt J

My code only has lb, ub, and nonlinear constraints.

[x_opt, fval] = fmincon(@(x) objectiveFunction(x, GN2_T_in, GW_T_in, GN2_MFR, GN2_Total_MFR, GW_MFR, GW_Total_MFR, GN2_D, GN2_Dh, GW_D, GW_Dh, GN2_Area, GW_Area, L_s, number_of_segments), ...

initial_guess, [], [], [], [], lb, ub, ...

@(x) constraintFunction(x, GN2_T_in, GW_T_in, GN2_MFR, GN2_Total_MFR, GW_MFR, GW_Total_MFR, GN2_D, GN2_Dh, GW_D, GW_Dh, GN2_Area, GW_Area, L_s, number_of_segments, Tolerance), options);

@Walter Roberson

The number of variables in my code is not fixed.

I ran from as few as 2 to as many as 200. All of the ones I checked were like this.

Thank you all for your hard work. I sincerely appreciate it.

Additionally, I'm currently in conversation with the developer for a response.

[Torsten]

@재현

I can't check the results right now because I'm running other code.

However, I guess the initial conditions will not satisfy the constraints.

Then it will first iterate in order to satisfy the constaints.

[재현]

Here is a part of my code:

F_1, F_2, F_3 are energy balance equation, the true value should be 0.

But considering the tolerance, I allowed up to 1.

for i = 1:1:number_of_segments

F_1(i) = f_1(i) - f_3(i); % = 0

F_2(i) = f_2(i) - f_3(i); % = 0

F_3(i) = f_1(i) - f_2(i); % = 0

end

% Inequality constraint

c = [abs(F_1) - 1 ; abs(F_2) - 1; abs(F_3) - 1];

And here is objective function "F":

F = 0;

for i = 1:1:number_of_segments

F = F + F_1(i)^2 + F_2(i)^2 + F_3(i)^2;

end

So, F wil have a small value. but as I run my code, Fval has very large value.

and The termination condition is satisfied in the 8th iteration, but the iteration does not end.

(ObjectiveLimit is 2)

fmincon stopped because the objective function value 7.267704e-01 is less than options.ObjectiveLimit = 2.000000e+00 and the relative maximum constraint violation 0.000000e+00 is less than options.ConstraintTolerance = 1.000000e-06

[Torsten]

Fval < ObjectiveLimit = 2 is satisfied in iteration 11 - i.e. when "fmincon" terminates.

[Matt J]

Fval < ObjectiveLimit = 2 is satisfied in iteration 11 - i.e. when "fmincon" terminates.

@재현 The output display also shows, in the Feasibility column, that your constraints aren't remotely satisfied, until about iteration 9 or 10.

My code only has lb, ub, and nonlinear constraints.

As I said before all constraints, including lb,ub must be satisfied in order for the ObjectiveLimit to terminate the iterations.

Also, keep in mind that if you are using fmincon's interior point algorithm, the initial x0 you give will not be used unless it satisfies the bounds. If x0 does not satisfy the bounds, fmincon will replace it with an alternative point.

[Walter Roberson]

Not sure why you did not code

    F = 0;
    for i = 1:1:number_of_segments
        F = F + F_1(i)^2 + F_2(i)^2 + F_3(i)^2;
    end

as simply

    F = sum(F_1.^2 + F_2.^2 + F_3.^2);

?

[재현]

@Torsten

I should have sent you another example, but I was mistaken.

The picture above is when there is 1 segment, that is, 2 variables.

In this case, you can see that it ends normally.

However, when there are 3 segments, that is, 6 variables,

the iteration does not end even when Fval < objectiveLimit(iter 13), as shown in the picture below.

@Matt J

"As I said before all constraints, including lb,ub must be satisfied in order for the ObjectiveLimit to terminate the iterations. "

I understand that part. But I still don't know if fmincon optimizes on solutions that satisfy constraints.

(In the early part of the iteration, F values ​​that cannot be obtained if the constraints are satisfied are obtained.)

Algorithm i used is sqp, not interior point.

@Walter Roberson

I used that method to see it intuitively.

"F = sum(F_1.^2 + F_2.^2 + F_3.^2);"

Are there any benefits to doing this?

[Matt J]

I understand that part. But I still don't know if fmincon optimizes on solutions that satisfy constraints.(In the early part of the iteration, F values that cannot be obtained if the constraints are satisfied are obtained.)

No, the individual iterations are not required to satisfy any constraints except (by default) the bounds. Even if you initialize with a point that satisfies all nonlinear constraints, the iterations may transit into the space of nonfeasible solutions. Although, when this happens, fmincon tries to push them back toward the feasible set as the algorithm converges.

[재현]

@Matt J

iterations may transit into the space of nonfeasible solutions.

Thank you so much, I really respect you very much. Another way to say the answer I want to know.

I wanted to know whether fmincon only optimizes on feasible solutions (If this were not, fmincon would optimize even on nonfeasible solutions).

We've come a long way because of my poor explanation.

But there's one thing I'm curious about your comment.

the individual iterations are not required to satisfy any constraints except (by default) the bounds.

Do bounds refer to lb, ub?

I ran the code, and the optimization went well even when I gave the initial value outside the range of lb, ub.

So is it okay if bounds are not satisfied?

Thank you.

[Matt J]

Thank you so much

You are quite welcome, but please Accept-click the answer if you consider the question resolved.

Do bounds refer to lb, ub? I ran the code, and the optimization went well even when I gave the initial value outside the range of lb, ub.

Yes, certain fmincon algorithms (interior-point and sqp) are guaranteed to satisfy the lb,ub bounds at all iterations, which you can read about here,

https://www.mathworks.com/help/optim/ug/choosing-the-algorithm.html

Also, in the case of the interior-point algorithm, you can turn off this behavior with the HonorBounds optimoption,

https://www.mathworks.com/help/optim/ug/fmincon.html#busog7r-options

However, none of the fmincon algorithms can guarantee if/when the nonlinear or the general linear constraints (A,b,Aeq,beq) will be satisfied.

[재현]

Even if I give an initial value that is outside the boundary lb, ub, it will immediately fall within lb, ub when the first iteration is executed, right?

Nonlinear constraints may not be like that.

[Walter Roberson]

Are there any benefits to doing this?

Vectorized code is typically faster.

F_1 = rand(1,1e6);
F_2 = rand(1,1e6);
F_3 = rand(1,1e6);
t1 = timeit(@()ByLoop(F_1, F_2, F_3), 1)

t1 = 0.0037

t2 = timeit(@()ByVector(F_1, F_2, F_3), 1)

t2 = 2.6420e-04

t1/t2

ans = 13.9356

function F = ByLoop(F_1, F_2, F_3)
    number_of_segments = numel(F_1);
    F = 0;
    for i = 1:1:number_of_segments
        F = F + F_1(i)^2 + F_2(i)^2 + F_3(i)^2;
    end
end

function F = ByVector(F_1, F_2, F_3)
    F = sum(F_1.^2 + F_2.^2 + F_3.^2);
end

[Walter Roberson]

Even if I give an initial value that is outside the boundary lb, ub, it will immediately fall within lb, ub when the first iteration is executed, right?

If you give initial values outside of lb, ub, then those values will be immediately moved inside the bounds (well, except for the case where the bounds are equal, in which case they will be moved to be the bounds and the corresponding variable will be internally eliminated from movement.)

If you give initial values that are exactly equal to (non-equal) bounds then the exact behaviour depends on which algorithm is active. Some of the algorithms (including the default interior-point) move values that are exactly on the bounds to be interior to the bounds, whereas some of the algorithms leave the values at the bounds.

[재현]

Oh, I see. i'll take it.

Thank you.

[Matt J]

Even if I give an initial value that is outside the boundary lb, ub, it will immediately fall within lb, ub when the first iteration is executed, right?

When using sqp or interior-point, yes.

Nonlinear constraints may not be like that.

Nonlinear constraints are never like that, nor are linear ones (that aren't bounds).

[재현]

Thank you again.

I learned exactly what I wanted.