77 #define min2(a, b) ((a) <= (b) ? (a) : (b))
78 #define max2(a, b) ((a) >= (b) ? (a) : (b))
79 #define max3(a, b, c) max2(max2((a), (b)), (c));
101 1e-20, 1e20, 1e-4, 0.9, 0.9, 1.0e-16,
204 memcpy(param, &
_defparam,
sizeof(*param));
219 int32_t i, j, k, ls, end, bound;
224 const int32_t m = param.
m;
227 float64_t *g = NULL, *gp = NULL, *pg = NULL;
228 float64_t *d = NULL, *w = NULL, *pf = NULL;
251 if (param.
past < 0) {
254 if (param.
delta < 0.) {
263 if (param.
ftol < 0.) {
272 if (param.
gtol < 0.) {
275 if (param.
xtol < 0.) {
323 if (xp == NULL || g == NULL || gp == NULL || d == NULL || w == NULL) {
345 for (i = 0;i < m;++i) {
351 if (it->s == NULL || it->y == NULL) {
358 if (0 < param.
past) {
387 std::copy(pg,pg+n,d);
400 if (xnorm < 1.0) xnorm = 1.0;
401 if (gnorm / xnorm <= param.
epsilon) {
420 ls = linesearch(n, x, &fx, g, d, &step, xp, gp, w, &cd, ¶m);
422 ls = linesearch(n, x, &fx, g, d, &step, xp, pg, w, &cd, ¶m);
430 std::copy(xp,xp+n,x);
431 std::copy(gp,gp+n,g);
456 if (xnorm < 1.0) xnorm = 1.0;
457 if (gnorm / xnorm <= param.
epsilon) {
470 if (param.
past <= k) {
472 rate = (pf[k % param.
past] - fx) / fx;
475 if (rate < param.
delta) {
482 pf[k % param.
past] = fx;
518 bound = (m <= k) ? m : k;
525 std::copy(g, g+n, d);
528 std::copy(pg, pg+n, d);
533 for (i = 0;i < bound;++i) {
545 for (i = 0;i < bound;++i) {
560 if (d[i] * pg[i] >= 0) {
574 if (ptr_fx != NULL) {
582 for (i = 0;i < m;++i) {
634 dgtest = param->
ftol * dginit;
637 std::copy(xp,xp+n,x);
648 if (*f > finit + *stp * dgtest) {
659 if (dg < param->wolfe * dginit) {
668 if(dg > -param->
wolfe * dginit) {
677 if (*stp < param->min_step) {
710 int32_t i, count = 0;
720 for (i = 0;i < n;++i) {
721 wp[i] = (xp[i] == 0.) ? -gp[i] : xp[i];
726 std::copy(xp,xp+n,x);
744 for (i = 0;i < n;++i) {
745 dgtest += (x[i] - xp[i]) * gp[i];
748 if (*f <= finit + param->ftol * dgtest) {
753 if (*stp < param->min_step) {
787 int32_t brackt, stage1, uinfo = 0;
813 dgtest = param->
ftol * dginit;
815 prev_width = 2.0 * width;
836 stmin =
min2(stx, sty);
837 stmax =
max2(stx, sty);
840 stmax = *stp + 4.0 * (*stp - stx);
844 if (*stp < param->min_step) *stp = param->
min_step;
851 if ((brackt && ((*stp <= stmin || stmax <= *stp) || param->
max_linesearch <= count + 1 || uinfo != 0)) || (brackt && (stmax - stmin <= param->
xtol * stmax))) {
859 std::copy(xp,xp+n,x);
868 ftest1 = finit + *stp * dgtest;
872 if (brackt && ((*stp <= stmin || stmax <= *stp) || uinfo != 0)) {
876 if (*stp == param->
max_step && *f <= ftest1 && dg <= dgtest) {
880 if (*stp == param->
min_step && (ftest1 < *f || dgtest <= dg)) {
884 if (brackt && (stmax - stmin) <= param->
xtol * stmax) {
892 if (*f <= ftest1 && fabs(dg) <= param->
gtol * (-dginit)) {
901 if (stage1 && *f <= ftest1 &&
min2(param->
ftol, param->
gtol) * dginit <= dg) {
912 if (stage1 && ftest1 < *f && *f <= fx) {
914 fm = *f - *stp * dgtest;
915 fxm = fx - stx * dgtest;
916 fym = fy - sty * dgtest;
929 stmin, stmax, &brackt
933 fx = fxm + stx * dgtest;
934 fy = fym + sty * dgtest;
946 stmin, stmax, &brackt
954 if (0.66 * prev_width <= fabs(sty - stx)) {
955 *stp = stx + 0.5 * (sty - stx);
958 width = fabs(sty - stx);
970 #define USES_MINIMIZER \
971 float64_t a, d, gamma, theta, p, q, r, s;
983 #define CUBIC_MINIMIZER(cm, u, fu, du, v, fv, dv) \
985 theta = ((fu) - (fv)) * 3 / d + (du) + (dv); \
992 gamma = s * sqrt(a * a - ((du) / s) * ((dv) / s)); \
993 if ((v) < (u)) gamma = -gamma; \
994 p = gamma - (du) + theta; \
995 q = gamma - (du) + gamma + (dv); \
1011 #define CUBIC_MINIMIZER2(cm, u, fu, du, v, fv, dv, xmin, xmax) \
1013 theta = ((fu) - (fv)) * 3 / d + (du) + (dv); \
1017 s = max3(p, q, r); \
1020 gamma = s * sqrt(max2(0, a * a - ((du) / s) * ((dv) / s))); \
1021 if ((u) < (v)) gamma = -gamma; \
1022 p = gamma - (dv) + theta; \
1023 q = gamma - (dv) + gamma + (du); \
1025 if (r < 0. && gamma != 0.) { \
1026 (cm) = (v) - r * d; \
1027 } else if (a < 0) { \
1042 #define QUARD_MINIMIZER(qm, u, fu, du, v, fv) \
1044 (qm) = (u) + (du) / (((fu) - (fv)) / a + (du)) / 2 * a;
1054 #define QUARD_MINIMIZER2(qm, u, du, v, dv) \
1056 (qm) = (v) + (dv) / ((dv) - (du)) * a;
1058 #define fsigndiff(x, y) (*(x) * (*(y) / fabs(*(y))) < 0.)
1113 if (*t <=
min2(*x, *y) ||
max2(*x, *y) <= *t) {
1117 if (0. <= *dx * (*t - *x)) {
1141 if (fabs(mc - *x) < fabs(mq - *x)) {
1144 newt = mc + 0.5 * (mq - mc);
1157 if (fabs(mc - *t) > fabs(mq - *t)) {
1162 }
else if (fabs(*dt) < fabs(*dx)) {
1178 if (fabs(*t - mc) < fabs(*t - mq)) {
1184 if (fabs(*t - mc) > fabs(*t - mq)) {
1200 }
else if (*x < *t) {
1237 if (tmax < newt) newt = tmax;
1238 if (newt < tmin) newt = tmin;
1244 if (*brackt && bound) {
1245 mq = *x + 0.66 * (*y - *x);
1247 if (mq < newt) newt = mq;
1249 if (newt < mq) newt = mq;
1264 const int32_t start,
1271 for (i = start;i < n;++i) {
1284 const int32_t start,
1291 for (i = 0;i < start;++i) {
1296 for (i = start;i < end;++i) {
1300 }
else if (0. < x[i]) {
1307 }
else if (c < g[i]) {
1316 for (i = end;i < n;++i) {
1324 const int32_t start,
1330 for (i = start;i < end;++i) {
1331 if (d[i] * sign[i] <= 0) {
static float64_t dot(const bool *v1, const bool *v2, int32_t n)
compute dot product between v1 and v2 (blas optimized)
double norm(double *v, double p, int n)
int32_t lbfgs(int32_t n, float64_t *x, float64_t *ptr_fx, lbfgs_evaluate_t proc_evaluate, lbfgs_progress_t proc_progress, void *instance, lbfgs_parameter_t *_param, lbfgs_adjust_step_t proc_adjust_step)
static int32_t line_search_morethuente(int32_t n, float64_t *x, float64_t *f, float64_t *g, float64_t *s, float64_t *stp, const float64_t *xp, const float64_t *gp, float64_t *wa, callback_data_t *cd, const lbfgs_parameter_t *param)
static int32_t line_search_backtracking_owlqn(int32_t n, float64_t *x, float64_t *f, float64_t *g, float64_t *s, float64_t *stp, const float64_t *xp, const float64_t *gp, float64_t *wp, callback_data_t *cd, const lbfgs_parameter_t *param)
static void owlqn_project(float64_t *d, const float64_t *sign, const int32_t start, const int32_t end)
#define QUARD_MINIMIZER(qm, u, fu, du, v, fv)
static const lbfgs_parameter_t _defparam
#define CUBIC_MINIMIZER2(cm, u, fu, du, v, fv, dv, xmin, xmax)
lbfgs_progress_t proc_progress
#define QUARD_MINIMIZER2(qm, u, du, v, dv)
static int32_t line_search_backtracking(int32_t n, float64_t *x, float64_t *f, float64_t *g, float64_t *s, float64_t *stp, const float64_t *xp, const float64_t *gp, float64_t *wa, callback_data_t *cd, const lbfgs_parameter_t *param)
lbfgs_adjust_step_t proc_adjust_step
void add(const SGVector< T > x)
static int32_t update_trial_interval(float64_t *x, float64_t *fx, float64_t *dx, float64_t *y, float64_t *fy, float64_t *dy, float64_t *t, float64_t *ft, float64_t *dt, const float64_t tmin, const float64_t tmax, int32_t *brackt)
static void owlqn_pseudo_gradient(float64_t *pg, const float64_t *x, const float64_t *g, const int32_t n, const float64_t c, const int32_t start, const int32_t end)
static float64_t owlqn_x1norm(const float64_t *x, const int32_t start, const int32_t n)
static void scale_vector(T alpha, T *vec, int32_t len)
scale vector inplace
#define CUBIC_MINIMIZER(cm, u, fu, du, v, fv, dv)
float64_t(* lbfgs_adjust_step_t)(void *instance, const float64_t *x, const float64_t *d, const int n, const float64_t step)
lbfgs_evaluate_t proc_evaluate
float64_t(* lbfgs_evaluate_t)(void *instance, const float64_t *x, float64_t *g, const int n, const float64_t step)
int32_t(* line_search_proc)(int32_t n, float64_t *x, float64_t *f, float64_t *g, float64_t *s, float64_t *stp, const float64_t *xp, const float64_t *gp, float64_t *wa, callback_data_t *cd, const lbfgs_parameter_t *param)
int(* lbfgs_progress_t)(void *instance, const float64_t *x, const float64_t *g, const float64_t fx, const float64_t xnorm, const float64_t gnorm, const float64_t step, int n, int k, int ls)
static T twonorm(const T *x, int32_t len)
|| x ||_2
void lbfgs_parameter_init(lbfgs_parameter_t *param)