conspire/math/optimize/line_search/
mod.rs

1use crate::math::{Jacobian, Scalar, Solution, Style, StyledError, styled_error};
2use std::{
3    fmt::{self, Debug, Display, Formatter},
4    ops::Mul,
5};
6
7/// Available line search algorithms.
8#[derive(Debug)]
9pub enum LineSearch {
10    /// The Armijo condition.
11    Armijo {
12        control: Scalar,
13        cut_back: Scalar,
14        max_steps: usize,
15    },
16    /// Backtrack for errors.
17    Error { cut_back: Scalar, max_steps: usize },
18    /// The Goldstein conditions.
19    Goldstein {
20        control: Scalar,
21        cut_back: Scalar,
22        max_steps: usize,
23    },
24    /// The Wolfe conditions.
25    Wolfe {
26        control_1: Scalar,
27        control_2: Scalar,
28        cut_back: Scalar,
29        max_steps: usize,
30        strong: bool,
31    },
32    /// No line search.
33    None,
34}
35
36impl Default for LineSearch {
37    fn default() -> Self {
38        Self::Armijo {
39            control: 1e-3,
40            cut_back: 9e-1,
41            max_steps: 100,
42        }
43    }
44}
45
46impl Display for LineSearch {
47    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
48        match self {
49            Self::Armijo { .. } => write!(f, "Armijo"),
50            Self::Error { .. } => write!(f, "Error"),
51            Self::Goldstein { .. } => write!(f, "Goldstein"),
52            Self::Wolfe { .. } => write!(f, "Wolfe"),
53            Self::None { .. } => write!(f, "None"),
54        }
55    }
56}
57
58impl LineSearch {
59    pub fn backtrack<X, J>(
60        &self,
61        mut function: impl FnMut(&X) -> Result<Scalar, String>,
62        mut jacobian: impl FnMut(&X) -> Result<J, String>,
63        argument: &X,
64        jacobian0: &J,
65        decrement: &X,
66        step_size: Scalar,
67    ) -> Result<Scalar, LineSearchError>
68    where
69        J: Jacobian,
70        for<'a> &'a J: From<&'a X>,
71        X: Solution,
72        for<'a> &'a X: Mul<Scalar, Output = X>,
73    {
74        if step_size <= 0.0 {
75            return Err(LineSearchError::NegativeStepSize(
76                format!("{self:?}"),
77                step_size,
78            ));
79        }
80        let mut n = step_size;
81        let f = if let Ok(value) = function(argument) {
82            value
83        } else {
84            return Err(LineSearchError::InvalidStartingPoint(format!("{self:?}")));
85        };
86        let m = jacobian0.full_contraction(decrement.into());
87        if m <= 0.0 {
88            return Err(LineSearchError::NotDescentDirection(format!("{self:?}")));
89        }
90        match self {
91            Self::Armijo {
92                control,
93                cut_back,
94                max_steps,
95            } => {
96                let mut f_n;
97                let t = control * m;
98                for _ in 0..*max_steps {
99                    f_n = function(&(decrement * -n + argument));
100                    if let Ok(value) = f_n
101                        && f - value >= n * t
102                    {
103                        return Ok(n);
104                    } else {
105                        n *= cut_back
106                    }
107                }
108                Err(LineSearchError::MaximumStepsReached(
109                    format!("{self:?}"),
110                    *max_steps,
111                ))
112            }
113            Self::Error {
114                cut_back,
115                max_steps,
116            } => {
117                for _ in 0..*max_steps {
118                    if function(&(decrement * -n + argument)).is_ok() {
119                        return Ok(n);
120                    } else {
121                        n *= cut_back
122                    }
123                }
124                Err(LineSearchError::MaximumStepsReached(
125                    format!("{self:?}"),
126                    *max_steps,
127                ))
128            }
129            Self::Goldstein {
130                control,
131                cut_back,
132                max_steps,
133            } => {
134                let mut f_n;
135                let t = control * m;
136                let u = (1.0 - control) * m;
137                let mut v;
138                for _ in 0..*max_steps {
139                    f_n = function(&(decrement * -n + argument));
140                    if let Ok(value) = f_n {
141                        v = f - value;
142                        if n * u < v || v < n * t {
143                            n *= cut_back
144                        } else {
145                            return Ok(n);
146                        }
147                    } else {
148                        n *= cut_back
149                    }
150                }
151                Err(LineSearchError::MaximumStepsReached(
152                    format!("{self:?}"),
153                    *max_steps,
154                ))
155            }
156            Self::Wolfe {
157                control_1,
158                control_2,
159                cut_back,
160                max_steps,
161                strong,
162            } => {
163                let mut f_n;
164                let mut j_n;
165                let t_1 = control_1 * m;
166                let t_2 = control_2 * m;
167                let mut trial_argument = decrement * -n + argument;
168                for _ in 0..*max_steps {
169                    f_n = function(&trial_argument);
170                    j_n = jacobian(&trial_argument);
171                    if let Ok(f_val) = f_n
172                        && let Ok(j_val) = j_n
173                        && f - f_val >= n * t_1
174                        && if *strong {
175                            j_val.full_contraction(decrement.into()) < t_2
176                        } else {
177                            j_val.full_contraction(decrement.into()).abs() < t_2.abs() // less than?
178                        }
179                    {
180                        return Ok(n);
181                    } else {
182                        n *= cut_back;
183                        trial_argument = decrement * -n + argument
184                    }
185                }
186                Err(LineSearchError::MaximumStepsReached(
187                    format!("{self:?}"),
188                    *max_steps,
189                ))
190            }
191            Self::None => {
192                panic!("Cannot call backtracking line search when there is no algorithm.")
193            }
194        }
195    }
196}
197
198/// Possible errors encountered during line search.
199pub enum LineSearchError {
200    InvalidStartingPoint(String),
201    MaximumStepsReached(String, usize),
202    NegativeStepSize(String, Scalar),
203    NotDescentDirection(String),
204}
205
206impl StyledError for LineSearchError {
207    fn message(&self, style: &Style) -> String {
208        let (h, c) = (style.headline, style.frame);
209        match self {
210            Self::InvalidStartingPoint(line_search) => format!(
211                "{h}Staring point is invalid.{c}\n\
212                In line search: {line_search}."
213            ),
214            Self::MaximumStepsReached(line_search, steps) => format!(
215                "{h}Maximum number of steps ({steps}) reached.{c}\n\
216                In line search: {line_search}."
217            ),
218            Self::NegativeStepSize(line_search, step_size) => format!(
219                "{h}Negative step size ({step_size}) encountered.{c}\n\
220                In line search: {line_search}."
221            ),
222            Self::NotDescentDirection(line_search) => format!(
223                "{h}Direction is not a descent direction.{c}\n\
224                In line search: {line_search}."
225            ),
226        }
227    }
228}
229
230styled_error!(LineSearchError);
conspire/math/optimize/line_search/mod.rs

conspire/math/optimize/line_search/
mod.rs
