nested calls to fmincon

David Brown

David Brown (view profile)

님이 질문을 제출함. 26 Oct 2019
최근 활동 John D'Errico

John D'Errico (view profile)

님이 편집함. 29 Oct 2019
Walter Roberson

Walter Roberson (view profile)

님이 답변을 채택함.
Can one make a second call to fmincon within a first call to fmincon? That is, does Matlab allow nested calls to fmincon?
I seek a method to solve a min-max problem. I wish to minimize f(D,A,b(A)), where the function b(.) solves the secondary problem: maximize g(D,A,B)) with optimal solution B=b(A). In this problem, D is data (stock returns), and A and B are vectors of parameters. The function is nonlinear, and there are simple linear constraints on A & B.
I set up the problem by (i) a call to fmincon, minimizing f(.) with respect to A, and within the function (script) defining f(.) a second call to fmincon to minimize -g(.). The second call generates an error "Not enough input arguments". This suggests to me that it is not possible in Matlab to nest these calls.
Am I correct in this conclusion? If so, what suggestions can you make that might allow me to solve this problem? Any advice is appreciated, and if necessary I can send the code and data.
Thanks very much,
David

로그인 to comment.

답변 수: 4

Walter Roberson

Walter Roberson (view profile)

님의 답변 26 Oct 2019
채택된 답변

Yes, you can use nested calls to fmincon.
I suspect you forgot a @ in designating the name of the function to call.

David Brown

David Brown (view profile)

27 Oct 2019
Thank you Walter!

로그인 to comment.

John D'Errico

John D'Errico (view profile)

님의 답변 27 Oct 2019
John D'Errico

John D'Errico (view profile)

님이 편집함. 27 Oct 2019

Um, yes, you can use nested calls to fmincon, but with a huge, massive caveat.
fmincon requires differentiability of the objective function. But the outut of fmincon will not in general be a differentiable function of the input! It can easily converge to different solutions depending on the staritng values, and the parameters in your function. As well, the convergence tolerance will leave any solution as only very approximate.
That means the outer call to fmincon will have serious problems converging.

Walter Roberson

27 Oct 2019
Good point John.

로그인 to comment.

David Brown

David Brown (view profile)

님의 답변 28 Oct 2019

John,
Your response is both helpful and troubling. Do you have a suggestion for optimization that avoids nesting calls to fmincon? My original problem and question, slightly revised, follows.
David
I seek a method to solve a min-max problem. I wish to minimize f(D,A,b(D,A)), where the function b(.) solves the secondary problem: maximize g(D,A,B)) with optimal solution B=b(D,A). In this problem, D is data (stock returns), and A and B are vectors of parameters. The function is nonlinear, and there are simple linear constraints and bounds on A & B.
I currently set up the problem by (i) a call to fmincon, minimizing f(.) with respect to A, and within the function (script) defining f(.) a second call to fmincon to minimize -g(.) with respect to B.

Walter Roberson

28 Oct 2019
John D'Errico

John D'Errico (view profile)

29 Oct 2019
This is difficult to answer, because your question is a bit confusing.
But let me start with an explanation of how an optimizer works. You give it a function, and a start point. Then it (hopefully) converges to some point, one that happens to satisfy the convergence criteria. Since a nonlinear problem often has mutliple potential solutions that an optimizer might converge to, there is the concept of a basin of attraction. That is, if you start at any point in a given set of points, the optimzer will converge to essentially the same solution that is attached to that basin. But in fact, that solution is actually a fuzzy thing, not a single point in the parameter space. The optimizer has various tolerances in it, it has an iteration max, etc. So what happens is you can envision any "solution" as actually a cloud or cluster of points, the set of points the optimizer will be willing to accept, based on all of the supplied tolerances. And just because you may have supplied TolX as extremely tight, this need not mean that fmincon can absolutely guarantee the solution it returns is correct to within that tolerance. It may just mean that fmincon may have decided that it cannot proceed any further. The exitflag may contain useful information in this respect.
The point is, you can think of the result from fmincon to be a cloud of points, not really a single point. But then, when you call this as a function itself, you are creating a situation where fmincon will need to differentiate that function numerically. Obviously, you cannot provide an analytical Jacobian, but fmincon needs a gradient vector. So it does a numerical differentiation. And what happens when you use a numerical differentiation on a cloud of fuzz? That is, on a "noisy" function? That is, here the noise is not random, but it is arbitrary.
The way a numerical gradient is computed, if you perturb the parameter set by a tiny amount. Then you compute a derivative, using the classical definition of derivative. That is, for small deltax as deltax approaches zero as a limit, we have
df/dx = (f(x+deltax) - f(x))/deltax
But here, what happens? Remember that f(x) is itself the result of an optimization, a fog of convergence fuzz around a true value. Divide that difference by a small number, and those numerical derivatives could possibly become corrupted, essential garbage.
This could possibly be a problem whenever you have one adaptive scheme calling another. For example, a numerical optimization on top of a numerical integration, or an ODE solver, etc. The tool on the inside creates a result that is accurate only to a tolerance, but the the tool on the outside tries to use that result in an intelligent way. This is arguably not very important for an integral of an integral, since a numerical integration tool does not try to differentiate the integration kernel. But when you pass a function to an optimizer, the first thing fmincon does is differentiate it. So fmincon on top of fmincon can be an issue.
So the outer instantiation of fmincon creates an inaccurate estimate of the gradient at every iteration. That may not be as much of a problem when the outer optimization is far away from the solution, as it then needs only to be pointed in a reasonable direction. But what happens when you get near the solution? Now the gradient will get pretty small, and then even small perturbations in the gradient elements can become important. But what did we say about? That a fear is the gradient estimate will be poor. So what can happen is near the eventual solution, the gradient might actually start pointing in directions that do not even represent a descent direction. And the gradient must always point in a reasonable direction, else fmincon will get upset and confused.
Now, I cannot positively say this will be a problem. But this is all something that can easily be an issue, and something that is at the very least an event you need to watch out for.
One solution might be to use a tight tolerance on the inner optimization. Then back off on the outer problem tolerances.
A perhaps better approach might be to use a derivative free optimization for the outer problem. GA comes to mind as a good choice here. GA does not attempt to differentiate the objective. Other stochastic optimizers can also be good, for example a PSO tool. In fact, those tools do not even require a differentiable result. That makes them a far more robust solver for a problem like this. (Having GA call a GA solve is another bad idea though.)

로그인 to comment.

David Brown

David Brown (view profile)

님의 답변 28 Oct 2019

Walter,
Thanks for the quick response, and I appreciate your suggestions.
I do not believe fminimax fits my problem. The specification max_x min_i Fi(x) assumes choice over a finite number of functions Fi(.). In my problem the choice variables A and B are vectors in bounded convex regions of Euclidean spaces, say, Rm and Rn.
Any other thoughts?
David

John D'Errico

28 Oct 2019