PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimizing Static Linear Feedback: Gradient Method

Ilyas Fatkhullin, Boris Polyak

arXiv:2004.09875v2math.OC

TL;DR

Static output feedback lacks an explicit-form solution and presents unresolved existence and optimality challenges. The paper treats state and output feedback gains as matrix-optimization variables and analyzes gradient methods, proving convergence to the state-feedback optimum and to stationary points for output feedback.

  • Problem

    Static output feedback has unresolved existence and optimality challenges, with no simple optimality certificates when a stabilizing controller exists.

    Source: §1 · p. 1

  • Method

    The paper optimizes the feedback gain matrix directly and applies gradient methods to the resulting objective over stabilizing controllers.

    Source: §1 · p. 1

  • Results

    State-feedback gradient descent converges to the single minimizer at a linear rate, while output-feedback analysis establishes convergence and a rate to stationary points.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The proof technique applies to both state and output feedback, unlike convex reparameterization, which is available only for state control.

    Source: §1 · p. 2

    For output feedback, multiple minima may occur, and whether the method converges only to a local minimum or can reach a saddle point remains open.

    Source: §1 · p. 2, §7 · p. 14

Abstract

from arXiv · show

The linear quadratic regulator is the fundamental problem of optimal control. Its state feedback version was set and solved in the early 1960s. However the static output feedback problem has no explicit-form solution. It is suggested to look at both of them from another point of view as matrix optimization problems, where the variable is a feedback matrix gain. The properties of such a function are investigated, it turns out to be smooth, but not convex, with possible non-connected domain. Nevertheless, the gradient method for it with the special step-size choice converges to the optimal solution in the state feedback case and to a stationary point in the output feedback case. The results can be extended for the general framework of unconstrained optimization and for reduced gradient method for minimization with equality-type constraints.

1. Introduction.

The introduction frames static output feedback as a difficult optimization problem and proposes direct gradient optimization over feedback gains. It presents convergence results for state feedback and stationary-point guarantees for output feedback, alongside extensions to broader optimization methods.

1. Introduction.

  • Static output feedback remains challenging because stabilizing controllers may not exist, optimality conditions are only necessary, and many iterative methods lack rigorous validation or require hard nonlinear solves.When stabilizing controllers exist, necessary conditions take the form of nonlinear matrix equations.Source: §1 · p. 1
  • Direct gradient optimization treats the feedback gain as the variable and applies unconstrained minimization to the performance function on the open set of stabilizing gains.The approach presupposes a known initial stabilizing controller.Source: §1 · pp. 1–2
  • Output-feedback domains may be disconnected and contain multiple local minima, so convergence to a stationary point is a realistic guarantee.The introduction notes that local minima in different connected components can have different values.Source: §1 · p. 2

Contributions of the paper

  • For continuous-time state feedback, the paper proves convergence to the single minimizer with a linear rate using a technique applicable to both state and output feedback.The authors contrast this with a change-of-variables approach that applies only to state control.Source: §1 · p. 2
  • For output feedback, the paper establishes convergence and convergence-rate results for stationary points based on the objective function's L-smoothness.The analysis also applies to parametric LQR problems, including low-order, PID, and decentralized control.Source: §1 · p. 2
  • The paper develops specialized gradient and conjugate-gradient step-size rules and a globally convergent reduced-gradient method, with extensions to general optimization settings.The paper is organized around the objective's properties, gradient convergence, simulations, and links to unconstrained and equality-constrained optimization.Source: §1 · p. 2

2. Problem Statement.

The problem statement represents LQR as optimization over a static feedback gain, with the performance cost expressed through a Lyapunov equation. It assumes an initial stabilizing gain is available and distinguishes state from output feedback.

2. Problem Statement.

  • The infinite-horizon LQR problem uses static control u(t) = −Ky(t), with gain K as the optimization variable and performance f(K) defined only for stabilizing gains.The system has state x and output y; the control cost uses positive-definite Q and R, and the initial-state distribution has covariance Σ.Source: §2 · p. 3
  • The method assumes a known initial stabilizing gain K0; if A is Hurwitz, K0 = 0 is one available choice.The stated goal is to improve the performance of this known regulator.Source: §2 · p. 3
  • The assumptions require Q, R, and Σ to be positive definite, rank(C) = r, and B ≠ 0, but impose no controllability or observability assumptions.The text notes that Q ≻ 0 can sometimes be relaxed to Q ⪰ 0, but does not pursue that case.Source: §2 · p. 3
  • SLQR denotes the case C = I, where the state is available, while OLQR denotes the case C ≠ I, where only the output is available.The corresponding objectives are denoted fS(K) and fO(K).Source: §2 · p. 3
  • The performance objective is f(K) = Tr(X(K)Σ), where X(K) solves the Lyapunov equation associated with the closed-loop system and quadratic cost.The matrix equality constraint is (A − BKC)⊤X + X(A − BKC) + C⊤K⊤RKC + Q = 0, with X ≻ 0.Source: §2 · p. 4

3. Properties of f(K).

