Linear-quadratic regulator (LQR)

Overview

A linear-quadratic regulator (LQR) gives linear state feedback for a linear system that minimises a quadratic cost. Its gain comes from a Riccati equation. Over a finite horizon the Riccati solution S(t) is time-varying, and the cost-to-go is quadratic in the state 1311.1839 §2. The paper's cost penalises the zero-moment-point (ZMP) tracking error ȳ = y − y_d along the horizon and at the final time 1311.1839 eq. 1. Its cost-to-go has the form x̄ᵀS(t)x̄ + s₁(t)ᵀx̄ + s₀(t), with feedback ū* = −K(t)x̄ 1311.1839 eq. 5.

The paper does not apply ū* as the controller output. The LQR input can be unachievable under actuator limits, friction and contacts. The controller therefore uses the cost-to-go to build a surrogate value function V and gives that to a full-robot QP 1311.1839 §2 1311.1839 eq. 6. Card: An Efficiently Solvable Quadratic Program for Stabilizing Dynamic Locomotion.

The second card uses the same kind of Riccati recursion on a different problem: the linearised optimal-control QP inside a sequential quadratic programming (SQP) model predictive controller for legged robots. There the recursion runs backward over the horizon, and the dynamics and cost change from node to node 2506.07823 §2.3 2506.07823 eq. 5.

Variants

Time-varying LQR for walking

The COM height changes over time and is known. The ZMP model is then linear with time-varying dynamics, and no linearisation is needed 1311.1839 §2. For walking, the tracking target is a ZMP plan made by linear interpolation between step locations. The final cost is Q_f = S, and the COM trajectory is found by simulating the closed loop 1311.1839 §5. The surrogate V from this LQR enters the QP objective 1311.1839 §2 1311.1839 eq. 6 1311.1839 eq. 10. Card: An Efficiently Solvable Quadratic Program for Stabilizing Dynamic Locomotion.

Time-invariant LQR for balancing

For balancing, the COM height is held constant. The LQR is solved once, with output weight Q = I regulating the ZMP to (0, 0). The cost-to-go is x̄ᵀSx̄, with S from the algebraic Riccati equation 1311.1839 §5. The paper says constant height has "minimal practical effect" on balancing, and gives no measurement for walking 1311.1839 §5. Card: An Efficiently Solvable Quadratic Program for Stabilizing Dynamic Locomotion.

Riccati recursion with a parallel scan inside an MPC

Each control call runs one SQP iteration on the linearised problem. The backward Riccati recursion gives feedback gains K_i and feed-forward terms k_i for every node, and a forward pass turns them into state and control steps 2506.07823 §2.3 2506.07823 eq. 5 2506.07823 eq. 6. The sequential recursion costs O(N(n+m)³) for horizon N, with state size n and input size m 2506.07823 §2.3.

The paper observes that the cost-to-go between any two nodes keeps the same quadratic form, and that combining two such pieces is associative. A parallel scan over those pieces produces the value-function matrices for all nodes in O(log N) depth 2506.07823 §2.4 2506.07823 eq. 8. The multiplier step is then computed for all nodes at once 2506.07823 eq. 7. Card: Primal-Dual iLQR for GPU-Accelerated Learning and Control in Legged Robots.

Two cautions from the card. The scan's combination rule has symbols that the paper does not resolve, so check it against a rollout on a small problem 2506.07823 eq. 11. Its O(log N) depth is an asymptotic bound, not a wall-clock claim, and the GPU version loses to a CPU solver on short whole-body horizons 2506.07823 §4.2.

When to use which

The paper of the first card reports no timing for the LQR step on its own. Its full controller takes about 1 ms per step, of which about 0.8 ms is QP setup 1311.1839 §5. The GPU solver of the second card adds about 1 ms of host-device transfer per call 2506.07823 §4.1.

Implementation sketch

The first block follows the time-varying and time-invariant solves of the first card. The A, B and C names stand for the ZMP model of 1311.1839 §2. Riccati details and numerical method are the implementer's choice. The second block is the per-node backward step of the second card, in the form of its equation 5.

# Offline: time-varying LQR for walking  [arxiv:1311.1839 §5]
def solve_tvlqr(model_at, Q, Q_f, t_f, dt):
    # Final condition from the final cost: S(t_f) = Q_f  [arxiv:1311.1839 §5]
    S = Q_f
    # Integrate the Riccati equation backward through the horizon  [§2]
    for t in reversed(time_grid(0, t_f, dt)):
        A, B = model_at(t)  # ZMP model at time t  [arxiv:1311.1839 §2]
        S = riccati_step_backward(S, A, B, Q, dt)
    # S(t) defines the cost-to-go x̄ᵀS(t)x̄  [arxiv:1311.1839 §2]
    return S

# Balancing: constant height, so S is constant  [arxiv:1311.1839 §5]
def solve_balance_lqr(A, B, Q):
    # Algebraic Riccati equation, solved once  [arxiv:1311.1839 §5]
    return solve_are(A, B, Q)

# Surrogate value for the QP objective  [§2] [eq. 6]
def surrogate_v(x_bar, x_bar_dot, S, s1, Q, y_bar):
    # Gradient of the cost-to-go w.r.t. x̄  [arxiv:1311.1839 §2]
    dJ_dx = 2 * S @ x_bar + s1
    # V = ȳᵀQȳ + (∂J*/∂x̄) ẋ̄  [arxiv:1311.1839 eq. 6]
    return y_bar @ Q @ y_bar + dJ_dx @ x_bar_dot

# One backward Riccati step at node i  [arxiv:2506.07823 eq. 5]
def riccati_step(A, B, b, Q, S, R, q, r, P_next, p_next):
    # Shorthand terms for the node  [arxiv:2506.07823 eq. 5]
    G = R + B.T @ P_next @ B
    H = S + B.T @ P_next @ A
    h = B.T @ (p_next + P_next @ b) + r
    # Feedback gain and feed-forward term  [arxiv:2506.07823 eq. 5]
    K = -solve(G, H)
    k = -solve(G, h)
    # Value-function matrices passed to the previous node  [arxiv:2506.07823 eq. 5]
    P = Q + A.T @ P_next @ A + K.T @ H
    p = q + A.T @ (p_next + P_next @ b) + K.T @ h
    return K, k, P, p

Contradictions

No direct disagreement between the two cards. They solve different problems, so their timing figures are not comparable. The first card reports a plan-time LQR solve and a full 1 ms controller for a 34-DOF humanoid, on a 2.1 GHz laptop 1311.1839 §5. The second reports per-tick MPC solve times for a quadruped, on a desktop GPU 2506.07823 §4. Both sets of numbers are author-reported and come from simulation.

Papers

• An Efficiently Solvable Quadratic Program for Stabilizing Dynamic Locomotion: a time-varying LQR on a ZMP model gives a value-function surrogate for a humanoid walking QP.
• Primal-Dual iLQR for GPU-Accelerated Learning and Control in Legged Robots: a Riccati recursion computed with a parallel scan, inside a GPU SQP model predictive controller for legged robots.