42 initial_stepsize = 1.0;
43 stop_epsilon_1 = 1e-4;
44 stop_epsilon_2 = 1e-8;
45 max_evaluations = 100;
95 it_assert(f !=
NULL,
"Newton_Search: Function pointer is not set");
96 it_assert(df_dx !=
NULL,
"Newton_Search: Gradient function pointer is not set");
98 it_assert(init,
"Newton_Search: Starting point is not set");
102 vec g = df_dx(x_start);
120 double Delta = initial_stepsize;
126 F_values.set_size(max_evaluations);
127 ng_values.set_size(max_evaluations);
128 Delta_values.set_size(max_evaluations);
132 ls.set_functions(f, df_dx);
134 if (ng <= stop_epsilon_1)
139 ls.set_stop_values(0.05, 0.99);
140 ls.set_max_iterations(5);
141 ls.set_max_stepsize(2);
146 while (!stop &&
more) {
159 if (nh <= stop_epsilon_2*(stop_epsilon_2 +
nx))
169 ls.set_start_point(x, F, g,
h);
170 more =
ls.search(x, F, g);
171 no_feval = no_feval +
ls.get_no_function_evaluations();
178 if (
ls.get_alpha() < 1)
180 else if (
red && (
ls.get_slope_ratio() > .7))
187 x_values(no_iter) = x;
188 F_values(no_iter) = F;
189 ng_values(no_iter) = ng;
190 Delta_values(no_iter) =
Delta;
202 if (
yh > std::sqrt(
eps) * nh *
norm(y)) {
207 w = (
a / 2) *
h -
v /
yh;
211 double thrx = stop_epsilon_2 * (stop_epsilon_2 +
norm(x));
212 if (ng <= stop_epsilon_1)
216 else if (no_feval >= max_evaluations)
231 F_values.set_size(no_iter,
true);
232 ng_values.set_size(no_iter,
true);
233 Delta_values.set_size(no_iter,
true);
256 it_assert(finished,
"Newton_Search: search is not run yet");
265 it_warning(
"Newton_Search::get_function_value, search has not been run");
275 it_warning(
"Newton_Search::get_stop_1, search has not been run");
285 it_warning(
"Newton_Search::get_stop_2, search has not been run");
295 it_warning(
"Newton_Search::get_no_iterations, search has not been run");
305 it_warning(
"Newton_Search::get_no_function_evaluations, search has not been run");
321 it_warning(
"Newton_Search::get_trace, trace is not enabled");
324 it_warning(
"Newton_Search::get_trace, search has not been run");
333 if (method == Soft) {
385 it_assert(finished,
"Line_Search: search is not run yet");
394 it_assert(f !=
NULL,
"Line_Search: Function pointer is not set");
395 it_assert(df_dx !=
NULL,
"Line_Search: Gradient function pointer is not set");
397 it_assert(init,
"Line_search: Starting point is not set");
416 double dF0 =
dot(h_start, g_end);
419 alpha_values.set_size(max_iterations);
420 F_values.set_size(max_iterations);
421 dF_values.set_size(max_iterations);
430 alpha_values.set_size(1,
true);
431 F_values.set_size(1,
true);
432 dF_values.set_size(1,
true);
440 if (method == Soft) {
452 double b = std::min(1.0, max_stepsize),
Fb = 0,
dFb = 0;
456 Fb = f(x_start + b * h_start);
457 g = df_dx(x_start + b * h_start);
463 alpha_values(no_feval) = b;
464 F_values(no_feval) =
Fb;
465 dF_values(no_feval) =
dFb;
472 if (method == Soft) {
478 x_end = x_start + b * h_start;
482 if ((
dFb < std::min(
slopethr, 0.0)) && (no_feval < max_iterations) && (b < max_stepsize)) {
484 if (method == Exact) {
489 if (2.5*b >= max_stepsize)
504 stop = (no_feval >= max_iterations)
512 alpha_values.set_size(no_feval,
true);
513 F_values.set_size(no_feval,
true);
514 dF_values.set_size(no_feval,
true);
524 if (C >= 5*n*
eps*b) {
525 double A =
a - 0.5 *
dFa * (
sqr(b -
a) / C);
526 c = std::min(std::max(
a + 0.1 * (b -
a), A), b - 0.1 * (b -
a));
531 Fc = f(x_start +
c * h_start);
532 g = df_dx(x_start +
c * h_start);
538 alpha_values(no_feval) =
c;
539 F_values(no_feval) =
Fc;
540 dF_values(no_feval) =
dFc;
543 if (method == Soft) {
549 x_end = x_start +
c * h_start;
568 x_end = x_start +
c * h_start;
582 stop = (std::abs(
dFc) <=
slopethr) | ((b -
a) < stop_beta * b);
585 stop = (stop | (no_feval >= max_iterations));
591 alpha_values.set_size(no_feval + 1,
true);
592 F_values.set_size(no_feval + 1,
true);
593 dF_values.set_size(no_feval + 1,
true);
607 vec &
xn,
double &
Fn, vec &
gn)
621 it_warning(
"Line_Search::get_alpha, search has not been run");
631 it_warning(
"Line_Search::get_slope_raio, search has not been run");
641 it_warning(
"Line_Search::get_no_function_evaluations, search has not been run");
649 it_assert(value > 0,
"Line_Search, max iterations must be > 0");
650 max_iterations = value;
655 it_assert(value > 0,
"Line_Search, max stepsize must be > 0");
656 max_stepsize = value;
663 if (method == Soft) {
684 it_warning(
"Line_Search::get_trace, trace is not enabled");
687 it_warning(
"Line_Search::get_trace, search has not been run");
int size() const
Returns the number of data elements in the array object.
void set_size(int n, bool copy=false)
Resizing an Array<T>.
void set_function(double(*function)(const vec &))
Set function pointer.
void set_method(const Line_Search_Method &method)
Set Line search method.
void set_stop_values(double rho, double beta)
Set stop criterion values.
void set_gradient(vec(*gradient)(const vec &))
Set gradient function pointer.
void set_max_stepsize(double value)
Set max stepsize.
void get_trace(vec &alphavalues, vec &Fvalues, vec &dFvalues)
bool search()
Do the line search.
void get_solution(vec &xn, double &Fn, vec &gn)
Get solution, function value and gradient at solution point.
Line_Search()
Default constructor.
int get_no_function_evaluations()
return number of function evaluations used in search
void set_max_iterations(int value)
Set max number of iterations.
double get_alpha()
return alpha at solution point, xn = x + alpha h
double get_slope_ratio()
return the slope ratio at solution poin, xn
void set_start_point(const vec &x, double F, const vec &g, const vec &h)
Set start point for search.
vec get_solution()
Get solution, function value and gradient at solution point.
double get_stop_1()
get value of stop criterion 1 at solution point
double get_stop_2()
get value of stop criterion 2 at solution point
void get_trace(Array< vec > &xvalues, vec &Fvalues, vec &ngvalues, vec &dvalues)
void set_gradient(vec(*gradient)(const vec &))
Set gradient function pointer.
bool search()
Do the line search.
void set_function(double(*function)(const vec &))
Set function pointer.
void set_start_point(const vec &x, const mat &D)
Set start point x for search and approx inverse Hessian at x.
double get_function_value()
get function value at solution point
int get_no_iterations()
get number of iterations used to reach solution
int get_no_function_evaluations()
get number of function evaluations used to reach solution
Newton_Search()
Default constructor.
#define it_warning(s)
Display a warning message.
#define it_assert(t, s)
Abort if t is not true.
T max(const Vec< T > &v)
Maximum value of vector.
vec sqr(const cvec &data)
Absolute square of elements.
ITPP_EXPORT vec zeros(int size)
A Double vector of zeros.
double norm(const cvec &v)
Calculate the 2-norm: norm(v)=sqrt(sum(abs(v).^2))
Miscellaneous statistics functions and classes - header file.
Line_Search_Method
Line Search method.
vec fminunc(double(*function)(const vec &), vec(*gradient)(const vec &), const vec &x0)
Unconstrained minimization.
template void eye(int, mat &)
Template instantiation of eye.
Num_T dot(const Vec< Num_T > &v1, const Vec< Num_T > &v2)
Inner (dot) product of two vectors v1 and v2.
const double eps
Constant eps.
bin abs(const bin &inbin)
absolute value of bin
Mat< Num_T > outer_product(const Vec< Num_T > &v1, const Vec< Num_T > &v2, bool hermitian=false)
Outer product of two vectors v1 and v2.
Newton Search optimization algorithms - header file.
Definitions of special vectors and matrices.