The examples and analysis characterize the objective f(K) and its stabilizing domain S: S may be nonconvex or disconnected, while bounded sublevels support important regularity and existence results.

3.1. Examples.

  • Examples show convex S and f in the 1D case, nonconvex S with nonsmooth boundary in other state-feedback cases, and output-feedback domains with disconnected components or multiple minima.For α = −1, the output-feedback domain has two components with one minimum each; for α = −1.4, it is a connected ray with two local minima. The α = 1.2 example has two local minima and a saddle point.Source: §3.1 · pp. 4–6

3.2. Connectednes of S, S0.

  • When C = I, both S and each sublevel set S0 are connected; the proof uses a convex reparameterization that does not extend to output feedback.For output feedback, the paper reports no convex reparameterization of this kind.Source: §3.2 · pp. 6–7

3.3. f(K) is coercive and S0 is bounded.

  • The objective f(K) is coercive, every sublevel set S0 is bounded, and a minimum point K∗ exists in S.The existence result follows from bounded sublevel sets and the minimum being attained away from the boundary of S.Source: §3.3 · p. 7

3.4. Gradient of f(K).

  • The gradient is differentiable, but general minimizers require solving nonlinear matrix equations numerically; in state feedback, the optimal gain reduces to a Riccati equation.Even in the state-feedback case, the Riccati equation must be solved numerically.Source: §3.4 · pp. 7–8

3.5. Second derivative of f(K).

  • Although f(K) can be nonconvex, it is strongly convex in a neighborhood of the state-feedback minimum K∗.The Hessian is positive definite at K∗, yielding this local strong-convexity result.Source: §3.5 · pp. 8–9

3.6. f(K) is L-smooth on S0.

  • The gradient of f(K) is L-smooth on S0, though not on all of S; its level sets are smooth even when the boundary of S is not.The smoothness result is restricted to the sublevel set S0.Source: §3.6 · p. 9

3.7. Gradient domination property.

  • On S0, fS(K) satisfies the LPL condition, but this guarantee does not extend to all of S or to output feedback.The constant depends on K0 and tends to zero as fS(K) tends to infinity; output-feedback examples violate the condition through unequal component minima or multiple minima in one component.Source: §3.7 · p. 10

4. Methods.

The methods use a known stabilizing controller to initialize gradient minimization of f(K). They are monotone, with global convergence to the minimum for state feedback and to a stationary point for output feedback.

4. Methods.

  • The methods start from a known stabilizing controller; state feedback converges globally to the minimum, whereas output feedback converges to a stationary point.The methods are developed for minimizing f(K), which is defined on the stabilizing-controller domain.Source: §4 · p. 10

4.1. Continuous Method.

  • The continuous flow exists for all time and decreases f(K); when C = I, it converges exponentially to the global minimum.The theorem also bounds the minimum squared gradient norm over a finite interval by f(K0)/T.Source: §4.1 · p. 10

4.2. Discrete Method.

  • For state feedback, the discrete method produces a nonincreasing objective sequence and converges linearly to the global minimum when C = I.The stated convergence result applies while the iterates remain in the stabilizing domain.Source: §4.2 · pp. 10–11

4.3. Algorithm.

  • Algorithm 4.1 uses step reductions, whose number is uniformly bounded, and retains the convergence guarantees of the discrete method.The paper also describes a step-size choice that keeps new iterates stabilizing, avoiding a stabilizing-domain check at each iteration.Source: §4.3 · p. 12

5. Simulation.

The simulations compare gradient and conjugate-gradient variants, reporting fast high-accuracy convergence on low-dimensional tests and differing convergence behavior on a medium-size state-feedback problem. The authors characterize these calculations as preliminary.

Simulation results

  • 10–20 iterations: Algorithm 4.1 converged to global or local minimizers with high accuracy across the low-dimensional tests.The authors report it was superior to the other tested step-size versions in those examples.Source: §5 · p. 12
  • In the n = 100, m = 10 test, conjugate gradient strongly accelerated convergence, GDN converged satisfactorily, and GD r was very slow.GDN required approximately 10 step reductions or truncations over 100 iterations; Figure 8 illustrates the three methods.Source: §5 · p. 12

Limitations

  • The authors call the calculations preliminary and say more work is needed on state-feedback algorithms and output-feedback behavior.They identify competition with Riccati-equation methods as a goal for state-feedback algorithms.Source: §5 · p. 12

6. Links with general optimization problems.

The paper extends feedback-minimization ideas to unconstrained step-size selection, conjugate gradient, and equality-constrained optimization. The extensions rely on problem-specific conditions for convergence.

6.1. Step-size choice for gradient descent.

  • The proposed step-size rule extends to smooth unconstrained optimization and is promising when its denominator's quadratic form is efficient to compute.It avoids requiring L and μ; for quadratic functions it coincides with steepest descent, while rigorous validation for nonquadratic functions is given for the strongly convex case.Source: §6.1 · pp. 12–13
  • For strongly convex functions with Lipschitz-continuous gradient and Hessian, the method converges linearly to the global minimizer under the theorem's stated initial-condition requirement.The paper also states a convergence result for arbitrary initial points under a condition involving L.Source: §6.1 · p. 13

