NumericalMethods::Optimization Namespace Reference

Classes
class	Function
struct	LineSearchResult
	Struct to bundle together the numerical results of a line search and a qualitative indicator of search success. More...
struct	SolverResult

Enumerations
enum class	SolverOutcome {   Invalid , Success , Incomplete , MaxIterations ,   Failure , FailureInvalidInput }
	Used when returning the solver result to indicate if the solver was successful or indicate failure reasons. More...
enum class	FunctionOutcome { InvalidInput }
enum class	LineSearchOutcome { Success , BestEffort , FailureExceededIterations }
	Used to indicated if a line search was successful or give details of failure reasons. More...

Functions
SolverResult	SolverBFGS (const Function &function, const AZStd::vector< double > &initialGuess)
bool	IsFailure (const LineSearchResult &result)
	Helper function to check whether a LineSearchResult should be considered a failure.
ScalarVariable	CubicMinimum (const double a, const double f_a, const double df_a, const double b, const double f_b, const double c, const double f_c)
ScalarVariable	QuadraticMinimum (const double a, const double f_a, const double df_a, const double b, const double f_b)
bool	ValidateStepSize (const ScalarVariable alphaNew, const double alpha0, const double alpha1, const double edgeThreshold)
LineSearchResult	SelectStepSizeFromInterval (double alpha0, double alpha1, double f_alpha0, double f_alpha1, double df_alpha0, const Function &f, const VectorVariable &x0, const VectorVariable &searchDirection, const double f_x0, const double df_x0, const double c1, const double c2)
LineSearchResult	LineSearchWolfe (const Function &f, const VectorVariable &x0, double f_x0, const VectorVariable &searchDirection)
SolverResult	MinimizeBFGS (const Function &f, const AZStd::vector< double > &xInitial)
double	FunctionValue (const Function &function, const VectorVariable &point)
	Helper function for evaluating a function at a point.
double	DirectionalDerivative (const Function &function, const VectorVariable &point, const VectorVariable &direction)
VectorVariable	Gradient (const Function &function, const VectorVariable &point)
	Vector of derivatives with respect to each of the independent variables of a function, evaluated at the specified point.

Variables
const AZ::u32	lineSearchIterations = 100
const AZ::u32	solverIterations = 500
const double	gradientTolerance = 1e-6
const double	epsilon = 1e-7
const double	WolfeConditionsC1 = 1e-4
const double	WolfeConditionsC2 = 0.9

Detailed Description

Namespace for methods for finding the values of function parameters which correspond to a (possibly local) optimum function value. For more information on optimization methods, see Numerical Optimization by Nocedal and Wright (ISBN 978-0387303031).

Enumeration Type Documentation

FunctionOutcome

enum class NumericalMethods::Optimization::FunctionOutcome

strong

Used when evaluating functions to indicate whether the evaluation was successful or indicate the failure reason.

Enumerator
InvalidInput	The number of parameters provided did not match the expected dimension.

LineSearchOutcome

enum class NumericalMethods::Optimization::LineSearchOutcome

strong

Used to indicated if a line search was successful or give details of failure reasons.

Enumerator
Success	A result which completely satisfies the line search requirements.
BestEffort	A result which is not optimal but should still be usable.
FailureExceededIterations	Failed because the iteration limit was reached and the value is not usable.

SolverOutcome

enum class NumericalMethods::Optimization::SolverOutcome

strong

Used when returning the solver result to indicate if the solver was successful or indicate failure reasons.

Enumerator
Invalid	Default value to which fields of this type should be initialized.
Success	The solver successfully achieved the stopping conditions.
Incomplete	The solver stalled, but the result may still be useful.
MaxIterations	Reached the iteration limit.
Failure	The solver failed for unspecified reasons.
FailureInvalidInput	The solver failed because the initial guess provided was not valid.

Function Documentation

CubicMinimum()

ScalarVariable NumericalMethods::Optimization::CubicMinimum	(	const double	a,
		const double	f_a,
		const double	df_a,
		const double	b,
		const double	f_b,
		const double	c,
		const double	f_c
	)

