Trait LineSearchSolver

Source

pub trait LineSearchSolver: ComputeDirection {
    // Required methods
    fn xk(&self) -> &DVector<Floating>;
    fn xk_mut(&mut self) -> &mut DVector<Floating>;
    fn k(&self) -> &usize;
    fn k_mut(&mut self) -> &mut usize;
    fn has_converged(&self, eval_x_k: &FuncEvalMultivariate) -> bool;

    // Provided methods
    fn setup(&mut self) { ... }
    fn evaluate_x_k(
        &mut self,
        oracle: &mut impl FnMut(&DVector<Floating>) -> FuncEvalMultivariate,
    ) -> Result<FuncEvalMultivariate, SolverError> { ... }
    fn update_next_iterate<LS: LineSearch>(
        &mut self,
        line_search: &mut LS,
        eval_x_k: &FuncEvalMultivariate,
        oracle: &mut impl FnMut(&DVector<Floating>) -> FuncEvalMultivariate,
        direction: &DVector<Floating>,
        max_iter_line_search: usize,
    ) -> Result<(), SolverError> { ... }
    fn minimize<LS: LineSearch>(
        &mut self,
        line_search: &mut LS,
        oracle: impl FnMut(&DVector<Floating>) -> FuncEvalMultivariate,
        max_iter_solver: usize,
        max_iter_line_search: usize,
        callback: Option<&mut dyn FnMut(&Self)>,
    ) -> Result<(), SolverError> { ... }
}

Required Methods§

Source

fn has_converged(&self, eval_x_k: &FuncEvalMultivariate) -> bool

Provided Methods§

Source

fn setup(&mut self)

Source

fn evaluate_x_k( &mut self, oracle: &mut impl FnMut(&DVector<Floating>) -> FuncEvalMultivariate, ) -> Result<FuncEvalMultivariate, SolverError>

Source

fn update_next_iterate<LS: LineSearch>( &mut self, line_search: &mut LS, eval_x_k: &FuncEvalMultivariate, oracle: &mut impl FnMut(&DVector<Floating>) -> FuncEvalMultivariate, direction: &DVector<Floating>, max_iter_line_search: usize, ) -> Result<(), SolverError>

Source

fn minimize<LS: LineSearch>( &mut self, line_search: &mut LS, oracle: impl FnMut(&DVector<Floating>) -> FuncEvalMultivariate, max_iter_solver: usize, max_iter_line_search: usize, callback: Option<&mut dyn FnMut(&Self)>, ) -> Result<(), SolverError>

Examples found in repository ?

examples/quadratic.rs (lines 29-35)

4fn main() {
5    // Setting up log verbosity and _
6    std::env::set_var("RUST_LOG", "debug");
7    let _ = Tracer::default().with_normal_stdout_layer().build();
8
9    // Setting up the oracle
10    let matrix = DMatrix::from_vec(2, 2, vec![1., 0., 0., 1.]);
11    let f_and_g = |x: &DVector<f64>| -> FuncEvalMultivariate {
12        let f = x.dot(&(&matrix * x));
13        let g = 2. * &matrix * x;
14        FuncEvalMultivariate::new(f, g)
15    };
16
17    // Setting up the line search
18    let mut ls = MoreThuente::default();
19    // Setting up the main solver, with its parameters and the initial guess
20    let tol = 1e-6;
21    let x0 = DVector::from_vec(vec![1., 1.]);
22    let mut solver = BFGS::new(tol, x0);
23
24    // Running the solver
25    let max_iter_solver = 100;
26    let max_iter_line_search = 10;
27    let callback = None;
28    solver
29        .minimize(
30            &mut ls,
31            f_and_g,
32            max_iter_solver,
33            max_iter_line_search,
34            callback,
35        )
36        .unwrap();
37    // Printing the result
38    let x = solver.x();
39    let eval = f_and_g(x);
40    println!("x: {:?}", x);
41    println!("f(x): {}", eval.f());
42    println!("g(x): {:?}", eval.g());
43    assert_eq!(eval.f(), &0.0);
44}

More examples

Hide additional examples

examples/quadratic_with_plots.rs (lines 35-41)

