---
kind: concept
slug: linear-quadratic-regulator
title: Linear-quadratic regulator (LQR)
summary: >-
  Optimal linear state feedback for a linear system with a quadratic cost, found by solving a Riccati equation. Two cards use it in legged and humanoid control: a time-varying LQR gives a value-function surrogate for a walking QP, and a Riccati recursion computed by a parallel scan solves the inner problem of a GPU MPC. All results are author-reported.
tags: [control, optimal-control, humanoid-locomotion, legged-locomotion]
papers: ["1311.1839", "2506.07823"]
related: [model-predictive-control, active-set-method, parallel-scan]
status: draft
updated_at: 2026-10-25
---

## 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 [arxiv: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 [arxiv: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̄
[arxiv: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 [arxiv:1311.1839 §2] [arxiv:1311.1839 eq. 6].
Card: [An Efficiently Solvable Quadratic Program for Stabilizing Dynamic Locomotion](/papers/1311.1839).

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 [arxiv:2506.07823 §2.3] [arxiv: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 [arxiv: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 [arxiv:1311.1839 §5]. The surrogate V from
this LQR enters the QP objective [arxiv:1311.1839 §2] [arxiv:1311.1839 eq. 6]
[arxiv:1311.1839 eq. 10]. Card:
[An Efficiently Solvable Quadratic Program for Stabilizing Dynamic Locomotion](/papers/1311.1839).

### 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 [arxiv:1311.1839 §5]. The paper says
constant height has "minimal practical effect" on balancing, and gives no
measurement for walking [arxiv:1311.1839 §5]. Card:
[An Efficiently Solvable Quadratic Program for Stabilizing Dynamic Locomotion](/papers/1311.1839).

### 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
[arxiv:2506.07823 §2.3] [arxiv:2506.07823 eq. 5] [arxiv:2506.07823 eq. 6].
The sequential recursion costs O(N(n+m)³) for horizon N, with state size n and
input size m [arxiv: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 [arxiv:2506.07823 §2.4] [arxiv:2506.07823 eq. 8]. The
multiplier step is then computed for all nodes at once
[arxiv:2506.07823 eq. 7]. Card:
[Primal-Dual iLQR for GPU-Accelerated Learning and Control in Legged Robots](/papers/2506.07823).

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
[arxiv: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 [arxiv:2506.07823 §4.2].

## When to use which

| Situation | Use | Why |
|---|---|---|
| Fixed COM height, balancing about one point | Time-invariant LQR, solved once | Constant S from the algebraic Riccati equation, Q = I [arxiv:1311.1839 §5] |
| COM height varies over time and is known | Time-varying LQR | Time-varying linear dynamics without linearisation [arxiv:1311.1839 §2] |
| Actuator limits, friction or contacts can make the LQR input unreachable | Pass the cost-to-go as a surrogate V into a constrained QP | The LQR input may be unachievable, so V is used in the QP instead [arxiv:1311.1839 §2] [arxiv:1311.1839 eq. 6] |
| Tight online latency budget for a walking plan | Solve the time-varying LQR before the walk | Plan-time solve takes about ¼ s for 10 m in unoptimised MATLAB, and is not an online cost [arxiv:1311.1839 §5] |
| Per-tick MPC for a legged robot on a GPU, horizon of 50 or more nodes | Riccati recursion with a parallel scan, inside a GPU SQP loop | Scan depth is O(log N). The paper reports 50 Hz on the whole-body model at 200 nodes [arxiv:2506.07823 §2.4] [arxiv:2506.07823 §4.2] |
| Short horizon or CPU only, whole-body model | A CPU solver | The paper's GPU version is slower than crocoddyl below 80 nodes on the whole-body model [arxiv:2506.07823 §4.2] |
| Planner inside a learning loop with thousands of simulated robots | Batched JAX version of the scan solver | 4096 environments, each with its own MPC [arxiv:2506.07823 §4.4] |

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
[arxiv:1311.1839 §5]. The GPU solver of the second card adds about 1 ms of
host-device transfer per call [arxiv: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
[arxiv: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.

```pseudocode
# 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
```

```pseudocode
# 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
[arxiv:1311.1839 §5]. The second reports per-tick MPC solve times for a
quadruped, on a desktop GPU [arxiv:2506.07823 §4]. Both sets of numbers are
author-reported and come from simulation.

## Papers

- [An Efficiently Solvable Quadratic Program for Stabilizing Dynamic Locomotion](/papers/1311.1839): 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](/papers/2506.07823): a Riccati recursion computed with a parallel scan, inside a GPU SQP model predictive controller for legged robots.