view release on metacpan or  search on metacpan

lbfgs.c  view on Meta::CPAN

	a = (v) - (u); \
	(qm) = (u) + (du) / (((fu) - (fv)) / a + (du)) / 2 * a;

/**
 * Find a minimizer of an interpolated quadratic function.
 *	@param	qm		The minimizer of the interpolated quadratic.
 *	@param	u		The value of one point, u.
 *	@param	du		The value of f'(u).
 *	@param	v		The value of another point, v.
 *	@param	dv		The value of f'(v).
 */
#define	QUARD_MINIMIZER2(qm, u, du, v, dv) \
	a = (u) - (v); \
	(qm) = (v) + (dv) / ((dv) - (du)) * a;

/**
 * Update a safeguarded trial value and interval for line search.
 *
 *	The parameter x represents the step with the least function value.
 *	The parameter t represents the current step. This function assumes
 *	that the derivative at the point of x in the direction of the step.
 *	If the bracket is set to true, the minimizer has been bracketed in
 *	an interval of uncertainty with endpoints between x and y.
 *
 *	@param	x		The pointer to the value of one endpoint.
 *	@param	fx		The pointer to the value of f(x).
 *	@param	dx		The pointer to the value of f'(x).
 *	@param	y		The pointer to the value of another endpoint.
 *	@param	fy		The pointer to the value of f(y).
 *	@param	dy		The pointer to the value of f'(y).
 *	@param	t		The pointer to the value of the trial value, t.
 *	@param	ft		The pointer to the value of f(t).
 *	@param	dt		The pointer to the value of f'(t).
 *	@param	tmin	The minimum value for the trial value, t.
 *	@param	tmax	The maximum value for the trial value, t.
 *	@param	brackt	The pointer to the predicate if the trial value is
 *					bracketed.
 *	@retval	int		Status value. Zero indicates a normal termination.
 *	
 *	@see
 *		Jorge J. More and David J. Thuente. Line search algorithm with
 *		guaranteed sufficient decrease. ACM Transactions on Mathematical
 *		Software (TOMS), Vol 20, No 3, pp. 286-307, 1994.
 */
