Optimal input design via Frank-Wolfe

Fethi Bencherki; Bruce Lee; Nikolai Matni; Anders Rantzer

Source-linked AI summary

Optimal input design via Frank-Wolfe

Fethi Bencherki, Bruce Lee, Nikolai Matni, Anders Rantzer

arXiv:2609.08751v1Sep 8, 2026math.OCcs.SYeess.SY

TL;DR

Finite-horizon input design seeks informative data under an energy budget, but causal policies induce an implicitly described covariance set. The paper applies Frank–Wolfe with LQ subproblems solved by Riccati recursion and scalar bisection, establishing an O(1/M) objective rate and applying the framework to identification and adaptive LQR.

Problem
Input design seeks to minimize a weighted inverse-covariance criterion under an energy budget, while the covariances achievable by causal policies form an implicitly described set.
Source: §I · p. 1
Method
Frank–Wolfe optimizes over achievable covariances by solving each linear minimization subproblem as a constrained LQ problem using Riccati recursion and scalar bisection.
Source: §I · p. 1, §IV · p. 3
Results
The objective converges at O(1/M), and in the adaptive LQR experiment the Frank–Wolfe controller achieves lower regret than naive exploration.
Source: §VII · p. 5, C. Adaptive online LQR · p. 5
Takeaways & Limitations
The same Frank–Wolfe machinery applies to system identification with unknown dynamics and to an adaptive LQR scheme interpolating between explicit and implicit dual control.
Source: §VII · p. 5
Regret guarantees for the adaptive scheme and infinite-horizon formulations are left for future work.
Source: §VII · p. 5

Abstract

from arXiv · show

We study optimal input design over a finite horizon for linear dynamical systems. The goal is to minimize a weighted inverse-covariance (information) criterion subject to an energy budget. The set of covariances achievable by causal policies is convex but lacks a tractable explicit description, ruling out projection-based methods. We show that Frank--Wolfe applies naturally: each linear minimization subproblem is a budget-constrained finite-horizon linear quadratic (LQ) problem, solvable by a Riccati recursion and one-dimensional bisection over a Lagrange multiplier. Using smoothness of the objective over the feasible set, we establish an $\mathcal{O}(1/M)$ convergence rate for the objective value, while strong convexity yields an $\mathcal{O}(1/\sqrt{M})$ rate for the iterates. We further extend the framework to input design for system identification with unknown dynamics and adaptive online LQR, and illustrate the approach numerically.

I. INTRODUCTION

The paper frames finite-horizon input design as minimizing a weighted inverse-covariance criterion under an energy budget. Frank–Wolfe avoids projections onto the implicitly defined feasible covariance set by reducing each linear minimization to a constrained LQ problem.

II. PROBLEM FORMULATION

The weighted trace of the inverse state–input covariance is the chosen A-optimal criterion for measuring least-squares parameter-estimation quality.The energy budget constrains the design, while regularization can encode information available before the experiment.Source: §I · p. 1, §II · p. 1

I. INTRODUCTION

Achievable covariances from causal policies form a convex set, but its implicit description makes projection-based methods impractical.The paper therefore uses Frank–Wolfe, which requires linear minimization over the feasible set.Source: §I · p. 1
Each Frank–Wolfe linear minimization subproblem is a finite-horizon LQ problem with an energy constraint.The reduction follows because linear functions of achievable covariance equal expected quadratic costs.Source: §I · p. 1

II. PROBLEM FORMULATION

The formulation allows prior information and establishes smoothness and strong convexity over the achievable set with explicit constants.The objective weights directions where information is valuable, and the budget is interpretable as a prescribed energy limit.Source: §I · p. 1, §II · p. 1

I. INTRODUCTION

The paper reports an O(1/M) objective rate and extends the framework to unknown-dynamics system identification and adaptive online LQR.The linear subproblem is solved by Riccati recursion and scalar bisection.Source: §I · p. 1

A. Motivation

For system identification, task-weighted estimation error is reduced by designing the next experiment using information from previously collected data.The task-relevant weight may be derived from task cost and noise covariance.Source: A. Motivation · p. 2

III. FRANK–WOLFE OVER ACHIEVABLE COVARIANCES

Frank–Wolfe optimizes over achievable covariances without projecting onto their implicitly defined feasible set. Its objective converges at O(1/M), and strong convexity gives an O(1/√M) iterate rate.

Algorithm

Frank–Wolfe avoids Euclidean projections by repeatedly solving a linear minimization problem over the implicitly defined achievable covariance set.Each update remains feasible because it is a convex combination of feasible points.Source: §III · p. 2

Stopping criterion

The Frank–Wolfe gap upper-bounds suboptimality and can serve as a stopping criterion.The linear minimization oracle may be solved approximately by bisection.Source: §III · p. 2

Convergence guarantee