6fn main() {
7    // Setting up log verbosity and _.
8    std::env::set_var("RUST_LOG", "debug");
9    let _ = Tracer::default().with_normal_stdout_layer().build();
10    // Setting up the oracle
11    let matrix = DMatrix::from_vec(2, 2, vec![100., 0., 0., 100.]);
12    let mut f_and_g = |x: &DVector<f64>| -> FuncEvalMultivariate {
13        let f = x.dot(&(&matrix * x));
14        let g = 2. * &matrix * x;
15        FuncEvalMultivariate::new(f, g)
16    };
17    // Setting up the line search
18    let armijo_factr = 1e-4;
19    let beta = 0.5; // (beta in (0, 1), ntice that beta = 0.5 corresponds to bisection)
20    let mut ls = BackTracking::new(armijo_factr, beta);
21    // Setting up the main solver, with its parameters and the initial guess
22    let tol = 1e-6;
23    let x0 = DVector::from_vec(vec![10., 10.]);
24    let mut solver = GradientDescent::new(tol, x0);
25    // We define a callback to store iterates and function evaluations
26    let mut iterates = vec![];
27    let mut solver_callback = |s: &GradientDescent| {
28        iterates.push(s.x().clone());
29    };
30    // Running the solver
31    let max_iter_solver = 100;
32    let max_iter_line_search = 10;
33
34    solver
35        .minimize(
36            &mut ls,
37            f_and_g,
38            max_iter_solver,
39            max_iter_line_search,
40            Some(&mut solver_callback),
41        )
42        .unwrap();
43    // Printing the result
44    let x = solver.x();
45    let eval = f_and_g(x);
46    println!("x: {:?}", x);
47    println!("f(x): {}", eval.f());
48    println!("g(x): {:?}", eval.g());
49
50    // Plotting the iterates
51    let n = 50;
52    let start = -5.0;
53    let end = 5.0;
54    let plotter = Plotter3d::new(start, end, start, end, n)
55        .append_plot(&mut f_and_g, "Objective function", 0.5)
56        .append_scatter_points(&mut f_and_g, &iterates, "Iterates")
57        .set_layout_size(1600, 1000);
58    plotter.build("quadratic.html");
59}

examples/gradient_descent_example.rs (lines 49-55)

6fn main() {
7    // Setting up logging
8    std::env::set_var("RUST_LOG", "info");
9    let _ = Tracer::default().with_normal_stdout_layer().build();
10
11    // Convex quadratic function: f(x,y) = x^2 + 2y^2
12    // Global minimum at (0, 0) with f(0,0) = 0
13    let f_and_g = |x: &DVector<f64>| -> FuncEvalMultivariate {
14        let x1 = x[0];
15        let x2 = x[1];
16
17        // Function value
18        let f = x1.powi(2) + 2.0 * x2.powi(2);
19
20        // Gradient
21        let g1 = 2.0 * x1;
22        let g2 = 4.0 * x2;
23        let g = DVector::from_vec(vec![g1, g2]);
24
25        FuncEvalMultivariate::new(f, g)
26    };
27
28    // Setting up the line search (backtracking with Armijo condition)
29    let armijo_factor = 1e-4;
30    let beta = 0.5;
31    let mut ls = BackTracking::new(armijo_factor, beta);
32
33    // Setting up the solver
34    let tol = 1e-6;
35    let x0 = DVector::from_vec(vec![2.0, 1.0]); // Starting point
36    let mut solver = GradientDescent::new(tol, x0.clone());
37
38    // Running the solver
39    let max_iter_solver = 100;
40    let max_iter_line_search = 20;
41
42    println!("=== Gradient Descent Example ===");
43    println!("Objective: f(x,y) = x^2 + 2y^2 (convex quadratic)");
44    println!("Global minimum: (0, 0) with f(0,0) = 0");
45    println!("Starting point: {:?}", x0);
46    println!("Tolerance: {}", tol);
47    println!();
48
49    match solver.minimize(
50        &mut ls,
51        f_and_g,
52        max_iter_solver,
53        max_iter_line_search,
54        None,
55    ) {
56        Ok(()) => {
57            let x = solver.x();
58            let eval = f_and_g(x);
59            println!("✅ Optimization completed successfully!");
60            println!("Final iterate: {:?}", x);
61            println!("Function value: {:.6}", eval.f());
62            println!("Gradient norm: {:.6}", eval.g().norm());
63            println!("Iterations: {}", solver.k());
64
65            // Check if we're close to the known minimum
66            let true_min = DVector::from_vec(vec![0.0, 0.0]);
67            let distance_to_min = (x - true_min).norm();
68            println!("Distance to true minimum: {:.6}", distance_to_min);
69            println!("Expected function value: 0.0");
70        }
71        Err(e) => {
72            println!("❌ Optimization failed: {:?}", e);
73        }
74    }
75}

examples/bfgs_example.rs (lines 46-52)

