Struct BackTracking 

pub struct BackTracking { /* private fields */ }

Implementations

impl BackTracking

pub fn new(c1: Floating, beta: Floating) -> Self

Examples found in repository

examples/quadratic_with_plots.rs (line 20)

fn main() {
    // Setting up log verbosity and _.
    std::env::set_var("RUST_LOG", "debug");
    let _ = Tracer::default().with_normal_stdout_layer().build();
    // Setting up the oracle
    let matrix = DMatrix::from_vec(2, 2, vec![100., 0., 0., 100.]);
    let mut f_and_g = |x: &DVector<f64>| -> FuncEvalMultivariate {
        let f = x.dot(&(&matrix * x));
        let g = 2. * &matrix * x;
        FuncEvalMultivariate::new(f, g)
    };
    // Setting up the line search
    let armijo_factr = 1e-4;
    let beta = 0.5; // (beta in (0, 1), ntice that beta = 0.5 corresponds to bisection)
    let mut ls = BackTracking::new(armijo_factr, beta);
    // Setting up the main solver, with its parameters and the initial guess
    let tol = 1e-6;
    let x0 = DVector::from_vec(vec![10., 10.]);
    let mut solver = GradientDescent::new(tol, x0);
    // We define a callback to store iterates and function evaluations
    let mut iterates = vec![];
    let mut solver_callback = |s: &GradientDescent| {
        iterates.push(s.x().clone());
    };
    // Running the solver
    let max_iter_solver = 100;
    let max_iter_line_search = 10;

    solver
        .minimize(
            &mut ls,
            f_and_g,
            max_iter_solver,
            max_iter_line_search,
            Some(&mut solver_callback),
        )
        .unwrap();
    // Printing the result
    let x = solver.x();
    let eval = f_and_g(x);
    println!("x: {:?}", x);
    println!("f(x): {}", eval.f());
    println!("g(x): {:?}", eval.g());

    // Plotting the iterates
    let n = 50;
    let start = -5.0;
    let end = 5.0;
    let plotter = Plotter3d::new(start, end, start, end, n)
        .append_plot(&mut f_and_g, "Objective function", 0.5)
        .append_scatter_points(&mut f_and_g, &iterates, "Iterates")
        .set_layout_size(1600, 1000);
    plotter.build("quadratic.html");
}

examples/gradient_descent_example.rs (line 31)

fn main() {
    // Setting up logging
    std::env::set_var("RUST_LOG", "info");
    let _ = Tracer::default().with_normal_stdout_layer().build();

    // Convex quadratic function: f(x,y) = x^2 + 2y^2
    // Global minimum at (0, 0) with f(0,0) = 0
    let f_and_g = |x: &DVector<f64>| -> FuncEvalMultivariate {
        let x1 = x[0];
        let x2 = x[1];

        // Function value
        let f = x1.powi(2) + 2.0 * x2.powi(2);

        // Gradient
        let g1 = 2.0 * x1;
        let g2 = 4.0 * x2;
        let g = DVector::from_vec(vec![g1, g2]);

        FuncEvalMultivariate::new(f, g)
    };

    // Setting up the line search (backtracking with Armijo condition)
    let armijo_factor = 1e-4;
    let beta = 0.5;
    let mut ls = BackTracking::new(armijo_factor, beta);

    // Setting up the solver
    let tol = 1e-6;
    let x0 = DVector::from_vec(vec![2.0, 1.0]); // Starting point
    let mut solver = GradientDescent::new(tol, x0.clone());

    // Running the solver
    let max_iter_solver = 100;
    let max_iter_line_search = 20;

    println!("=== Gradient Descent Example ===");
    println!("Objective: f(x,y) = x^2 + 2y^2 (convex quadratic)");
    println!("Global minimum: (0, 0) with f(0,0) = 0");
    println!("Starting point: {:?}", x0);
    println!("Tolerance: {}", tol);
    println!();

    match solver.minimize(
        &mut ls,
        f_and_g,
        max_iter_solver,
        max_iter_line_search,
        None,
    ) {
        Ok(()) => {
            let x = solver.x();
            let eval = f_and_g(x);
            println!("✅ Optimization completed successfully!");
            println!("Final iterate: {:?}", x);
            println!("Function value: {:.6}", eval.f());
            println!("Gradient norm: {:.6}", eval.g().norm());
            println!("Iterations: {}", solver.k());

            // Check if we're close to the known minimum
            let true_min = DVector::from_vec(vec![0.0, 0.0]);
            let distance_to_min = (x - true_min).norm();
            println!("Distance to true minimum: {:.6}", distance_to_min);
            println!("Expected function value: 0.0");
        }
        Err(e) => {
            println!("❌ Optimization failed: {:?}", e);
        }
    }
}

examples/coordinate_descent_example.rs (line 33)