Under exact oracles (δ = 0), the objective and iterates both converge at rate O(1/M); strong convexity and compactness of D give existence and uniqueness of Σ⋆.Source: §III · p. 2

Policy realization

A policy can realize the iterates by sampling a search-point policy at time zero and following it for the entire horizon.The resulting policy inherits the stated guarantee.Source: §III · pp. 2–3

IV. THE LINEAR SUBPROBLEM IS CONSTRAINED LQ

Each Frank–Wolfe linear minimization subproblem is a budget-constrained finite-horizon LQ problem. Dualization reduces it to Riccati recursion and scalar bisection, with a certificate controlling oracle error.

Dualized LQ problem

The linear minimization oracle is a finite-horizon LQ problem with negative-definite stage cost and one scalar quadratic constraint.Dualizing the constraint gives a generalized LQ problem solved by backward Riccati recursion.Source: §IV · p. 3

Bisection procedure

For admissible λ, the optimal policy is linear feedback, and its budget cost b(λ) supports scalar bisection.The bisection procedure stops when the bound λ(β − b(λ)) on oracle error is at most δ.Source: §IV · p. 3

Active budget and degenerate case

When b(λ) = β, the policy is exactly optimal; if b(λ) remains below budget, independent noise in singular directions can fill it without changing fixed-λ cost.The resulting policy is an exact solution under the stated lemma.Source: §IV · p. 3

Cost per iteration

Each bisection step costs one Riccati recursion and one covariance propagation, or O(Hd^3) arithmetic.The number of steps to reach tolerance is logarithmic in the multiplier bracket divided by δ.Source: §IV · p. 3

V. EXTENSIONS AND APPLICATIONS

The framework extends to variants that preserve the structure of the Frank–Wolfe subproblems.

Extensions and applications

Across the stated extensions, the linear minimization oracle remains a generalized LQ problem solved with scalar bisection.The passage presents this as the preserved structure of the extensions.Source: §V · p. 3

A. Added LQR cost

The framework accommodates an added LQR cost and objectives over covariances at multiple horizons. In both cases, the Frank–Wolfe oracle retains a tractable LQ structure.

A. Added LQR cost

Adding a control-cost penalty leaves the smoothness and strong-convexity constants unchanged, while adding W^(0) to the gradient changes the LMO stage weight.The budget remains to keep the feasible set compact and may be inactive for large β.Source: A. Added LQR cost · p. 4

B. Covariances over multiple horizons

A multi-horizon objective rewards informativeness at intermediate times as well as at the experiment’s end.The achievable covariance tuple is convex, and its LMO uses time-varying stage weights with scalar bisection; the curvature bound is the sum of per-component bounds.Source: B. Covariances over multiple horizons · p. 4

C. Input design for system identification

For system identification, the method episodically designs inputs using estimated dynamics and information accumulated from prior data, optimizing over covariances achievable by causal feedback. In adaptive online LQR, it uses a receding-horizon Frank–Wolfe scheme to direct probing toward control-relevant directions.

C. Input design for system identification

The identification method optimizes directly over covariances achievable by causal feedback policies, unlike approaches restricted to classes such as periodic inputs,.Each episode uses the current dynamics estimate and accumulated information matrix to solve the design problem, then executes a selected policy and re-estimates the dynamics.Source: C. Input design for system… · p. 4

D. Adaptive online LQR

Adaptive online LQR minimizes certainty-equivalent control cost plus predicted excess cost from future estimation error, using a posterior over model parameters.The model-task Hessian and the regularized information matrix from collected data enter the prediction of future excess cost.Source: D. Adaptive online LQR · p. 4
At each update, the remaining-horizon budget is retained and the Frank–Wolfe linear minimization oracle becomes a generalized LQ problem with time-varying stage weights.The problem is re-solved in receding-horizon fashion using newly collected data to update the parameter estimate and information matrix.Source: D. Adaptive online LQR · p. 5
The adaptive scheme places probing energy only in directions that matter for control, which can enable lower regret when the system structure permits it.Source: D. Adaptive online LQR · p. 5

VI. NUMERICAL EXAMPLES

The numerical examples cover covariance design, system identification with unknown dynamics, and adaptive online LQR. The conclusion presents the Frank–Wolfe framework and identifies future work on regret guarantees and infinite-horizon formulations.

VI. NUMERICAL EXAMPLES

The examples illustrate the approach on known-dynamics covariance design, unknown-dynamics system identification, and adaptive online LQR.Source: §VI · p. 5

A. Covariance design

The covariance-design objective converges monotonically across 50 Frank–Wolfe iterations, and larger budgets yield more informative covariances and lower limiting values.Every iterate is feasible by construction; the observed convergence is consistent with the O(1/M) rate.Source: A. Covariance design · p. 5

B. Experiment design for system identification

