PaperlayerView exact revision on arXiv

Source-linked AI summary

LQR through the Lens of First Order Methods: Discrete-time Case

Jingjing Bu, Afshin Mesbahi, Maryam Fazel, Mehran Mesbahi

arXiv:1907.08921v2eess.SYcs.SYmath.OC

TL;DR

The paper addresses direct optimization of LQR feedback gains, rather than relying only on the traditional Riccati-equation route. It develops an initial-state-independent objective and first-order flows and iterations, proving global linear convergence for gradient methods and quadratic convergence for the quasi-Newton iteration.

  • Problem

    Traditional LQR synthesis obtains the feedback gain through the algebraic Riccati equation, while direct gain optimization is of interest for first-order and structured-control settings.

    Source: §1 · p. 2

  • Method

    The paper sums LQR costs over linearly independent initial states to form an initial-state-independent objective over stabilizing feedback gains, then studies gradient, natural gradient, and quasi-Newton flows and their discretizations.

    Source: §1 · pp. 2–3

  • Results

    Gradient descent and natural gradient descent converge linearly to the global optimum, while quasi-Newton iterates and function values converge quadratically.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The objective’s smoothness, coercivity, and gradient domination support well-posed flows with exponentially decaying Lyapunov functionals and exponentially stable trajectories.

    Source: §1 · p. 2

    For structured synthesis, the update analysis is restricted to the path-connected component containing the initialized feedback gain.

    Source: §7 · p. 28

Abstract

from arXiv · show

We consider the Linear-Quadratic-Regulator (LQR) problem in terms of optimizing a real-valued matrix function over the set of feedback gains. Such a setup facilitates examining the implications of a natural initial-state independent formulation of LQR in designing first order algorithms. It is shown that this cost function is smooth and coercive, and provide an alternate means of noting its gradient dominated property. In the process, we provide a number of analytic observations on the LQR cost when directly analyzed in terms of the feedback gain. We then examine three types of well-posed flows for LQR: gradient flow, natural gradient flow and the quasi-Newton flow. The coercive property suggests that these flows admit unique solutions while gradient dominated property indicates that the corresponding Lyapunov functionals decay at an exponential rate; we also prove that these flows are exponentially stable in the sense of Lyapunov. We then discuss the forward Euler discretization of these flows, realized as gradient descent, natural gradient descent and the quasi-Newton iteration. We present stepsize criteria for gradient descent and natural gradient descent, guaranteeing that both algorithms converge linearly to the global optima. An optimal stepsize for the quasi-Newton iteration is also proposed, guaranteeing a $Q$-quadratic convergence rate--and in the meantime--recovering the Hewer algorithm.

1 Introduction

The paper formulates LQR as direct optimization over feedback gains and analyzes continuous and discrete first-order methods for centralized and structured synthesis. It establishes convergence guarantees for these methods under their respective settings.

1 Introduction

  • Traditional LQR synthesis obtains the feedback gain through the algebraic Riccati equation, while direct gain optimization is motivated by first-order methods and distributed control.Distributed feedback gains can encode locality through a prescribed sparsity pattern.Source: §1 · pp. 1–2
  • Summing LQR costs over linearly independent initial states yields an initial-state-independent objective over stabilizing gains that is smooth, coercive, and gradient dominated.Its sublevel sets are compact, and the formulation attains a global minimum.Source: §1 · p. 2
  • Gradient, natural gradient, and quasi-Newton flows are well-posed, with exponentially decaying Lyapunov functionals and trajectories exponentially stable in the sense of Lyapunov.The paper attributes uniqueness of the flows to coercivity and exponential decay to gradient domination.Source: §1 · p. 2
  • Gradient descent and natural gradient descent converge linearly to the global optimum, while the quasi-Newton iteration converges quadratically.The quasi-Newton iteration is consistent with Hewer’s algorithm [3].Source: §1 · p. 3
  • For structured synthesis, the cost is smooth and coercive on the information-exchange subspace but is not gradient dominated, and the proposed stepsize ensures sublinear convergence to a first-order stationary point.The stepsize is obtained by bounding the Hessian over the initial sublevel set.Source: §1 · p. 3
  • The paper motivates the quasi-Newton iteration as a direct policy-space method, whereas prior emphasis was on convergence of value matrices.The iteration is consistent with Hewer’s algorithm [3].Source: §1 · p. 3
  • The paper notes that prior structured-synthesis work did not verify the stated stepsize conditions and could guarantee only convergence to a first-order stationary point.The stated convergence to a local minimum in is not necessarily valid for a nonconvex objective.Source: §1 · p. 3

