PaperlayerView exact revision on arXiv

Source-linked AI summary

The Global Asymptotic Stability Problem for Linear MPC Is Undecidable

Johan Löfberg

arXiv:2609.09930v1math.OCcs.SYeess.SY

TL;DR

The paper asks whether global asymptotic stability can be decided for constrained finite-horizon linear MPC, a problem not settled by results for broader piecewise-affine systems. It reduces saturated-system stability to MPC through exact horizon-one constructions, establishing undecidability under several constraint formulations. The result persists with identity weights, unique optimizers, global feasibility, and, in a separate reduction, fixed dimensions.

  • Problem

    Undecidability for broader piecewise-affine systems does not settle whether stability is decidable when feedback must be generated by a finite-horizon MPC quadratic program.

    Source: §II · p. 2

  • Method

    Computable reductions construct horizon-one MPC instances whose closed-loop components reproduce saturated linear dynamics or rational continuous piecewise-affine dynamics.

    Source: §II · pp. 2–3, §V · p. 6

  • Results

    Global asymptotic-stability decision for constrained finite-horizon linear MPC is undecidable, including horizon-one instances with identity weights, unique optimizers, and feasibility for every state.

    Source: §II · p. 2

  • Takeaways & Limitations

    The undecidability result does not preclude stabilizing controller design or rigorous certificates for particular controllers, and some subclasses remain decidable.

    Source: §V · p. 6

    The impossibility concerns a universal decision algorithm; outside decidable subclasses, a general method must allow inconclusive answers, restrict itself to sufficient conditions, or fail to terminate on some instances.

    Source: §V · p. 6

Abstract

from arXiv · show

We prove that deciding global asymptotic stability for constrained finite-horizon linear model predictive control is undecidable. This holds at horizon one with identity state, input, and terminal weights, unique optimizers, and global feasibility. Separate reductions cover predicted-state boxes, hard input boxes, and quadratically softened input boxes. A fourth reduction fixes the state and input dimensions to three and six. Hence undecidability is not caused by long horizons, growing dimensions, failures of recursive feasibility, or nonuniqueness.

I. INTRODUCTION

MPC handles dynamics and constraints through online optimization, but finite-horizon formulations do not guarantee closed-loop stability by themselves. This paper asks whether global asymptotic stability can be decided for constrained linear MPC and establishes undecidability even at horizon one with identity weights.

I. INTRODUCTION

  • Stability is not intrinsic to basic finite-horizon MPC; it may require design ingredients, a sufficiently long horizon under controllability conditions, or a posteriori analysis.A posteriori analysis can study the optimization-based controller directly or its explicit piecewise-affine representation.Source: §I · p. 1
  • The standard controller optimizes predicted state and input sequences subject to linear prediction dynamics and polyhedral constraints, with quadratic weights Q, R, and P.The hard-constrained optimizer is unique under the stated positive-definiteness condition, and a positive-definite slack penalty gives uniqueness in the softened construction.Source: §I · p. 1
  • The decision problem asks whether every trajectory initialized in the feasible set remains feasible and converges to the origin, with the origin also Lyapunov stable relative to that set.The feasible set X_N consists of states for which the MPC problem is feasible.Source: §I · p. 1
  • Global asymptotic stability for constrained finite-horizon linear MPC is undecidable, even with horizon one and identity state, input, and terminal weights.A separate reduction fixes the state and input dimensions at 3 and 6.Source: §I · p. 2

II. A KNOWN UNDECIDABLE STABILITY PROBLEM

Undecidability for piecewise-affine systems does not directly settle the question for MPC, whose feedback must arise from a structured quadratic program. The paper reduces saturated-system stability to MPC stability through exact horizon-one realizations.

II. A KNOWN UNDECIDABLE STABILITY PROBLEM

  • Undecidability for broader continuous piecewise-affine classes does not itself transfer to MPC, because MPC feedback must be the optimizer of a plant-consistent finite-horizon quadratic program.The needed direction is a stability-preserving construction from a known undecidable problem to MPC.Source: §II · p. 2
  • Saturated linear-system stability is undecidable for rational matrices, providing the source problem for the reductions.The paper also cites an undecidable fixed-dimensional continuous piecewise-affine source problem on R^3 fixing the origin.Source: §II · p. 2
  • The MPC constructions use separate predicted-state, hard-input, and quadratically softened-input constraint reductions, and each is feasible for every state.The constructions make the origin an equilibrium; recursive feasibility is therefore not the mechanism encoding undecidability.Source: §II · p. 2
  • Theorem 3 establishes undecidability for horizon-one MPC with identity weights, unique optimizers, and feasibility for every state across three constraint subclasses.The subclasses use predicted-state/terminal boxes, hard input boxes, or quadratically softened input boxes.Source: §II · p. 2
  • A computable many-one reduction maps each rational matrix A to an MPC instance whose relevant closed-loop component exactly reproduces x_k+1 = sat(Ax_k).The two systems are globally asymptotically stable together, so a decision algorithm for MPC would decide the saturated-system problem.Source: §II · p. 3

A. Predicted-state constraints only

The predicted-state-only construction realizes saturated linear dynamics through a horizon-one MPC problem. Its stability undecidability holds both with a globally feasible problem and on a compact invariant feasible set.