The system-identification experiment compares certainty equivalence, random-input naive exploration, and a periodic-input baseline at the same energy budget per episode.It records the combined Frobenius estimation error for A and B and plots estimation error and design objective across Monte Carlo noise realizations.Source: B. Experiment design for system… · p. 5

C. Adaptive online LQR

The adaptive online LQR experiment uses a receding-horizon scheme with the identity matrix as a surrogate for the model-task Hessian.Source: C. Adaptive online LQR · p. 5
The experiment’s energy budget is enforced under estimated dynamics and may be violated under the true dynamics; a hard constraint can be tightened for model uncertainty.Source: C. Adaptive online LQR · p. 5
The Frank–Wolfe controller achieves lower regret than certainty-equivalent LQR with naive exploration in the adaptive online LQR experiment.The comparison uses 50 noise realizations; a sampling-based optimization serves as a reference for similar behavior.Source: C. Adaptive online LQR · p. 5

VII. CONCLUSION

The paper concludes that the same Frank–Wolfe machinery extends from covariance design to system identification and adaptive LQR, while regret guarantees and infinite-horizon formulations remain future work.Source: §VII · p. 5

APPENDIX

The appendix states that achievable covariance matrices form a closed set and includes numerical-figure descriptions for the design and adaptive-control results.

Appendix

The achievable covariance set C is closed.Source: A. Closedness of the achievable… · p. 5
Figure 1 plots objective by Frank–Wolfe iteration for several budgets, and identification error and design objective by episode for four methods.Source: Figure 1 · p. 6
Figure 2 compares cumulative regret for the proposed adaptive online LQR method, certainty-equivalent LQR with naive exploration, and a sampling-based baseline.Source: Figure 2 · p. 6
The proof constructs a policy for a limiting covariance sequence by preserving the covariance constraints and realizing the limit with linear feedback and independent noise.The stated covariance constraints include the state-transition relation under the system dynamics.Source: A. Closedness of the achievable… · pp. 5–6

B. Proof of Lemma 2

The proof establishes convexity of the objective and uses inverse-covariance bounds to analyze its derivatives over feasible covariance segments.

B. Proof of Lemma 2

The objective is convex because matrix inversion is convex on the positive definite cone, while the regularized covariance is affine and the weighted trace is linear and monotone.Source: B. Proof of Lemma 2 · p. 6
The gradient is strictly negative definite: the positive definite regularized inverse and positive definite weight yield ∇f(Σ) = −YW(1)Y ≺ 0.Source: B. Proof of Lemma 2 · p. 6
Along a feasible covariance segment, the inverse regularized covariance Yε has spectral norm bounded by λmin(Σ0)^−1.Source: B. Proof of Lemma 2 · p. 6

C. Proof of Theorem 1

The proof establishes an objective-gap bound by induction using the curvature bound, an approximate linear minimization oracle, and convexity. Strong convexity and first-order optimality then yield a bound on the iterates.

h_i ≤ 2C_f/(i + 2) + δ follows by induction from the curvature bound, the δ-approximate LMO, and convexity.The proof verifies the base case and induction step using α_i = 2/(i+2).Source: C. Proof of Theorem 1 · pp. 6–7
The inductive objective-gap estimate proves (10).The induction closes using (i + 1)(i + 3) ≤ (i + 2)^2.Source: C. Proof of Theorem 1 · p. 7
Strong convexity and first-order optimality at Σ⋆ provide the inequality used to bound the distance of iterates from the optimum.Applying it at Σ(M) together with (10) yields (11).Source: C. Proof of Theorem 1 · p. 7

D. Proof of Lemma 3

The proof characterizes admissible multipliers for the Riccati-based LQ subproblem and shows that the resulting budget use is continuous and nonincreasing in the multiplier. These properties support multiplier search and identify when the resulting policy is feasible and optimal.

For λ > ∥M∥₂/μ, the stage weight is positive definite, making the Riccati minimizations well posed; admissibility persists as λ increases.The admissible set is an open interval (λ_crit, ∞).Source: D. Proof of Lemma 3 · p. 7
The budget use b(λ) is continuous on the admissible interval and nonincreasing as λ increases.Continuity follows from the Riccati recursion and covariance propagation; monotonicity follows by comparing the optimal policies at two multipliers.Source: D. Proof of Lemma 3 · p. 7
If b(λ) ≤ β, the policy is feasible; if b(λ) = β, it solves the constrained subproblem.The proof establishes optimality by bounding the constrained objective and using feasibility for the reverse inequality.Source: D. Proof of Lemma 3 · p. 7
Under β > b₀, every λ ≥ λ̄ satisfies the stated upper bound on b(λ).The bound follows by combining the multiplier-dependent bounds and rearranging the resulting inequality.Source: D. Proof of Lemma 3 · p. 7