Nested fmincon call to solve min max optimization

Hello, I try to implement a complex min max optimization problem but I have some issues with nested fmincon, so I just tried to code it with a really dummy example that can be solved by hand:

Trivially, the result should be , and

f = @(x, y) x + y;

% Minimize over y
min_fun_1 = @(x) fmincon(@(y) f(x, y), 0, [], [], [], [], -10, 10, [], optimoptions('fmincon', 'Display', 'iter'));


% Minimize over x
initial_x = 0; 
[x_opt_minmin, fval_minmin] = fmincon(@(x) min_fun_1(x), initial_x, [], [], [], [], -10, 10, [], optimoptions('fmincon', 'Display', 'iter'));

% Display the results
disp('Optimal minmin x:');
disp(x_opt_minmin);
disp('Optimal minmin value of f:');
disp(fval_minmin);

But the code above gave me something else, so what did I do wrong in my code or did not understand ? Thanks in advance

Optimal minmin x:

0

Optimal minmin value of f:

-10.0000

For info the fminimax function doesn't seem to fit my problem, as I don't want to discretize objective functions.

Answer 1

[Jack]

Explanation of the Issue

In your nested fmincon setup, the inner call to fmincon returns the optimal y, but you are passing that directly to the outer fmincon as if it were the objective function value. Essentially, the outer optimization is minimizing the solution y* rather than minimizing x + y*. That’s why you get x=0 and f=−10 instead of the expected (x,y)=(−10,−10) and -20.

How to Fix

1. Capture Both the Solution and Objective from the inner problem. In MATLAB, fmincon’s second output argument is the minimum function value. For example:[yOpt, fvalInner] = fmincon(@(y) f(x,y), ... );

Here, yOpt is the y that minimizes f(x,y), and fvalInner is the corresponding minimum value f(x,yOpt).

1. Return the Inner Objective to the Outer Problem. Instead of returning yOpt from your inner function, return fvalInner. That way, the outer fmincon will correctly minimize f(x,y*), not y*.

Corrected Example

f = @(x, y) x + y;

% Nested function for the inner minimization
function val = min_fun_1(x)
    % Solve for the best y
    [~, fvalInner] = fmincon(@(y) f(x, y), 0, [], [], [], [], -10, 10);
    val = fvalInner;  % Return the minimized function value, not y
end

% Outer minimization
initial_x = 0; 
[x_opt_minmin, fval_minmin] = fmincon(@(x) min_fun_1(x), initial_x, ...
    [], [], [], [], -10, 10);

% Display the results
disp('Optimal minmin x:');
disp(x_opt_minmin);
disp('Optimal minmin value of f:');
disp(fval_minmin);

With this change, you should get x=−10, and the inner solution will be y=−10, giving f=−20.

Follow me so you can message me anytime with future questions. If this helps, please accept the answer and upvote it as well.

[Matt J]

It does work in this case, see below. In general, though, it is a bad approach, because the partial minimization g(x) =min_y f(x,y) is not always a differentiable function of x, which fmincon assumes. Use fseminf instead as shown here.

% Outer minimization
initial_x = 0; 
[x_opt_minmin, fval_minmin] = fmincon(@(x) min_fun_1(x), initial_x, ...
    [], [], [], [], -10, 10);

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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.


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.

% Display the results
disp('Optimal minmin x:');

Optimal minmin x:

disp(x_opt_minmin);

  -10.0000

disp('Optimal minmin value of f:');

Optimal minmin value of f:

disp(fval_minmin);

  -20.0000

% Nested function for the inner minimization
function val = min_fun_1(x)

    f = @(x, y) x + y;

    % Solve for the best y
    [~, fvalInner] = fmincon(@(y) f(x, y), 0, [], [], [], [], -10, 10);
    val = fvalInner;  % Return the minimized function value, not y
end

[John D'Errico]

As @Matt J says, the nested optimization is a not good idea in general. Here, it would probably work due to the simplicity of the objective. A linear objective means things will work well, no matter what you do.

But remember that an optimizer like fmincon does not return an exact value in general. It stops when it gets close enough to the objective, to be within the tolerance. And that means the result tends to be a little "fuzzy". In turn, that makes the objective passed to the outer optimization non-differentiable, a requirement for fmincon to perform well. This is thecase for any such nested pair. For example, if you used an optimizer to optimize the result of a numerical integration, performed using integral, you would be risking failure.

Avoid doing such nested operations that employ tolerances whenever possible. When ABSOLUTELY necessary, you want to make the outer tolerances a bit looser. And you may also want to raise the minimum difference for the finite differencing used to compute the gradient. Again, you want to get out of the fuzz, to allow it to see a signal above that fuzz.

[Matthieu]

Thank you all @Jack @Matt J @John D'Errico for your answers and clarifications.

Answer 2

[Matt J]

To solve without nested optimization, reformulate as,

which can be solved using fseminf. The example below is for

xlb=-10; xub=+10;  %bounds on x
ylb=-10; yub=+10;  %bounds on y

lb=[xlb,-inf];
ub=[xub,+inf];

[xt,fval]=fseminf(@(xt) xt(2),[0,1000],1,...  %xt=[x,t]
    @(xt,s)myinfcon(xt,s,ylb,yub),[],[],[],[],lb,ub);

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.

x=xt(1);
y=fmincon(@(y)-f(x,y) , 0,[],[],[],[], -ylb,+yub );

Initial point is a local minimum that satisfies the constraints.

Optimization completed because at the initial point, 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.

x,y %min/max solution

x = -10

y = 10

function fval=f(x,y)
   fval = x+y;
end
function [c,ceq,K,s]=myinfcon(xt,s,ylb,yub)

    x=xt(1);
    t=xt(2);

    % Sample set
    if isnan(s)
        % Initial sampling interval
        s = [0.01 0];
    end
    y = -ylb:s(1):yub;
 
    c = [];
    ceq = [];
    K = f(x,y)-t; %seminf constraint
    
 end