# Accelerated Optimization Landscape of Linear-Quadratic Regulator

arXiv: https://arxiv.org/abs/2307.03590 · HTML: https://mlsanity.com/paper/2307.03590/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 48 references that are in the map.
- First posted on arXiv 7 Jul 2023.

## Builds on (most cited first, 29 of 29)

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [A Variational Perspective on Accelerated Methods in Optimization](https://mlsanity.com/paper/1603.04245/) (2016)
- [Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent](https://mlsanity.com/paper/1711.10456/) (2017)
- [Policy Optimization for H2 Linear Control with H_∞ Robustness Guarantee: Implicit Regularization and Global Convergence](https://mlsanity.com/paper/1910.09496/) (2019)
- [Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problem](https://mlsanity.com/paper/1912.11899/) (2019)
- [LQR through the Lens of First Order Methods: Discrete-time Case](https://mlsanity.com/paper/1907.08921/) (2019)
- [A Dynamical Systems Perspective on Nesterov Acceleration](https://mlsanity.com/paper/1905.07436/) (2019)
- [Conformal Symplectic and Relativistic Optimization](https://mlsanity.com/paper/1903.04100/) (2019)
- [Analysis of the Optimization Landscape of Linear Quadratic Gaussian (LQG) Control](https://mlsanity.com/paper/2102.04393/) (2021)
- [Acceleration via Symplectic Discretization of High-Resolution Differential Equations](https://mlsanity.com/paper/1902.03694/) (2019)
- [Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives](https://mlsanity.com/paper/2002.12493/) (2020)
- [Optimizing Static Linear Feedback: Gradient Method](https://mlsanity.com/paper/2004.09875/) (2020)
- [Stabilizing Dynamical Systems via Policy Gradient Methods](https://mlsanity.com/paper/2110.06418/) (2021)
- [First-order optimization algorithms via inertial systems with Hessian driven damping](https://mlsanity.com/paper/1907.10536/) (2019)
- [Accelerated Methods for Non-Convex Optimization](https://mlsanity.com/paper/1611.00756/) (2016)
- [Learning the Globally Optimal Distributed LQ Regulator](https://mlsanity.com/paper/1912.08774/) (2019)
- [Global Convergence of Policy Gradient Primal-dual Methods for Risk-constrained LQRs](https://mlsanity.com/paper/2104.04901/) (2021)
- [Generalized Momentum-Based Methods: A Hamiltonian Perspective](https://mlsanity.com/paper/1906.00436/) (2019)
- [Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Lojasiewicz Functions when the Non-Convexity is Averaged-Out](https://mlsanity.com/paper/2206.11872/) (2022)
- [Fixed-Time Stable Gradient Flows: Applications to Continuous-Time Optimization](https://mlsanity.com/paper/1808.10474/) (2018)
- [Optimization Landscape of Gradient Descent for Discrete-time Static Output Feedback](https://mlsanity.com/paper/2109.13132/) (2021)
- [From differential equation solvers to accelerated first-order methods for convex optimization](https://mlsanity.com/paper/1909.03145/) (2019)
- [A Unified Convergence Analysis of First Order Convex Optimization Methods via Strong Lyapunov Functions](https://mlsanity.com/paper/2108.00132/) (2021)
- [Escaping High-order Saddles in Policy Optimization for Linear Quadratic Gaussian (LQG) Control](https://mlsanity.com/paper/2204.00912/) (2022)
- [Geometric Optimization Methods for Adaptive Filtering](https://mlsanity.com/paper/1305.1886/) (2013)
- [An Accelerated Proximal Alternating Direction Method of Multipliers for Optimal Decentralized Control of Uncertain Systems](https://mlsanity.com/paper/2304.11037/) (2023)
- [On the Optimization Landscape of Dynamic Output Feedback: A Case Study for Linear Quadratic Regulator](https://mlsanity.com/paper/2209.05042/) (2022)

## Abstract (arXiv)

Linear-quadratic regulator (LQR) is a landmark problem in the field of optimal control, which is the concern of this paper. Generally, LQR is classified into state-feedback LQR (SLQR) and output-feedback LQR (OLQR) based on whether the full state is obtained. It has been suggested in existing literature that both SLQR and OLQR could be viewed as textitconstrained nonconvex matrix optimization problems in which the only variable to be optimized is the feedback gain matrix. In this paper, we introduce a first-order accelerated optimization framework of handling the LQR problem, and give its convergence analysis for the cases of SLQR and OLQR, respectively. Specifically, a Lipschiz Hessian property of LQR performance criterion is presented, which turns out to be a crucial property for the application of modern optimization techniques. For the SLQR problem, a continuous-time hybrid dynamic system is introduced, whose solution trajectory is shown to converge exponentially to the optimal feedback gain with Nesterov-optimal order 1-frac1√kappa (kappa the condition number). Then, the symplectic Euler scheme is utilized to discretize the hybrid dynamic system, and a Nesterov-type method with a restarting rule is proposed that preserves the continuous-time convergence rate, i.e., the discretized algorithm admits the Nesterov-optimal convergence order. For the OLQR problem, a Hessian-free accelerated framework is proposed, which is a two-procedure method consisting of semiconvex function optimization and negative curvature exploitation. In a time O(ε-7/4log(1/ε)), the method can find an ε-stationary point of the performance criterion; this entails that the method improves upon the O(ε-2) complexity of vanilla gradient descent. Moreover, our method provides the second-order guarantee of stationary point.