MATLAB Answers

Minimization of a function with unknown gradient but known sparsity pattern of its hessian

3 ビュー (過去 30 日間)
Jan Valdman
Jan Valdman 2019 年 10 月 29 日
Answered: Jan Valdman 2019 年 10 月 30 日
Dear colleagues,
is there a fmincon option to minimize a function without the knowledge of its gradient but providing a sparsity pattern of a Hessian?
My function comes from a FEM formulation of an energy in nonlinear mechanics of solids and it is too difficult to differentiate analytically.
However the sparsity pattern of the hessian is easily available though a FEM connectivity of variables.
Is there a way to exploit it efficiently? If I run with 'Algorithm','quasi-newton', it seems not to accept 'HessPattern' option. An alternative would be to obtain an appriximative gradient (can you suggest one?) and use 'Algorithm','trust-region' insteady. Does anyone have experience with it?
Best wishes,
Jan

  0 件のコメント

サインイン to comment.

採用された回答

Alan Weiss
Alan Weiss 2019 年 10 月 29 日
Sorry, I am afraid that the available options don't work efficiently for your case. The HessPattern option is available only for the 'trust-region-reflective' algorithm, but for that algorithm you need to supply a derivative.
I am not sure what to suggest that you probably have not yet tried. For the default 'interior-point' algorithm you can try using the HessianApproximation option set to 'lbfgs' or {'lbfgs',Positive Integer}, but that does not directly use the sparsity pattern that you know. Or, and this seems crazy, you could code a finite difference gradient in your objective funtion, bypassing MATLAB's internal one, and then you could use the 'trust-region-reflective' algorithm with the HessPattern option. I am not sure that the 'trust-region-reflective' algorithm would satisfy you anyway, as it accepts only bound constraints or only linear equality constraints.
Sorry.
Alan Weiss
MATLAB mathematical toolbox documentation

  5 件のコメント

表示 2 件の古いコメント
Jan Valdman
Jan Valdman 2019 年 10 月 29 日
I already tried to use John´s package and wrote him and his focus is more on a quality of the obtained gradient rather than the speed of his code. So far it is not faster then 'quasi-newton'. Anyway I should give it another try. Thank you.
To Alan: Bound constraints are perfectly enough. In fact, if there was the same option (no gradient and hessian pattern only) for fminunc, it would really help me. Do you have any ideas for fminunc function instead?
Catalytic
Catalytic 2019 年 10 月 29 日
One possibility might be to use a 1-iteration call to fmincon itself to return the gradient. This uses Matlab's finite differencer and so might be faster than 3rd party implementations,
function [f,numerical_grad]=myObjective(x)
f=...
if nargout>1
options=optimoptions('fmincon','MaxIter',1,'SpecifyObjectiveGradient',false);
[~,~,~,~,~,numerical_grad] = fmincon(@myObjective,x,[],[],[],[],...
[],[],[],options);
end
end
Jan Valdman
Jan Valdman 2019 年 10 月 29 日
Thank you, can you add please add your numerical gradient to the code attached below and beat 'quasi-newton' times? Alan's limited BFGS also works fine, but it is not that fast. Maybe one might even use the sparsity pattern to generate a gradient faster, since the functional is a sum of values (in this example and in my computations as well).

サインイン to comment.

More Answers (1)

Jan Valdman
Jan Valdman 2019 年 10 月 30 日
Dear colleague,
based on our discussions from yesterday, I implemented a finite difference scheme for a gradient approximation exploiting a particular sum form of the function f. It enables me to compute an approximate gradient very quicky and then I can feed fminunc with it in both variants 'quasi-newton' and 'trust-region-reflective'. Please fiind resulting two files attached.
For n=1000, 'quasi-newton' is still faster.
For n=20000, 'trust-region-reflective' beats 'quasi-newton'.
For n=40000, 'trust-region-reflective' converges and 'quasi-newton' fails due to memory issues.
So,an efficient evaluation of an approximative gradient might be a way to my speedup in FEM formulations. I will look further into it. Thank you.

  0 件のコメント

サインイン to comment.

サインイン してこの質問に回答します。


Translated by