Fmincon stuck within an iteration for a particular start point

Hi,

I'm doing (nonlinear/non-convex) constrained optimization using SQP algorithm on a fairly small sized problem (average ~0.5 second to optimal solution in a 2 core i7 computer under no other load). I'm solving this problem across a large # of start points (and some parameterization) using parfor loop.

The algorithm runs fine for most part and I'm getting valid solutions.

Unfortunately for certain start point combinations (and parameterization) the algorithm is endlessly executing without doing a time-out.

I tried to understand why it is stuck and turned on certain options in fmincon/SQP using:

SQPoptions = optimoptions(@fmincon,'Algorithm','sqp','Display','iter-detailed','TolX',Tol(4),'TolFun',Tol(1),...
                            'GradObj','on', 'GradConstr','on','ObjectiveLimit',1e-20);

[sqpxstar, sqpfval, sqpmflag, sqpoutput] = fmincon(ObjFunGrad,[TempRw(NumOfParms+1:NumOfParms+...
          (NumOfExpVar*CurrExpRunCnter))],LHSMatrixLinIneq{CurrExpRunCnter},...
    RHSVectorLinIneq{CurrExpRunCnter},LHSMatrixLinEq{CurrExpRunCnter},RHSVectorLinEq{CurrExpRunCnter},...
                    FillUpAlgoDesBoundsLow,FillUpAlgoDesBoundsHigh,[],SQPoptions);

I'm not providing the objective function, constraints etc as they are very nasty expressions (dynamically generated using symbolic expression)

But here is the output for one of the start point combinations. It will display the Iteration 3 and nothing after that (even after waiting for 1 hour). Do note that the initial 3 iterations do not take more than a fraction of a second but after that it is endlessly processing with no seeming progress

                                                          Norm of First-order
   Iter F-count            f(x) Feasibility  Steplength        step  optimality
      0       1    4.113395e+19   0.000e+00                           2.940e+19
  User objective function returned Inf; trying a new point...
      1       3    5.096751e+04   0.000e+00   7.000e-01   6.623e+01   2.058e+19
  User objective function returned NaN; trying a new point...
      2       5    8.540454e+03   0.000e+00   7.000e-01   2.213e+01   6.174e+18
  User objective function returned NaN; trying a new point...
      3       7    4.774538e+03   0.000e+00   7.000e-01   3.456e+02   3.519e+02

Stopping it by pressing control + break just spits out the message that

Operation terminated by user during computeSearchDirSQP (line 49)

In sqpLineSearch (line 281)

