betaFeedback

Reading v1View latest version

WorksMathematics

Worst-Case Finite-Horizon Analysis of Perturbed LQR via Performance Estimation Problem

Abstract

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.

Introduction

In the current control literature, there is a gap between the theoretical design of optimal controllers, such as a Linear Quadratic Regulator (LQR), and their real-world applications. These control laws are typically designed assuming a perfectly known, nominal model over an infinite horizon, whereas practical applications often involve deploying them for finite durations on systems subject to parametric uncertainties. Such parameter variations, which create a mismatch between the design model and the true physical system, can arise, for example, from changing operating conditions or unmodeled nonlinearities like a varying resistance in an electronic circuit.

To handle these parametric uncertainties, it is natural to turn to robust control to provide guarantees on the desired behaviors [1, 2, 3]. Robust control approaches include, for example, μ\mu-analysis [4] (which evaluates worst-case stability and performance against structured uncertainties), robust Lyapunov functions and Integral Quadratic Constraints (IQC) [5] (a framework that bounds the input-output behavior of complex uncertainties and nonlinearities using quadratic inequalities). These methods provide theoretical certificates under the presence of such perturbations.

However, while powerful, most robust control certificates evaluate only asymptotic behavior or specific perturbations, limiting their use in finite-horizon applications. For instance, μ\mu-analysis computes exact robust stability margins for Linear Time-Invariant (LTI) systems [4], but it evaluates asymptotic stability (see Example 1). Similarly, while recent structured pseudospectral algorithms provide robust transient bounds [6, 7], they rely on continuous-time resolvent envelopes rather than finite-horizon trajectories. Time-domain IQC methods handle finite horizons using dissipation inequalities [8], but rely on dual bounding techniques, which create two limitations. First, standard time-domain IQC formulations relax the static LTI parameter variations into a larger class of Linear Time-Varying (LTV) uncertainties, introducing conservatism. Second, the dual approach acts primarily as a bounding oracle. Because the optimization variables are dual multipliers rather than system trajectories, extracting the exact physical worst-case perturbation matrices or initial conditions remains difficult.

By contrast, in this paper we evaluate the finite-horizon performance of an LQR controller under norm-bounded LTI uncertainties using the Performance Estimation Problem (PEP) framework [9, 10] and exhibit worst-case behaviors. Originally developed to analyze optimization algorithms, PEP treats worst-case analysis as an optimization problem over discrete trajectories. Using necessary and sufficient operator interpolation conditions, we formulate the search for worst-case LTI trajectories as Quadratically Constrained Quadratic Program (QCQP) and then as a rank-constrained Semidefinite Program (SDP). This primal approach avoids LTV conservatism. By retaining the sequence variables, we can extract the exact worst-case initial conditions and perturbation matrices. Instead of just providing scalar bounds, PEP acts as a diagnostic tool to uncover geometric failure modes when these controllers are deployed over a finite horizon. Finally, we compare our rank-relaxed SDP and numerically extracted lower bounds against standard IQC results to quantify the conservatism gap introduced by the LTV relaxation.

Notation. We denote by R\mathbb{R} the set of real numbers. Vectors of dimension nn will be denoted as x∈Rnx \in\mathbb{R}^n in lowercase and a matrix A∈Rn×nA \in\mathbb{R}^{n \times n} in uppercase letters. The concatenation of a sequence of vectors {xk}k=0N−1\{x_k\}_{k=0}^{N-1} is denoted by x=[x0,…,xN−1]∈Rn×Nx=[x_0,\ldots,x_{N-1}]\in\mathbb{R}^{n\times N}. For two matrices A,B∈Rn×nA,B\in\mathbb{R}^{n\times n}, we denote by A⪰BA\succeq B the Loewner partial order, i.e., A−BA-B is positive semidefinite.

Problem Formulation

Consider a discrete-time linear system xk+1=Axk+Bukx_{k+1}=Ax_k+Bu_k with state trajectory {xk}k=0N⊂Rn\{x_k\}_{k=0}^{N}\subset\mathbb{R}^n, control sequence {uk}k=0N−1⊂Rm\{u_k\}_{k=0}^{N-1}\subset\mathbb{R}^m, for the nominal matrices A∈Rn×nA\in\mathbb{R}^{n\times n} and B∈Rn×mB\in\mathbb{R}^{n\times m}. Let uk=Kxku_k=Kx_k be a nominal state-feedback control law, where K=−(R+BTPB)−1BTPAK=-(R+B^\mathsf{T}PB)^{-1}B^\mathsf{T}PA is the standard infinite-horizon LQR gain derived from state and input penalty matrices Q⪰0Q\succeq0 and R≻0R\succ0, and P≻0P\succ0 is the solution to the discrete algebraic Riccati equation: P=ATPA−ATPB(R+BTPB)−1BTPA+QP=A^\mathsf{T}PA-A^\mathsf{T}PB(R+B^\mathsf{T}PB)^{-1}B^\mathsf{T}PA+Q.

As discussed in § 1, deploying this nominal controller in practice subjects the system to parametric mismatches. We therefore evaluate the performance of the fixed controller KK under unknown but bounded LTI perturbations on the system matrices:

xk+1=(A+ΔA)xk+(B+ΔB)uk(1)x_{k+1}=(A+\Delta_A)x_k+(B+\Delta_B)u_k \tag*{(1)}

where ΔA∈Rn×n\Delta_A\in\mathbb{R}^{n\times n} and ΔB∈Rn×m\Delta_B\in\mathbb{R}^{n\times m} are static perturbations bounded in spectral norm by εA,εB≥0\varepsilon_A,\varepsilon_B\geq0:

ΔA∈DA:={M∈Rn×n∣∥M∥2≤εA},\Delta_A\in\mathcal{D}_A:=\{M\in\mathbb{R}^{n\times n}\mid\|M\|_2\leq\varepsilon_A\},
ΔB∈DB:={M∈Rn×m∣∥M∥2≤εB}.\Delta_B\in\mathcal{D}_B:=\{M\in\mathbb{R}^{n\times m}\mid\|M\|_2\leq\varepsilon_B\}.

Under the nominal control law uk=Kxku_k=Kx_k, the closed-loop perturbed dynamics becomes:

xk+1=(Φ+ΔA+ΔBK)xk,(2)x_{k+1}=(\Phi+\Delta_A+\Delta_BK)x_k, \tag*{(2)}

where Φ=A+BK\Phi=A+BK is the nominal closed-loop state matrix.

To quantify the transient performance degradation caused by these uncertainties, we consider a finite-horizon evaluation cost over NN steps, with a terminal penalty S⪰0S\succeq0:

JN(x0,Δ)=∑k=0N−1(xkTQxk+ukTRuk)+xNTSxN,J_N(x_0,\Delta)=\sum_{k=0}^{N-1}(x_k^\mathsf{T}Qx_k+u_k^\mathsf{T}Ru_k)+x_N^\mathsf{T}Sx_N,

where the state trajectory depends on the perturbations Δ=(ΔA,ΔB)\Delta=(\Delta_A,\Delta_B) through the closed-loop dynamics defined in (2). Substituting uk=Kxku_k=Kx_k, this cost simplifies to a quadratic function of the state trajectory:

JN(x0,Δ)=∑k=0N−1xkTQKxk+xNTSxN,(3)J_N(x_0,\Delta)=\sum_{k=0}^{N-1}x_k^\mathsf{T}Q_Kx_k+x_N^\mathsf{T}Sx_N, \tag*{(3)}

where QK=Q+KTRK⪰0Q_K=Q+K^\mathsf{T}RK\succeq0 is the equivalent closed-loop stage cost matrix, and the state sequence {xk}k=0N\{x_k\}_{k=0}^{N} is generated by the perturbed dynamics (2). As an infinite-horizon gain, KK remains suboptimal for this finite-horizon cost even if Δ=0\Delta=0.

Given an initial state bounded by the unit ball, the worst-case performance is:

JN∗(εA,εB,QK,S):=max⁡x0,ΔA,ΔBJN(x0,Δ)J_N^*(\varepsilon_A,\varepsilon_B,Q_K,S):=\max_{x_0,\Delta_A,\Delta_B}J_N(x_0,\Delta)
s.t.∥x0∥22≤1\text{s.t.}\quad\|x_0\|_2^2\leq1
xk+1=(Φ+ΔA+ΔBK)xk,∀k∈Kx_{k+1}=(\Phi+\Delta_A+\Delta_BK)x_k,\quad\forall k\in\mathcal{K}
ΔA∈DA,ΔB∈DB(4)\Delta_A\in\mathcal{D}_A,\quad\Delta_B\in\mathcal{D}_B \tag*{(4)}

where K={0,…,N−1}\mathcal{K}=\{0,\ldots,N-1\}. We restrict x0x_0 to the unit ball without loss of generality. Because the dynamics is linear and the cost is quadratic, the worst-case cost under an arbitrary bound ∥x0∥22≤γ\|x_0\|_2^2\leq\gamma equals γJN∗\gamma J_N^*.

Example 1 (Worst-case with nominal pole): Consider

A=[054014],B=[1212],Q=diag⁡(1,34),R=1.A=\begin{bmatrix}0&\frac{5}{4}\\0&\frac{1}{4}\end{bmatrix},\quad B=\begin{bmatrix}\frac{1}{2}\\\frac{1}{2}\end{bmatrix},\quad Q=\operatorname{diag}\left(1,\frac{3}{4}\right),\quad R=1.

The Riccati solution is P=diag⁡(1,2)P=\operatorname{diag}(1,2), so that K=[0−12]K=\begin{bmatrix}0&-\frac{1}{2}\end{bmatrix}, Φ=[0001]\Phi=\begin{bmatrix}0&0\\0&1\end{bmatrix} and QK=IdQ_K=\mathrm{Id}. Take N=2N=2, S=0S=0, εA=3/8\varepsilon_A=3/8 and εB=1/4\varepsilon_B=1/4.

