fmincon options: How can i prevent the optimization to make big steps of X, to search for a possible global optimum, when she solver found a possible lokal minimum?

Hey guys, (excuse my englisch, i'm not a native speaker) im using fmincon to optimize a tendon driven robot. The value i optimize right now is the tendon-force X = tau(in my code). And the function that is optimized passes back the distance of the robot-tip to a point in 3D space. Can't give more information on that.

My function worked fine until i used nonlcon. The distance was optimized to less than a milimeter. With nonlcon the distance is 12mm or more. Often the function finds a lokal minimum, that is not near the gobal minimum. But then X = tau is increased to much and another function (TM_IVP_2) malfunctions.

tipError =

      0.0449

tipError =

      0.0449

tipError =

      0.0449

tipError =

      0.0450

Warning: No solution for BVP found, exitflag=0 
> In TM_IVP_2 (line 106)
  In Test_Code_fmincon_voxel/optimFct (line 8)
  In sqpInterface
  In fmincon (line 808)
  In Test_Code_fmincon_voxel (line 64)
  In Test_Code_Start_noloop_voxel (line 97) 

tipError =

      0.1254

Warning: No solution for BVP found, exitflag=0 
> In TM_IVP_2 (line 106)
  In Test_Code_fmincon_voxel/Test_Code_Collision (line 26)
  In sqpInterface
  In fmincon (line 808)
  In Test_Code_fmincon_voxel (line 64)
  In Test_Code_Start_noloop_voxel (line 97) 
Warning: No solution for BVP found, exitflag=0 
> In TM_IVP_2 (line 106)
  In Test_Code_fmincon_voxel/optimFct (line 8)
  In sqpInterface
  In fmincon (line 808)
  In Test_Code_fmincon_voxel (line 64)
  In Test_Code_Start_noloop_voxel (line 97) 

tipError =

      0.1289

Warning: No solution for BVP found, exitflag=0 
> In TM_IVP_2 (line 106)
  In Test_Code_fmincon_voxel/Test_Code_Collision (line 26)
  In sqpInterface
  In fmincon (line 808)
  In Test_Code_fmincon_voxel (line 64)
  In Test_Code_Start_noloop_voxel (line 97) 

tipError =

      0.1196

tipError =

      0.1217

tipError =

      0.1350

tipError =

      0.1220

tipError =

      0.1117

tipError =

      0.0976

tipError =

      0.0776

tipError =

      0.0629

tipError =

      0.0541

What i want to know is:

• Am i using nonlcon wrong? I need it to constrain the 3D space, because there are objects the robot should not pass.
• Is there a way to stop the optimization to search for a global minimum, when a possible local minimum is found?

function [ tau , Optimization, exflag, output ] = Test_Code_fmincon_voxel(indexKid, u_init_guess, tau_start, param, l, F, Voxel)
%UNTITLED Summary of this function goes here
%   Detailed explanation goes here
Optimization = 0;
% tau = tau_start;
    function tipError = optimFct(tau)
      Optimization = Optimization +1;
      [y] = TM_IVP_2(u_init_guess,tau,l,F,param);
      indexRobo = Test_Code_Voxelize_Points(y(end,1:3), Voxel);  % pass row vector
      tipError = norm(Test_Code_Coordinate_Voxel(indexKid, Voxel)-y(end,1:3))
%       memory
%       drawnow
    end

      %%Constraints
      function [c, ceq] = Test_Code_Collision(tau)
      
      ceq = [];
      [y] = TM_IVP_2(u_init_guess,tau,l,F,param);  % calculates Robot structure
      indexRobo = Test_Code_Voxelize_Points(y(1:end,1:3), Voxel);  % pass row vector
      c = 0;
      for i=1:length(indexRobo(1:end,1))

      if Voxel.volume(indexRobo(i,1),indexRobo(i,2),indexRobo(i,3)) == 2
        c = 1;
        break
      else
        c = -1;
      end
    end
    end
  
    nonlcon = @Test_Code_Collision;

      options = optimoptions('fmincon');
      options.Display = 'final-detailed';%'off','iter','notify','notify-detailed','final','final-detailed',iter-detailed'
      options.Algorithm='sqp';
      options.TolX = 1e-4;
      options.Diagnostics = 'off';
  %     options.UseParallel = 'always';
      % my options
  %     options.PlotFcns = @optimplotstepsize;
      options.TolFun = 1e-6;
      options.MaxIterations = 500;
      options.FiniteDifferenceStepSize = 1e-2;
      options.OptimalityTolerance = 1e-20;
      options.ConstraintTolerance = 1e-8;
  %     options.DiffMaxChange = 5e-2;
      ub = Inf*ones(3,2);
  %     ub = [5,5;5,5;5,5];
  %     lb = zeros(3,2);
      lb = -Inf*ones(3,2);
      [tau, val, exflag, output] = fmincon(@optimFct,tau_start,[],[],[],[],lb,ub,nonlcon,options);
  end

TM_IVP_2 calculates the robot structure. I have to use FiniteDifferenceStepSize, otherwise the optimization does not increase X = tau in a significant way.

If you need more information, let me know. Glad for all help.

(how can i produce a textparagraph, like one after "Hey guys,". cant figure it out :D )

Greetings Vince

Answer 1

[Matt J]

Am i using nonlcon wrong?

At the very least, you appear to be ignoring smoothness/differentiabilty requirements on the objective function and constraints. In particular your constraint is discrete (taking only values of 1 and -1) and therefore cannot be differentiable. Similarly, your objective function looks at norm(z) which is non-differentiable at z=0 instead of norm(z)^2.

Is there a way to stop the optimization to search for a global minimum, when a possible local minimum is found?

fmincon always stops when a possible local minimum is found. fmincon has no way of distinguishing between local and global minima.

[Vincent Hielscher]

Hey thanks for your response.

The calculation in the function TM_IVP_2 are differentiable. But that effect nonlcon not directly. The problem is, the roboter structure has to be calculated for each new set of tendon forces (tau). But that does not really constrain the calculation. Im just checking if the structure of the new robot collides with an object. And i want to prevent the optimization to generade a structure that collides.

There has to be a better way. I can do that by checking the distance of the robot tip to all points of the object. But on the one hand thats non-differentiable again.

I think the main Problem is, that i dont know a good way to combine the optimization and the collision-check.

fmincon always stops when a possible local minimum is found. fmincon has no way of distinguishing between local and global minima.

But why does it change the optimized value at a point of optimization, that the error grow so much?

[Matt J]

The calculation in the function TM_IVP_2 are differentiable

Even so, you break differentiabilty (probably) in this line

 tipError = norm(Test_Code_Coordinate_Voxel(indexKid, Voxel)-y(end,1:3))

because norm(z) is not differentiable at z=0 (which is exactly where you want the algorithm to go). Use norm(z)^2 instead.

But why does it change the optimized value at a point of optimization, that the error grow so much?

Because your constraints are 'illegal', it is doubtful that you have reached any meaningful optimum, but we would have to see the exitflag to be sure.

I can do that by checking the distance of the robot tip to all points of the object. But on the one hand thats non-differentiable again.

But the squared distance is differentiable.

[Walter Roberson]

When a possible local minima violates constraints, fmincon will keep searching trying, attempting to violate the constraints less. This can require that it move away from the potential minima.

[Vincent Hielscher]

Here are an exitflag and output of an "succesful" optimization:

Optimization stopped because the relative changes in all elements of x are
less than options.StepTolerance = 1.000000e-04, and the relative maximum constraint
violation, 0.000000e+00, is less than options.ConstraintTolerance = 1.000000e-08.

Optimization Metric                                           Options
max(abs(delta_x./x)) =   8.93e-05                       StepTolerance =   1e-04 (selected)
relative max(constraint violation) =   0.00e+00   ConstraintTolerance =   1e-08 (selected)

Elapsed time is 129.402779 seconds.

ans =

      'error = 0.0122'

>> exflag

exflag =

       2

>> output

output = 

    struct with fields:

           iterations: 11
            funcCount: 141
            algorithm: 'sqp'
              message: 'Local minimum possible. Constraints satisfied.↵↵fmincon stopped because the size of the current step is less than↵the selected value of the step size tolerance and constraints are ↵satisfied to within the selected value of the constraint tolerance.↵↵Stopping criteria details:↵↵Optimization stopped because the relative changes in all elements of x are↵less than options.StepTolerance = 1.000000e-04, and the relative maximum constraint↵violation, 0.000000e+00, is less than options.ConstraintTolerance = 1.000000e-08.↵↵Optimization Metric                                           Options↵max(abs(delta_x./x)) =   8.93e-05                       StepTolerance =   1e-04 (selected)↵relative max(constraint violation) =   0.00e+00   ConstraintTolerance =   1e-08 (selected)'
      constrviolation: 0
             stepsize: 1.1959e-04
         lssteplength: 3.9098e-04
        firstorderopt: 0.0346

The distance of 12mm is still to much for my needs. But thats not the point. For me it appears the contraints are not respected by the optimization.

I tried norm()^2 . Worked fine for the few optimations i did so far, even when the error is still too big. As example sqrt(4.1599e-04) = 20mm .

I have to work arround my Constraints... i will try to figure out a new way tommorow. I see that fix values for c(x) of 1 and -1 are no good way.

But the squared distance is differentiable. Thing is i know were the object is, because i use Voxel. When i voxelize the robot, i can check only the Voxel that represent the robot and check if it hits an object (without any distance check). I thought that will keep calculation time low. But when there is no other way then using the distance^2 check, i do that. :)