Finds the value of x which minimizes the cubic polynomial which interpolates the provided points. Finds the cubic polynomial P(x) which satisfies P(a) = f_a P'(a) = df_a P(b) = f_b P(c) = f_c and returns the value of x which minimizes P.

DirectionalDerivative()

double NumericalMethods::Optimization::DirectionalDerivative	(	const Function &	function,
		const VectorVariable &	point,
		const VectorVariable &	direction
	)

The 1-dimensional rate of change of a function with respect to changing the independent variables along the specified direction. Note that some textbooks / authors define the directional derivative with respect to a normalized direction, but that convention is not used here.

LineSearchWolfe()

LineSearchResult NumericalMethods::Optimization::LineSearchWolfe	(	const Function &	f,
		const VectorVariable &	x0,
		double	f_x0,
		const VectorVariable &	searchDirection
	)

Searches for a step size satisfying the Wolfe conditions for solution improvement. Given a search direction, attempts to find a step size in that direction which satisfies the Wolfe conditions ( conditions for solution improvement which have nice properties for algorithms which rely on the line search). The first wolfe condition requires that the function value at the new point is sufficiently improved relative to the previous iteration. The second condition requires that the directional derivative at the new point is sufficient to indicate that significantly more progress could not have been made by choosing a larger step. The search proceeds in two phases - first an interval containing a suitable point is found, then a point within that interval is narrowed down using the SelectStepSizeFromInterval function.

MinimizeBFGS()

SolverResult NumericalMethods::Optimization::MinimizeBFGS	(	const Function &	f,
		const AZStd::vector< double > &	xInitial
	)

Minimizes the supplied function using the Broyden-Fletcher-Goldfarb-Shanno algorithm (see Nocedal and Wright).

Parameters

f	Function to be minimized.
xInitial	Initial guess for the independent variable.

Returns

Value of the independent variable which minimizes f.

QuadraticMinimum()

ScalarVariable NumericalMethods::Optimization::QuadraticMinimum	(	const double	a,
		const double	f_a,
		const double	df_a,
		const double	b,
		const double	f_b
	)

Finds the value of x which minimizes the quadratic which interpolates the provided points. Finds the quadratic Q(x) which satisfies Q(a) = f_a Q'(a) = df_a Q(b) = f_b and returns the value of value which minimizes Q.

SelectStepSizeFromInterval()

LineSearchResult NumericalMethods::Optimization::SelectStepSizeFromInterval	(	double	alpha0,
		double	alpha1,
		double	f_alpha0,
		double	f_alpha1,
		double	df_alpha0,
		const Function &	f,
		const VectorVariable &	x0,
		const VectorVariable &	searchDirection,
		const double	f_x0,
		const double	df_x0,
		const double	c1,
		const double	c2
	)

Used in LineSearchWolfe to narrow down a step size once a bracketing interval has been found. This corresponds to the zoom function in Nocedal and Wright.

SolverBFGS()

SolverResult NumericalMethods::Optimization::SolverBFGS	(	const Function &	function,
		const AZStd::vector< double > &	initialGuess
	)

Minimizes the given mathematical function, using the initial guess as a starting point.

Parameters

function	The function to minimize.
initialGuess	The input vector whose size must be equal to the dimension of the function.

Returns

An instance of SolverResult.

ValidateStepSize()

bool NumericalMethods::Optimization::ValidateStepSize	(	const ScalarVariable	alphaNew,
		const double	alpha0,
		const double	alpha1,
		const double	edgeThreshold
	)

Checks that the result of an interpolation is satisfactory. Checks that the result of an interpolation is valid, inside the expected interval, and sufficiently far from interval boundaries.

Parameters

alphaNew	The new step size to be checked.
alpha0	One boundary of the current step size interval.
alpha1	The other boundary of the current interval.
edgeThreshold	Defines how close to the edges of current interval the new step size is allowed to be.