Module least_squares 

Levenberg–Marquardt, constrained: minimizing a sum of squared residuals Σ r(x)² among the points where other residuals c(x) vanish, from their values and Jacobians.

Each step solves the problem linearized at the current point — minimize |r + J_r δ|² + δᵀ(B + λD)δ subject to c + J_c δ = 0, or as near to it as first order gets — by the null-space method. D is Marquardt’s scaling, the diagonal of the Jacobians’ normal matrix, and λ shrinks after every step taken and grows after every one turned down: Gauss–Newton near a solution, gradient descent far from one. B is what Gauss–Newton leaves out — the curvature of the constraints, weighted by how hard the sum pulls against them — estimated from the steps taken (a symmetric rank-one update, along the constraints only): without it, wherever the sum cannot reach zero against curved constraints, steps along them overshoot and the minimizer zig-zags. That curvature is as often negative as positive — a mate pulled outwards curves the sum down along it — so B is not kept positive, as a BFGS estimate would be: one that cannot learn a negative curvature left an arm’s drags creeping towards the preferences’ minimum until they ran out of steps. Only J_rᵀJ_r + B + λD, over the directions the constraints leave free, must be positive, and λ grows until it is. Where a step it proposed is turned down, the step is tried again without it, and it is learned afresh if that does better — a configuration passing through a singular one changes it abruptly.

Keeping c exact, rather than adding it to the sum with a large weight, is what makes the sum a pure preference: it can never buy itself a little lower with a little violation of c — which, wherever a long lever multiplies that violation, is a lot of motion.

Nor are the two weighed against each other to judge a step. A step is taken where it definitely lowers either the sum or the constraints’ violation |c| — against the point it starts from and against every point taken before (a filter), so the two cannot trade back and forth forever. A merit Σ r² + ρ |c| would need ρ above the multipliers the sum pulls against the constraints with, and those grow without bound at a singular configuration — two links in line, say — where the merit’s own width then hides every step that does reduce the violation.

A variable no residual depends on is never moved, and a step never has a component along a direction no residual depends on — unlike a quasi-Newton method on the sum alone, whose curvature estimate grows without bound along such a direction until rounding noise in the gradient throws it arbitrarily far.

Every value is an honest enclosure. The steps themselves are free choices — any step is a valid seed for the next — so they are sharpened; whether a step is taken is not, and it is taken only where it definitely improves. So the minimizer needs no tolerance: it stops where no step can definitely improve on where it is, which is as near the minimum as the residuals’ own uncertainty can tell.

Structs

Euclidean

The variables themselves, as points: a step is added to them.

Evaluation

The residuals at a point: those that must vanish, and those whose squares are minimized.

Options

How long minimize may try, and how far a step may go.

Outcome

Where minimize ended, and how it got there.

Rows

Residuals, and their Jacobian row by row.

Enums

Rejection

Why a step was turned down.

Stop

Why minimize stopped where it did.

Traits

Space

Where minimize’s points are, and how a step moves one: the variables themselves, a step added to them (Euclidean) — or a manifold, where a step is taken from a point along its tangent space (a pose by the exponential map of a twist, say), and the Jacobians evaluated at a point are by steps from that point.

Functions

minimize

Minimizes Σ r(x)² from x0 among the points where c(x) = 0, with evaluate giving both and their Jacobians — by steps from the point, in space — and None where they cannot be evaluated, which makes the point infeasible. Where the constraints cannot all hold, it ends where they come closest. Always returns the best point found; whether it is good enough is the caller’s question.