Writing ΦΔ=Φ+ΔA+ΔBK\Phi_\Delta=\Phi+\Delta_A+\Delta_BK, the cost reduces to J2(x0,Δ)=∥x0∥22+∥ΦΔx0∥22J_2(x_0,\Delta)=\|x_0\|_2^2+\|\Phi_\Delta x_0\|_2^2, hence J2∗=1+max⁡Δ∥ΦΔ∥22J_2^*=1+\max_{\Delta}\|\Phi_\Delta\|_2^2. The triangle inequality gives ∥ΦΔ∥2≤∥Φ∥2+εA+εB∥K∥2=3/2\|\Phi_\Delta\|_2\leq\|\Phi\|_2+\varepsilon_A+\varepsilon_B\|K\|_2=3/2, and this bound is attained by

ΔA∗=[03800],ΔB∗=[−140],ΦΔ∗=[03200].\Delta_A^*=\begin{bmatrix}0&\frac{3}{8}\\0&0\end{bmatrix},\quad \Delta_B^*=\begin{bmatrix}-\frac{1}{4}\\0\end{bmatrix},\quad \Phi_{\Delta^*}=\begin{bmatrix}0&\frac{3}{2}\\0&0\end{bmatrix}.

From x0=[0 1]Tx_0=[0\ 1]^\mathsf{T}, this gives J2∗=1+9/4=3.25J_2^*=1+9/4=3.25, against 22 for the nominal loop. Yet Φ\Phi and ΦΔ∗\Phi_{\Delta^*} have the same eigenvalues {0,0}\{0,0\}: the worst-case perturbation leaves the poles in place and strengthens the coupling from the second state to the first. An analysis based on eigenvalue location, such as μ\mu-analysis or pseudospectra, sees no degradation here. In our computations, the perturbations that maximize the spectral radius (ρ≈0.79\rho\approx0.79) yield at most J2≈3.05J_2\approx3.05. The IQC bound is tight in this case, since with N=2N=2 only one transition is penalized and a time-varying perturbation has no extra freedom.

IQC is exact in this short-horizon example, but not in general. Over longer horizons, a time-varying perturbation can steer the state in a different direction at each step, which a single matrix of the same norm cannot always do. The LTV relaxation then overestimates the LTI worst-case, as § 5 shows numerically.

The Performance Estimation Problem (PEP) Reformulation

Our main result, Theorem 1, uses the PEP framework to recast the exact worst-case optimization problem (4) into a rank-constrained SDP. To derive this formulation, we abstract the problem over discrete sequences, enforce the LTI behavior of the perturbations through operator interpolation, and lift the sequence variables into a positive semidefinite Gram matrix.

The Abstract Optimization Problem

To bypass the coupling between the perturbation matrices ΔA,ΔB\Delta_A,\Delta_B and the state xkx_k in (2), we treat the perturbation outputs as independent sequence variables. Over the horizon NN, we define:

x=[x0,…,xN−1]∈Rn×N,x = [x_0,\ldots,x_{N-1}] \in\mathbb{R}^{n \times N},
vA=[vA,0,…,vA,N−1]∈Rn×N,v_A = [v_{A,0},\ldots,v_{A,N-1}] \in\mathbb{R}^{n \times N},
vB=[vB,0,…,vB,N−1]∈Rn×N,v_B = [v_{B,0},\ldots,v_{B,N-1}] \in\mathbb{R}^{n \times N},

where at each time step k∈Kk \in\mathcal{K}, the pointwise perturbations are given by:

vA,k=ΔAxk,vB,k=ΔBKxk.v_{A,k} = \Delta_A x_k,\qquad v_{B,k} = \Delta_B K x_k.

By substituting these vectors into the system dynamics, the state update becomes a linear equation independent of the explicit matrices ΔA\Delta_A and ΔB\Delta_B:

xk+1=Φxk+vA,k+vB,k.(5)x_{k+1} = \Phi x_k + v_{A,k} + v_{B,k}. \tag*{(5)}

Instead of optimizing over the matrices ΔA,ΔB\Delta_A,\Delta_B, our decision variables are now the sequences of vectors: the states {xk}k=0N\{x_k\}_{k=0}^{N} and the perturbations {vA,k}k=0N−1\{v_{A,k}\}_{k=0}^{N-1} and {vB,k}k=0N−1\{v_{B,k}\}_{k=0}^{N-1}. The optimization problem (4) can thus be rewritten as the abstract optimization problem over sequences:

JN∗(εA,εB,QK,S)=max⁡xk,vA,k,vB,kJN(x0,vA,vB)J_N^*(\varepsilon_A,\varepsilon_B,Q_K,S) = \max_{x_k,v_{A,k},v_{B,k}} J_N(x_0,v_A,v_B)
s.t.∥x0∥22≤1xk+1=Φxk+vA,k+vB,k,∀k∈K∃ΔA∈DA s.t. vA,k=ΔAxk,∀k∈K∃ΔB∈DB s.t. vB,k=ΔBKxk,∀k∈K(6)\begin{aligned} \text{s.t.}\quad&\lVert x_0\rVert_2^2 \le1 \\ &x_{k+1} = \Phi x_k + v_{A,k} + v_{B,k},\qquad\forall k \in\mathcal{K} \\ &\exists\Delta_A \in\mathcal{D}_A\ \text{s.t.}\ v_{A,k} = \Delta_A x_k,\qquad\forall k \in\mathcal{K} \\ &\exists\Delta_B \in\mathcal{D}_B\ \text{s.t.}\ v_{B,k} = \Delta_B Kx_k,\qquad\forall k \in\mathcal{K} \tag*{(6)} \end{aligned}