Thanks so far

[Matt J]

For me it appears the contraints are not respected by the optimization.

The output of the optimization says that the constraints, as provided by you, were satisfied.

[Vincent Hielscher]

The output says every time the contraints are satisfied. But when i plot the final robot-structur, it obviously collides with the object. Not every time, but it happens.

I receive exitflags of 2 and -2 .

[Matt J]

Well, then you obviously have a bug in you constraint function (or a bug in your plotting routine).

[Vincent Hielscher]

Over night i ran 63 otimizations. It crashed at the 63rd... exitflag was -2 in 3 cases and 2 in the others.

So now, when i use the distance as constraint c(x)<=0 will be huge. Dimension of c(dim,1) will be:

dim = NumberOfVoxelObject * NumberOfVoxelRobot;

And the NumberOfVoxelRobot can change over time, so the size of c can change during the optimization. That's not allowed, right?

[Matt J]

Nothing is allowed to change during the optimization except x and things that are functions of x.

You might consider using ga() for this problem instead. It looks like it is difficult to pose the problem differentiably.

[Vincent Hielscher]

So, now i tried out something new. I check the distance of a Voxel of the Robot to all Voxel of the object. During checking of the distance only the shortest is saved. Going on to the next Voxel of the Robot and repeat this process. In the end i only saved the shortest distance between a Voxel of the robot and a Voxel of the object. With this i calculate c(x) <= 0 . So i receive only one c.

The Robot never hits the object anymore. But it does not get really close to the point it should reach. Any tipps for the optimization options?

exitflag is most of the time 2. final error is 4.7500e-04 -> sqrt -> 0.0218m -> 21.8mm

The plan was, to use global optimization anyway. But first start with lokal optimization. To get used to it. Maybe i use globel optimization right away.

function [ tau , Optimization, exflag, output ] = Test_Code_fmincon_voxel2(indexKidPoint, u_init_guess, tau_start, param, l, F, Voxel)
%UNTITLED Summary of this function goes here
%   Detailed explanation goes here
Optimization = 0;
% tau = tau_start;
    function tipError = optimFct(tau)
      Optimization = Optimization +1;
      [y] = TM_IVP_2(u_init_guess,tau,l,F,param);
      indexRobo = Test_Code_Voxelize_Points(y(end,1:3), Voxel);  % pass row vector
      tipError = (norm(Test_Code_Coordinate_Voxel(indexKidPoint, Voxel)-y(end,1:3)))^2;
%       memory
%       drawnow
    end

      %%Constraints
      function [c, ceq] = Test_Code_Collision(tau)
        ceq = [];
        minDist = norm([1,1,1]);  % minimal Distance of two Voxel
        [y] = TM_IVP_2(u_init_guess,tau,l,F,param);  % calculates Robot structure
        indexRobo = Test_Code_Voxelize_Points(y(1:end,1:3), Voxel);  % pass row vector

      dist = 1e3; indexDistKid = 0; indexDistRobo = 0;
      for i = length(indexRobo(1:end,1)):-1:1
        for j=1:length(Voxel.indexKid(:,1))
          distTemp = norm(Voxel.indexKid(j,:)-indexRobo(i,:));
          if distTemp < dist
            dist = distTemp;
            indexDistKid = j;
            indexDistRobo = i;
          end
        end
      end
      c = (minDist)^2-(norm(Voxel.indexKid(indexDistKid,:)-indexRobo(indexDistRobo,:)))^2;

    end
  
    nonlcon = @Test_Code_Collision;

      options = optimoptions('fmincon');
      options.Display = 'final-detailed';%'off','iter','notify','notify-detailed','final','final-detailed',iter-detailed'
      options.Algorithm='sqp';
      options.StepTolerance = 1e-5;  % 6 funktioniert einigermaßen
      options.Diagnostics = 'off';
  %     options.UseParallel = 'always';
      % my options
  %     options.PlotFcns = @optimplotstepsize;
      options.TolFun = 1e-8;
      options.MaxIterations = 500;
      options.FiniteDifferenceStepSize = 1e-2;
  %     options.OptimalityTolerance = 1e-20;
      options.ConstraintTolerance = 1e-1;
  %     options.DiffMaxChange = 5e-2;
      ub = Inf*ones(3,2);
  %     ub = [5,5;5,5;5,5];
  %     lb = zeros(3,2);
      lb = -Inf*ones(3,2);
      [tau, val, exflag, output] = fmincon(@optimFct,tau_start,[],[],[],[],lb,ub,nonlcon,options);
      end

[Matt J]

So, now i tried out something new. I check the distance of a Voxel of the Robot to all Voxel of the object.

Voxelizing the robot seems like a bad idea, because it is a discrete function of your optimization variables, x. This again creates differentiability problems and forces you to use very large finite difference step sizes.

Could you not draw a simpler bounding surface around the object you are trying to avoid? A sphere, for example, or a set of planes? The distance of the robot tip to the surface would be easier to express analytically/differentiably.

Consider also that you are not looking for an exact solution anyway - just something you will later refine with global optimization.

[Vincent Hielscher]

Strange i checked for answers each day. But today it's the 1. time i see it.

Anyway...i'll invest some time on thinking about the way i set my boundings. Yeah i know, i don't get the exact solution with optimization.

Thanks a lot for your help Matt! Greetings Vince