Loading...
Searching...
No Matches
ConjugateGradients.cpp
Go to the documentation of this file.
1/*
2** This file is part of eOn.
3**
4** SPDX-License-Identifier: BSD-3-Clause
5**
6** Copyright (c) 2010--present, eOn Development Team
7** All rights reserved.
8**
9** Repo:
10** https://github.com/TheochemUI/eOn
11*/
13#include "eon/ExactReduction.h"
14#include "eon/SafeMath.h"
15
16#include <cmath>
17
18namespace eonc {
19
20Eigen::VectorXd ConjugateGradients::getStep() {
21 double a = std::abs(eonc::exact::dot(m_force, m_forceOld));
23 double gamma = 0.0;
24 if (a < 0.5 * b) {
25 // Polak-Ribiere way to determine how much to mix in of old direction
28 } else {
29 gamma = 0;
30 }
36
37 // Only if value for max nr of iteration before reset
38 if (m_optConfig.opts.cg.max_iter_before_reset > 0 &&
39 m_optConfig.opts.cg.max_iter_before_reset <= m_cg_i) {
40 m_cg_i = 0;
41 m_forceOld.setZero();
42 m_directionOld.setZero();
43 }
44 m_cg_i += 1;
45
46 return m_direction;
47}
48
50 // getStep() already mixed the rejected direction into the history.
51 m_directionOld.setZero();
52 m_forceOld.setZero();
53 m_cg_i = 0;
54}
55
56int ConjugateGradients::step(double a_maxMove) {
57 bool converged;
58 if (m_optConfig.opts.cg.line_search) {
59 converged = line_search(a_maxMove);
60 } else {
61 converged = single_step(a_maxMove);
62 }
63 if (converged)
64 return 1;
65 return 0;
66}
67
68int ConjugateGradients::line_search(double a_maxMove) {
69 Eigen::VectorXd pos;
70 Eigen::VectorXd posStep;
71 Eigen::VectorXd forceBeforeStep;
72 double stepSize;
73 double projectedForce;
74 double projectedForceBeforeStep;
75 double curvature;
76
77 forceBeforeStep = -m_objf->getGradient();
78 m_force = forceBeforeStep;
79 getStep();
80 pos = m_objf->getPositions();
81 projectedForceBeforeStep = eonc::exact::dot(m_force, m_directionNorm);
82
83 // move system an infinitesimal step to determine the optimal step size along
84 // the search line
85 posStep = pos + m_directionNorm * m_optConfig.finiteDifference;
86 m_objf->setPositions(posStep);
87 m_force = -m_objf->getGradient(true);
88 projectedForce = eonc::exact::dot(m_force, m_directionNorm);
89 stepSize = m_optConfig.finiteDifference;
90
91 int line_i = 0;
92 do {
93 // Determine curvature from last step (Secant method)
94 curvature = std::abs(eonc::safemath::safe_div(
95 projectedForceBeforeStep - projectedForce, stepSize, 0.0));
96 // A negative max move is a length (bowl breakout), not a backward step.
97 const double maxMove = std::fabs(a_maxMove);
98 stepSize = eonc::safemath::safe_div(projectedForce, curvature, maxMove);
99
100 if (maxMove < std::fabs(stepSize)) {
101 // first part get the sign of stepSize
102 stepSize = ((stepSize > 0) - (stepSize < 0)) * maxMove;
103 }
104
105 forceBeforeStep = m_force;
106 projectedForceBeforeStep = projectedForce;
107
108 pos += stepSize * m_directionNorm;
109 m_objf->setPositions(pos);
110 m_force = -m_objf->getGradient();
111 projectedForce = eonc::exact::dot(m_force, m_directionNorm);
112
113 line_i += 1;
114
115 // Line search considered converged based in the ratio between the projected
116 // force and the norm of the true force
117 } while (m_optConfig.opts.cg.line_converged <
118 std::abs(projectedForce) /
119 (std::sqrt(eonc::exact::dot(m_force, m_force) +
120 m_optConfig.opts.cg.line_converged)) &&
121 line_i < m_optConfig.opts.cg.line_search_max_iter);
122 if (m_objf->isConverged())
123 return 1;
124 return 0;
125}
126
127int ConjugateGradients::single_step(double a_maxMove) {
128 Eigen::VectorXd pos;
129 Eigen::VectorXd posStep;
130 Eigen::VectorXd forceAfterStep;
131
132 m_force = -m_objf->getGradient();
133 pos = m_objf->getPositions();
134 const Eigen::VectorXd posBefore = pos;
135 getStep();
136
137 if (!m_objf->reuseDisplacementCurvature()) {
138 // Minimization and dimer translation. One finite-difference probe
139 // along the search line, then a Newton length, every iteration.
140 posStep = pos + m_directionNorm * m_optConfig.finiteDifference;
141 m_objf->setPositions(posStep);
142 forceAfterStep = -m_objf->getGradient(true);
143
144 double projectedForce1 = eonc::exact::dot(m_force, m_directionNorm);
145 double projectedForce2 = eonc::exact::dot(forceAfterStep, m_directionNorm);
146 double curvature = eonc::safemath::safe_div(
147 projectedForce1 - projectedForce2, m_optConfig.finiteDifference, 0.0);
148
149 double stepSize = a_maxMove;
150 if (curvature > 0.0) {
151 stepSize =
152 eonc::safemath::safe_div(projectedForce1, curvature, a_maxMove);
153 }
154 if (m_optConfig.bowlBreakout && a_maxMove < 0.0) {
155 stepSize = -a_maxMove;
156 a_maxMove = -a_maxMove;
157 }
158 if (!m_optConfig.opts.cg.no_overshooting) {
159 if (m_optConfig.bowlBreakout) {
161 a_maxMove);
162 } else {
164 a_maxMove);
165 }
166 m_objf->setPositions(pos);
167 } else {
168 double passedMinimum = -1.;
169 double forceChange = 0.;
170 while (passedMinimum < 0.0 &&
171 0.1 * std::abs(projectedForce1) < std::abs(projectedForce2)) {
173 stepSize * m_directionNorm, a_maxMove);
174 m_objf->setPositions(posStep);
175 forceAfterStep = -m_objf->getGradient(true);
176 projectedForce2 = eonc::exact::dot(forceAfterStep, m_directionNorm);
177 passedMinimum = projectedForce1 * projectedForce2;
178 if (passedMinimum < 0.0 &&
179 0.1 * std::abs(projectedForce1) < std::abs(projectedForce2)) {
180 forceChange = (projectedForce1 - projectedForce2);
181 stepSize =
182 eonc::safemath::safe_div(projectedForce1, forceChange, 0.0) *
183 stepSize;
184 QUILL_LOG_DEBUG(m_log, "Force changed {}, step size adjusted to {}",
185 forceChange, stepSize);
186 }
187 }
188 }
189 if (m_optConfig.opts.cg.knock_out_max_move) {
190 if (stepSize >= a_maxMove) {
191 m_directionOld.setZero();
192 m_forceOld.setZero();
193 QUILL_LOG_DEBUG(m_log, "Resetting the old search direction");
194 }
195 }
196 return m_objf->isConverged() ? 1 : 0;
197 }
198
199 const double maxMove = std::fabs(a_maxMove);
200 double projectedForce1 = eonc::exact::dot(m_force, m_directionNorm);
201 if (projectedForce1 <= 0.0 && eonc::exact::squaredNorm(m_force) > 0.0) {
202 // A restarted mix can point uphill. Step along the force.
204 projectedForce1 = eonc::exact::dot(m_force, m_directionNorm);
205 }
206 double stepSize = maxMove;
207
208 if (m_optConfig.opts.cg.no_overshooting) {
209 // The overshoot guard still probes. The stock band path does not.
210 posStep = pos + m_directionNorm * m_optConfig.finiteDifference;
211 m_objf->setPositions(posStep);
212 forceAfterStep = -m_objf->getGradient(true);
213 double projectedForce2 = eonc::exact::dot(forceAfterStep, m_directionNorm);
214 double curvature = eonc::safemath::safe_div(
215 projectedForce1 - projectedForce2, m_optConfig.finiteDifference, 0.0);
216 if (curvature > 0.0) {
217 stepSize =
218 eonc::safemath::safe_div(projectedForce1, curvature, a_maxMove);
219 }
220 if (m_optConfig.bowlBreakout && a_maxMove < 0.0) {
221 stepSize = -a_maxMove;
222 a_maxMove = -a_maxMove;
223 }
224 double passedMinimum = -1.;
225 double forceChange = 0.;
226 while (passedMinimum < 0.0 &&
227 0.1 * std::abs(projectedForce1) < std::abs(projectedForce2)) {
229 stepSize * m_directionNorm, a_maxMove);
230 m_objf->setPositions(posStep);
231 forceAfterStep = -m_objf->getGradient(true);
232 projectedForce2 = eonc::exact::dot(forceAfterStep, m_directionNorm);
233
234 passedMinimum = projectedForce1 * projectedForce2;
235 if (passedMinimum < 0.0 &&
236 0.1 * std::abs(projectedForce1) < std::abs(projectedForce2)) {
237 forceChange = (projectedForce1 - projectedForce2);
238 stepSize = eonc::safemath::safe_div(projectedForce1, forceChange, 0.0) *
239 stepSize;
240 QUILL_LOG_DEBUG(m_log, "Force changed {}, step size adjusted to {}",
241 forceChange, stepSize);
242 }
243 }
244 } else {
245 // First step: one finite-difference probe, then a Newton length.
246 // Later steps: secant curvature of the previous real displacement.
247 // A restart only drops the old search direction. The trust region
248 // shrinks when that step raised the force, so a bad length is not
249 // repeated at the max-move cap.
250 double trust = maxMove;
251 const double fd = m_optConfig.finiteDifference;
252 if (!m_haveSecant && fd > 0.0) {
253 posStep = pos + m_directionNorm * fd;
254 m_objf->setPositions(posStep);
255 forceAfterStep = -m_objf->getGradient(true);
256 const double projectedForce2 =
257 eonc::exact::dot(forceAfterStep, m_directionNorm);
258 const double curvature = (projectedForce1 - projectedForce2) / fd;
259 m_objf->setPositions(pos);
260 if (curvature > 0.0 && projectedForce1 > 0.0) {
261 stepSize = projectedForce1 / curvature;
262 } else {
263 stepSize = 0.25 * maxMove;
264 }
265 } else if (m_haveSecant) {
266 const Eigen::VectorXd disp = m_objf->difference(pos, m_secantPos);
267 const double ds = eonc::exact::dot(disp, m_secantDir);
268 if (std::abs(ds) > 1e-14) {
269 const double projNow = eonc::exact::dot(m_force, m_secantDir);
270 const double curvature = (m_secantProj - projNow) / ds;
271 if (curvature > 0.0 && projectedForce1 > 0.0) {
272 stepSize = projectedForce1 / curvature;
273 } else {
274 stepSize = 0.25 * maxMove;
275 }
276 }
277 if (m_secantForce.size() == m_force.size() && m_force.size() >= 6 &&
278 m_force.size() % 3 == 0) {
279 const long nAtoms = m_force.size() / 3;
280 if (static_cast<long>(m_atomCurv.size()) != nAtoms) {
281 m_atomCurv.assign(static_cast<size_t>(nAtoms), 0.0);
282 }
283 for (long a = 0; a < nAtoms; ++a) {
284 const auto dsAtom = disp.segment(3 * a, 3);
285 const double dsn = dsAtom.squaredNorm();
286 if (dsn < 1e-12) {
287 continue;
288 }
289 const auto df =
290 m_secantForce.segment(3 * a, 3) - m_force.segment(3 * a, 3);
291 const double c = df.dot(dsAtom) / dsn;
292 if (c > 0.05) {
293 m_atomCurv[static_cast<size_t>(a)] = c;
294 }
295 }
296 }
297 if (m_lastMotion > 0.0) {
298 const double fNorm = std::sqrt(eonc::exact::squaredNorm(m_force));
299 // Halve the trust when the force rose. A slower grow stalls the
300 // stiff pairs at the iteration cap, so a falling force may double.
301 const double grow = (fNorm > m_lastForceNorm * 1.05) ? 0.5 : 2.0;
302 trust = std::min(maxMove, grow * m_lastMotion);
303 }
304 }
305
306 Eigen::VectorXd delta = m_directionNorm;
307 if (m_optConfig.bowlBreakout && a_maxMove < 0.0) {
308 stepSize = maxMove;
309 a_maxMove = maxMove;
310 trust = maxMove;
311 delta *= stepSize;
312 } else {
313 delta *= stepSize;
314 }
315
316 if (m_optConfig.bowlBreakout) {
317 pos += eonc::geometry::maxMotionAppliedV(delta, a_maxMove);
318 } else if (!m_atomCurv.empty() &&
319 static_cast<long>(m_atomCurv.size()) * 3 == delta.size()) {
320 // Per-atom Newton length, then a cap. A scalar step is stuck on
321 // the stiffest atom and crawls along the soft ones.
322 const long nAtoms = static_cast<long>(m_atomCurv.size());
323 for (long a = 0; a < nAtoms; ++a) {
324 const double c = m_atomCurv[static_cast<size_t>(a)];
325 auto seg = delta.segment(3 * a, 3);
326 const double motion = seg.norm();
327 if (!(c > 0.0) || motion < 1e-14) {
328 continue;
329 }
330 const double newton = m_force.segment(3 * a, 3).norm() / c;
331 const double target = std::min(trust, std::max(newton, 0.0));
332 const double scale = std::min(4.0, target / motion);
333 if (scale > 0.0 && std::abs(scale - 1.0) > 1e-6) {
334 seg *= scale;
335 }
336 const double capped = seg.norm();
337 if (capped > trust) {
338 seg *= trust / capped;
339 }
340 }
341 pos += delta;
342 } else {
343 pos += eonc::geometry::maxAtomMotionAppliedV(delta, trust);
344 }
345 m_objf->setPositions(pos);
348 eonc::geometry::maxAtomMotionV(m_objf->difference(pos, posBefore));
349 m_secantPos = posBefore;
352 m_secantProj = projectedForce1;
353 m_haveSecant = true;
354 }
355 if (m_optConfig.opts.cg.knock_out_max_move) {
356 if (stepSize >= a_maxMove) {
357 // knockout old search direction
358 m_directionOld.setZero();
359 m_forceOld.setZero();
360 m_haveSecant = false;
361 m_atomCurv.clear();
362 QUILL_LOG_DEBUG(m_log, "Resetting the old search direction");
363 }
364 }
365
366 return m_objf->isConverged() ? 1 : 0;
367}
368
369int ConjugateGradients::run(size_t a_maxIterations, double a_maxMove) {
370 size_t iterations = 0;
371 while (!m_objf->isConverged() && iterations < a_maxIterations) {
372 step(a_maxMove);
373 iterations++;
374 }
375 return m_objf->isConverged() ? 1 : 0;
376}
377
378} // namespace eonc
Direct optimization for energy minimization.
int single_step(double a_maxMove)
Steps the conjugate gradient.
Eigen::VectorXd m_force
Current force vector.
Eigen::VectorXd getStep()
Gets the direction of the next step.
Eigen::VectorXd m_directionNorm
Normalised version of the current direction vector.
Eigen::VectorXd m_directionOld
Algorithms previous step direction.
int run(size_t a_maxIterations, double a_maxMove) override
Runs the conjugate gradient.
size_t m_cg_i
Counts the number of discrete steps until algorithm convergence.
std::vector< double > m_atomCurv
void onTranslationPulledBack() override
Eigen::VectorXd m_direction
Current step direction of the conjugate gradient.
int step(double a_maxMove) override
Calls the next step in the algorithm.
Eigen::VectorXd m_forceOld
Previous force vector.
eonc::log::FileScoped m_log
int line_search(double a_maxMove)
Steps the conjugate gradient.
const OptimizerConfig m_optConfig
Definition Optimizer.h:73
std::shared_ptr< ObjectiveFunction > m_objf
Definition Optimizer.h:74
double squaredNorm(const Eigen::MatrixBase< A > &x)
A::PlainObject normalized(const Eigen::MatrixBase< A > &x, double min_norm=1e-300)
x / norm(x), or zero below min_norm (the safemath convention).
double dot(const double *x, const double *y, std::size_t n)
Round-to-nearest-even value of the exact sum of x[i] * y[i].
VectorXd maxMotionAppliedV(const VectorXd v1, double maxMotion)
VectorXd maxAtomMotionAppliedV(const VectorXd v1, double maxMotion)
double maxAtomMotionV(const VectorXd v1)
constexpr double safe_div(double num, double denom, double fallback=0.0)
Definition SafeMath.h:21
RAII resource manager for the ARTn C library with global synchronization.