2 Notation and Preliminaries

The preliminaries establish notation and recall matrix and function properties used in the paper’s analysis.

2 Notation and Preliminaries

  • The section defines matrix and vector notation, including transpose, spectral radius, rank, trace, vectorization, Kronecker product, and matrix norms.It also specifies conventions for eigenvalue ordering and positive semidefinite and definite comparisons.Source: §2 · p. 4
  • It defines smoothness and L-smoothness and recalls the Kalman rank condition for controllability.L-smoothness means the gradient is Lipschitz.Source: §2 · p. 4
  • The preliminaries name the set of Schur stabilizing feedback gains and collect matrix-equation relations whose proofs are attributed to.The supplied passages do not state the individual relations.Source: §2 · pp. 4–5

3 Problem Setup and its Analytic Properties

This section formulates discrete-time LQR as optimization over feedback gains, examines how the cost domain depends on the initial-state formulation, and establishes analytic properties of the initial-state-independent cost on stabilizing gains. It also bounds the cost gap by the squared gradient norm and estimates the gradient-dominance coefficient over a cost sublevel set.

3.1 Discrete-time LQR

  • Discrete-time LQR chooses a linear feedback gain u_k=-Kx_k to minimize a quadratic cost with Q⪰0 and R≻0; traditional solutions lead to the Algebraic Riccati Equation [2].Source: §3.1 · p. 5

3.2 Cost function for direct policy update

  • For a fixed initial state, the cost may be finite at some nonstabilizing gains, but stabilizing gains form the interior of its domain, where the cost is differentiable.Source: §3.2 · pp. 6–7

3.3 Initial condition independent formulation of LQR

  • Aggregating costs over linearly independent initial states makes f infinite for every nonstabilizing gain, so its effective domain is exactly the stabilizing gains.Source: §3.3 · p. 7

3.4 Analytical Properties of the LQR cost function

  • On the stabilizing set, f is real analytic and gradient dominated, diverges at the boundary and infinity, and has compact sublevel sets.Source: §3.4 · pp. 8–9
  • The unique global minimizer is K*=(B^T X* B+R)^-1 B^T X* A; the Hessian is characterized on stabilizing gains and positive definite at K*.Source: §3.4 · pp. 10–11
  • Over the sublevel set S_f(K0), the gradient-dominance coefficient satisfies τ ≤ f(K0) / [4λ_1(Q)λ_1(R)λ_1^2(Σ)].The passage states that this coefficient determines the linear convergence rate of gradient descent for LQR.Source: §3.4 · p. 13

4 Gradient Flow on S

The gradient flow on stabilizing gains has a unique solution and is globally exponentially stable. Its forward Euler discretization uses stepsizes that preserve stabilization and decrease the cost, yielding convergence to the optimum at a linear rate.

4 Gradient Flow on S

  • The gradient flow has a unique solution for every stabilizing initial gain and is globally defined for all time.Its vector field is smooth on the stabilizing-gain set.Source: §4 · pp. 13–14
  • The gradient-flow trajectory is globally exponentially stable in the sense of Lyapunov, with the cost gap also decaying exponentially.The rate constants depend on the LQR parameters and initial gain.Source: §4 · p. 14

4.1 Discretization of Gradient Flow

  • A stepsize rule for gradient descent guarantees both sufficient cost decrease and stabilizing iterates.The proof uses compact sublevel sets to rule out steps that leave the stabilizing region or fail to decrease the cost.Source: §4.1 · pp. 16–17
  • With the prescribed stepsize, gradient descent converges to the unique optimum at a linear rate.The iterates converge to K∗, and the cost gap contracts geometrically.Source: §4.1 · p. 19
  • The resulting iteration-complexity bound is conservative because its stepsize analysis uses crude bounds; simulations show faster convergence.The paper also notes that the observed linear rate is much better than the theoretical estimate.Source: §4.1 · pp. 19–20

