Projected gradient descent

Projected gradient descent is a local optimizer for smooth functions with box bounds. It takes a step along the negative gradient, then clamps each parameter to its permitted interval. This gives a simple way to keep iterates feasible without storing a Hessian approximation.

API reference

When to use it

Consider projected gradient descent when each parameter has an independent lower or upper bound and you want a method with little working storage. It is also a useful baseline for comparing more elaborate bound-constrained solvers. Gradient projection methods are discussed in Nocedal and Wright (2006).

For a smooth problem where curvature information could reduce the number of iterations, compare L-BFGS-B. For an unconstrained problem, use gradient descent or L-BFGS. Linear and nonlinear constraints need a method that supports those blocks, such as SLSQP.

The method follows local descent directions. Different starting points can lead to different constrained minima, and a poorly scaled objective can make progress slow even though every published iterate satisfies the box bounds.

How it works

Basin first projects the starting point into the box, then evaluates the objective and gradient there. At each iteration it chooses a step length, moves along the negative gradient, and projects the result back into the box. Projection clamps each coordinate to its lower and upper bounds. Equal bounds pin a coordinate at a fixed value.

At a constrained minimum, the negative gradient can point out of the box. The relevant stationarity test measures the infinity norm of x - projection(x - gradient). This residual vanishes when a unit gradient step followed by projection returns to the same point. It accounts for active bounds, so it can vanish even when the raw gradient is nonzero.

ProjectedGradientDescent::new(alpha) uses a fixed step length. Basin also accepts a custom line search, but that search may evaluate unconstrained trial points before projection. Its decrease conditions do not automatically carry over to the projected point.

Example

This quadratic has its unconstrained minimum at [1.0, -2.0]. The box moves the constrained minimum to [0.5, -1.0], where the raw gradient is nonzero. The example declares bounds on the problem, uses a fixed step, and stops on the projected-gradient residual.

use basin::{
    BoxBounds, ConstraintDescription, ConstraintSet, Constraints, CostFunction,
    Executor, Gradient, ProjectedGradientDescent, Termination,
};
use std::convert::Infallible;

struct BoundedQuadratic {
    lower: Vec<f64>,
    upper: Vec<f64>,
}

impl Constraints for BoundedQuadratic {
    type Set = ConstraintSet<BoxBounds<Vec<f64>>>;

    fn constraints(
        &self,
    ) -> <Self::Set as ConstraintDescription>::Borrowed<'_> {
        ConstraintSet::new()
            .with_bounds(BoxBounds::new(Some(&self.lower), Some(&self.upper)))
    }
}

impl CostFunction for BoundedQuadratic {
    type Param = Vec<f64>;
    type Output = f64;
    type Error = Infallible;

    fn cost(&self, x: &Self::Param) -> Result<f64, Self::Error> {
        Ok((x[0] - 1.0).powi(2) + 4.0 * (x[1] + 2.0).powi(2))
    }
}

impl Gradient for BoundedQuadratic {
    type Gradient = Vec<f64>;

    fn gradient(&self, x: &Self::Param) -> Result<Self::Gradient, Self::Error> {
        Ok(vec![2.0 * (x[0] - 1.0), 8.0 * (x[1] + 2.0)])
    }
}

fn main() {
    let problem = BoundedQuadratic {
        lower: vec![-1.0, -1.0],
        upper: vec![0.5, 1.0],
    };
    let solver = ProjectedGradientDescent::new(0.1)
        .with_absolute_projected_gradient_tolerance(1e-8);

    let result = Executor::from_start(problem, solver, vec![-3.0, 5.0])
        .max_iter(200)
        .run()
        .unwrap();

    assert!(matches!(
        result.report.termination,
        Termination::Converged(_)
    ));
    assert!((result.param()[0] - 0.5).abs() < 1e-7);
    assert!((result.param()[1] + 1.0).abs() < 1e-7);
}

The starting point lies outside the box. Initialization projects it to [-1.0, 1.0] before the first objective or gradient evaluation.

Practical considerations

Choose a step for your objective’s scale

A small fixed step can make progress slow, while an overly large one can cause oscillation or repeated jumps between bounds. Rescale parameters and check objective values as you tune the step. The value 0.1 is appropriate for the example’s curvature; it is not a general default.

Use a projected stationarity test

Configure with_absolute_projected_gradient_tolerance for the infinity norm of x - projection(x - gradient). The check is disabled by default; zero tests exact stationarity. Choose the tolerance for your parameter units and derivative accuracy. Optional step and cost-change checks can also stop a run, but a small observed change alone does not establish stationarity.

Keep budgets on the executor

Set iteration and evaluation limits there, then inspect the termination report. Reaching a budget and satisfying a convergence test give different reasons for stopping.

Check where the objective is defined

The fixed-step strategy evaluates the projected iterates. A custom line search may call your objective and gradient outside the box. If those evaluations are invalid, use a fixed step or a solver with a bound-aware search, such as L-BFGS-B.

Implementation

Bounds belong to the problem through Constraints, using a box-only ConstraintSet<BoxBounds<V>>. The solver requires this declaration and rejects unsupported constraint blocks. It validates the bounds and projects the seed before publishing the first evaluated point through FirstOrderState.

Each accepted iteration publishes the projected point with its matching objective and gradient. The solver stores the step strategy; it does not keep curvature history or momentum. Fresh initialization resets the line search, while exact solver-and-state checkpoints retain its history.

Supported parameter types are Vec<F>, nalgebra::DVector<F>, ndarray::Array1<F>, and faer::Col<F>, with F = f32 or f64. The method uses vector operations and coordinate-wise clamping without matrix factorizations or a BLAS/LAPACK provider. Custom line searches and optional convergence checks can require additional vector capabilities. See the API’s Backends section for the requirements.