mod_trust_region Module Reference

Data Types
interface	dasum
interface	daxpy
interface	ddot
interface	dnrm2
interface	dpotrf
interface	dscal
interface	dtrmv
interface	dtrsv

Functions/Subroutines
pure character(len=:) function, allocatable, public	trust_region_get_info (info)
	Transform info value in human readable message.
pure subroutine, public	solve_trust_region (hessian, gradient, delta, relative_tolerance, absolute_tolerance, max_iter, lagrange_multiplier, quadratic_form_value, solution, iter, info)
	Solve the trust-region problem.
pure subroutine	estimate_smallest_singular_value (matrix, smallest_singular_value, singular_vector)
	Estimate the smallest singular value and the associate singular vector of a upper triangular matrix.

Function/Subroutine Documentation

estimate_smallest_singular_value()

pure subroutine mod_trust_region::estimate_smallest_singular_value ( double precision, dimension(:,:), intent(in) matrix, double precision, intent(out) smallest_singular_value, double precision, dimension(:), intent(out) singular_vector )

private

Estimate the smallest singular value and the associate singular vector of a upper triangular matrix.

Given an n by n upper triangular matrix R, this subroutine estimates the smallest singular value and the associated singular vector of R.

In the algorithm a vector e is selected so that the solution y to the system R'*y = e is large. The choice of sign for the components of e cause maximal local growth in the components of y as the forward substitution proceeds. The vector singular_vector denoted by z is the solution of the system R*z = y, and the estimate smallest_singular_value is norm(y)/norm(z) in the Euclidean norm.

Parameters

[in]	matrix	Upper triangular matrix.
[out]	smallest_singular_value	Estimate of the smallest singular value.
[out]	singular_vector	Singular vector associated with the smallest singular value.

Reference:

• Original source-code: MINPACK-2 Project. October 1993.

solve_trust_region()

pure subroutine, public mod_trust_region::solve_trust_region	(	double precision, dimension(:,:), intent(inout)	hessian,
		double precision, dimension(:), intent(in)	gradient,
		double precision, intent(in)	delta,
		double precision, intent(in)	relative_tolerance,
		double precision, intent(in)	absolute_tolerance,
		integer, intent(in)	max_iter,
		double precision, intent(inout)	lagrange_multiplier,
		double precision, intent(out)	quadratic_form_value,
		double precision, dimension(:), intent(out)	solution,
		integer, intent(out)	iter,
		integer, intent(out)	info )

Solve the trust-region problem.

Trust-region problem:

  !!   min {ψ(x) | |x| ≤ Δ}
  !! 

where ψ(x) = g⋅x + 1/2 Hx⋅x is a quadratic form where g denotes the gradient, H denotes the hessian matrix or its approximation, and Δ denotes the radius delta of the trust region.

The solution of this problem if of the form

  !!   (H + λI)x = -g
  !! 

where I denotes the identity matrix, λ a lagrange_multiplier, and x the solution.

The present code is the translation in Fortran 2008 of the DGQT routine of the MINPACK-2 Project.

Stop criterions:

• Relative tolerance:

    !!    ψ(x) ≤ ((1 - relative_tolerance)**2)*ψ(solution)
    !! 

• Absolute tolerance:

    !!    |x| ≤ (1 + relative_tolerance)*delta
    !!    max(-ψ(x), -ψ(solution) ≤ absolute_tolerance
    !! 

Values of info:

• info = 1: the quadratic form ψ(x) has the relative accuracy specified by relative_tolerance.
• info = 2: the quadratic form ψ(x) has the absolute accuracy specified by absolute_tolerance.
• info = 3: rounding errors prevent further progress.
• info = 4: failure to converge after max_iter iterations.

References:

• Moré, Jorge J., and Danny C. Sorensen. "Computing a trust region step." SIAM Journal on scientific and statistical computing 4.3 (1983): 553-572.
• MINPACK-2 sources: https://ftp.mcs.anl.gov/pub/MINPACK-2/gqt/dgqt.f

Parameters

[in,out]	hessian	Symmetric Hessian matrix.
[in]	gradient	Gradient vector.
[in]	delta	Radius of the trust region.
[in]	relative_tolerance	Relative tolerance.
[in]	absolute_tolerance	Absolute tolerance.
[in]	max_iter	Maximum number of iterations.
[in,out]	lagrange_multiplier	Lagrange multiplier.
[out]	quadratic_form_value	Final value of the quadratic form ψ.
[out]	solution	Final value of that minimize the quadratic form ψ under constraint.
[out]	info	exit value.

trust_region_get_info()

pure character(len=:) function, allocatable, public mod_trust_region::trust_region_get_info

(

integer, intent(in)

info

)

Transform info value in human readable message.

Parameters

[in]

info

info value returned by the trust-region algorithm.

Returns

human readable message