optimization_solvers/line_search/
backtracking_b.rs

1// Inexact line search described in chapter 9.2 of Boyd's convex optimization book, adapted for solvers handling constraints (such as Projected Gradient Descent)
2
3use super::*;
4pub struct BackTrackingB {
5    c1: Floating,   // recommended: [0.01, 0.3]
6    beta: Floating, // recommended: [0.1, 0.8]
7    lower_bound: DVector<Floating>,
8    upper_bound: DVector<Floating>,
9}
10impl BackTrackingB {
11    pub fn new(
12        c1: Floating,
13        beta: Floating,
14        lower_bound: DVector<Floating>,
15        upper_bound: DVector<Floating>,
16    ) -> Self {
17        BackTrackingB {
18            c1,
19            beta,
20            lower_bound,
21            upper_bound,
22        }
23    }
24    fn sufficient_decrease_with_bounds(
25        &self,
26        x0: &DVector<Floating>,
27        x: &DVector<Floating>,
28        f0: &Floating,
29        f: &Floating,
30        t: &Floating, //step len
31    ) -> bool {
32        let diff = x - x0;
33        f - f0 <= (-&self.c1 / t) * diff.dot(&diff)
34    }
35}
36
37impl HasBounds for BackTrackingB {
38    fn lower_bound(&self) -> &DVector<Floating> {
39        &self.lower_bound
40    }
41    fn upper_bound(&self) -> &DVector<Floating> {
42        &self.upper_bound
43    }
44    fn set_lower_bound(&mut self, lower_bound: DVector<Floating>) {
45        self.lower_bound = lower_bound;
46    }
47    fn set_upper_bound(&mut self, upper_bound: DVector<Floating>) {
48        self.upper_bound = upper_bound;
49    }
50}
51
52impl LineSearch for BackTrackingB {
53    fn compute_step_len(
54        &mut self,
55        x_k: &DVector<Floating>,
56        eval_x_k: &FuncEvalMultivariate,
57        direction_k: &DVector<Floating>,
58        oracle: & mut impl FnMut(&DVector<Floating>) -> FuncEvalMultivariate,
59        max_iter: usize,
60    ) -> Floating {
61        let mut t = 1.0;
62        let mut i = 0;
63
64        while max_iter > i {
65            let x_kp1 = x_k + t * direction_k;
66            // we project the next iterate onto the feasible set
67            let x_kp1 = x_kp1.box_projection(&self.lower_bound, &self.upper_bound);
68            let eval_kp1 = oracle(&x_kp1);
69            // we check if we are out of domain
70            if eval_kp1.f().is_nan() || eval_kp1.f().is_infinite() {
71                trace!(target: "backtracking_b line search", "Step size too big: next iterate is out of domain. Decreasing step by beta ({:?})", x_kp1);
72                t *= self.beta;
73                continue;
74            }
75            if self.sufficient_decrease_with_bounds(x_k, &x_kp1, eval_x_k.f(), eval_kp1.f(), &t) {
76                trace!(target: "backtracking_b line search", "Modified Armijo rule met. Exiting with step size: {:?} at iteration {:?}", t, i);
77                return t;
78            }
79
80            //if we are here, it means that the we still didn't meet the exit condition, so we decrease the step size accordingly
81            t *= self.beta;
82            i += 1;
83        }
84        trace!(target: "backtracking_b line search", "Max iter reached. Early stopping.");
85        t
86        // worst case scenario: t=0 (or t>0 but t<1 because of early stopping).
87        // if t=0 we are not updating the iterate
88        // if early stop triggered, we benefit from some image reduction but it is not enough to be considered satisfactory
89    }
90}
optimization_solvers/line_search/backtracking_b.rs

optimization_solvers/line_search/
backtracking_b.rs
