optimization_solvers/line_search/
gll_quadratic.rs

1use super::*;
2
3pub struct GLLQuadratic {
4    c1: Floating,
5    // setting m equal to one is equivalent to the monotone line search vith armijo condition
6    m: usize,
7    f_previous: Vec<Floating>,
8    sigma1: Floating,
9    sigma2: Floating,
10}
11
12impl GLLQuadratic {
13    pub fn new(c1: Floating, m: usize) -> Self {
14        let sigma1 = 0.1;
15        let sigma2 = 0.9;
16        Self {
17            c1,
18            m,
19            f_previous: vec![],
20            sigma1,
21            sigma2,
22        }
23    }
24    pub fn with_sigmas(mut self, sigma1: Floating, sigma2: Floating) -> Self {
25        self.sigma1 = sigma1;
26        self.sigma2 = sigma2;
27        self
28    }
29
30    fn append_new_f(&mut self, f: Floating) {
31        if self.f_previous.len() == self.m {
32            self.f_previous.remove(0);
33        }
34        self.f_previous.push(f);
35    }
36
37    fn f_max(&self) -> Floating {
38        let max = self
39            .f_previous
40            .iter()
41            .fold(Floating::NEG_INFINITY, |acc, x| x.max(acc));
42        max
43    }
44}
45
46impl SufficientDecreaseCondition for GLLQuadratic {
47    fn c1(&self) -> Floating {
48        self.c1
49    }
50}
51
52impl LineSearch for GLLQuadratic {
53    fn compute_step_len(
54        &mut self,
55        x_k: &DVector<Floating>,         // current iterate
56        eval_x_k: &FuncEvalMultivariate, // function evaluation at x_k
57        direction_k: &DVector<Floating>, // direction of the ray along which we are going to search
58        oracle: & mut impl FnMut(&DVector<Floating>) -> FuncEvalMultivariate, // oracle
59        max_iter: usize, // maximum number of iterations during line search (if direction update is costly, set this high to perform more exact line search)
60    ) -> Floating {
61        // we append the function eval to the previous function evals
62        self.append_new_f(*eval_x_k.f());
63        let mut t = 1.0;
64        let f_max = self.f_max();
65        let mut i = 0;
66
67        while max_iter > i {
68            let x_kp1 = x_k + t * direction_k;
69
70            let eval_kp1 = oracle(&x_kp1);
71
72            // armijo condition
73            if self.sufficient_decrease(&f_max, eval_kp1.f(), eval_x_k.g(), &t, direction_k) {
74                trace!(target: "gll quadratic line search", "Sufficient decrease condition met. Exiting with step size: {:?}", t);
75                return t;
76            }
77
78            if t <= 0.1 {
79                trace!(target: "gll quadratic line search", "Step size too small: {}; Bissecting.", t);
80                t *= 0.5;
81            } else {
82                // here step size is sufficiently large to perform a quadratic interpolation
83                let t_tmp = -0.5 * t * t * eval_x_k.g().dot(direction_k)
84                    / (eval_kp1.f() - eval_x_k.f() - t * eval_x_k.g().dot(direction_k));
85                if t_tmp > self.sigma1 && t_tmp < self.sigma2 * t {
86                    trace!(target: "gll quadratic line search", "Safeguarded step size: {}", t_tmp);
87                    t = t_tmp;
88                } else {
89                    // if step is not safeguarded, we take a conservative bissected step
90                    trace!(target: "gll quadratic line search", "t_tmp = {} not in [{}, {}]. Bissecting t_tmp.", t_tmp, self.sigma1, self.sigma2 * t);
91                    t = t_tmp * 0.5;
92                }
93            }
94
95            i += 1;
96        }
97        trace!(target: "gll quadratic line search", "Max iter reached. Early stopping.");
98        t
99    }
100}
optimization_solvers/line_search/gll_quadratic.rs

optimization_solvers/line_search/
gll_quadratic.rs
