#[cfg(test)]
mod test;
use crate::math::{
Erase, Jacobian, Quantity, Scalar, Solution, Style, StyledError, Tensor, styled_error,
};
use std::{
fmt::{self, Debug, Display, Formatter},
ops::Mul,
};
#[derive(Clone, Debug)]
pub enum LineSearch {
Armijo {
control: Scalar,
cut_back: Scalar,
max_steps: usize,
},
Error { cut_back: Scalar, max_steps: usize },
Goldstein {
control: Scalar,
cut_back: Scalar,
max_steps: usize,
},
Wolfe {
control_1: Scalar,
control_2: Scalar,
cut_back: Scalar,
max_steps: usize,
strong: bool,
},
None,
}
impl Default for LineSearch {
fn default() -> Self {
Self::Armijo {
control: 1e-3,
cut_back: 9e-1,
max_steps: 100,
}
}
}
impl Display for LineSearch {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
match self {
Self::Armijo { .. } => write!(f, "Armijo"),
Self::Error { .. } => write!(f, "Error"),
Self::Goldstein { .. } => write!(f, "Goldstein"),
Self::Wolfe { .. } => write!(f, "Wolfe"),
Self::None { .. } => write!(f, "None"),
}
}
}
impl LineSearch {
pub fn backtrack_merit(
&self,
mut merit: impl FnMut(Scalar) -> Result<Scalar, String>,
value: Scalar,
slope: Scalar,
step_size: Scalar,
) -> Result<Scalar, LineSearchError> {
if step_size <= 0.0 {
return Err(LineSearchError::NegativeStepSize(
format!("{self:?}"),
step_size,
));
} else if slope <= 0.0 {
return Err(LineSearchError::NotDescentDirection(format!("{self:?}")));
}
let mut n = step_size;
match self {
Self::Armijo {
control,
cut_back,
max_steps,
} => {
let t = control * slope;
for _ in 0..*max_steps {
if let Ok(trial) = merit(n)
&& value - trial >= n * t
{
return Ok(n);
} else {
n *= cut_back
}
}
Err(LineSearchError::MaximumStepsReached(
format!("{self:?}"),
*max_steps,
))
}
Self::Error {
cut_back,
max_steps,
} => {
for _ in 0..*max_steps {
if merit(n).is_ok() {
return Ok(n);
} else {
n *= cut_back
}
}
Err(LineSearchError::MaximumStepsReached(
format!("{self:?}"),
*max_steps,
))
}
Self::Goldstein {
control,
cut_back,
max_steps,
} => {
let t = control * slope;
let u = (1.0 - control) * slope;
let mut v;
for _ in 0..*max_steps {
if let Ok(trial) = merit(n) {
v = value - trial;
if n * u < v || v < n * t {
n *= cut_back
} else {
return Ok(n);
}
} else {
n *= cut_back
}
}
Err(LineSearchError::MaximumStepsReached(
format!("{self:?}"),
*max_steps,
))
}
Self::Wolfe { .. } => panic!(
"The Wolfe conditions need the gradient of the merit function, which the exact penalty function does not have."
),
Self::None => {
panic!("Cannot call backtracking line search when there is no algorithm.")
}
}
}
pub fn backtrack<X, J, D, W, E>(
&self,
mut function: impl FnMut(&X, Scalar) -> Result<Scalar, String>,
mut jacobian: impl FnMut(&X) -> Result<J, String>,
argument: &X,
jacobian0: &J,
decrement: &D,
step_size: Scalar,
) -> Result<Scalar, LineSearchError>
where
J: Erase<Erased = E> + Jacobian,
D: Erase<Erased = E>,
E: Tensor,
X: Solution,
for<'a> &'a D: Mul<Quantity<W>, Output = X>,
{
if step_size <= 0.0 {
return Err(LineSearchError::NegativeStepSize(
format!("{self:?}"),
step_size,
));
}
let mut n = step_size;
let f = if let Ok(value) = function(argument, 0.0) {
value
} else {
return Err(LineSearchError::InvalidStartingPoint(format!("{self:?}")));
};
let m = jacobian0.erase().full_contraction(decrement.erase());
if m <= 0.0 {
return Err(LineSearchError::NotDescentDirection(format!("{self:?}")));
}
let trial = |n: Scalar| decrement * Quantity::new(-n) + argument;
match self {
Self::Armijo {
control,
cut_back,
max_steps,
} => {
let mut f_n;
let t = control * m;
for _ in 0..*max_steps {
f_n = function(&trial(n), n);
if let Ok(value) = f_n
&& f - value >= n * t
{
return Ok(n);
} else {
n *= cut_back
}
}
Err(LineSearchError::MaximumStepsReached(
format!("{self:?}"),
*max_steps,
))
}
Self::Error {
cut_back,
max_steps,
} => {
for _ in 0..*max_steps {
if function(&trial(n), n).is_ok() {
return Ok(n);
} else {
n *= cut_back
}
}
Err(LineSearchError::MaximumStepsReached(
format!("{self:?}"),
*max_steps,
))
}
Self::Goldstein {
control,
cut_back,
max_steps,
} => {
let mut f_n;
let t = control * m;
let u = (1.0 - control) * m;
let mut v;
for _ in 0..*max_steps {
f_n = function(&trial(n), n);
if let Ok(value) = f_n {
v = f - value;
if n * u < v || v < n * t {
n *= cut_back
} else {
return Ok(n);
}
} else {
n *= cut_back
}
}
Err(LineSearchError::MaximumStepsReached(
format!("{self:?}"),
*max_steps,
))
}
Self::Wolfe {
control_1,
control_2,
cut_back,
max_steps,
strong,
} => {
let mut f_n;
let mut j_n;
let t_1 = control_1 * m;
let t_2 = control_2 * m;
let mut trial_argument = trial(n);
for _ in 0..*max_steps {
f_n = function(&trial_argument, n);
j_n = jacobian(&trial_argument);
if let Ok(f_val) = f_n
&& let Ok(j_val) = j_n
&& f - f_val >= n * t_1
&& if *strong {
j_val.erase().full_contraction(decrement.erase()).abs() < t_2.abs()
} else {
j_val.erase().full_contraction(decrement.erase()) < t_2
}
{
return Ok(n);
} else {
n *= cut_back;
trial_argument = trial(n)
}
}
Err(LineSearchError::MaximumStepsReached(
format!("{self:?}"),
*max_steps,
))
}
Self::None => {
panic!("Cannot call backtracking line search when there is no algorithm.")
}
}
}
}
pub enum LineSearchError {
InvalidStartingPoint(String),
MaximumStepsReached(String, usize),
NegativeStepSize(String, Scalar),
NotDescentDirection(String),
}
impl StyledError for LineSearchError {
fn message(&self, style: &Style) -> String {
let (h, c) = (style.headline, style.frame);
match self {
Self::InvalidStartingPoint(line_search) => format!(
"{h}Starting point is invalid.{c}\n\
In line search: {line_search}."
),
Self::MaximumStepsReached(line_search, steps) => format!(
"{h}Maximum number of steps ({steps}) reached.{c}\n\
In line search: {line_search}."
),
Self::NegativeStepSize(line_search, step_size) => format!(
"{h}Negative step size ({step_size}) encountered.{c}\n\
In line search: {line_search}."
),
Self::NotDescentDirection(line_search) => format!(
"{h}Direction is not a descent direction.{c}\n\
In line search: {line_search}."
),
}
}
}
styled_error!(LineSearchError);