4fn main() {
5    // Setting up logging
6    std::env::set_var("RUST_LOG", "info");
7    let _ = Tracer::default().with_normal_stdout_layer().build();
8
9    // Convex quadratic function: f(x,y,z) = x^2 + 2y^2 + 3z^2 + xy + yz
10    // This function has a unique minimum that we can verify
11    let f_and_g = |x: &DVector<f64>| -> FuncEvalMultivariate {
12        let x1 = x[0];
13        let x2 = x[1];
14        let x3 = x[2];
15
16        // Function value
17        let f = x1.powi(2) + 2.0 * x2.powi(2) + 3.0 * x3.powi(2) + x1 * x2 + x2 * x3;
18
19        // Gradient
20        let g1 = 2.0 * x1 + x2;
21        let g2 = 4.0 * x2 + x1 + x3;
22        let g3 = 6.0 * x3 + x2;
23        let g = DVector::from_vec(vec![g1, g2, g3]);
24
25        FuncEvalMultivariate::new(f, g)
26    };
27
28    // Setting up the line search (More-Thuente line search)
29    let mut ls = MoreThuente::default();
30
31    // Setting up the solver
32    let tol = 1e-8;
33    let x0 = DVector::from_vec(vec![1.0, 1.0, 1.0]); // Starting point
34    let mut solver = BFGS::new(tol, x0.clone());
35
36    // Running the solver
37    let max_iter_solver = 50;
38    let max_iter_line_search = 20;
39
40    println!("=== BFGS Quasi-Newton Example ===");
41    println!("Objective: f(x,y,z) = x^2 + 2y^2 + 3z^2 + xy + yz (convex quadratic)");
42    println!("Starting point: {:?}", x0);
43    println!("Tolerance: {}", tol);
44    println!();
45
46    match solver.minimize(
47        &mut ls,
48        f_and_g,
49        max_iter_solver,
50        max_iter_line_search,
51        None,
52    ) {
53        Ok(()) => {
54            let x = solver.x();
55            let eval = f_and_g(x);
56            println!("✅ Optimization completed successfully!");
57            println!("Final iterate: {:?}", x);
58            println!("Function value: {:.8}", eval.f());
59            println!("Gradient norm: {:.8}", eval.g().norm());
60            println!("Iterations: {}", solver.k());
61
62            // Verify optimality conditions
63            let gradient_at_solution = eval.g();
64            println!("Gradient at solution: {:?}", gradient_at_solution);
65            println!(
66                "Gradient norm should be close to 0: {}",
67                gradient_at_solution.norm()
68            );
69
70            // For this convex quadratic function, the minimum should be at the solution of the linear system
71            // ∇f(x) = 0, which gives us a system of linear equations
72            println!("Expected minimum: solution of ∇f(x) = 0");
73        }
74        Err(e) => {
75            println!("❌ Optimization failed: {:?}", e);
76        }
77    }
78}

examples/coordinate_descent_example.rs (lines 51-57)

6fn main() {
7    // Setting up logging
8    std::env::set_var("RUST_LOG", "info");
9    let _ = Tracer::default().with_normal_stdout_layer().build();
10
11    // Separable convex function: f(x,y,z) = x^2 + 2y^2 + 3z^2
12    // This function is separable and has a minimum at (0, 0, 0)
13    let f_and_g = |x: &DVector<f64>| -> FuncEvalMultivariate {
14        let x1 = x[0];
15        let x2 = x[1];
16        let x3 = x[2];
17
18        // Function value
19        let f = x1.powi(2) + 2.0 * x2.powi(2) + 3.0 * x3.powi(2);
20
21        // Gradient
22        let g1 = 2.0 * x1;
23        let g2 = 4.0 * x2;
24        let g3 = 6.0 * x3;
25        let g = DVector::from_vec(vec![g1, g2, g3]);
26
27        FuncEvalMultivariate::new(f, g)
28    };
29
30    // Setting up the line search (backtracking)
31    let armijo_factor = 1e-4;
32    let beta = 0.5;
33    let mut ls = BackTracking::new(armijo_factor, beta);
34
35    // Setting up the solver
36    let tol = 1e-6;
37    let x0 = DVector::from_vec(vec![1.0, 1.0, 1.0]); // Starting point
38    let mut solver = CoordinateDescent::new(tol, x0.clone());
39
40    // Running the solver
41    let max_iter_solver = 100;
42    let max_iter_line_search = 10;
43
44    println!("=== Coordinate Descent Example ===");
45    println!("Objective: f(x,y,z) = x^2 + 2y^2 + 3z^2 (separable convex)");
46    println!("Global minimum: (0, 0, 0) with f(0,0,0) = 0");
47    println!("Starting point: {:?}", x0);
48    println!("Tolerance: {}", tol);
49    println!();
50
51    match solver.minimize(
52        &mut ls,
53        f_and_g,
54        max_iter_solver,
55        max_iter_line_search,
56        None,
57    ) {
58        Ok(()) => {
59            let x = solver.x();
60            let eval = f_and_g(x);
61            println!("✅ Optimization completed successfully!");
62            println!("Final iterate: {:?}", x);
63            println!("Function value: {:.6}", eval.f());
64            println!("Gradient norm: {:.6}", eval.g().norm());
65            println!("Iterations: {}", solver.k());
66
67            // Check if we're close to the known minimum
68            let true_min = DVector::from_vec(vec![0.0, 0.0, 0.0]);
69            let distance_to_min = (x - true_min).norm();
70            println!("Distance to true minimum: {:.6}", distance_to_min);
71            println!("Expected function value: 0.0");
72
73            // Verify optimality conditions
74            let gradient_at_solution = eval.g();
75            println!("Gradient at solution: {:?}", gradient_at_solution);
76            println!(
77                "Gradient norm should be close to 0: {}",
78                gradient_at_solution.norm()
79            );
80        }
81        Err(e) => {
82            println!("❌ Optimization failed: {:?}", e);
83        }
84    }
85}