By shifting to this sequence-based formulation, the objective and the dynamics are now quadratic and linear, respectively. However, the final two constraints ensuring the perturbation sequences can be generated by single norm-bounded LTI operators cannot be directly encoded in a solver. The PEP framework works by translating these abstract existence constraints into algebraic inequalities.

Operator Interpolation: Enforcing LTI Behavior

Let L[0,L]\mathcal{L}_{[0,L]} denote the set of matrices M∈Rd2×d1M \in\mathbb{R}^{d_2 \times d_1} with an induced 2-norm bounded by L≥0L \ge0. We use operator interpolation to enforce LTI behavior on the perturbation variables. Let p=[p0,…,pN−1]∈Rd1×Np = [p_0,\ldots,p_{N-1}] \in\mathbb{R}^{d_1 \times N} and q=[q0,…,qN−1]∈Rd2×Nq = [q_0,\ldots,q_{N-1}] \in\mathbb{R}^{d_2 \times N} be matrices containing vector sequences. We say the sequences are L[0,L]\mathcal{L}_{[0,L]}-interpolable if there exists M∈L[0,L]M \in\mathcal{L}_{[0,L]} such that qk=Mpkq_k = Mp_k for all kk. For L[0,L]\mathcal{L}_{[0,L]} the interpolation conditions are given by algebraic conditions over the data matrices from [11].

Lemma 1 (L[0,L]\mathcal{L}_{[0,L]}-Interpolation Condition). Let p∈Rd1×Np \in\mathbb{R}^{d_1 \times N} and q∈Rd2×Nq \in\mathbb{R}^{d_2 \times N} be data matrices. The sequences are L[0,L]\mathcal{L}_{[0,L]}-interpolable if and only if the following LMI holds:

L2p⊤p−q⊤q⪰0.L^2p^\top p-q^\top q \succeq0.

Lemma 1 allows us to map the operator existence condition in (6) to quadratic constraints on the data matrix, which turn the problem into a QCQP.

Proposition 1 (QCQP formulation). The worst-case finite-horizon performance JN∗J_N^* defined in (6) equals the optimal value of the following QCQP over the finite vector sequences x,vAx,v_A, and vBv_B:

JN∗(εA,εB,QK,S)=max⁡x,vA,vBJN(x0,vA,vB)J_N^*(\varepsilon_A,\varepsilon_B,Q_K,S)=\max_{x,v_A,v_B} J_N(x_0,v_A,v_B)
s.t.∥x0∥22≤1xk+1=Φxk+vA,k+vB,k,∀k∈KεA2x⊤x−vA⊤vA⪰0εB2x⊤K⊤Kx−vB⊤vB⪰0(7)\begin{aligned} \text{s.t.}\quad&\lVert x_0\rVert_2^2 \le1 \\ &x_{k+1}=\Phi x_k+v_{A,k}+v_{B,k},\qquad\forall k\in\mathcal{K}\\ &\varepsilon_A^2x^\top x-v_A^\top v_A\succeq0\\ &\varepsilon_B^2x^\top K^\top Kx-v_B^\top v_B\succeq0 \tag*{(7)} \end{aligned}

Proof. Using Lemma 1, we map the existence constraints ∃ΔA∈DA\exists\Delta_A\in\mathcal{D}_A in the optimization problem (6) to the LMI εA2x⊤x−vA⊤vA⪰0\varepsilon_A^2x^\top x-v_A^\top v_A\succeq0. Similarly, ∃ΔB∈DB\exists\Delta_B\in\mathcal{D}_B is replaced by $\varepsilon_B^2x^\top K^\top Kx-v_B^\top v_B\succeq 0, yielding (7). ■

Proposition 1 provides an equivalent formulation of (6) and thus to (4). However, the resulting QCQP remains non-convex due to the quadratic matrix inequalities.

The Gram Matrix SDP Formulation

To bypass the intractability of the QCQP, we use a Gram lifting approach [12]. Because the objective function and constraints in (7) depend solely on quadratic inner products of the sequence variables, we can linearize them by shifting our decision variables to a positive semidefinite Gram matrix.

We concatenate the initial state and the independent perturbation sequences into a single lifted vector zz:

z=[x0⊤    vA,0⊤…vA,N−1⊤    vB,0⊤…vB,N−1⊤]⊤.z=\left[x_0^\top\;\;v_{A,0}^\top\ldots v_{A,N-1}^\top\;\;v_{B,0}^\top\ldots v_{B,N-1}^\top\right]^\top.

We define block-selector matrices E0,EA,k,EB,k∈Rn×(1+2N)nE_0,E_{A,k},E_{B,k}\in\mathbb{R}^{n\times(1+2N)n} to extract the corresponding blocks from zz:

x0=E0z,vA,k=EA,kz,vB,k=EB,kz.x_0=E_0z,\qquad v_{A,k}=E_{A,k}z,\qquad v_{B,k}=E_{B,k}z.

Because the linear dynamics determines the state trajectory, every state xkx_k is a linear combination of the components of zz. Using the dynamics from Proposition 1, we define the state extraction matrices Hx,kH_{x,k} recursively:

Hx,0=E0,Hx,k+1=ΦHx,k+EA,k+EB,k,∀k∈K.H_{x,0}=E_0,\qquad H_{x,k+1}=\Phi H_{x,k}+E_{A,k}+E_{B,k},\qquad\forall k\in\mathcal{K}.

Thus, xk=Hx,kzx_k=H_{x,k}z for all k∈Kk\in\mathcal{K}. Any scalar inner product in the system can be expressed as a linear trace operation on the (1+2N)n×(1+2N)n(1+2N)n\times(1+2N)n positive semidefinite Gram matrix Z=zz⊤Z=zz^\top, which has rank at most 1. Indeed, for any symmetric matrix M∈Rn×nM\in\mathbb{R}^{n\times n}, one has:

xi⊤Mxj=z⊤Hx,i⊤MHx,jz=Tr⁡(Hx,j⊤MHx,iZ).x_i^\top Mx_j=z^\top H_{x,i}^\top M H_{x,j}z=\operatorname{Tr}\left(H_{x,j}^\top M H_{x,i}Z\right).

By the trace property, the (i,j)(i,j)-th entry of this matrix is Tr⁡(Hx,j⊤Hx,iZ)\operatorname{Tr}(H_{x,j}^\top H_{x,i}Z). Similarly, the cost JNJ_N can be expressed as a linear operator acting on ZZ. Explicitly, the symmetric cost matrix MJN∈R(1+2N)n×(1+2N)nM_{J_N}\in\mathbb{R}^{(1+2N)n\times(1+2N)n} is obtained from the state extraction matrices Hx,kH_{x,k} as:

MJN=∑k=0N−1Hx,kTQKHx,k+Hx,NTSHx,N,M_{J_N}=\sum_{k=0}^{N-1}H_{x,k}^{\mathsf T}Q_KH_{x,k}+H_{x,N}^{\mathsf T}SH_{x,N},

which yields JN(x0,vA,vB)=Tr⁡(MJNZ)J_N(x_0,v_A,v_B)=\operatorname{Tr}(M_{J_N}Z).

Let Gx(Z)∈SN×N\mathcal{G}_x(Z)\in\mathbb{S}^{N\times N} denote the linear operator mapping ZZ to the N×NN\times N sequence inner-product matrix xTxx^{\mathsf T}x. We define analogous linear operators GvA(Z)\mathcal{G}_{v_A}(Z), GvB(Z)\mathcal{G}_{v_B}(Z), and GKx(Z)\mathcal{G}_{Kx}(Z) for the other sequences. This allows us to express the interpolation conditions as LMIs over ZZ.

Theorem 1 (Rank-constrained SDP formulation). The worst-case finite-horizon performance JN∗J_N^* equals the optimal value of the following rank-constrained SDP over the Gram matrix ZZ:

JN∗(εA,εB,QK,S)=max⁡Z⪰0Tr⁡(MJNZ)s.t.Tr⁡(E0TE0Z)≤1εA2Gx(Z)−GvA(Z)⪰0εB2GKx(Z)−GvB(Z)⪰0rank⁡(Z)≤1(8)\begin{aligned} J_N^*(\varepsilon_A,\varepsilon_B,Q_K,S)&=\max_{Z\succeq0} && \operatorname{Tr}(M_{J_N}Z)\\ &\text{s.t.} && \operatorname{Tr}(E_0^{\mathsf T}E_0Z)\le1\\ &&&\varepsilon_A^2\mathcal{G}_x(Z)-\mathcal{G}_{v_A}(Z)\succeq0\\ &&&\varepsilon_B^2\mathcal{G}_{Kx}(Z)-\mathcal{G}_{v_B}(Z)\succeq0\\ &&&\operatorname{rank}(Z)\le1 \tag*{(8)} \end{aligned}

This reformulates the problem into an SDP with a rank constraint. While still NP-hard, isolating the nonconvexity allows us to drop the rank constraint to form a tractable convex relaxation. Moreover, the rank then serves as an admissibility check: if the relaxed solution has rank one, the bound is tight and produces an exact, physically realizable worst-case trajectory. However, the convex relaxation suffers from conservatism. Indeed, the optimal relaxed Gram matrix ZSDPZ_{\mathrm{SDP}} often has a rank strictly greater than one [12]. In this case, the relaxation only provides an upper bound on JN∗J_N^* that is not necessarily physical, as it may correspond to a superposition of trajectories.

Extracting Worst-Case via PEP