fn main() {
    // Setting up logging
    std::env::set_var("RUST_LOG", "info");
    let _ = Tracer::default().with_normal_stdout_layer().build();

    // Separable convex function: f(x,y,z) = x^2 + 2y^2 + 3z^2
    // This function is separable and has a minimum at (0, 0, 0)
    let f_and_g = |x: &DVector<f64>| -> FuncEvalMultivariate {
        let x1 = x[0];
        let x2 = x[1];
        let x3 = x[2];

        // Function value
        let f = x1.powi(2) + 2.0 * x2.powi(2) + 3.0 * x3.powi(2);

        // Gradient
        let g1 = 2.0 * x1;
        let g2 = 4.0 * x2;
        let g3 = 6.0 * x3;
        let g = DVector::from_vec(vec![g1, g2, g3]);

        FuncEvalMultivariate::new(f, g)
    };

    // Setting up the line search (backtracking)
    let armijo_factor = 1e-4;
    let beta = 0.5;
    let mut ls = BackTracking::new(armijo_factor, beta);

    // Setting up the solver
    let tol = 1e-6;
    let x0 = DVector::from_vec(vec![1.0, 1.0, 1.0]); // Starting point
    let mut solver = CoordinateDescent::new(tol, x0.clone());

    // Running the solver
    let max_iter_solver = 100;
    let max_iter_line_search = 10;

    println!("=== Coordinate Descent Example ===");
    println!("Objective: f(x,y,z) = x^2 + 2y^2 + 3z^2 (separable convex)");
    println!("Global minimum: (0, 0, 0) with f(0,0,0) = 0");
    println!("Starting point: {:?}", x0);
    println!("Tolerance: {}", tol);
    println!();

    match solver.minimize(
        &mut ls,
        f_and_g,
        max_iter_solver,
        max_iter_line_search,
        None,
    ) {
        Ok(()) => {
            let x = solver.x();
            let eval = f_and_g(x);
            println!("✅ Optimization completed successfully!");
            println!("Final iterate: {:?}", x);
            println!("Function value: {:.6}", eval.f());
            println!("Gradient norm: {:.6}", eval.g().norm());
            println!("Iterations: {}", solver.k());

            // Check if we're close to the known minimum
            let true_min = DVector::from_vec(vec![0.0, 0.0, 0.0]);
            let distance_to_min = (x - true_min).norm();
            println!("Distance to true minimum: {:.6}", distance_to_min);
            println!("Expected function value: 0.0");

            // Verify optimality conditions
            let gradient_at_solution = eval.g();
            println!("Gradient at solution: {:?}", gradient_at_solution);
            println!(
                "Gradient norm should be close to 0: {}",
                gradient_at_solution.norm()
            );
        }
        Err(e) => {
            println!("❌ Optimization failed: {:?}", e);
        }
    }
}

examples/pnorm_descent_example.rs (line 31)

fn main() {
    // Setting up logging
    std::env::set_var("RUST_LOG", "info");
    let _ = Tracer::default().with_normal_stdout_layer().build();

    // Convex quadratic function: f(x,y) = x^2 + 4y^2
    // This function has a minimum at (0, 0)
    let f_and_g = |x: &DVector<f64>| -> FuncEvalMultivariate {
        let x1 = x[0];
        let x2 = x[1];

        // Function value
        let f = x1.powi(2) + 4.0 * x2.powi(2);

        // Gradient
        let g1 = 2.0 * x1;
        let g2 = 8.0 * x2;
        let g = DVector::from_vec(vec![g1, g2]);

        FuncEvalMultivariate::new(f, g)
    };

    // Setting up the line search (backtracking)
    let armijo_factor = 1e-4;
    let beta = 0.5;
    let mut ls = BackTracking::new(armijo_factor, beta);

    // Setting up the solver with a diagonal preconditioner
    let tol = 1e-6;
    let x0 = DVector::from_vec(vec![2.0, 1.0]); // Starting point

    // Create a diagonal preconditioner matrix P = diag(1, 1/4) to improve conditioning
    let inverse_p = DMatrix::from_vec(2, 2, vec![1.0, 0.0, 0.0, 0.25]);
    let mut solver = PnormDescent::new(tol, x0.clone(), inverse_p);

    // Running the solver
    let max_iter_solver = 50;
    let max_iter_line_search = 20;

    println!("=== P-Norm Descent Example ===");
    println!("Objective: f(x,y) = x^2 + 4y^2 (convex quadratic)");
    println!("Global minimum: (0, 0) with f(0,0) = 0");
    println!("Preconditioner: P = diag(1, 1/4)");
    println!("Starting point: {:?}", x0);
    println!("Tolerance: {}", tol);
    println!();

    match solver.minimize(
        &mut ls,
        f_and_g,
        max_iter_solver,
        max_iter_line_search,
        None,
    ) {
        Ok(()) => {
            let x = solver.x();
            let eval = f_and_g(x);
            println!("✅ Optimization completed successfully!");
            println!("Final iterate: {:?}", x);
            println!("Function value: {:.6}", eval.f());
            println!("Gradient norm: {:.6}", eval.g().norm());
            println!("Iterations: {}", solver.k());

            // Check if we're close to the known minimum
            let true_min = DVector::from_vec(vec![0.0, 0.0]);
            let distance_to_min = (x - true_min).norm();
            println!("Distance to true minimum: {:.6}", distance_to_min);
            println!("Expected function value: 0.0");

            // Verify optimality conditions
            let gradient_at_solution = eval.g();
            println!("Gradient at solution: {:?}", gradient_at_solution);
            println!(
                "Gradient norm should be close to 0: {}",
                gradient_at_solution.norm()
            );

            // Show some properties of P-norm descent
            println!("P-norm descent properties:");
            println!("  - Uses a preconditioner P to improve convergence");
            println!("  - Equivalent to steepest descent with P = identity");
            println!("  - Good preconditioner can significantly improve convergence rate");
        }
        Err(e) => {
            println!("❌ Optimization failed: {:?}", e);
        }
    }
}

