core/vnl/algo/vnl_powell.cxx
Go to the documentation of this file.
00001 // This is core/vnl/algo/vnl_powell.cxx
00002 #ifdef VCL_NEEDS_PRAGMA_INTERFACE
00003 #pragma implementation
00004 #endif
00005 //:
00006 // \file
00007 #include "vnl_powell.h"
00008 
00009 #include <vcl_cassert.h>
00010 #include <vnl/vnl_math.h>
00011 #undef VNL_USE_OLD_BRENT_MINIMIZER // #define VNL_USE_OLD_BRENT_MINIMIZER
00012 // This version was deprecated, and the refactoring to the new minimizer was not done correctly with respect to initialisation.
00013 #ifdef VNL_USE_OLD_BRENT_MINIMIZER
00014 #include <vnl/algo/vnl_brent.h>
00015 #else
00016 #include <vnl/algo/vnl_brent_minimizer.h>
00017 #include <vnl/algo/vnl_bracket_minimum.h>
00018 #endif
00019 #ifdef DEBUG
00020 #include <vnl/vnl_matlab_print.h>
00021 #include <vcl_iostream.h>
00022 #endif
00023 
00024 class vnl_powell_1dfun : public vnl_cost_function
00025 {
00026  public:
00027   vnl_powell* powell_;
00028   vnl_cost_function* f_;
00029   unsigned int n_;
00030   vnl_vector<double> x0_;
00031   vnl_vector<double> dx_;
00032   vnl_vector<double> tmpx_;
00033   vnl_powell_1dfun(int n, vnl_cost_function* func, vnl_powell* p)
00034    : vnl_cost_function(1), powell_(p), f_(func), n_(n), x0_(n), dx_(n), tmpx_(n) {}
00035 
00036   void init(vnl_vector<double> const& x0, vnl_vector<double> const& dx)
00037   {
00038     x0_ = x0;
00039     dx_ = dx;
00040     assert(x0.size() == n_);
00041     assert(dx.size() == n_);
00042   }
00043 
00044   double f(const vnl_vector<double>& x)
00045   {
00046     uninit(x[0], tmpx_);
00047     double e = f_->f(tmpx_);
00048     powell_->pub_report_eval(e);
00049     return e;
00050   }
00051 
00052   void uninit(double lambda, vnl_vector<double>& out)
00053   {
00054     for (unsigned int i = 0; i < n_; ++i)
00055       out[i] = x0_[i] + lambda * dx_[i];
00056   }
00057 };
00058 
00059 vnl_nonlinear_minimizer::ReturnCodes
00060 vnl_powell::minimize(vnl_vector<double>& p)
00061 {
00062  // verbose_ = true;
00063   int n = p.size();
00064   vnl_powell_1dfun f1d(n, functor_, this);
00065 
00066   vnl_matrix<double> xi(n,n, vnl_matrix_identity);
00067   vnl_vector<double> ptt(n);
00068   vnl_vector<double> xit(n);
00069   double fret = functor_->f(p);
00070   report_eval(fret);
00071   vnl_vector<double> pt = p;
00072   while (num_iterations_ < unsigned(maxfev))
00073   {
00074     double fp = fret;
00075     int ibig=0;
00076     double del=0.0;
00077 
00078     for (int i=0;i<n;i++)
00079     {
00080       // xit = ith column of xi
00081       for (int j = 0; j < n; ++j)
00082         xit[j] = xi[j][i];
00083       double fptt = fret;
00084 
00085       // 1D minimization along xi
00086       f1d.init(p, xit);
00087 #ifdef VNL_USE_OLD_BRENT_MINIMIZER
00088       vnl_brent brent(&f1d);
00089       double ax;
00090       double xx = initial_step_;
00091       double bx = 0.0;
00092       brent.bracket_minimum(&ax, &xx, &bx);
00093       fret = brent.minimize_given_bounds(bx, xx, ax, linmin_xtol_, &xx);
00094 #else
00095       vnl_brent_minimizer brent(f1d);
00096       double ax = 0.0;
00097       double xx = initial_step_;
00098       double bx;
00099       {
00100         double fa, fxx, fb;
00101         vnl_bracket_minimum(f1d,ax,xx,bx,fa,fxx,fb);
00102       }
00103       brent.set_x_tolerance (linmin_xtol_);
00104       xx=brent.minimize_given_bounds(ax,xx,bx);
00105       fret=brent.f_at_last_minimum();
00106 #endif
00107 
00108       f1d.uninit(xx, p);
00109       // Now p is minimizer along xi
00110 
00111       if (vcl_fabs(fptt-fret) > del) {
00112         del = vcl_fabs(fptt-fret);
00113         ibig = i;
00114       }
00115     }
00116 
00117     if (2.0*vcl_fabs(fp-fret) <= ftol*(vcl_fabs(fp)+vcl_fabs(fret)))
00118     {
00119 #ifdef DEBUG
00120       vnl_matlab_print(vcl_cerr, xi, "xi");
00121 #endif
00122       return CONVERGED_FTOL;
00123     }
00124 
00125     if (num_iterations_ == unsigned(maxfev))
00126       return TOO_MANY_ITERATIONS;
00127 
00128     for (int j=0;j<n;++j)
00129     {
00130       ptt[j]=2.0*p[j]-pt[j];
00131       xit[j]=p[j]-pt[j];
00132       pt[j]=p[j];
00133     }
00134 
00135     double fptt = functor_->f(ptt);
00136     report_eval(fret);
00137     if (fptt < fp)
00138     {
00139       double t=2.0*(fp-2.0*fret+fptt)*vnl_math_sqr(fp-fret-del)-del*vnl_math_sqr(fp-fptt);
00140       if (t < 0.0)
00141       {
00142         f1d.init(p, xit);
00143 #ifdef VNL_USE_OLD_BRENT_MINIMIZER
00144         vnl_brent brent(&f1d);
00145         double ax;
00146         double xx = 1.0;
00147         double bx = 0.0;
00148         brent.bracket_minimum(&ax, &xx, &bx);
00149         fret = brent.minimize_given_bounds(bx, xx, ax, linmin_xtol_, &xx);
00150 #else
00151         vnl_brent_minimizer brent(f1d);
00152         double ax = 0.0;
00153         double xx = 1.0;
00154         double bx;
00155         {
00156           double fa, fxx, fb;
00157           vnl_bracket_minimum(f1d,ax,xx,bx,fa,fxx,fb);
00158         }
00159         brent.set_x_tolerance (linmin_xtol_);
00160         xx=brent.minimize_given_bounds(ax,xx,bx);
00161         fret=brent.f_at_last_minimum();
00162 #endif
00163         f1d.uninit(xx, p);
00164 
00165         for (int j=0;j<n;j++) {
00166           xi[j][ibig]=xi[j][n-1];
00167           xi[j][n-1]=xit[j];
00168         }
00169       }
00170     }
00171     if (report_iter())
00172       return FAILED_USER_REQUEST;
00173   }
00174   return TOO_MANY_ITERATIONS;
00175 }