As noted above, the solution to the relaxed problem (8), denoted ZSDPZ_{\mathrm{SDP}}, is often of rank strictly greater than one, already for relatively short planning horizons (N≥5N\ge5). To find a valid LTI trajectory, we keep the SDP result as an upper bound and search for an admissible worst case directly over the perturbations. For fixed (ΔA,ΔB)(\Delta_A,\Delta_B), the worst initial condition is the dominant eigenvector of the finite-horizon Gramian, so the search reduces to maximizing JNJ_N over the perturbations alone. We do so by projected gradient ascent on the norm balls DA×DB\mathcal{D}_A\times\mathcal{D}_B, following the norm-constrained gradient flows of [6], [7]. The ascent is started from the principal eigenvector of ZSDPZ_{\mathrm{SDP}}, from the best Monte Carlo (MC) sample and from random perturbations. The result is an admissible LTI perturbation, so its cost is a lower bound on JN∗J_N^*, and it satisfies first-order stationarity conditions. When rank⁡(ZSDP)=1\operatorname{rank}(Z_{\mathrm{SDP}})=1, it matches the SDP bound.

We provide an interactive interface [13] for changing the parameters (matrix AA, BB, QQ, RR, SS and hyperparameter NN, εA\varepsilon_A, εB\varepsilon_B) in real time using the solver MOSEK.

Pseudospectral Targeting and Trajectories for Large N

To illustrate the PEP approach, we apply it to three 2D systems (Figure 1). We chose the following nominal matrices AA because they each represent one of the three distinct worst-case behaviors we observed, making the differences visually clear:

Worst-case perturbation: spectral representation and trajectories

Figure 1. Worst-case perturbation: spectral representation (top row) and trajectories (bottom row) extracted via PEP and projected gradient ascent.

A1=[1101],A2=[−0.9101]andA3=[10.9−0.81],A_1=\begin{bmatrix}1&1\\0&1\end{bmatrix},\quad A_2=\begin{bmatrix}-0.9&1\\0&1\end{bmatrix}\quad\text{and}\quad A_3=\begin{bmatrix}1&0.9\\-0.8&1\end{bmatrix},

with B=[01]TB=\begin{bmatrix}0&1\end{bmatrix}^{\mathsf T} and Q=R=S=IdQ=R=S=I_d for N=20N=20.

Varying the nominal system matrices reveals three classes of worst-case behavior, which we interpret through their spectral geometry (Figure 1, top row). This spectral view is used as a diagnostic of the PEP solution: in general, the finite-horizon objective is not determined by the perturbed eigenvalues alone (Example 1). For given uncertainty bounds εA\varepsilon_A and εB\varepsilon_B, the structured ε\varepsilon-pseudospectrum of the closed-loop system [7] is the set of all possible eigenvalues for the perturbed matrix ΦΔ=Φ+ΔA+ΔBK\Phi_\Delta=\Phi+\Delta_A+\Delta_BK under valid LTI perturbations, computed exactly via the real stability radius formula [14]:

Λε(Φ):={λ∈C∣det⁡(λI−(Φ+ΔA+ΔBK))=0, for some ∥ΔA∥2≤εA, ∥ΔB∥2≤εB}.\Lambda_\varepsilon(\Phi):=\left\{\lambda\in\mathbb{C}\mid\det\left(\lambda I-\left(\Phi+\Delta_A+\Delta_BK\right)\right)=0,\ \text{for some }\lVert\Delta_A\rVert_2\le\varepsilon_A,\ \lVert\Delta_B\rVert_2\le\varepsilon_B\right\}.

As the red stars show, the optimal perturbation often pushes a dominant eigenvalue toward the boundary of Λε(Φ)\Lambda_\varepsilon(\Phi). For large horizons, this behavior approaches the spectral-radius-maximizing perturbations predicted by classical μ\mu-analysis and pseudospectral theory [4], [15]. However, these asymptotic tools do not fully characterize the finite-horizon optimum: PEP captures transient dynamics and invariant-direction effects, so the worst-case cost is not determined by the eigenvalues alone. In our numerical evaluations, the pseudospectral heuristic that maximizes the spectral radius of ΦΔ\Phi_\Delta over the admissible perturbations [6] therefore yields a lower cost than PEP (e.g., on system A1A_1, JNp≈20.95J_N^{\mathrm p}\approx20.95 versus JNPEP≈21.06J_N^{\mathrm{PEP}}\approx21.06). Since this maximizer is not unique, JNpJ_N^{\mathrm p} denotes the largest finite-horizon cost among the sampled maximizers, the most favorable choice for the heuristic.

This occurs because the finite-horizon cost depends on transient amplification, whereas asymptotic tools mainly focus on pole locations. PEP does not impose or target any particular spectral configuration: it optimizes directly over admissible finite-horizon trajectories. A posteriori, we observe that the resulting perturbations may remain slightly inside Λε(Φ)\Lambda_\varepsilon(\Phi) depending on the cost matrices while modifying the associated invariant directions in a way that produces a larger transient cost.