static int update_trial_interval(
	lbfgsfloatval_t *x,
	lbfgsfloatval_t *fx,
	lbfgsfloatval_t *dx,
	lbfgsfloatval_t *y,
	lbfgsfloatval_t *fy,
	lbfgsfloatval_t *dy,
	lbfgsfloatval_t *t,
	lbfgsfloatval_t *ft,
	lbfgsfloatval_t *dt,
	const lbfgsfloatval_t tmin,
	const lbfgsfloatval_t tmax,
	int *brackt
	)
{
	int bound;
	int dsign = fsigndiff(dt, dx);
	lbfgsfloatval_t mc;	/* minimizer of an interpolated cubic. */
	lbfgsfloatval_t mq;	/* minimizer of an interpolated quadratic. */
	lbfgsfloatval_t newt;	/* new trial value. */
	USES_MINIMIZER;		/* for CUBIC_MINIMIZER and QUARD_MINIMIZER. */

	/* Check the input parameters for errors. */
	if (*brackt) {
		if (*t <= min2(*x, *y) || max2(*x, *y) <= *t) {
			/* The trival value t is out of the interval. */
			return LBFGSERR_OUTOFINTERVAL;
		}
		if (0. <= *dx * (*t - *x)) {
			/* The function must decrease from x. */
			return LBFGSERR_INCREASEGRADIENT;
		}
		if (tmax < tmin) {
			/* Incorrect tmin and tmax specified. */
			return LBFGSERR_INCORRECT_TMINMAX;
		}
	}

	/*
		Trial value selection.
	 */
	if (*fx < *ft) {
		/*
			Case 1: a higher function value.
			The minimum is brackt. If the cubic minimizer is closer
			to x than the quadratic one, the cubic one is taken, else
			the average of the minimizers is taken.
		 */
		*brackt = 1;
		bound = 1;
		CUBIC_MINIMIZER(mc, *x, *fx, *dx, *t, *ft, *dt);
		QUARD_MINIMIZER(mq, *x, *fx, *dx, *t, *ft);
		if (fabs(mc - *x) < fabs(mq - *x)) {
			newt = mc;
		} else {
			newt = mc + 0.5 * (mq - mc);
		}
	} else if (dsign) {
		/*
			Case 2: a lower function value and derivatives of
			opposite sign. The minimum is brackt. If the cubic
			minimizer is closer to x than the quadratic (secant) one,
			the cubic one is taken, else the quadratic one is taken.
		 */
		*brackt = 1;
		bound = 0;
		CUBIC_MINIMIZER(mc, *x, *fx, *dx, *t, *ft, *dt);
		QUARD_MINIMIZER2(mq, *x, *dx, *t, *dt);
		if (fabs(mc - *t) > fabs(mq - *t)) {
			newt = mc;
		} else {
			newt = mq;
		}
	} else if (fabs(*dt) < fabs(*dx)) {
		/*
			Case 3: a lower function value, derivatives of the
			same sign, and the magnitude of the derivative decreases.
			The cubic minimizer is only used if the cubic tends to
			infinity in the direction of the minimizer or if the minimum
			of the cubic is beyond t. Otherwise the cubic minimizer is
			defined to be either tmin or tmax. The quadratic (secant)
			minimizer is also computed and if the minimum is brackt
			then the the minimizer closest to x is taken, else the one
			farthest away is taken.
		 */
		bound = 1;
		CUBIC_MINIMIZER2(mc, *x, *fx, *dx, *t, *ft, *dt, tmin, tmax);
		QUARD_MINIMIZER2(mq, *x, *dx, *t, *dt);
		if (*brackt) {
			if (fabs(*t - mc) < fabs(*t - mq)) {
				newt = mc;
			} else {
				newt = mq;
			}
		} else {
			if (fabs(*t - mc) > fabs(*t - mq)) {
				newt = mc;
			} else {
				newt = mq;
			}
		}
	} else {
		/*
			Case 4: a lower function value, derivatives of the
			same sign, and the magnitude of the derivative does
			not decrease. If the minimum is not brackt, the step
			is either tmin or tmax, else the cubic minimizer is taken.
		 */
		bound = 0;
		if (*brackt) {
			CUBIC_MINIMIZER(newt, *t, *ft, *dt, *y, *fy, *dy);
		} else if (*x < *t) {
			newt = tmax;
		} else {
			newt = tmin;
		}
	}

	/*
		Update the interval of uncertainty. This update does not
		depend on the new step or the case analysis above.

		- Case a: if f(x) < f(t),
			x <- x, y <- t.
		- Case b: if f(t) <= f(x) && f'(t)*f'(x) > 0,
			x <- t, y <- y.
		- Case c: if f(t) <= f(x) && f'(t)*f'(x) < 0, 
			x <- t, y <- x.
	 */
	if (*fx < *ft) {
		/* Case a */
		*y = *t;
		*fy = *ft;
		*dy = *dt;
	} else {
		/* Case c */
		if (dsign) {
			*y = *x;
			*fy = *fx;
			*dy = *dx;
		}
		/* Cases b and c */
		*x = *t;
		*fx = *ft;
		*dx = *dt;
	}

	/* Clip the new trial value in [tmin, tmax]. */
	if (tmax < newt) newt = tmax;
	if (newt < tmin) newt = tmin;

	/*
		Redefine the new trial value if it is close to the upper bound
		of the interval.
	 */
	if (*brackt && bound) {
		mq = *x + 0.66 * (*y - *x);
		if (*x < *y) {
			if (mq < newt) newt = mq;
		} else {
			if (newt < mq) newt = mq;
		}
	}

	/* Return the new trial value. */
	*t = newt;
	return 0;
}