10#if !defined(MiniTensor_Solvers_h)
11#define MiniTensor_Solvers_h
26template<
typename T,
int N>
27using FAD = Sacado::Fad::SLFad<T, N>;
35template<
typename FunctionDerived,
typename S, Index M>
54 template<
typename T, Index N>
61 template<
typename T, Index N>
68 template<
typename T, Index N>
75 template<
typename T, Index N>
126template<
typename Constra
intDerived,
typename S, Index NC, Index NV>
137 template<
typename T, Index N>
144 template<
typename T, Index N>
179template<
typename Constra
intDerived,
typename S, Index NC, Index NV>
194template<
typename T, Index N>
218template<
typename T, Index N>
228 template<
typename STEP,
typename FN>
264 template<
typename FN>
478template<
typename T, Index N>
485 template<
typename FN>
505template<
typename T, Index N>
512 template<
typename FN>
558template<
typename T, Index N>
579template<
typename T, Index N>
606template<
typename T, Index N>
633template<
typename T, Index N>
654template<
typename T, Index N>
674template<
typename FN,
typename T, Index N>
680 is_fad = Sacado::IsADType<T>::value ==
true;
682 static_assert(is_fad ==
false,
"AD types not allowed for type T");
741template<
typename FN,
typename T, Index N>
742std::unique_ptr<StepBase<FN, T, N>>
748template<
typename FN,
typename T, Index N>
790template<
typename FN,
typename T, Index N>
798 NAME{
"Newton with Line Search"};
832template<
typename FN,
typename T, Index N>
899template<
typename FN,
typename T, Index N>
907 NAME{
"Preconditioned Conjugate Gradient"};
975template<
typename FN,
typename T, Index N>
983 NAME{
"Line Search Regularized"};
1035template<
typename FunctionDerived,
typename S, Index M>
1036template<
typename T, Index N>
1046 return 0.5 *
dot(r, r);
1052template<
typename FunctionDerived,
typename S, Index M>
1053template<
typename T, Index N>
1068 for (
Index i{0}; i < dimension; ++i) {
1069 x_ad(i) = AD(dimension, i, x(i));
1073 f_ad = f.value(x_ad);
1078 for (
Index i{0}; i < dimension; ++i) {
1088template<
typename FunctionDerived,
typename S, Index M>
1089template<
typename T, Index N>
1094 return f.gradient(x);
1100template<
typename FunctionDerived,
typename S, Index M>
1101template<
typename T, Index N>
1116 for (
Index i{0}; i < dimension; ++i) {
1117 x_ad(i) = AD(dimension, i, x(i));
1121 r_ad = f.gradient(x_ad);
1126 for (
Index i{0}; i < dimension; ++i) {
1127 for (
Index j{0}; j < dimension; ++j) {
1128 Hessian(i, j) = r_ad(i).dx(j);
1138template<
typename FunctionDerived,
typename S, Index M>
1151template<
typename FunctionDerived,
typename S, Index M>
1162template<
typename FunctionDerived,
typename S, Index M>
1174template<
typename FunctionDerived,
typename S, Index M>
1186template<
typename FunctionDerived,
typename S, Index M>
1197template<
typename Constra
intDerived,
typename S, Index NC, Index NV>
1198template<
typename T, Index N>
1210template<
typename Constra
intDerived,
typename S, Index NC, Index NV>
1211template<
typename T, Index N>
1226 for (
Index i{0}; i < num_var; ++i) {
1227 x_ad(i) = AD(num_var, i, x(i));
1231 r_ad = c.value(x_ad);
1237 Jacobian(num_constr, num_var);
1239 for (
Index i{0}; i < num_constr; ++i) {
1240 for (
Index j{0}; j < num_var; ++j) {
1241 Jacobian(i, j) = r_ad(i).dx(j);
1251template<
typename T, Index N>
1261template<
typename T, Index N>
1266 is_fad = Sacado::IsADType<T>::value ==
true;
1268 static_assert(is_fad ==
false,
"AD types not allowed for type T");
1276template<
typename T, Index N>
1277template<
typename STEP,
typename FN>
1287 resi = fn.gradient(soln);
1292 if (fn.get_failed() ==
true)
failure_message = fn.get_failure_message();
1297 step_method.initialize(fn, soln, resi);
1302 step = step_method.step(fn, soln, resi);
1306 resi = fn.gradient(soln);
1309 if (fn.get_failed() ==
true)
failure_message = fn.get_failure_message();
1312 norm_resi =
norm(resi);
1317 value = fn.value(soln);
1320 if (fn.get_failed() ==
true)
failure_message = fn.get_failure_message();
1334template<
typename T, Index N>
1340 converged_string =
converged ==
true ?
"YES" :
"NO";
1349 os <<
"Converged : " << converged_string <<
'\n';
1351 os <<
"Iters Taken : " <<
num_iter <<
'\n';
1353 os << std::scientific << std::setprecision(17);
1355 os <<
"Initial |R| : " << std::setw(24) <<
initial_norm <<
'\n';
1356 os <<
"Abs Tol : " << std::setw(24) <<
abs_tol <<
'\n';
1357 os <<
"Abs Error : " << std::setw(24) <<
abs_error <<
'\n';
1358 os <<
"Rel Tol : " << std::setw(24) <<
rel_tol <<
'\n';
1359 os <<
"Rel Error : " << std::setw(24) <<
rel_error <<
'\n';
1361 os <<
"Initial f(X) : " << std::setw(24) <<
initial_value <<
'\n';
1363 os <<
"Final f(X) : " << std::setw(24) <<
final_value <<
'\n';
1374template<
typename T, Index N>
1388 converged = converged_absolute || converged_relative;
1393 if (
converged ==
false && converged_acceptable ==
true) {
1405template<
typename T, Index N>
1449template<
typename T, Index N>
1455 if (
failed ==
true)
return false;
1459 zero_resi = ((
abs_error > 0.0) ==
false);
1461 if (zero_resi ==
true)
return false;
1468 if (exceeds_min_iter ==
false)
return true;
1475 if (exceeds_max_iter ==
true)
return false;
1481 return continue_solve;
1487template<
typename T, Index N>
1488template<
typename FN>
1502template<
typename FN,
typename T, Index N>
1513template<
typename T, Index N>
1525template<
typename T, Index N>
1541 lambda =
norm(Hessian);
1546 K = Hessian + lambda * I;
1554 std::tie(L, is_posdef) =
cholesky(K);
1556 if (is_posdef ==
false) {
1557 MT_ERROR_EXIT(
"Trust region subproblem encountered singular Hessian.");
1577 lambda += std::max(lambda_incr, 0.0);
1589template<
typename T, Index N>
1605 lambda =
norm(Hessian);
1617 K = HTH + lambda * I;
1625 std::tie(L, is_posdef) =
cholesky(K);
1627 if (is_posdef ==
false) {
1628 MT_ERROR_EXIT(
"Trust region subproblem encountered singular Hessian.");
1648 lambda += std::max(lambda_incr, 0.0);
1660template<
typename T, Index N>
1666 normg_H =
dot(gradient,
dot(Hessian, gradient));
1668 if (normg_H < 0.0) {
1669 MT_ERROR_EXIT(
"Trust region subproblem encountered singular Hessian.");
1675 normg_squared =
dot(gradient, gradient);
1678 step_minimizer = - normg_squared / normg_H * gradient;
1681 step_unconstrained = - this->
lin_solve(Hessian, gradient);
1684 normg_cubed =
norm(gradient) * normg_squared;
1693 step = step_minimizer + (
tau - 1.0) * (step_unconstrained - step_minimizer);
1704template<
typename T, Index N>
1713 normHTr_squared =
dot(HTr, HTr);
1719 normHTr_HTH =
dot(HTr,
dot(HTH, HTr));
1721 if (normHTr_HTH < 0.0) {
1722 MT_ERROR_EXIT(
"Trust region subproblem encountered singular Hessian.");
1728 normHTr_cubed =
norm(HTr) * normHTr_squared;
1731 tau = std::min(1.0, normHTr_cubed / (
region_size * normHTr_HTH));
1734 step_minimizer = - normHTr_squared / normHTr_HTH * HTr;
1737 step_unconstrained = - this->
lin_solve(HTH, HTr);
1743 step = step_minimizer + (
tau - 1.0) * (step_unconstrained - step_minimizer);
1752template<
typename T, Index N>
1753template<
typename FN>
1765 projection_direction =
dot(direction, direction);
1770 soln_next = soln +
step;
1773 gradient_next = fn.gradient(soln_next);
1776 Hessian_next = fn.hessian(soln_next);
1779 projection =
dot(gradient_next, direction);
1782 contraction =
dot(direction,
dot(Hessian_next, direction));
1785 step_length = - projection / contraction;
1787 step += step_length * direction;
1790 ls_length2 = step_length * step_length * projection_direction;
1795 if (line_search_converged ==
true)
break;
1806template<
typename T, Index N>
1807template<
typename FN>
1822 resid = fn.gradient(soln);
1825 resid_newton = fn.gradient(soln +
step);
1831 resid_norm =
dot(resid, resid);
1834 resid_newton_norm =
dot(resid_newton, resid_newton);
1837 resid_line_norm = resid_newton_norm;
1853 soln_line_search = soln + step_line_search;
1856 gradient_line_search = fn.gradient(soln_line_search);
1859 resid_line_norm_old = resid_line_norm;
1861 resid_line_norm =
dot(gradient_line_search, gradient_line_search);
1864 step = step_line_search;
1869 num = 0.25 *
alpha *
alpha * resid_line_norm_old;
1872 den = resid_line_norm + resid_line_norm_old * (0.5 *
alpha - 1.0);
1878 is_zero_den = (std::fabs(den) < den_tol);
1892template<
typename FN,
typename T, Index N>
1903template<
typename FN,
typename T, Index N>
1909 Hessian = fn.hessian(soln);
1921template<
typename FN,
typename T, Index N>
1932template<
typename FN,
typename T, Index N>
1938 Hessian = fn.hessian(soln);
1945 newton_backtrack_ls;
1948 ls_step = newton_backtrack_ls.
step(fn,
step, soln);
1956template<
typename FN,
typename T, Index N>
1969template<
typename FN,
typename T, Index N>
1975 Hessian = fn.hessian(soln);
1993 step = tr_exact.
step(Hessian, resi);
1996 soln_next = soln +
step;
1999 resi_next = fn.gradient(soln_next);
2012 reduction = (nr - nrp) / (nr - nrKp);
2019 if (reduction < 0.25) {
2026 increase_region_size = reduction > 0.75;
2028 if (increase_region_size ==
true) {
2044template<
typename FN,
typename T, Index N>
2050 Hessian = fn.hessian(soln);
2070template<
typename FN,
typename T, Index N>
2083 soln_next = soln +
step;
2086 gradient_next = fn.gradient(soln_next);
2095 Hessian = fn.hessian(soln_next);
2102 gram_schmidt_factor = (
projection_new - projection_mid) / projection_old;
2110 bad_directions = gram_schmidt_factor <= 0.0;
2113 restart_directions = rewind || bad_directions;
2115 if (restart_directions ==
true) {
2132template<
typename FN,
typename T, Index N>
2143template<
typename FN,
typename T, Index N>
2152 Hessian = fn.hessian(soln);
2161 if (bad_hessian ==
true) {
2169 step = tr_exact.
step(Hessian, gradient);
2181 ls_step = newton_ls.
step(fn,
step, soln);
2192template<
typename FN,
typename T, Index N>
2193std::unique_ptr<StepBase<FN, T, N>>
2196 using STUP = std::unique_ptr<StepBase<FN, T, N>>;
2198 switch (step_type) {
2225 return STUP(
nullptr);
#define MT_ERROR_EXIT(...)
KOKKOS_INLINE_FUNCTION Tensor< T, N > const identity()
KOKKOS_INLINE_FUNCTION Index get_dimension() const
KOKKOS_INLINE_FUNCTION Vector< typename Promote< S, T >::type, M > dot(Matrix< T, M, N > const &A, Vector< S, N > const &u)
KOKKOS_INLINE_FUNCTION Matrix< T, M, N > transpose(Matrix< T, N, M > const &A)
KOKKOS_INLINE_FUNCTION T norm_square(Vector< T, N > const &u)
T inv_cond(Tensor< T, N > const &A)
std::pair< Tensor< T, N >, bool > cholesky(Tensor< T, N > const &A)
RHS solve(Tensor< T, N > const &A, RHS const &b, PreconditionerType const pt=PreconditionerType::IDENTITY)
KOKKOS_INLINE_FUNCTION T norm(Tensor< T, N > const &A)
Vector< T, N > final_soln
Vector< T, N > gradient(FunctionDerived &f, Vector< T, N > const &x)
char const * step_method_name
PreconditionerType preconditioner_type
Tensor< T, N > hessian(FunctionDerived &f, Vector< T, N > const &x)
virtual Vector< T, N > step(FN &fn, Vector< T, N > const &x, Vector< T, N > const &r)
virtual ~NewtonWithLineSearchStep()
static constexpr char const *const NAME
Vector< T, N > step(Tensor< T, N > const &Hessian, Vector< T, N > const &gradient)
virtual Vector< T, N > step(FN &fn, Vector< T, N > const &x, Vector< T, N > const &r)
virtual char const * name()
void set_failure_message(char const *const msg=nullptr)
T value(FunctionDerived &f, Vector< T, N > const &x)
virtual char const * name()=0
Vector< T, N > lin_solve(Tensor< T, N > const &A, Vector< T, N > const &b)
Vector< T, N > step(Tensor< T, N > const &Hessian, Vector< T, N > const &gradient)
virtual void initialize(FN &fn, Vector< T, N > const &x, Vector< T, N > const &r)
static constexpr char const *const NAME
Vector< T, N > step(FN &fn, Vector< T, N > const &direction, Vector< T, N > const &soln)
Bounds(Vector< T, N > const &l, Vector< T, N > const &u)
PreconditionerType preconditioner_type
Vector< T, NC > value(ConstraintDerived &c, Vector< T, N > const &x)
virtual char const * name()
virtual Vector< T, N > step(FN &fn, Vector< T, N > const &x, Vector< T, N > const &r)
void printReport(std::ostream &os)
void set_failed(char const *const msg=nullptr)
void recordFinals(FN &fn, Vector< T, N > const &x)
Vector< T, N > precon_resi
Vector< T, N > step(Tensor< T, N > const &Hessian, Vector< T, N > const &gradient)
Vector< T, N > residual(FunctionDerived &f, Vector< T, N > const &x)
char const * failure_message
bool enforce_monotonicity
virtual char const * name()
static constexpr char const *const NAME
Vector< T, N > initial_guess
static constexpr Index NUM_VAR
Index num_stagnation_iter
static constexpr Index NUM_CONSTR
static constexpr char const *const NAME
virtual ~LineSearchRegularizedStep()
Vector< T, N > search_direction
char const * function_name
char const * warning_message
virtual ~TrustRegionStep()
static constexpr bool IS_EQUALITY
void updateDivergenceCriterion(T const fn_value)
std::unique_ptr< StepBase< FN, T, N > > stepFactory(StepType step_type)
Index restart_directions_counter
Index restart_directions_interval
Vector< T, N > final_gradient
virtual Vector< T, N > step(FN &fn, Vector< T, N > const &x, Vector< T, N > const &r)
static constexpr bool IS_EQUALITY
virtual void initialize(FN &fn, Vector< T, N > const &x, Vector< T, N > const &r)
virtual char const * name()
Index max_stagnation_iter
Vector< T, N > step(Tensor< T, N > const &Hessian, Vector< T, N > const &gradient)
Vector< T, N > lin_solve(Tensor< T, N > const &A, Vector< T, N > const &b)
Matrix< T, NC, NV > gradient(ConstraintDerived &c, Vector< T, N > const &x)
virtual Vector< T, N > step(FN &fn, Vector< T, N > const &x, Vector< T, N > const &r)
virtual void initialize(FN &fn, Vector< T, N > const &x, Vector< T, N > const &r)
void solve(STEP &step_method, FN &fn, Vector< T, N > &x)
virtual void initialize(FN &fn, Vector< T, N > const &x, Vector< T, N > const &r)
virtual void initialize(FN &fn, Vector< T, N > const &x, Vector< T, N > const &r)=0
virtual Vector< T, N > step(FN &fn, Vector< T, N > const &x, Vector< T, N > const &r)=0
Vector< T, N > step(FN &fn, Vector< T, N > const &direction, Vector< T, N > const &soln)
static constexpr Index DIMENSION
char const * failure_message
Sacado::Fad::SLFad< T, N > FAD
The Fad type to use.
static constexpr char const *const NAME
virtual void initialize(FN &fn, Vector< T, N > const &x, Vector< T, N > const &r)
Tensor< T, N > final_hessian
bool enforce_non_stagnation
virtual char const * name()
char const * get_failure_message()
virtual ~ConjugateGradientStep()
void updateConvergenceCriterion(T const abs_error)
bool continueSolve() const
KOKKOS_INLINE_FUNCTION Sacado::ScalarType< T >::type tau()
KOKKOS_INLINE_FUNCTION T max(T const &a, T const &b)
uint32_t Index
Indexing type.