The maximum spectral radius on the boundary can occur at a real positive, real negative, or complex eigenvalue, depending on the nominal eigenvalues. This shift changes the state-space trajectories (bottom row of Figure 1). The perturbation modifies the dominant eigenspace of ΦΔ∗\Phi_{\Delta^*} to confine the state energy to a slowly decaying invariant manifold. In our computations, we observe three cases:

  • Monotonic 1D Slow Manifold (λ∗>0\lambda^* > 0, Figure 1d): When the dominant worst-case eigenvalue is real and positive, the optimal perturbation applies a rank-one shear opposing the nominal damping. The trajectory collapses onto a 1D invariant line (a “slow manifold”) and moves monotonically toward the origin.

  • Oscillatory 1D Slow Manifold (λ∗<0\lambda^* < 0, Figure 1e): If the perturbed eigenvalue on the boundary is real and negative, the trajectory again collapses onto a 1D line. The negative eigenvalue causes the state to alternate signs, jumping back and forth across the origin at each step while slowly decaying.

  • Spiraling 2D Invariant Subspace (λ∗∈C\R\lambda^* \in\mathbb{C}\backslash\mathbb{R}, Figure 1f): When the worst-case eigenvalue is a complex conjugate pair, ΦΔ∗\Phi_{\Delta^*} acts on a 2D invariant plane, and the state trajectory spirals. The perturbation changes the rotational frequency and minimizes radial contraction, creating a slowly decaying spiral.

In classical matrix perturbation theory, asymptotic variations that maximize the spectral radius correspond to rank-one (for real eigenvalues) or rank-two (for complex conjugate pairs) perturbations [16]. The PEP solutions recover this geometry. The primal formulation collapses finite-horizon trajectories onto the slow manifolds dictated by worst-case μ\mu-analysis.

Pole-Placement bifurcation with respect to NN

The optimal adversarial LTI perturbation depends directly on the length of the evaluation horizon. We illustrate this using the system A1A_1 with the same BB, QQ and RR but terminal cost S=diag⁡(0,1)S = \operatorname{diag}(0,1), which penalizes only the second state component. We set the uncertainty bounds εA=0.15\varepsilon_A = 0.15 and εB=0.05\varepsilon_B = 0.05. The different worst-case pole placements under those settings are shown in Figure 2.

Spectral migration of worst-case closed-loop poles

Figure 2. Spectral migration of the worst-case closed-loop poles as a function of the finite planning horizon NN. The colored diamonds represent the worst-case poles extracted from the PEP solution.

As the horizon NN increases, the initial transient growth contributes less to the total cumulative cost JNJ_N. The slow asymptotic decay of the state begins to drive the cost instead. As NN approaches 15, the perturbation stops manipulating transient eigenvectors. The poles migrate toward the rightmost edge of the structured ε\varepsilonpseudospectrum to maximize the asymptotic time constant. Along the way, the poles undergo a geometric bifurcation. For horizons N≤5N \le5, the optimal perturbation maintains a complex conjugate pole pair. For N≥6N \ge6, the poles meet on the real axis and split. This implies that the worst-case trajectories transition from 2D spiraling behavior (Figure 1f) to a 1D slow manifold one (Figure 1d). Evaluating controllers over finite horizons therefore requires more than identifying the worst-case asymptotic poles on the pseudospectrum boundary.

Performance: Classical vs. PEP

We now compare the worst-case performance obtained from the different approaches discussed in this paper: standard IQC [5], the relaxed PEP SDP, the worst-case LTI perturbation extracted by projected gradient ascent, and the pseudospectral heuristic defined in Section IV-A. We evaluate these methods on system A1A_1 to solve problem (4), using the same matrix BB as in the previous section. The cost matrices are set to Q=R=S=IdQ = R = S = \mathrm{I}d, with perturbation bounds εA=0.15\varepsilon_A = 0.15 and εB=0.05\varepsilon_B = 0.05. Figure 3 shows how the accumulated cost changes with the horizon NN under each approach.

Finite-horizon accumulated cost bounds

Figure 3. Finite-horizon accumulated cost bounds for system A1A_1 with εA=0.15\varepsilon_A = 0.15 and εB=0.05\varepsilon_B = 0.05 for the different approaches.

The IQC framework (red dashed line) bounds the cost over all allowable parameter variations, including LTV sequences [5]. Because the physical perturbation in (4) is LTI, the relaxed PEP formulation (orange squares) tightens this bound by enforcing time invariance. The pink shaded area shows the cost difference between the LTV and LTI bounds.

As discussed at the end of Section III-C, dropping the rank constraint in the PEP SDP introduces conservatism, as it admits infeasible trajectories; this gap is shown by the orange shaded region. This gap initially

grows as NN increases then plateaus similarly to the IQC vs Relaxed SDP one. However, the LTI worst case extracted by projected gradient ascent (blue circles) is admissible, so its cost is a lower bound on JN∗J_N^*. It is first-order stationary but not certified globally optimal. Its cost is higher than what random Monte Carlo sampling (black stars) typically finds, as random sampling struggles to hit the narrow geometric manifold where the worst-case parameters lie.

The pseudospectral heuristic (green solid line) yields the lowest cost of the group. As discussed in Section IV-A, maximizing the spectral radius places the dominant eigenvalue on the boundary of the pseudospectrum and thus minimizes the long-term decay rate. However, it misses the short-term transient growth. The heuristic does not align the eigenvectors with a worst-case initial condition x0x_0, leaving out a large portion of the finite-horizon cost for short horizons.

Conclusions and Perspectives