A. Predicted-state constraints only

  • With no input constraints, the only inequalities are a hard box on the one-step predicted state, equivalently a terminal or predicted-output constraint.The original construction has feasible set R^n; adding the current-state restriction yields the compact invariant variant.Source: A. Predicted-state constraints only · p. 3
  • The MPC optimizer is the Euclidean projection of Ax_k onto B_n, yielding z* = sat(Ax_k) with global feasibility and a unique optimizer.Choosing z = 0 makes the problem feasible for every current state; strict convexity gives uniqueness.Source: A. Predicted-state constraints only · p. 3
  • Stability undecidability persists when the predicted-state-only construction is restricted to the compact invariant feasible polytope B_n.The source system enters B_n after one step, so global convergence follows from stability relative to B_n.Source: A. Predicted-state constraints only · p. 3

B. Input constraints only

A hard input box can realize saturated linear dynamics in MPC. A memoryless state augmentation preserves global asymptotic stability, allowing the construction to transfer the source system's stability question.

B. Input constraints only

  • For continuous f and h vanishing at the origin, the augmented system (z_{k+1}, y_{k+1}) = (f(z_k), h(z_k)) preserves global asymptotic stability exactly.The augmented origin is globally asymptotically stable if and only if the origin of z_{k+1} = f(z_k) is.Source: B. Input constraints only · p. 3
  • The input box is the construction's only inequality constraint.The controller is described as horizon one, and the construction introduces an augmented state.Source: B. Input constraints only · pp. 3–4
  • The hard-input realization is globally asymptotically stable if and only if z_{k+1} = sat(Az_k) is globally asymptotically stable.The optimizer depends only on z_k, not on the memoryless component y_k.Source: B. Input constraints only · p. 4

C. Quadratically softened input constraints

A quadratic slack softens the input box while recovering saturated linear dynamics in the closed loop. The resulting optimization remains feasible for every current state without imposing hard bounds on physical states or inputs.

C. Quadratically softened input constraints

  • An unbounded nonnegative slack makes the problem feasible for every current state without hard bounds on physical states or inputs.The inequalities remain hard constraints of the quadratic program, but do not impose hard bounds on those physical variables.Source: C. Quadratically softened input… · p. 4
  • For each coordinate, the unique optimizer is u*_i = (v_i + sat(v_i))/2, with slack s*_i = (|u*_i| - 1)+.Inside the unit interval u*_i = v_i; outside it, u*_i is halfway between v_i and its saturation.Source: C. Quadratically softened input… · p. 4
  • The soft-input construction's complete augmented closed loop is globally asymptotically stable if and only if the source saturated system is.The first closed-loop component obeys the source update; the remaining successor component is continuous and vanishes at the origin.Source: C. Quadratically softened input… · p. 4

IV. UNDECIDABILITY WITH FIXED STATE AND INPUT DIMENSIONS

This section lifts rational continuous PWA dynamics into a fixed-dimensional, horizon-one MPC formulation. The epigraph construction realizes the target map under identity-weight costs, establishing undecidability with three states and six inputs.

Exact epigraph realization

  • The construction uses an epigraph lifting of continuous PWA maps, while inflated components make the epigraph corner optimal for the plant-consistent identity-weight quadratic.Inverse parametric optimization already represents continuous PWA maps through LPs or QPs; the contribution is their realization by this prescribed MPC quadratic.Source: §IV · pp. 4–5

Nonnegative epigraph decomposition

  • Each target-map coordinate is decomposed using effectively computable rational convex PWA functions p_i and q_i that both upper-bound the coordinate's absolute value.Each function is represented as the maximum of finitely many rational affine functions.Source: §IV · p. 5
  • The decomposition uses a max-affine Lipschitz bound to construct the envelopes; the required operations are effective, though the piece count may grow.The construction sets K_i = 2(L_ai + L_bi).Source: §IV · p. 5

Fixed-dimensional MPC undecidability

  • Undecidability holds for horizon-one MPC with nx = 3 and nu = 6, identity weights, a unique optimizer, and feasibility for every state.The constructed closed-loop map exactly matches the source continuous PWA map, so their global asymptotic-stability outcomes coincide.Source: §IV · pp. 5–6

V. SUMMARY AND CONCLUSIONS

The conclusions establish undecidability across several constrained MPC realizations, including a fixed-dimensional construction. The paper distinguishes this universal decision barrier from controller design and identifies remaining scope boundaries.

Summary and conclusions

  • Undecidability holds across three horizon-one constraint realizations and a fixed-dimensional realization, with unique optimizers and global feasibility.The predicted-state variant also establishes undecidability on the compact invariant feasible set [−1, 1]^n.Source: §V · p. 6
  • The impossibility rules out a universal stability decision algorithm, not controller design or verification through sufficient conditions.Outside decidable subclasses, a general method must permit inconclusive answers, restrict itself to sufficient conditions, or fail to terminate on some instances.Source: §V · p. 6
  • Whether undecidability persists for few-state plants with scalar input or under a fixed simple constraint structure remains open.The fixed-dimensional construction uses six inputs and general mixed state-input inequalities.Source: §V · p. 6
Loading 2609.09930v1…