fmincon step size and speed

Hello all,

I'm using fmincon to solve a nonconvex optimization problem. Mainly my problem is optimizing some function over a 2D area, where the optimizing variables are the x and y coordinates of N points, so my minimizer myX for my objective function f(myX) is a (2 by N) matrix representing the x and y coordinates. For this optimization, I'm interested in changes >1 meter because my objective function is not very sensitive for small changes in x and y.

So, mainly I have these two problems:

• The step size of fmincon is very small. I'm using this configuration for fmincon:

myoptions = optimoptions(@fmincon,'Algorithm','interior-point','Display','iter', 'FiniteDifferenceStepSize', 5,...
     'TolX', 1, 'UseParallel',1);

Example of the output:

                                            First-order      Norm of
 Iter F-count            f(x)  Feasibility   optimality         step
    0      21   -1.660633e+00    0.000e+00    7.942e-04
    1      42   -1.660634e+00    0.000e+00    7.942e-04    1.598e-03

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 default value of the constraint tolerance.

As you can see, the objective function f(myX) is slightly changing (that is also happening to x and y coordinates). In this simulation I'm starting from points that satisfy the constraints but they are very far from optimality. So, how can I change the step size of fmincon (I'm interested in steps greater than 1 meter or changes on objective function that is greater than 0.1).

• My objective function and constraint contain integral that needs to be evaluated numerically, so fmin is very slow. Are there ways to speed up fmincon.

Best Regards and thank you in advance for your help.

Answer 1

[Alan Weiss]

It sounds like you need to use the Global Optimization Toolbox solver patternsearch with a large value of the MeshTolerance option, like 3/4. You should also change the InitialMeshSize option to 16 or so, and, because your objective function is slow, consider using the Cache option. You seem to have about 20 control variables, so patternsearch should work fine.

The reason I say this is that fmincon is a gradient-based solver, but your function is insensitive to small changes.

Alan Weiss

MATLAB mathematical toolbox documentation

[Hussein Ammar]

Thank you for mentioning the patternsearch function, which seems very useful, but I don't have access to the Global Optimization Toolbox. Is there another way to do the same thing using fmincon?

[Alan Weiss]

I think that patternsearch is the solver of choice of this kind of problem, or even better the newer surrogateopt. But let's see if fmincon can work for you. You seem to have set reasonable options, except notice that fmincon stopped because the step size was too small. So don't set the 'TolX' option. I'd also try setting the OptimalityTolerance option to 1e-10, just in case that kicks in too early, and maybe try setting the Algorithm option to 'sqp' just to see if it helps.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[Hussein Ammar]

Thank you for your reply. I have tried this option:

myoptions = optimoptions(@fmincon,'Algorithm','sqp','Display','iter', 'FiniteDifferenceStepSize', 5,...
            'OptimalityTolerance', 1e-10, 'UseParallel',true);

And now I get:

        Iter  Func-count            Fval   Feasibility   Step Length       Norm of   First-order  
                                                                       step    optimality
    0          21   -2.818853e+00     8.000e-01     1.000e+00     0.000e+00     5.295e-04  
    1          42   -1.570722e-16     0.000e+00     1.000e+00     5.653e+07     2.000e-01  
    2          63   -1.570722e-16     0.000e+00     1.000e+00     2.871e-09     3.453e-24  

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>

And my optimization variables are not optimal at all. Also, the optimization function fval didn't decrease.

Also, I have tried this option:

myoptions = optimoptions(@fmincon,'Algorithm','sqp','Display','iter', ... 'DiffMinChange', 1,...
             'UseParallel',true);

I got this:

 Iter  Func-count            Fval   Feasibility   Step Length       Norm of   First-order  
                                                                       step    optimality
    0          21   -2.818853e+00     8.000e-01     1.000e+00     0.000e+00     1.054e-03  
    1          42   -1.976003e-13     0.000e+00     1.000e+00     1.091e+07     2.000e-01  
    2          63   -1.976003e-13     0.000e+00     1.000e+00     5.367e-10     5.832e-20  

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>
         

And still, the resulted optimization variables are very bad.

By the way when l check the 'output' term returned by fmincon I get this:

struct with fields:

         iterations: 2
          funcCount: 63
          algorithm: 'sqp'
            message: '↵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, 3.453441e-24,↵is less than options.OptimalityTolerance = 1.000000e-10, and the relative maximum constraint↵violation, 0.000000e+00, is less than options.ConstraintTolerance = 1.000000e-06.↵↵'
    constrviolation: 0
           stepsize: 2.8705e-09
       lssteplength: 1
      firstorderopt: 3.4534e-24

Is the mentioned stepsize used directly in updating the x and y coordinated or it is being multiplied with some number (like the gradient for example).

[Alan Weiss]

I'm sorry that the solver is not performing satisfactorily, but it was really not designed for this kind of problem. I suggest that you get a trial version of Global Optimization Toolbox and try the patternsearch solver, which was designed for this kind of problem. Or, try surrogateopt with the workaround for nonlinear constraints given in this example.

Also, you can find the meaning of the fields in the output structure in the fmincon documentation.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[Hussein Ammar]

I think fmincon can still get good solutions for this problem. I just need to try different configurations for the parameters in optimoptions and see which one works better. Thank you.