Extracting worst-case trajectories with the PEP framework shows how finite-horizon robustness differs from infinite-horizon stability. We found that LTI perturbations align with specific initial conditions to cause short-term transient growth. For example, we observed that, as the planning horizon NN changes, the failure mode of a system can transition from 2D spiraling invariant subspaces to 1D monotonic slow manifolds. Because of this transient behavior, analyzing the boundary eigenvalues of the structured pseudospectrum does not capture the full finite-time cost.

Comparing these PEP solutions to the standard IQC framework highlights an open question regarding LTV relaxations. While these relaxations usually introduce conservatism when bounding LTI uncertainties, we observed numerical instances where the IQC upper bounds exactly or closely match the LTI cost from our PEP approach. Finding the algebraic conditions that explain when a worst-case LTV sequence inherently collapses to an LTI structure will help determine when the IQC (LTV) relaxation is tight.

Finally, sequence-based optimization offers a direct path for extending this analysis. Operator interpolation relies on algebraic inequalities rather than specific physical models. This makes it possible to replace the norm-bounded LTI constraints with data-driven uncertainty sets or sector-bounded nonlinearities. Future work could focus on integrating these finite-horizon certificates into the controller design process to synthesize control laws optimized against worst-case transient behavior.

References

  1. [1]F. Amato, M. Ariola, and P. Dorato, “Finite-Time Control of Linear Systems Subject to Parametric Uncertainties and Disturbances,” Automatica, vol. 37, no. 9, pp. 1459–1463, 2001.DOI
  2. [2]D. Q. Mayne, M. M. Seron, and S. V. Raković, “Robust Model Predictive Control of Constrained Linear Systems with Bounded Disturbances,” Automatica, vol. 41, no. 2, pp. 219–224, 2005.DOI
  3. [3]I. Abel, D. Steeves et al., “Prescribed-Time Safety Design for Strict-Feedback Nonlinear Systems,” IEEE Transactions on Automatic Control, vol. 69, no. 3, pp. 1464–1479, 2024.DOI
  4. [4]A. Packard and J. Doyle, “The Complex Structured Singular Value,” Automatica, vol. 29, no. 1, pp. 71–109, 1993.DOI
  5. [5]A. Megretski and A. Rantzer, “System Analysis via Integral Quadratic Constraints,” IEEE Transactions on Automatic Control, vol. 42, no. 6, pp. 819–830, 1997.
  6. [6]N. Guglielmi, C. Lubich, and S. Sicilia, “Rank-1 Matrix Differential Equations for Structured Eigenvalue Optimization,” SIAM Journal on Numerical Analysis, vol. 61, no. 4, pp. 1737–1762, 2023.arxiv.org/abs/2206.09338
  7. [7]N. Guglielmi and C. Lubich, “Transient Dynamics Under Structured Perturbations: Bridging Unstructured and Structured Pseudospectra,” SIAM Journal on Numerical Analysis, vol. 63, no. 2, pp. 908–930, 2025.arxiv.org/abs/2401.09601
  8. [8]P. Seiler, R. M. Moore et al., “Finite Horizon Robustness Analysis of LTV Systems Using Integral Quadratic Constraints,” Automatica, vol. 100, pp. 135–143, 2019.DOI
  9. [9]Y. Drori and M. Teboulle, “Performance of First-Order Methods for Smooth Convex Minimization: A Novel Approach,” Mathematical Programming, vol. 145, no. 1, pp. 451–482, 2014.arxiv.org/abs/1206.3209
  10. [10]A. B. Taylor, J. M. Hendrickx, and F. Glineur, “Smooth Strongly Convex Interpolation and Exact Worst-Case Performance of First-Order Methods,” Mathematical Programming, vol. 161, no. 1, pp. 307–345, 2017.arxiv.org/abs/1502.05666
  11. [11]N. Bousselmi, J. M. Hendrickx, and F. Glineur, “Interpolation Conditions for Linear Operators and Applications to Performance Estimation Problems,” arXiv, 2024.arxiv.org/abs/2302.08781
  12. [12]Z.-Q. Luo, W.-K. Ma et al., “Semidefinite Relaxation of Quadratic Optimization Problems,” IEEE Signal Processing Magazine, vol. 27, no. 3, pp. 20–34, 2010.DOI
  13. [13]A. Couthures, “Worst-case LTI perturbations of finite-horizon LQR: A performance estimation problem approach,” 10.5281/zenodo.23161489, 2026. https://github.com/AnthonyCouthures/PEP-LQRDOI
  14. [14]L. Qiu, B. Bernhardsson et al., “A Formula for Computation of the Real Stability Radius,” Automatica, vol. 31, no. 6, pp. 879–890, 1995.DOI
  15. [15]D. Hinrichsen and A. J. Pritchard, “Real and Complex Stability Radii: A Survey,” in Control of Uncertain Systems: Proceedings of an International Workshop Bremen, West Germany, June 1989, D. Hinrichsen and B. Mårtensson, Eds. Boston, MA: Birkhäuser, 1990, pp. 119–162.DOI
  16. [16]L. N. Trefethen and M. Embree, Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators. Princeton University Press, 2005.

Paper details

vlnc:W_tecjxxq2
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents