00001
00002 #ifdef VCL_NEEDS_PRAGMA_INTERFACE
00003 #pragma implementation
00004 #endif
00005
00006
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
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
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
00081 for (int j = 0; j < n; ++j)
00082 xit[j] = xi[j][i];
00083 double fptt = fret;
00084
00085
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
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 }