5 Natural Gradient Flow on S

The natural gradient flow equips stabilizing gains with a Riemannian metric parameterized by γ and yields exponential decay and Lyapunov stability. Its discretization preserves stability under a stepsize bound, while a specified choice guarantees linear convergence of the cost.

5 Natural Gradient Flow on S

  • The metric induced by Y^γ defines a Riemannian structure on the stabilizing-gain set, with γ > 0 parameterizing the flow.The associated inner product is ⟨M,N⟩ = Tr(MᵀNY^γ).Source: §5 · p. 20
  • Under this metric, the natural gradient flow has an exponentially decaying energy functional and an exponentially stable trajectory.The convergence-rate factor depends on the eigenvalues of Y and can make the flow faster or slower than gradient flow.Source: §5 · pp. 21–22
  • For γ = 1, the value matrix along the natural gradient flow is well-posed and monotonically decreases in Loewner order.This monotonicity is not guaranteed for ordinary gradient flow, for which only Tr(X_tΣ) is guaranteed to decrease.Source: §5 · p. 22

5.1 Discretization of Natural Gradient Flow

  • In the discretization, η_j ≤ 1/(λ_n(R) + BᵀX_0B) guarantees stabilizing gains and nonincreasing value matrices.The stated bound also yields X_{j+1} ⪯ X_j.Source: §5.1 · p. 23
  • Choosing η_j = 1/(2λ_n(R + BᵀX_jB)) makes the function value converge linearly to its optimum.The paper notes that this discretization can outperform gradient descent, assessed by the one-step cost decrease.Source: §5.1 · p. 24

6 Quasi-Newton Flow on S

Because the LQR cost Hessian is not everywhere positive definite, the paper constructs a quasi-Newton flow from a local second-order approximation in a Riemannian metric. Its forward Euler iteration with stepsize 1/2 coincides with Hewer’s algorithm and converges quadratically to the global minimum.

6 Quasi-Newton Flow on S

  • The LQR cost has no well-defined global Newton iteration over policy space because its Hessian is not positive definite everywhere.The paper instead develops a local second-order approximation using the Riemannian metric Y.Source: §6 · p. 25
  • The local approximation expresses the cost change through a metric gradient term, a quadratic term weighted by R + BᵀXB, and a remainder of order O(∥ΔK∥²).It applies when K and K + ΔK are stabilizing for sufficiently small ΔK.Source: §6 · p. 25
  • Minimizing this local second-order approximation yields a quasi-Newton flow preconditioned by (R + BᵀX_tB)⁻¹.The resulting flow update moves the gain toward K_t − (R + BᵀX_tB)⁻¹BᵀX_tA.Source: §6 · p. 25

6.1 Discretization of Quasi-Newton Flow

  • With η_j < 1, the discrete quasi-Newton iterates remain stabilizing and their value matrices are nonincreasing in Loewner order.The stated result gives X_{j+1} ⪯ X_j.Source: §6.1 · p. 26
  • The optimal stepsize η_j = 1/2 makes the iteration coincide with Hewer’s algorithm and yields Q-quadratic convergence to the global minimum.Both the cost gap and the gain iterates converge quadratically.Source: §6.1 · p. 26

7 Structured LQR Synthesis

The section extends LQR gain optimization to feedback gains with prescribed sparsity, using projected gradient descent (PGD). It establishes convergence guarantees and a problem-dependent stepsize choice for this structured setting.

7 Structured LQR Synthesis

  • Structured LQR synthesis restricts feedback gains to a graph-compatible sparsity pattern, with inaccessible state-agent pairs assigned zero gain entries.The structure models distributed networked systems with a prescribed information-exchange graph.Source: §7 · p. 28
  • The stabilizing-gain set can have exponentially many path-connected components, and the analysis follows the component containing the initialized gain.Favorable system and graph structure can ensure a single component, but this paper does not further analyze that case.Source: §7 · p. 28

