Source-linked AI summary
Worst-Case Finite-Horizon Analysis of Perturbed LQR via Performance Estimation Problem
Anthony Couthures, Gianluca Bianchin, Julien M. Hendrickx
TL;DR
Finite-horizon deployment of LQR under parametric uncertainty is not fully captured by approaches focused on asymptotic behavior or relaxed LTV bounds. The paper uses PEP and operator interpolation to formulate an exact worst-case search over LTI trajectories, finding transient growth associated with alignment of perturbations and initial conditions. Its numerical comparisons place PEP performance bounds between IQC upper bounds and a pseudospectral-heuristic lower bound.
Problem
Robust-control certificates often assess asymptotic behavior or specific perturbations, leaving finite-horizon LQR performance under static LTI uncertainty less directly characterized.
Source: §I · p. 1Method
PEP uses operator interpolation to formulate the search over finite-horizon LTI trajectories as a rank-constrained SDP while retaining sequence variables for worst-case reconstruction.
Source: §I · p. 1, A. The Abstract Optimization Problem · p. 3Results
Finite-horizon LTI perturbations align with specific initial conditions to drive transient growth, and PEP bounds sit between IQC upper bounds and a pseudospectral-heuristic lower bound.
Source: §VI · p. 6, §V · p. 6Takeaways & Limitations
Worst-case finite-horizon behavior can shift between spiraling two-dimensional invariant subspaces and monotonic one-dimensional slow manifolds as the horizon changes.
Source: A. Pseudospectral Targeting and… · p. 5, §VI · p. 6
Abstract
from arXiv · showhide
We propose an exact formulation to quantify the finite-horizon robustness of a Linear Quadratic Regulator (LQR) subject to norm-bounded Linear Time-Invariant (LTI) parametric uncertainties, using the Performance Estimation Problem (PEP) framework. Originally developed for optimization, this method allows us to reformulate the worst-case performance search as a rank-constrained Semidefinite Program (SDP). By applying operator interpolation, this formulation retains the sequence variables, allowing the worst-case to be explicitly reconstructed when a rank-one solution is found. This approach also opens new possibilities for the finite-horizon certification of broader system classes, such as data-driven models or nonlinear components. Using this framework, we observe that finite-horizon LTI perturbations do not simply follow asymptotic strategies. Instead, they align slowly decaying invariant manifolds with specific initial conditions to drive transient growth, causing a bifurcation in the worst-case behavior as the horizon length changes. Finally, we show numerically that our performance bounds sit between the upper bounds of Integral Quadratic Constraint (IQC) relaxations and a lower bound derived from a pseudospectral heuristic.
I. Introduction
LQRs are typically designed for known nominal models over infinite horizons, while real deployments face finite durations and parametric mismatch. Existing robust-control certificates often do not capture finite-horizon behavior without conservatism or difficulty reconstructing worst-case systems; this paper uses PEP to search over finite-horizon LTI trajectories.
I. Introduction
- Practical finite-duration control can face parametric mismatch between the design model and physical system, including variation from changing operating conditions or unmodeled nonlinearities.The introduction identifies varying circuit resistance as one example.Source: §I · p. 1
- Robust-control approaches including μ-analysis, robust Lyapunov functions, and IQCs provide theoretical certificates under perturbations.The cited discussion describes μ-analysis as evaluating worst-case stability and performance against structured uncertainties, and IQCs as bounding input-output behavior.Source: §I · p. 1
- Most robust-control certificates assess asymptotic behavior or specific perturbations, while finite-horizon IQC methods relax static LTI variations to LTV uncertainty and make worst cases difficult to reconstruct.The dual IQC variables are multipliers rather than system trajectories.Source: §I · p. 1
- PEP formulates finite-horizon LQR performance under norm-bounded LTI uncertainty as a rank-constrained SDP, retaining trajectories to extract worst-case initial conditions and perturbation matrices.Operator interpolation enforces the LTI behavior, avoiding the LTV conservatism of standard time-domain IQC formulations.Source: §I · p. 1
II. Problem Formulation
The paper evaluates a fixed infinite-horizon LQR gain over a finite horizon when system matrices have bounded static perturbations. Its finite-horizon cost can differ from nominal performance, while IQC exactness in the two-step example does not extend generally.
II. Problem Formulation
- The setup bounds static perturbations to the system matrices in spectral norm and evaluates the resulting dynamics under the nominal state-feedback law.The initial state is restricted to the unit ball without loss of generality; any bound γ scales the worst-case cost by γJ*_N.Source: §II · p. 2
- The evaluated finite-horizon cost sums closed-loop state penalties over N steps and includes a terminal penalty S.The fixed controller is the nominal infinite-horizon LQR gain, which remains suboptimal for this finite-horizon cost even when Δ = 0.Source: §II · p. 2
- 3.25 versus 2: for N = 2, the worst-case cost is 3.25, compared with 2 for the nominal loop.The worst-case perturbation leaves both eigenvalues at {0, 0} while strengthening coupling; spectral-radius-maximizing perturbations yield at most J2 ≈ 3.05.Source: §II · p. 2
- The IQC bound is exact for the N = 2 example, but over longer horizons LTV perturbations can steer the state at each step and overestimate the LTI worst case.A single LTI matrix of the same norm cannot always reproduce that step-by-step steering.Source: §II · p. 2
III. The Performance Estimation Problem (PEP) Reformulation
The main result recasts exact worst-case finite-horizon optimization as a rank-constrained SDP using PEP and operator interpolation.
III. The Performance Estimation Problem (PEP) Reformulation
- PEP converts the exact worst-case optimization into a rank-constrained SDP by abstracting discrete sequences, enforcing LTI behavior through operator interpolation, and lifting sequence variables into a positive semidefinite Gram matrix.The rank constraint is part of the exact formulation.Source: §III · p. 2
A. The Abstract Optimization Problem
The abstract formulation replaces explicit perturbation matrices with sequence variables, then encodes whether those sequences can arise from norm-bounded LTI operators through algebraic inequalities.
A. The Abstract Optimization Problem
- The formulation treats perturbation outputs as independent sequence variables to bypass their coupling to the state and perturbation matrices.The state update then becomes a linear equation without explicit perturbation matrices.Source: A. The Abstract Optimization Problem · p. 3
- The decision variables become state and perturbation-output sequences, yielding an abstract optimization over sequences rather than over perturbation matrices.The objective and dynamics are quadratic and linear, respectively.Source: A. The Abstract Optimization Problem · p. 3
- Algebraic inequalities translate the existence constraints that require perturbation sequences to be generated by single norm-bounded LTI operators.These constraints cannot be directly encoded in a solver in their original form.Source: A. The Abstract Optimization Problem · p. 3
B. Operator Interpolation: Enforcing LTI Behavior
Operator interpolation enforces that perturbation sequences arise from a single norm-bounded LTI matrix. Its algebraic conditions yield an equivalent finite-horizon QCQP, which remains non-convex.
B. Operator Interpolation: Enforcing LTI Behavior
- L[0,L]-interpolability requires one matrix M with induced 2-norm at most L to map every p_k to its corresponding q_k.The interpolation conditions are algebraic conditions on the sequence data matrices.Source: B. Operator Interpolation: Enforcing… · p. 3
- The interpolation lemma converts the existence of such an operator into an LMI on the data matrices.This makes the LTI constraint usable in the sequence-based optimization formulation.Source: B. Operator Interpolation: Enforcing… · p. 3
- The worst-case finite-horizon performance equals the optimum of a QCQP over the state and perturbation sequences.The proposition’s sequences are x, vA, and vB.Source: B. Operator Interpolation: Enforcing… · p. 3
- The equivalent QCQP remains non-convex because of its quadratic matrix inequalities.The formulation maps the perturbation-existence constraints into interpolation constraints.Source: B. Operator Interpolation: Enforcing… · p. 3
C. The Gram Matrix SDP Formulation
The formulation lifts the finite-horizon sequence variables into a positive semidefinite Gram matrix, making the objective and interpolation constraints linear in that matrix. Retaining a rank constraint gives the exact formulation; dropping it yields a tractable relaxation that may be conservative.
C. The Gram Matrix SDP Formulation
- The lifted vector z concatenates the initial state and perturbation sequences, with selector matrices extracting their blocks.The extracted blocks are x0, vA,k, and vB,k.Source: C. The Gram Matrix SDP Formulation · p. 3
- Recursive state-extraction matrices express each state xk as a linear function of z, enabling trajectory quantities to be represented through Z = zz⊤.Scalar inner products become linear trace operations on the positive semidefinite Gram matrix.Source: C. The Gram Matrix SDP Formulation · p. 3
- The finite-horizon cost is linear in Z, and the sequence interpolation constraints can be written as LMIs over Z.The cost uses a symmetric matrix built from the state-extraction matrices.Source: C. The Gram Matrix SDP Formulation · pp. 3–4
- The theorem expresses worst-case finite-horizon performance as an optimization over a Gram matrix with a rank constraint.The rank-constrained SDP preserves the sequence-variable formulation’s exactness.Source: C. The Gram Matrix SDP Formulation · p. 4
- Dropping the rank constraint gives a tractable convex relaxation, but a higher-rank solution may only provide an upper bound that does not represent a physical trajectory.A rank-one relaxed solution instead yields a tight bound and a physically realizable worst-case trajectory.Source: C. The Gram Matrix SDP Formulation · p. 4
IV. Extracting Worst-Case via PEP
When the relaxed Gram matrix is higher rank, the paper searches directly over admissible perturbations using projected gradient ascent. The resulting LTI perturbation supplies a lower bound, while a rank-one relaxation matches the SDP bound.
IV. Extracting Worst-Case via PEP
- When the relaxed solution has rank above one, projected gradient ascent searches over norm-bounded perturbations to find an admissible LTI case.The search starts from the relaxed solution’s principal eigenvector, the best Monte Carlo sample, and random perturbations.Source: §IV · p. 4
- The admissible perturbation’s cost is a lower bound on worst-case performance, and the search satisfies first-order stationarity conditions.For fixed perturbations, the worst initial condition is the dominant eigenvector of the finite-horizon Gramian.Source: §IV · p. 4
- When the relaxed Gram matrix has rank one, the admissible result matches the SDP bound.An interactive interface allows real-time parameter changes using MOSEK.Source: §IV · p. 4
A. Pseudospectral Targeting and Trajectories for Large N
For large horizons, worst-case perturbations tend toward spectral-radius-maximizing pole placements, but finite-horizon cost also depends on transient amplification and invariant directions. PEP solutions show trajectories confined to slowly decaying invariant manifolds, with behavior shaped by the dominant eigenvalue geometry.
A. Pseudospectral Targeting and Trajectories for Large N
- The pseudospectral heuristic that maximizes spectral radius yields a lower cost than PEP because finite-horizon cost depends on transient amplification and invariant directions.The optimal perturbation may remain inside the structured pseudospectrum while changing invariant directions to produce greater transient cost.Source: A. Pseudospectral Targeting and… · p. 4
- For large horizons, optimal perturbations approach the spectral-radius-maximizing placements predicted by classical μ-analysis and pseudospectral theory,.The optimal perturbation often pushes a dominant eigenvalue toward the structured pseudospectrum boundary.Source: A. Pseudospectral Targeting and… · p. 4
- When the worst-case eigenvalue is a complex pair, the state spirals in a 2D invariant plane as the perturbation minimizes radial contraction.For real positive and real negative eigenvalues, the trajectory instead collapses onto a 1D slow manifold, moving monotonically or alternating signs, respectively.Source: A. Pseudospectral Targeting and… · p. 5
- PEP recovers the rank-one or rank-two perturbation geometry associated with real or complex worst-case eigenvalues, while finite-horizon trajectories collapse onto the corresponding slow manifolds.The finite-horizon objective is not determined by perturbed eigenvalues alone.Source: A. Pseudospectral Targeting and… · pp. 4–5
B. Pole-Placement bifurcation with respect to N
The worst-case pole placement changes with the finite planning horizon. As the horizon grows, the optimum shifts from transient eigenvector manipulation toward slow asymptotic decay, with a pole bifurcation that changes the trajectory geometry.
B. Pole-Placement bifurcation with respect to N
- As N approaches 15, the perturbation stops manipulating transient eigenvectors and pole placement shifts toward maximizing the asymptotic time constant.The poles migrate toward the rightmost edge of the structured ε-pseudospectrum.Source: B. Pole-Placement bifurcation with… · p. 5
- For N ≤ 5, the worst-case poles form a complex conjugate pair; for N ≥ 6, they meet on the real axis and split.The corresponding worst-case trajectories shift from 2D spiraling to a 1D slow manifold.Source: B. Pole-Placement bifurcation with… · p. 6, Figure 2 · p. 6
- Finite-horizon controller evaluation requires more than identifying the worst-case asymptotic poles on the pseudospectrum boundary.The example uses system A1 with terminal cost S = diag(0, 1), uncertainty bounds εA = 0.15 and εB = 0.05.Source: B. Pole-Placement bifurcation with… · pp. 5–6
V. Performance: Classical vs. PEP
For system A1, the finite-horizon comparison shows that enforcing LTI uncertainty tightens the IQC bound, while the pseudospectral heuristic misses short-horizon transient cost. The relaxed PEP bound can be conservative, whereas projected ascent produces an admissible lower bound.
V. Performance: Classical vs. PEP
- Dropping the PEP rank constraint admits infeasible trajectories, making the relaxed SDP bound conservative.Fig. 3 marks this difference as the orange shaded region.Source: §V · p. 6
- The relaxed PEP bound tightens the IQC bound by enforcing time invariance on system A1's LTI perturbations.Fig. 3 compares finite-horizon accumulated cost bounds for εA = 0.15 and εB = 0.05.Source: Figure 3 · p. 6, §V · p. 6
- Projected-gradient extraction gives an admissible LTI perturbation whose cost is a lower bound on J∗_N, though it is only first-order stationary and not certified globally optimal.Its cost exceeds what random Monte Carlo sampling typically finds, which struggles to hit the narrow geometric manifold where worst-case parameters lie.Source: §V · p. 6
- The pseudospectral heuristic yields the lowest cost of the compared approaches but misses short-horizon transient growth by not aligning eigenvectors with a worst-case initial condition.It maximizes spectral radius and thus minimizes long-term decay rate, but leaves out a large portion of finite-horizon cost for short horizons.Source: §V · p. 6
VI. Conclusions and Perspectives
The conclusions emphasize that finite-horizon worst cases depend on transient dynamics and initial conditions, with behavior changing as the horizon changes. They also identify potential extensions of sequence-based certification and an open question about when LTV IQC bounds are tight for LTI uncertainty.
VI. Conclusions and Perspectives
- Finite-horizon LTI perturbations align with specific initial conditions to cause short-term transient growth, and the failure mode can shift from 2D spiraling invariant subspaces to 1D monotonic slow manifolds as N changes.This transient behavior means boundary eigenvalues of the structured pseudospectrum do not capture the full finite-time cost.Source: §VI · p. 6
- Numerical instances show IQC upper bounds can exactly or closely match the LTI cost from PEP, leaving open when a worst-case LTV sequence collapses to an LTI structure.The authors identify algebraic conditions for this collapse as an open question for determining when the LTV relaxation is tight.Source: §VI · pp. 6–7
- Operator interpolation uses algebraic inequalities rather than specific physical models, allowing sequence-based analysis to replace norm-bounded LTI constraints with data-driven uncertainty sets or sector-bounded nonlinearities.Future work could integrate finite-horizon certificates into controller design against worst-case transient behavior.Source: §VI · p. 7