fminsearchbnd, fminsearchcon

Bound constrained optimization using fminsearch

Description

Fminsearch does not admit bound constraints.
However simple transformation methods exist to
convert a bound constrained problem into an
unconstrained problem.

Fminsearchbnd is used exactly like fminsearch,
except that bounds are applied to the variables.
The bounds are applied internally, using a
transformation of the variables. (Quadratic for
single bounds, sin(x) for dual bounds.)

The bounds are inclusive inequalities, which admit
the boundary values themselves, but will not permit
ANY function evaluations outside the bounds.

Note that fminsearchbnd allows the user to exactly fix a variable at some given value, by setting both bounds to the exact same value.

Example usage:
rosen = @(x) (1-x(1)).^2 + 105*(x(2)-x(1).^2).^2;

% unconstrained fminsearch solution
fminsearch(rosen,[3 3])
ans =
    1.0000 1.0000

% Lower bounds, no upper bounds
fminsearchbnd(rosen,[2.5 2.5],[2 2],[])
ans =
    2.0000 4.0000

Lower bounds on both vars, upper bound on x(2)
fminsearchbnd(rosen,[2.5 2.5],[2 2],[inf 3])
ans =
    2.0000 3.0000

I've now included fminsearchcon in the package, a tool that also allows nonlinear constraints.

• Acknowledgements: This submission has inspired the following:; Fminspleas, fminsearchbnd new, optimize, easyfitGUI, Zfit, variogramfit, Total Least Squares Method
• MATLAB release: MATLAB 7.0.1 (R14SP1)
• Other requirements: This code should work on any release of matlab which allows the use of sub-functions.

[Ken Campbell]

Nice trick solving a common problem

[Vijit Nair]

This is a great funcn. Thanks John.

[Evan Palmer]

Works really well and is very handy! Nice job!

[Kaushik b]

Thanks a lot. It really useful and works beautifully.

[Rui Miguel]

I was really needing it! thanks a lot.
Has worked flawlessly for me.

[cedric penard]

Works very well, exellent ! Thanks.

[G.H. Rao]

excellent program. on these lines I applied bounds successfully to the genetic algorithm program 'ga' of Matlab release 14

[CC Gomez]

Nicely written.

[Yes its Good]

works very well!

[Umberto .]

 

[Dmitrey Kroshko]

I connected John D'Errico file to the OpenOpt project
http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=13115&objectType=file
& informed him (I hope my letter passed antispam filter OK)
if any pretensions will be received, I promise to exclude the one
btw now default inner solver is Shor ralg with AST, which is better than current implementation of fminsearch, at least, for those task I tried with. Also, it can handle (sub)gradient info provided by user, and corresponding changes in John code were made.

[Natis Angarita]

 

[jimmy tsai]

It's great. I couldn't solve my problem with fmincon but did it with this file. I really appreciate it.

[Eli Tom]

Nice indeed.

[Lauren Cooney]

thank you for this great program! it saved me a lot of time and frustration!

[Yang Zhang]

I like this program and do you think it is possible to expand it to deal with linear constraints?

[John D'Errico]

See fminsearchcon for linear and nonlinear inequality constraints. Equality constraints are more difficult to implement when coupled with bound constraints as implemented using transformations - John.

[Alex Chirokov]

I really like this code: it is very well written and useful.

[Yossef Ehrlichman]

It's really working. Helped alot! Matlab should incoprate it into its libraries.

[Mert Sabuncu]

excellent code - gets the job done!

[Ken Purchase]

Notice: I have submitted a slightly modified version that includes output and plot functions as well as slightly improved handling of varargin. Search for fminsearch.

The original is excellent and very useful- I hope the changes didn't break anything.

[M. P.]

Worked beautifully for my own optimization problem. Thanks John.

[M. P.]

 

[Chirackel Yoonus]

Very useful

[leo nidas]

Thanks John!

[Umesh Rudrapatna]

Thanks a lot! Helped me a lot.

[Chris Men]

the beauty is yours.

[Srinivasa Chemudupati]

Cannot Thank you enough John!!

[Will]

Excellent modification to create a very useful algorithm. Thanks!

[Ryan Webb]

 Great Function. Used it mane times.

However, now I have a trickier problem where one of the boundaries is a function of one of the variables. Making UB a function of xtrans is possible, but how would fminsearchbnd determine this intent given that the cases for transformation (k) are determined solely by the initial numerical values of the constraints? Thoughts?

[John D'Errico]

Ryan,

This is really not a bound constrained problem. Your constraint is a general one, either a linear or a nonlinear inequality constraint.

The simple solution is to use a code that allows explicit linear or nonlinear constraints. There are a few on the FEX. In fact my fminsearchcon on the FEX does that, by applying a penalty to the problem when a constraint is violated. You might also look at optimize, by Rody Oldenhuis. This code allows explicit constraints of all forms.

However, there is a simple way to solve this class of problem with fminsearchbnd. Use another class of transformation. For example, suppose one wishes to minimize the function f(x,y), subject to the "bound" constraint that x <= erf(y).

Transform your problem such that

u = x + erf(y)
v = x - erf(y)

Clearly, v must be bounded above by 0. So use fminsearchbnd to optimize over the two dimensional domain (u,v). Inside your objective function, for any value of (u,v) you will compute the parameters (x,y) as

x = (u + v)/2;
y = erfinv(u - x);

Now you can finish evaluating the function f(x,y).

The only problem here happens if you also had other fixed bounds on x and y. But many other transformations would also have worked. For example, this transformation:

u = x
v = x - erf(y)

will still allow simple bound constraints on the parameter x, as well as allowing the nonlinear constraint x <= erf(y) as a bound constraint.

John

[Sahin Aktas]

Excellent Code...

[nico]

Very useful...thank you !

[Prabuddha Mukherjee]

Thank you very much...very useful

[Oleg]

This is great! Thank you!

[ks]

Thank you very much. It works Great! :)

[Yankun]

Very useful.

[Christophe]

Dear John,

Many thanks for this very useful program. I have a question if I may:

I deal with the optimization of "physical" problems, keeping in mind the manufacturing-accuracies available to me. I know, for example, that I cannot have my parameters (defining the geometry I optimize) accurately machined. To me, a parameter set at 12.000, 12.001 or even 12.01 would give pretty much the same value for the output function.
So, I would like to be able to ensure that the parameters are moved by at least a minimum "delta" in the optimization, say 1e-2 for example.
Is this something that fminsearchbnd can handle?

[Nick M.]

Hi John

This is a great work and I actually used it and worked for me. I have a question though. I used fminsearchbnd and it turned it parameters, how can I compute uncertainty for those parameters?(covariance matrix?)
Thanks!

[Brennan Smith]

Thanks! Very useful

[John D'Errico]

Nick - fminsearchbnd is a simple optimizer, a close cousin to fminsearch. All it cares about is finding an optimum value, and it has no idea that your objective is based on a least squares estimation problem of some sort. If you need confidence bounds, a simple solution is to use a linear approximation to your function at the optimum, computing the Jacobian matrix at that point. Then it is a simple problem to compute approximate confidence intervals on the parameters. You can find this procedure explained, with an example, in my Optimization Tips & Tricks, also on the File Exchange.

[Kathleen]

Hi John

I use fminsearchbnd a lot and I'd like to cite it in my work. Do you have a reference you would like used?
Thanks
Kathleen

[Kathleen]

Hi John

I use fminsearchbnd a lot and I'd like to cite it in my work. Do you have a reference you would like used?
Thanks
Kathleen

[John D'Errico]

HI Kathleen - I've been asked about citing many of my submissions before. WE came up with a few options, detailed here:

http://blogs.mathworks.com/desktop/2010/12/13/citing-file-exchange-submissions/

[Martin Richard]

John,
I've been using that function for years now. Love it. Perhaps you may want to change the function name so that it fits the file name in the new version (fminsearchbnd3 in new file).

[John D'Errico]

Sorry. I'd been playing with various alternatives sometime ago. The name on the header will be correct now when the latest update comes alive.

[Romain]

Great function, very handy.

I have noticed a small error, though. If fminsearch is not called, the function returns output.funcount, whereas it returns output.funcCount otherwise.

[Stefan]

The following test shows strange results:
----------------------------------
G0bnd 2.22e+014 L0bnd 2.707e-006

G0 2e+014 L0 3e-006

----------------------------------

function test()
options=optimset('Display','on', ...
                   'MaxFunEvals',1e4, ...
                   'MaxIter',1e4, ...
                   'TolFun', eps, ...
                   'TolX', eps, ...
                   'FunValCheck', 'on' ...
                   );
 
 w= 150e-6;
 xData = 1e-6:1e-6:w;
 G0 = 2e14;
 L0 = 3e-6;
 yData = G0*exp(-xData./L0);
 
 start_params = [G0, L0];
 min_params = [ 1, 1e-6];
 max_params = [1e30, 1];
 
 
 plot(xData,yData,'-r');
 hold('on');
 
 
 result_params=fminsearchbnd(@fitG_error_function,start_params,min_params,max_params,options,xData,yData);
 ['G0bnd ' num2str(result_params(1),4) ' L0bnd ' num2str(result_params(2),4)]
 plot(xData, result_params(1)*exp(-xData./result_params(2)),'-g');
 
 result_params=fminsearch(@fitG_error_function,start_params,options,xData,yData);
 ['G0 ' num2str(result_params(1),4) ' L0 ' num2str(result_params(2),4)]
 plot(xData, result_params(1)*exp(-xData./result_params(2)),'-b');
  
 
 function fiterror = fitG_error_function(start_params,xData,yData)
   Fitted_Curve= start_params(1) * exp(-xData./start_params(2));
   Error_Vector=Fitted_Curve - yData;
   fiterror=sum(Error_Vector.^2);
   results.fiterror=fiterror;
 end
end

[John D'Errico]

(I've fixed the bug about the outputfcn problem and re-posted it. The new version should appear sometime this morning.)

As far as Stefan's problem goes, anytime you throw problems with variables that vary by 20 to 30 powers of 10 at ANY numerical optimizer, expect serious things to go wrong. This is a no-no for literally ANY numerical tool. And setting a convergence tolerance (TolX) to eps is just as silly, especially when your parameters vary by that many orders of magnitude.

Essentially, you are asking that one variable, which can apparently vary somewhere between 1 and 1e30, must be computed to an absolute accuracy of roughly 2e-16.

A common solution is to normalize your variables, so that both are at least of similar orders of magnitude. If you were trying to solve a problem where one variable had bounds of 1e20 to 5e20, and a second variable was bounded in the interval 1e-6 to 1e-5, then normalizing the variables to both be of order 1 would make complete sense. But your variables each vary by many powers of 10!

One thing all novices need to learn about computing, is that when things vary by that many powers of 10, is to use logs! Let fminsearch vary the log10 of your variables, so they now have bound vectors that look like [0, -6] for the lower bounds, and [30, 0] for the upper bound. Now, inside your function, take the parameters and raise 10 to that power BEFORE they are used. Do the same with the output when it is returned. As far as fminsearch is concerned, your numbers are perfectly normal looking, but your objective sees the numbers in their proper scales.

You will find that any optimizer runs much more happily when you do this, as now the variables are very nicely normalized. All of the mathematics works more simply when you work in the log space. In fact, this is surely the natural way to work with variables that vary by many powers of 10. A nice consequence is the tolerances in TolX become relative tolerances on the variables, something that surely makes much more sense.

And DON'T use eps as a convergence tolerance. Fminsearch will never be able to give you even a reasonable shot at convergence in even 10000 function evals with that fine of a tolerance. So what happens is fminsearch will keep on iterating until it runs out of function evaluations. Use a meaningful, realistic tolerance. You were probably only setting that fine of a tolerance because of the ridiculous variable scaling anyway.