6.2. New version of the conjugate gradient method.

  • The authors propose replacing one-dimensional step-size minimization in conjugate gradient with a different step-size approach, but say convergence results remain prospective.They provide the simplest of several possible formulas for βj.Source: §6.1 · p. 14, §6.2 · p. 14

6.3. Reduced gradient method.

  • For equality-type constraints, the reduced gradient method optimizes F(y) = f(x(y), y) after solving the constraint for x(y).The paper says global convergence analysis would require analogues of its L-smoothness and LPL conditions.Source: §6.3 · p. 14

7. Conclusion.

The conclusion identifies local acceleration and unresolved output-minimization questions as directions for further work, while noting that validation of extensions remains open. Appendix A supplies a trace identity for solutions of dual Lyapunov equations.

7. Conclusion.

  • Local acceleration is a direction for further work because fS(K) is strongly convex near the optimal solution K∗.The conclusion says accelerated methods can therefore apply to local convergence.Source: §7 · p. 14
  • Output minimization leaves open whether multiple minima occur in one connectivity component and whether the method can converge to a saddle point.The conclusion also says validation of extensions to decentralized control and other parametric LQR problems remains open.Source: §7 · p. 14

Appendix A. Basic Facts.

  • For solutions X and Y to dual Lyapunov equations with Hurwitz matrix A, Appendix A states Tr(XV) = Tr(YW).Source: Appendix A · p. 15

B.1. Proof of Lemma 3.8.

The proof passages use stability-degree and Lyapunov-equation estimates, then construct bounds intended to yield a uniform estimate for Theorem 3.15. The excerpts provide only partial details of those arguments.

B.1. Proof of Lemma 3.8.

  • The B.1 proof tracks the stability degree as stabilizing gains approach the boundary, where the degree tends to zero.It then estimates quantities from the associated Lyapunov equations; the excerpt does not state the lemma’s full conclusion.Source: §B.1 · p. 15

B.2. Proof of Theorem 3.15.

  • The B.2 proof seeks a uniform estimate depending only on problem parameters and K0, using bounds on X′ relative to X.It sets X′ ⪯ αX for some constant α and uses that bound to control ∥X′∥F.Source: §B.2 · pp. 16–17
  • The proof chooses α and β through a two-dimensional minimization with a relaxed matrix-inequality constraint.The passage says the estimate (3.8) follows by applying the resulting bounds.Source: §B.2 · pp. 16–17

Appendix C. Analysis of SLQR.

The appendix develops technical bounds for state-feedback LQR and uses them in proofs concerning the objective and gradient flow. The flow proof relies on monotonicity to keep the trajectory in its initial sublevel set.

C.1. Technical Lemmas.

  • For state feedback, the technical lemmas bound the gain when f(K) is bounded and bound an eigenvalue of a Lyapunov-equation solution in terms of f(K).The appendix also states a lemma for K∗, K0, and K in S0 and gives a relation involving M = RK − B⊤X.Source: §C.1 · pp. 17–18

C.2. Proof of Theorem 3.17.

  • The proof of Theorem 3.17 follows by substituting the cited bounds into the technical lemma.Source: §C.2 · p. 18

D.1. Proof of Theorem 4.1.

  • Along the gradient flow, f(Kt) is monotone and K(t) remains in S0, allowing the proof to apply L-smoothness along the trajectory.Source: §D.1 · p. 18

D.2. Proof of Theorem 4.2.

The proof establishes a safe initial step by bounding the first intersection with the boundary of S0. It then uses L-smoothness along the descent trajectory; the following proof passage says its argument can be reconstructed from the algorithm’s formulation.

D.2. Proof of Theorem 4.2.

  • The proof bounds smoothness up to the first boundary intersection by restricting the ray to the bounded sublevel set S0.At the intersection, the objective returns to its starting value, which yields the lower bound on the intersection time.Source: §D.2 · p. 19
  • The first boundary intersection occurs no earlier than 2/L, so the initial gradient step remains in S0 for 0 ≤ t ≤ 2/L.The proof applies L-smoothness along the descent trajectory to complete the convergence argument.Source: §D.2 · p. 19

D.3. Proof of Theorem 4.3.

  • The D.3 proof can be reconstructed from the comments that led to the algorithm’s formulation.Source: §D.3 · p. 19

D.4. Proof of Theorem 6.1.

The proof establishes decrease of the iterates’ objective under a gradient-based condition, using smoothness and strong convexity to support its convergence argument.

D.4. Proof of Theorem 6.1.

  • The proof states that condition (6.2) ensures its per-step condition is satisfied.Source: §D.4 · p. 19
  • When M∥∇f(x_j)∥ < 3µ^2, the proof obtains φ_{j+1} < φ_j, and the objective sequence is strictly decreasing.Source: §D.4 · p. 19
  • The proof applies the smooth, strongly convex function inequality to x_j and the gradient step x_j − σγ_j∇f(x_j).Source: §D.4 · p. 19
Loading 2004.09875v2…