Fmincon stuck within an iteration for a particular start point

Question

Hari 2015-8-3

2
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/232170-fmincon-stuck-within-an-iteration-for-a-particular-start-point

评论： Sean de Wolski 2016-12-13

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')

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Matt J 2015-8-3

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/232170-fmincon-stuck-within-an-iteration-for-a-particular-start-point#answer_188081

编辑：Matt J 2015-8-3

在 MATLAB Online 中打开

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.

5 个评论
显示 3更早的评论隐藏 3更早的评论

Hari 2015-8-3

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 2015-8-3

编辑：Matt J 2015-8-4

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.

Sean de Wolski 2015-8-4

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 2015-8-5

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 2016-12-13

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/232170-fmincon-stuck-within-an-iteration-for-a-particular-start-point#answer_247017

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.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Sean de Wolski 2016-12-13

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.

请先登录，再进行评论。

Fmincon stuck within an iteration for a particular start point

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

5 个评论
显示 3更早的评论隐藏 3更早的评论

更多回答（1 个）

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

另请参阅

类别

标签

产品

Community Treasure Hunt

Fmincon stuck within an iteration for a particular start point

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

5 个评论 显示 3更早的评论隐藏 3更早的评论

更多回答（1 个）

1 个评论 显示 -1更早的评论隐藏 -1更早的评论

另请参阅

类别

标签

产品

Community Treasure Hunt

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

5 个评论
显示 3更早的评论隐藏 3更早的评论

1 个评论
显示 -1更早的评论隐藏 -1更早的评论