In fmincon (line 806)
    [X,FVAL,EXITFLAG,OUTPUT,LAMBDA,GRAD,HESSIAN] =
    sqpLineSearch(funfcn,X,full(A),full(B),full(Aeq),full(Beq), ...

What is the right way to debug this?

I'm ok with prematurely exiting if there is no progress after X amount of time and will just try the next start point in the par for loop. But failed to see any such option in fmincon?

Thanks

Hari

PS: Here is the final SQP options:

>> SQPoptions

SQPoptions =

fmincon options:

   Options used by current Algorithm ('sqp'):
   (Other available algorithms: 'active-set', 'interior-point', 'trust-region-reflective')

     Set by user:
            Algorithm: 'sqp'
              Display: 'iter-detailed'
           GradConstr: 'on'
              GradObj: 'on'
       ObjectiveLimit: 1.0000e-20
               TolFun: 1.0000e-06
                 TolX: 1.0000e-04

     Default:
      DerivativeCheck: 'off'
          Diagnostics: 'off'
        DiffMaxChange: Inf
        DiffMinChange: 0
       FinDiffRelStep: 'sqrt(eps)'
          FinDiffType: 'forward'
          FunValCheck: 'off'
          MaxFunEvals: '100*numberOfVariables'
              MaxIter: 400
            OutputFcn: []
             PlotFcns: []
         ScaleProblem: 'none'
               TolCon: 1.0000e-06
             TypicalX: 'ones(numberOfVariables,1)'
          UseParallel: 0

     Show options not used by current Algorithm ('sqp')

Answer 1

[Matt J]

What is the right way to debug this?

My suspicion is that fmincon is reaching a point x which, when fed to your objective function and/or constraints, results in a lot of calculations with NaNs in your "nasty expressions". Computations involving NaNs are very slow and bundling a million NaN operations into one big long expression could result in a particularly slow function evaluation. It's just one of the disadvantages of symbolically generated objectives/constraints.

To debug, my suggestion would be to do

>>dbstop if naninf

and rerun the code (without parfor). Use DBSTEP (or its equivalent in the debugger GUI) until you reach the point where the algorithm hangs. Then you can identify the particular point x which is causing your code to hang and study what your expressions are doing at that x.

[Hari]

Hello Matt,

Thanks for the suggestion on dbstop. I tried it but then realized after fiddling around for a couple of minutes that it may not be the best for my scenario. The symbolic expressions I have are simply too laboursome and as it was taking long time to save as matlabfunction files I had originally made them in to anonymous function handles.

I had tried using dbstop in 2 different situations. A start point whose intermediate iterations result in nan/inf but ultimately does get to a local minima. Another is the start point I stated in the question originally for which intermediate iterations result in nan/inf and it never gets to any solution. Comparing the "dbstop.." between these two situations the program keeps flitting between "workspacefunc.m", dataviewerhelper.m" for both situations. At this point I think my question "What is the right way to debug this?" may not be the right approach.

Let me focus on the 2nd question that I had posed "I'm ok with prematurely exiting if there is no progress after X amount of time and will just try the next start point in the par for loop. But failed to see any such option in fmincon?"

Is there a way I can prematurely exit from fmincon for that particular start-point if no progress made after certain amount of time Or if beyond Y Nan/Inf evaluations.

I'm surprised that options like "MaxFunEvals", "MaxIter" never come in to play for terminating this prematurely? As you seem to suggest it is probably stuck within a particular evaluation having ridiculous amount of nan/inf

Any ideas on prematurely terminating would be highly welcome.

Thanks

Hari

[Matt J]

Is there a way I can prematurely exit from fmincon for that particular start-point if no progress made after certain amount of time

You can use fmincon's OutputFcn option, in particular its Stop Flag,

http://www.mathworks.com/help/matlab/math/output-functions.html#bsgpq6q-39

to add any stopping criteria that you want, whether based on elapsed time, or anything else. However, the Output Function is called at the beginning, end, and a few other strategic places during an iteration, not in the middle of a function evaluation. The only thing you can do to make the algorithm bail out of an evaluation is to break its code into multiple steps and insert your own if/else tests to see if it is worth continuing with further steps. This brings me back to my point about dynamically generated function code and its pitfalls...

I'm surprised that options like "MaxFunEvals", "MaxIter" never come in to play for terminating this prematurely? As you seem to suggest it is probably stuck within a particular evaluation having ridiculous amount of nan/inf

I think you've answered your own question. The stopping criteria based on MaxFunEvals and MaxIter aren't relevant to cases where the algorithm gets stuck in the middle of an early function evaluation.

[Hari]

Hi,

Thanks for the tip regarding Output Function. Certainly interesting for future applications.

Regarding current problem: I cannot NOT use symbolic as there is lot of differential calculus (though straightforward) and linear algebra used for representing physical/biological/chemical phenomena that Iam working with.

But one thing I did is, the major computation issue is with gradient of objective rather than the objective itself (objective is determinant of a matrix) so I decided to turn off the GRADIENT "on" option in SQL. So the issues stopped.

Ofcourse there is a penalty associated in terms of quality of solutions but am ok with it compared to being stuck in a no progress loop

Thanks

Hari

[Sean de Wolski]

You could use parfeval in the Parallel Computing Toolbox to "submit" a call or bunch of calls to fmincon. If enough time elapses (or if you get a positive exit flag(!)), then cancel the parfeval futures and keep going.

[Hari]

Hello Sean,

That seems like a very interesting approach. I will read up on parfeval and get back in case of questions

Thanks

Hari

Answer 2

[Tao Lu]

Hi, Hari:

Do you already solve the original problem? Since I also have the same problem when using fmincon with lots of initial guesses and conditions.

Thank you.

[Sean de Wolski]

In recent releases of MATLAB there is a "Pause" button. I would encourage you to use it to stop fmincon in its tracks in debug mode so you can see what's going on.