Eigen-Contrib  5.0.1-dev+master
 
Loading...
Searching...
No Matches
LMonestep.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2009 Thomas Capricelli <orzel@freehackers.org>
5//
6// This code initially comes from MINPACK whose original authors are:
7// Copyright Jorge More - Argonne National Laboratory
8// Copyright Burt Garbow - Argonne National Laboratory
9// Copyright Ken Hillstrom - Argonne National Laboratory
10//
11// This Source Code Form is subject to the terms of the Minpack license
12// (a BSD-like license) described in the CopyrightMINPACK.txt file.
13// SPDX-License-Identifier: MPL-2.0 AND LicenseRef-MINPACK
14
15#ifndef EIGEN_LMONESTEP_H
16#define EIGEN_LMONESTEP_H
17
18// IWYU pragma: private
19#include "./InternalHeaderCheck.h"
20
21namespace Eigen {
22
23template <typename FunctorType>
24LevenbergMarquardtSpace::Status LevenbergMarquardt<FunctorType>::minimizeOneStep(FVectorType &x) {
25 using std::abs;
26 using std::sqrt;
27 RealScalar temp, temp1, temp2;
28 RealScalar ratio;
29 RealScalar pnorm, xnorm, fnorm1, actred, dirder, prered;
30 eigen_assert(x.size() == n); // check the caller is not cheating us
31
32 temp = 0.0;
33 // MINPACK keeps xnorm from the last accepted step; x has not moved since, nor has m_diag.
34 xnorm = m_iter > 1 ? m_diag.cwiseProduct(x).stableNorm() : RealScalar(0);
35 /* calculate the jacobian matrix. */
36 Index df_ret = m_functor.df(x, m_fjac);
37 if (df_ret < 0) return LevenbergMarquardtSpace::UserAsked;
38 if (df_ret > 0)
39 // numerical diff, we evaluated the function df_ret times
40 m_nfev += df_ret;
41 else
42 m_njev++;
43
44 /* compute the qr factorization of the jacobian. */
45 for (int j = 0; j < x.size(); ++j) m_wa2(j) = m_fjac.col(j).blueNorm();
46 QRSolver qrfac(m_fjac);
47 if (qrfac.info() != Success) {
48 m_info = NumericalIssue;
49 return LevenbergMarquardtSpace::ImproperInputParameters;
50 }
51 // Make a copy of the first factor with the associated permutation
52 m_rfactor = qrfac.matrixR();
53 m_permutation = (qrfac.colsPermutation());
54
55 /* on the first iteration and if external scaling is not used, scale according */
56 /* to the norms of the columns of the initial jacobian. */
57 if (m_iter == 1) {
58 if (!m_useExternalScaling)
59 for (Index j = 0; j < n; ++j) m_diag[j] = (m_wa2[j] == 0.) ? 1. : m_wa2[j];
60
61 /* on the first iteration, calculate the norm of the scaled x */
62 /* and initialize the step bound m_delta. */
63 xnorm = m_diag.cwiseProduct(x).stableNorm();
64 m_delta = m_factor * xnorm;
65 if (m_delta == 0.) m_delta = m_factor;
66 }
67
68 /* form (q transpose)*m_fvec and store the first n components in */
69 /* m_qtf. */
70 m_wa4 = m_fvec;
71 m_wa4 = qrfac.matrixQ().adjoint() * m_fvec;
72 m_qtf = m_wa4.head(n);
73
74 /* compute the norm of the scaled gradient. */
75 m_gnorm = 0.;
76 if (m_fnorm != 0.)
77 for (Index j = 0; j < n; ++j)
78 if (m_wa2[m_permutation.indices()[j]] != 0.)
79 m_gnorm = (std::max)(m_gnorm, abs(m_rfactor.col(j).head(j + 1).dot(m_qtf.head(j + 1) / m_fnorm) /
80 m_wa2[m_permutation.indices()[j]]));
81
82 /* test for convergence of the gradient norm. */
83 if (m_gnorm <= m_gtol) {
84 m_info = Success;
85 return LevenbergMarquardtSpace::CosinusTooSmall;
86 }
87
88 /* rescale if necessary. */
89 if (!m_useExternalScaling) m_diag = m_diag.cwiseMax(m_wa2);
90
91 do {
92 /* determine the levenberg-marquardt parameter. */
93 internal::lmpar2(qrfac, m_diag, m_qtf, m_delta, m_par, m_wa1);
94
95 /* store the direction p and x + p. calculate the norm of p. */
96 m_wa1 = -m_wa1;
97 m_wa2 = x + m_wa1;
98 pnorm = m_diag.cwiseProduct(m_wa1).stableNorm();
99
100 /* on the first iteration, adjust the initial step bound. */
101 if (m_iter == 1) m_delta = (std::min)(m_delta, pnorm);
102
103 /* evaluate the function at x + p and calculate its norm. */
104 if (m_functor(m_wa2, m_wa4) < 0) return LevenbergMarquardtSpace::UserAsked;
105 ++m_nfev;
106 fnorm1 = m_wa4.stableNorm();
107
108 /* compute the scaled actual reduction. */
109 actred = -1.;
110 if (Scalar(.1) * fnorm1 < m_fnorm) actred = 1. - numext::abs2(fnorm1 / m_fnorm);
111
112 /* compute the scaled predicted reduction and */
113 /* the scaled directional derivative. */
114 m_wa3.noalias() = m_rfactor.template triangularView<Upper>() * (m_permutation.inverse() * m_wa1);
115 temp1 = numext::abs2(m_wa3.stableNorm() / m_fnorm);
116 temp2 = numext::abs2(sqrt(m_par) * pnorm / m_fnorm);
117 prered = temp1 + temp2 / Scalar(.5);
118 dirder = -(temp1 + temp2);
119
120 /* compute the ratio of the actual to the predicted */
121 /* reduction. */
122 ratio = 0.;
123 if (prered != 0.) ratio = actred / prered;
124
125 /* update the step bound. */
126 if (ratio <= Scalar(.25)) {
127 if (actred >= 0.) temp = RealScalar(.5);
128 if (actred < 0.) temp = RealScalar(.5) * dirder / (dirder + RealScalar(.5) * actred);
129 if (RealScalar(.1) * fnorm1 >= m_fnorm || temp < RealScalar(.1)) temp = Scalar(.1);
130 /* Computing MIN */
131 m_delta = temp * (std::min)(m_delta, pnorm / RealScalar(.1));
132 m_par /= temp;
133 } else if (!(m_par != 0. && ratio < RealScalar(.75))) {
134 m_delta = pnorm / RealScalar(.5);
135 m_par = RealScalar(.5) * m_par;
136 }
137
138 /* test for successful iteration. */
139 if (ratio >= RealScalar(1e-4)) {
140 /* successful iteration. update x, m_fvec, and their norms. */
141 x = m_wa2;
142 m_wa2 = m_diag.cwiseProduct(x);
143 m_fvec = m_wa4;
144 xnorm = m_wa2.stableNorm();
145 m_fnorm = fnorm1;
146 ++m_iter;
147 }
148
149 /* tests for convergence. */
150 if (abs(actred) <= m_ftol && prered <= m_ftol && Scalar(.5) * ratio <= 1. && m_delta <= m_xtol * xnorm) {
151 m_info = Success;
152 return LevenbergMarquardtSpace::RelativeErrorAndReductionTooSmall;
153 }
154 if (abs(actred) <= m_ftol && prered <= m_ftol && Scalar(.5) * ratio <= 1.) {
155 m_info = Success;
156 return LevenbergMarquardtSpace::RelativeReductionTooSmall;
157 }
158 if (m_delta <= m_xtol * xnorm) {
159 m_info = Success;
160 return LevenbergMarquardtSpace::RelativeErrorTooSmall;
161 }
162
163 /* tests for termination and stringent tolerances. */
164 if (m_nfev >= m_maxfev) {
165 m_info = NoConvergence;
166 return LevenbergMarquardtSpace::TooManyFunctionEvaluation;
167 }
168 if (abs(actred) <= NumTraits<Scalar>::epsilon() && prered <= NumTraits<Scalar>::epsilon() &&
169 Scalar(.5) * ratio <= 1.) {
170 m_info = Success;
171 return LevenbergMarquardtSpace::FtolTooSmall;
172 }
173 if (m_delta <= NumTraits<Scalar>::epsilon() * xnorm) {
174 m_info = Success;
175 return LevenbergMarquardtSpace::XtolTooSmall;
176 }
177 if (m_gnorm <= NumTraits<Scalar>::epsilon()) {
178 m_info = Success;
179 return LevenbergMarquardtSpace::GtolTooSmall;
180 }
181
182 } while (ratio < Scalar(1e-4));
183
184 return LevenbergMarquardtSpace::Running;
185}
186
187} // end namespace Eigen
188
189#endif // EIGEN_LMONESTEP_H
NumericalIssue
Namespace containing all symbols from the Eigen library.