examples/dfp_example.rs (lines 44-50)

4fn main() {
5    // Setting up logging
6    std::env::set_var("RUST_LOG", "info");
7    let _ = Tracer::default().with_normal_stdout_layer().build();
8
9    // Convex function: f(x,y) = x^2 + 5y^2 + xy
10    // This function is convex and has a unique minimum
11    let f_and_g = |x: &DVector<f64>| -> FuncEvalMultivariate {
12        let x1 = x[0];
13        let x2 = x[1];
14
15        // Function value
16        let f = x1.powi(2) + 5.0 * x2.powi(2) + x1 * x2;
17
18        // Gradient
19        let g1 = 2.0 * x1 + x2;
20        let g2 = 10.0 * x2 + x1;
21        let g = DVector::from_vec(vec![g1, g2]);
22
23        FuncEvalMultivariate::new(f, g)
24    };
25
26    // Setting up the line search (More-Thuente line search)
27    let mut ls = MoreThuente::default();
28
29    // Setting up the solver
30    let tol = 1e-6;
31    let x0 = DVector::from_vec(vec![2.0, 1.0]); // Starting point
32    let mut solver = DFP::new(tol, x0.clone());
33
34    // Running the solver
35    let max_iter_solver = 100;
36    let max_iter_line_search = 20;
37
38    println!("=== DFP (Davidon-Fletcher-Powell) Quasi-Newton Example ===");
39    println!("Objective: f(x,y) = x^2 + 5y^2 + xy (convex quadratic)");
40    println!("Starting point: {:?}", x0);
41    println!("Tolerance: {}", tol);
42    println!();
43
44    match solver.minimize(
45        &mut ls,
46        f_and_g,
47        max_iter_solver,
48        max_iter_line_search,
49        None,
50    ) {
51        Ok(()) => {
52            let x = solver.x();
53            let eval = f_and_g(x);
54            println!("✅ Optimization completed successfully!");
55            println!("Final iterate: {:?}", x);
56            println!("Function value: {:.6}", eval.f());
57            println!("Gradient norm: {:.6}", eval.g().norm());
58            println!("Iterations: {}", solver.k());
59
60            // Verify optimality conditions
61            let gradient_at_solution = eval.g();
62            println!("Gradient at solution: {:?}", gradient_at_solution);
63            println!(
64                "Gradient norm should be close to 0: {}",
65                gradient_at_solution.norm()
66            );
67
68            // For this convex quadratic function, the minimum should be at the solution of the linear system
69            // ∇f(x) = 0, which gives us: 2x + y = 0, x + 10y = 0
70            // Solving: x = 0, y = 0
71            let expected_min = DVector::from_vec(vec![0.0, 0.0]);
72            let distance_to_expected = (x - expected_min).norm();
73            println!(
74                "Distance to expected minimum (0,0): {:.6}",
75                distance_to_expected
76            );
77            println!("Expected function value at (0,0): 0.0");
78        }
79        Err(e) => {
80            println!("❌ Optimization failed: {:?}", e);
81        }
82    }
83}