7.1 Convergence of Projected Gradient Descent

  • PGD is equivalent to gradient descent on the smooth restriction of the LQR cost to the structured subspace, and its iterates remain stabilizing.The restriction is coercive, which helps address the nonconvex geometry of the feasible set.Source: §7 · p. 28, §7.1 · p. 30
  • For L = sup_{K∈Sg(K0)} ||∇²g(K)|| and stepsize η = 1/L, projected gradient descent (33) converges to a first-order stationary point at a sublinear rate of O(1/k).Source: §7.1 · p. 31

7.2 Choosing the stepsize for projected gradient descent

  • A problem-dependent Lipschitz bound on the cost gradient over a sublevel set supplies a stepsize using the LQR parameters and initial gain.The bound can be re-estimated as cost values decrease, though the resulting stepsize may be smaller than the unstructured-case choice.Source: §7.2 · p. 33

8 Simulation Results

Simulations illustrate exponential stability of the continuous flows and convergence of their discrete updates. The relative performance of gradient and natural gradient flows depends on the initial-state matrix, while quasi-Newton and projected gradient descent show their stated convergence behavior in the tested settings.

8 Simulation Results

  • For Σ = 0.5I, natural gradient flows converge faster than gradient flow when λ1(Y) < 1, and the Y²-induced metric outperforms the Y-induced metric.The simulations report exponential stability of the trajectories and exponential decay of the Lyapunov functionals.Source: §8 · p. 34, Figure 3 · p. 34
  • With initial-state matrix Σ = 2I, Figure 4 reports exponential stability of trajectory Kt, while Figure 5 reports exponential decay of the Lyapunov functional.Source: Figure 4 · p. 34, Figure 5 · p. 34
  • Adaptive-step gradient descent stabilizes its feedback-gain iterates and converges to the global optimal gain, while its cost converges linearly.The reported adaptive stepsize is 4.5.Source: §8 · p. 35, Figure 6 · p. 35, Figure 7 · p. 35
  • Natural gradient descent converges linearly in the simulations and is faster than gradient descent.The simulations report relative-error convergence for both the feedback gain and LQR cost.Source: §8 · p. 35, Figure 8 · p. 35, Figure 9 · p. 35
  • With stepsize 1/2, the quasi-Newton iteration recovers Hewer’s algorithm and exhibits quadratic convergence in the tested setting.The paper reports this as the fastest convergence rate among the tested discrete updates.Source: §8 · p. 35
  • On a lollipop-graph system, projected gradient descent produces stabilizing gains that converge to a first-order stationary point.The projection zeros gain entries that do not correspond to graph edges, and the cost is also shown to converge.Source: §8 · p. 36, Figure 12 · p. 36

9 Concluding Remarks

The paper analyzes LQR directly over stabilizing feedback gains and examines continuous flows and their discretizations. It also treats structured LQR, where projected gradient descent has a sublinear convergence guarantee to a first-order stationary point.

9 Concluding Remarks

  • Figure 13 plots the relative error of the LQR cost under projected gradient descent on a lollipop graph.Source: Figure 13 · p. 36
  • The paper presents the LQR cost as a smooth, coercive, gradient-dominated objective over stabilizing feedback gains and examines gradient, natural-gradient, and quasi-Newton flows.Source: §9 · p. 36
  • For structured LQR, projected gradient descent with the proposed stepsize rule converges sublinearly to a first-order stationary point.Source: §9 · p. 37
  • Forward Euler discretizations of the examined flows yield algorithms with linear and quadratic convergence rates.Source: §9 · p. 37

A Bounding ∥Y ′(θ)∥2 in Lemma 4.5

This appendix section develops a derivative bound for Y′(θ), considering a specified gain update and using Proposition 2.1. The supplied passages also identify the choice of υ that minimizes an upper bound.

A Bounding ∥Y ′(θ)∥2 in Lemma 4.5

B Lower Bounding Stepsize ηj in Gradient Descent

The appendix establishes that the stepsize ηj from Theorem 4.6 is bounded away from zero, a condition the text identifies as important for linear convergence. The bound is obtained by bounding bj and cj over a sublevel set.

B Lower Bounding Stepsize ηj in Gradient Descent

Loading 1907.08921v2…