examples/spg_example.rs (line 32)

fn main() {
    // Setting up logging
    std::env::set_var("RUST_LOG", "info");
    let _ = Tracer::default().with_normal_stdout_layer().build();

    // Convex function: f(x,y) = x^2 + y^2 + exp(x^2 + y^2)
    // This function is convex and has a minimum at (0, 0)
    let f_and_g = |x: &DVector<f64>| -> FuncEvalMultivariate {
        let x1 = x[0];
        let x2 = x[1];

        // Function value
        let f = x1.powi(2) + x2.powi(2) + (x1.powi(2) + x2.powi(2)).exp();

        // Gradient
        let exp_term = (x1.powi(2) + x2.powi(2)).exp();
        let g1 = 2.0 * x1 * (1.0 + exp_term);
        let g2 = 2.0 * x2 * (1.0 + exp_term);
        let g = DVector::from_vec(vec![g1, g2]);

        FuncEvalMultivariate::new(f, g)
    };

    // Setting up the line search (backtracking)
    let armijo_factor = 1e-4;
    let beta = 0.5;
    let mut ls = BackTracking::new(armijo_factor, beta);

    // Setting up the solver with box constraints
    let tol = 1e-6;
    let x0 = DVector::from_vec(vec![0.5, 0.5]); // Starting point
    let lower_bound = DVector::from_vec(vec![-1.0, -1.0]); // -1 <= x <= 1, -1 <= y <= 1
    let upper_bound = DVector::from_vec(vec![1.0, 1.0]);

    // Create a mutable oracle for SPG initialization
    let mut oracle_for_init = f_and_g;
    let mut solver = SpectralProjectedGradient::new(
        tol,
        x0.clone(),
        &mut oracle_for_init,
        lower_bound.clone(),
        upper_bound.clone(),
    );

    // Running the solver
    let max_iter_solver = 100;
    let max_iter_line_search = 20;

    println!("=== Spectral Projected Gradient (SPG) Example ===");
    println!("Objective: f(x,y) = x^2 + y^2 + exp(x^2 + y^2) (convex)");
    println!("Global minimum: (0, 0) with f(0,0) = 1");
    println!("Constraints: -1 <= x <= 1, -1 <= y <= 1");
    println!("Starting point: {:?}", x0);
    println!("Lower bounds: {:?}", lower_bound);
    println!("Upper bounds: {:?}", upper_bound);
    println!("Tolerance: {}", tol);
    println!();

    match solver.minimize(
        &mut ls,
        f_and_g,
        max_iter_solver,
        max_iter_line_search,
        None,
    ) {
        Ok(()) => {
            let x = solver.x();
            let eval = f_and_g(x);
            println!("✅ Optimization completed successfully!");
            println!("Final iterate: {:?}", x);
            println!("Function value: {:.6}", eval.f());
            println!("Gradient norm: {:.6}", eval.g().norm());
            println!("Iterations: {}", solver.k());

            // Check constraint satisfaction
            println!("Constraint satisfaction:");
            for i in 0..x.len() {
                println!(
                    "  x[{}] = {:.6} (bounds: [{:.1}, {:.1}])",
                    i, x[i], lower_bound[i], upper_bound[i]
                );
            }

            // Check if we're close to the known minimum
            let true_min = DVector::from_vec(vec![0.0, 0.0]);
            let distance_to_min = (x - true_min).norm();
            println!("Distance to true minimum: {:.6}", distance_to_min);
            println!("Expected function value: 1.0");

            // Show some properties of SPG
            println!("SPG properties:");
            println!("  - Uses spectral step length estimation");
            println!("  - Handles box constraints efficiently");
            println!("  - Often faster than standard projected gradient");
        }
        Err(e) => {
            println!("❌ Optimization failed: {:?}", e);
        }
    }
}

Trait Implementations

impl LineSearch for BackTracking

fn compute_step_len( &mut self, x_k: &DVector<Floating>, eval_x_k: &FuncEvalMultivariate, direction_k: &DVector<Floating>, oracle: &mut impl FnMut(&DVector<Floating>) -> FuncEvalMultivariate, max_iter: usize, ) -> Floating

impl SufficientDecreaseCondition for BackTracking

fn c1(&self) -> Floating

fn sufficient_decrease( &self, f_k: &Floating, f_kp1: &Floating, grad_k: &DVector<Floating>, t: &Floating, direction_k: &DVector<Floating>, ) -> bool