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);
134 if (ng <= stop_epsilon_1)
146 while (!stop && more) {
159 if (nh <= stop_epsilon_2*(stop_epsilon_2 + nx))
162 if (fst || nh > Delta) {
163 h = (Delta / nh) * h;
170 more = ls.
search(x, F, g);
187 x_values(no_iter) = x;
188 F_values(no_iter) = F;
189 ng_values(no_iter) = ng;
190 Delta_values(no_iter) = Delta;
206 a = (1 + yv / yh) / yh;
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");
317 ngvalues = ng_values;
318 dvalues = Delta_values;
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);
438 double F0 = F_start, slope0, slopethr;
440 if (method == Soft) {
441 slope0 = stop_rho * dF0;
442 slopethr = stop_beta * dF0;
446 slopethr = stop_rho *
std::abs(dF0);
450 double a = 0, Fa = F_end, dFa = dF0;
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);
461 dFb =
dot(g, h_start);
463 alpha_values(no_feval) = b;
464 F_values(no_feval) = Fb;
465 dF_values(no_feval) = dFb;
468 if (Fb < F0 + slope0*b) {
470 slope_ratio = dFb / dF0;
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)
505 || (b >= max_stepsize && dFb < slopethr)
506 || (a > 0 && dFb >= slopethr);
512 alpha_values.set_size(no_feval,
true);
513 F_values.set_size(no_feval,
true);
514 dF_values.set_size(no_feval,
true);
523 double C = Fb - Fa - (b - a) * dFa;
524 if (C >= 5*n*
eps*b) {
525 double A = a - 0.5 * dFa * (
sqr(b - a) / C);
531 Fc = f(x_start + c * h_start);
532 g = df_dx(x_start + c * h_start);
533 dFc =
dot(g, h_start);
538 alpha_values(no_feval) = c;
539 F_values(no_feval) = Fc;
540 dF_values(no_feval) = dFc;
543 if (method == Soft) {
545 if (Fc < F0 + slope0*c) {
547 slope_ratio = dFc / dF0;
549 x_end = x_start + c * h_start;
555 stop = (dFc > slopethr);
567 slope_ratio = dFc / dF0;
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;
661 method = search_method;
663 if (method == Soft) {
679 alphavalues = alpha_values;
681 dFvalues = dF_values;
684 it_warning(
"Line_Search::get_trace, trace is not enabled");
687 it_warning(
"Line_Search::get_trace, search has not been run");
692 vec
fminunc(
double(*
function)(
const vec&), vec(*gradient)(
const vec&),
const vec &x0)
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.
int get_no_iterations()
get number of iterations used to reach solution
void set_max_iterations(int value)
Set max number of iterations.
Newton Search optimization algorithms - header file.
double get_function_value()
get function value at solution point
vec fminunc(double(*function)(const vec &), vec(*gradient)(const vec &), const vec &x0)
Unconstrained minimization.
void set_gradient(vec(*gradient)(const vec &))
Set gradient function pointer.
double norm(const cvec &v)
Calculate the 2-norm: norm(v)=sqrt(sum(abs(v).^2))
void set_gradient(vec(*gradient)(const vec &))
Set gradient function pointer.
template void eye(int, mat &)
Template instantiation of eye.
void set_stop_values(double rho, double beta)
Set stop criterion values.
void set_function(double(*function)(const vec &))
Set function pointer.
double get_slope_ratio()
return the slope ratio at solution poin, xn
#define it_assert(t, s)
Abort if t is not true.
Line_Search()
Default constructor.
double get_stop_2()
get value of stop criterion 2 at solution point
void set_size(int n, bool copy=false)
Resizing an Array<T>.
Line_Search_Method
Line Search method.
ITPP_EXPORT vec zeros(int size)
A Double vector of zeros.
const double eps
Constant eps.
T min(const Vec< T > &in)
Minimum value of vector.
void get_trace(Array< vec > &xvalues, vec &Fvalues, vec &ngvalues, vec &dvalues)
void set_max_stepsize(double value)
Set max stepsize.
void set_functions(double(*function)(const vec &), vec(*gradient)(const vec &))
Set both function and gradient function pointers.
void get_trace(vec &alphavalues, vec &Fvalues, vec &dFvalues)
T max(const Vec< T > &v)
Maximum value of vector.
bool search()
Do the line search.
int get_no_function_evaluations()
get number of function evaluations used to reach solution
vec get_solution()
Get solution, function value and gradient at solution point.
void set_start_point(const vec &x, double F, const vec &g, const vec &h)
Set start point for search.
Miscellaneous statistics functions and classes - header file.
double get_alpha()
return alpha at solution point, xn = x + alpha h
void get_solution(vec &xn, double &Fn, vec &gn)
Get solution, function value and gradient at solution point.
vec sqr(const cvec &data)
Absolute square of elements.
Definitions of special vectors and matrices.
#define it_warning(s)
Display a warning message.
int get_no_function_evaluations()
return number of function evaluations used in search
double get_stop_1()
get value of stop criterion 1 at solution point
Newton_Search()
Default constructor.
vec sqrt(const vec &x)
Square root of the elements.
void set_functions(double(*function)(const vec &), vec(*gradient)(const vec &))
Set both function and gradient function pointers.
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.
bin abs(const bin &inbin)
absolute value of bin
void set_method(const Line_Search_Method &method)
Set Line search method.
Num_T dot(const Vec< Num_T > &v1, const Vec< Num_T > &v2)
Inner (dot) product of two vectors v1 and v2.
bool search()
Do the line search.