fmincon optimizes a non-differentiable function, How?
19 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Maaz Ahmad
el 16 de Oct. de 2022
Comentada: Walter Roberson
el 17 de Oct. de 2022
I am using sqp solver of fmincon to solve a bound-constrained optimization problem. I found that my objective function is continuous but non-differntiable at a few points (due to sharp corners). Still, fmincon optimized my objective and returned an optimal value as the corner point which has the lowest function value. While this makes sense as the optimal point of the function, my understanding was that fmincon should have thrown an error while trying to optimize a non-differentiable function!
As an example, I tried to optimize a simple continuous, non-differentiable objective function: over bounds , which is simply , non-differntiable at . However, using fmincon with sqp solver, providing different initial guesses , the problem converges with an optimal solution of . The exitflag returned was 1, which indicates that the optimization run stopped when the 1st order optimality measure at the iterate point was less than optimality tolerance ( by default). But I am unable to understand how the optimality criterion gets satisfed given that the function is non-differentiable at and the derivatives on either side of it are either or .
1 comentario
Walter Roberson
el 17 de Oct. de 2022
The short summary is that programs are not required to detect and report every case in which the inputs violate the conditions under which the function works.
Detection of violations in numeric routines is generally not possible.
Suppose for example the function divides by the minimum complex component of the non-trivial roots of the zeta function. As far as anyone has been able to tell, the non-trivial roots all have complex component 1/2 (or is it negative 1/2?) But proving that has turned out to be exceedingly difficult. There is no realistic chance that any numeric optimization routine could implement a foolproof theorem prover to determine whether the function meets the mathematical requirements.
Respuesta aceptada
Matt J
el 16 de Oct. de 2022
Editada: Matt J
el 16 de Oct. de 2022
But I am unable to understand how the optimality criterion gets satisfed given that the function is non-differentiable at and the derivatives on either side of it are either -1 or +1
The derivatives are approximated by default with central finite differences which, because of the symmetry of the function abs(x), achieves low values around the minimum. With a more asymmetric example, like below, you can see that we cannot approach the minimum as closely with central finite differences as the tolerances request.
fun=@(x)5*x.*(x>=0)-x.*(x<0);
fplot(fun,[-1,1]);
opts=optimoptions(@fmincon,'Algorithm','sqp','FiniteDifferenceType','central',...
'OptimalityTol',1e-16,'FunctionTol',1e-16,'StepTol',1e-16);
[x,fval, exitflag]=fmincon(fun,-0.2,[],[],[],[],[],[],[],opts)
2 comentarios
Matt J
el 16 de Oct. de 2022
But note that the behavior depends a lot on the algorithm and finite difference type as well. Below, we can see that convergence improves greatly with the default interior-point algorithm and using 'FiniteDifferenceType'='forward':
fun=@(x)5*x.*(x>=0)-x.*(x<0);
opts=optimoptions(@fmincon,'FiniteDifferenceType','forward',...
'OptimalityTol',1e-16,'FunctionTol',1e-16,'StepTol',1e-16);
[x,fval, exitflag]=fmincon(fun,-0.2,[],[],[],[],[],[],[],opts)
Más respuestas (1)
John D'Errico
el 16 de Oct. de 2022
Editada: John D'Errico
el 16 de Oct. de 2022
No. It does NOT throw an error, though maybe sometimes a warning. It may often even survive as it did here. fmincon does not automatically know when a function is non-differentiable. It cannot know that, unless it happens to trip over such a problem point, where it decides something strange could be happening. Of course a discontinuity is worse than a point of non-differentiability.
Anyway, fmincon never LOOKS for points of non-differentiability. Identifying such a point takes effort that is not worth the time invested or the programming effort.
In the case of your test function, consider the history of points it evaluates the function at.
format long g
format compact
[x,f] = fmincon(@testobj,.2,[],[],[],[],0,1)
function z = testobj(x)
z = sqrt((x-.5).^2);
disp([x,z])
end
So you see it generate one point, then use a finite difference to compute a derivative. Then it takes a step. If it has gone too far, it generates another derivative estimate, bounces backwards. In fact, it appears to be bouncing back and forth across the point of non-differentiability. This makes for slow convergence of course, BECAUSE it assumes the function is smooth and well-behaved. Typically we would expect quadratic convergence near a solution. That fails to happen of course here.
Does this mean that fmincon would be expected to work always, even on such a problem? Of course not. It can far too easily get stuck. With some time invested, I could probably come up with some function that causes it to oscillate infinitely between two points.
The point is, fmincon is designed to handle a specific class of problem. That is, continuously differentiable in the domain of the function. When that fails, fmincon can fail, sometimes in strange ways, and it usually does only when convergence is most important to someone. Conversely, the gods of computing insure that it survives on non-important problems as you have given here.
In the cases where you KNOW you have a non-differentiable objective, then you really want to use tools that are not sensitive to such issues. For example, use fminsearch instead, which does not care as much about the smoothness of your function (though smoothness will probably help it to converge better.) Or for more nasty problems yet, use a tool like GA, which gives even less of a hoot about what you throw at it.
Ver también
Categorías
Más información sobre Solver Outputs and Iterative Display en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!