Descent: Gradient, Newton, Interior-Point

Every physics solver and every control step is an optimizer wearing a costume. A contact solve, a QP for a torque, an MPC horizon: each reduces to move the current guess downhill until the residual is small. How fast that happens is set by two choices, how much curvature you use and how you respect constraints.

Gradient descent: first order

Gradient descent follows the steepest slope with a scalar step $\alpha$,

$$x_{k+1} = x_k - \alpha\,\nabla f(x_k).$$

On a strongly convex quadratic $f(x) = \tfrac{1}{2}x^{\top}Qx$ with eigenvalues $\mu = \lambda_{\min}$ and $L = \lambda_{\max}$, the optimal fixed step $\alpha = 2/(L+\mu)$ contracts the error by a fixed factor each step,

$$\lVert x_{k} \rVert \le \left(\frac{\kappa - 1}{\kappa + 1}\right)^{k}\lVert x_0 \rVert, \qquad \kappa = \frac{L}{\mu}.$$

A single scalar $\alpha$ cannot match two different curvatures at once. As $\kappa \to \infty$ the rate $\to 1$ and the iterates zigzag across the narrow valley, taking many steps to crawl along its floor.¹

Newton: second order

Newton's method rescales the gradient by the local curvature,

$$x_{k+1} = x_k - \big(\nabla^2 f(x_k)\big)^{-1}\nabla f(x_k).$$

Multiplying by $(\nabla^2 f)^{-1}$ makes the step affine invariant: it is unchanged if you rescale the coordinates, so the condition number stops mattering. On a quadratic the model is exact and Newton reaches the minimum in one step from any start, independent of $\kappa$.²

A quadratic, by hand

Take $Q = \begin{bmatrix} 10 & 0 \\ 0 & 1 \end{bmatrix}$, so $\kappa = 10$, with $\nabla f(x) = Qx$ and $\nabla^2 f = Q$. Start at $x_0 = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$, where $\nabla f(x_0) = \begin{bmatrix} 10 \\ 1 \end{bmatrix}$.

One gradient step with $\alpha = 1/L = 0.1$ gives

$$x_1 = \begin{bmatrix} 1 \\ 1 \end{bmatrix} - 0.1\begin{bmatrix} 10 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0.9 \end{bmatrix}.$$

The stiff coordinate ($\lambda = 10$) is solved, but the soft coordinate ($\lambda = 1$) barely moved. Pushing $\alpha$ up to fix $x_2$ faster overshoots $x_1$: stability caps $\alpha < 2/L = 0.2$, yet the soft axis wants $\alpha \approx 1$. That gap is $\kappa$.

Newton uses $Q^{-1} = \begin{bmatrix} 0.1 & 0 \\ 0 & 1 \end{bmatrix}$ and each coordinate gets its own curvature,

$$x_1 = x_0 - Q^{-1}Qx_0 = \begin{bmatrix} 1 \\ 1 \end{bmatrix} - \begin{bmatrix} 0.1 & 0 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} 10 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \end{bmatrix} - \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}.$$

One step, exactly on the minimum, for any $\kappa$.

Interior-point: descend from strictly inside

Contacts, friction cones, and actuator limits are inequality constraints $g_i(x) \le 0$. An interior-point method replaces them with a smooth log barrier that blows up at the boundary,

$$\min_x\; t\,f(x) - \sum_i \log\!\big(-g_i(x)\big).$$

For finite $t$ the barrier keeps every iterate strictly feasible; the minimizer $x^{\star}(t)$ traces the central path. Raising $t$ shrinks the barrier's pull, and $x^{\star}(t) \to x^{\star}$ approaches the true optimum from inside the feasible set. Each recentering is a Newton solve, so a QP needs only a handful of outer iterations.²

Descent on an ill-conditioned quadraticinteractive

condition number κ = 10

gradient descentNewtoninterior-point

gradient descent

25 steps

Newton

1 step

interior-point

8 steps

iter 0/25 · f = 5.500

PlayStepReset

What runs inside a solver

This is the machinery behind a contact or control step, not an analogy for it. Projected Gauss-Seidel, the sequential-impulse method from the constraint-solvers article, updates one impulse at a time using the diagonal $A_{ii}$ of the Delassus operator: it is coordinate-wise descent on the contact LCP. Its rate is governed by the conditioning of $A$, and a tall stack or a large mass ratio makes $\kappa(A)$ huge, which is exactly why PGS crawls: like gradient descent on the stretched quadratic, it needs about one sweep per unit of coupling. Newton and convex solvers instead use the full curvature to take affine-invariant steps that do not degrade with $\kappa$, and interior-point is what a QP contact model or an MPC step runs to keep non-penetration and cone constraints satisfied while descending from strictly inside. The engine's choice of solver is a bet on how badly conditioned its constraints are.

Footnotes

1. Nocedal & Wright, Numerical Optimization (2006). ↩

2. Boyd & Vandenberghe, Convex Optimization (2004). ↩ ↩²