PaperlayerView exact revision on arXiv

Source-linked AI summary

LQG Control with Minimum Directed Information: Semidefinite Programming Approach

Takashi Tanaka, Peyman Mohajerin Esfahani, Sanjoy K. Mitter

arXiv:1510.04214v3math.OCcs.ITmath.IT

TL;DR

LQG control requires balancing achievable performance against the data-rate of feedback, and this paper asks for the minimum directed information compatible with a target performance. It characterizes that trade-off and gives an SDP-based synthesis; for directly observable plants, the resulting policy uses a linear sensor, Kalman filter, and certainty-equivalence controller.

  • Problem

    The paper asks how to minimize directed information from plant observations to control inputs while attaining a desired level of LQG control performance, addressing the trade-off between control performance and feedback data-rate.

    Source: §I · p. 1, A. Contributions of this paper · p. 2

  • Method

    The rate-performance trade-off is defined by optimizing directed information over causal decision policies, and the optimal policy is synthesized using semidefinite programming.

    Source: §I · p. 1, D. Connections to existing results · p. 6, §VIII · p. 11

  • Results

    For directly observable plants, the optimal policy has a linear sensor with additive Gaussian noise, a Kalman filter, and a certainty-equivalence controller; the directed-information trade-off also has a finite-dimensional characterization.

    Source: B. Time-invariant plants · p. 5, §VIII · p. 11

  • Takeaways & Limitations

    The designed linear sensor is optimal among all nonlinear (Borel measurable) sensor mechanisms.

    Source: D. Connections to existing results · p. 6

Abstract

from arXiv · show

We consider a discrete-time Linear-Quadratic-Gaussian (LQG) control problem in which Massey's directed information from the observed output of the plant to the control input is minimized while required control performance is attainable. This problem arises in several different contexts, including joint encoder and controller design for data-rate minimization in networked control systems. We show that the optimal control law is a Linear-Gaussian randomized policy. We also identify the state space realization of the optimal policy, which can be synthesized by an efficient algorithm based on semidefinite programming. Our structural result indicates that the filter-controller separation principle from the LQG control theory, and the sensor-filter separation principle from the zero-delay rate-distortion theory for Gauss-Markov sources hold simultaneously in the considered problem. A connection to the data-rate theorem for mean-square stability by Nair and Evans is also established.

I. INTRODUCTION

The paper studies the trade-off between LQG control performance and the information rate fed back to a controller, where rate-performance analysis faces uncertainty about rate definitions and computationally difficult optimizations. It characterizes minimum directed information policies and develops an SDP synthesis framework, connecting the rate-performance trade-off to the data-rate theorem for mean-square stability.

I. INTRODUCTION

  • Rate-performance analysis still faces uncertainty about whether different data-rate definitions yield different conclusions and often requires intractable optimization.The paper contrasts these challenges with stability results that are invariant across several data-rate definitions.Source: §I · p. 1
  • Directed information is selected as a causality-based measure of information flow from observation to action, and prior work gives it an operational lower-bound interpretation in a practical NCS setup –.In that setup, it lower-bounds the minimum operational data-rate needed for the desired control performance.Source: §I · p. 1

A. Contributions of this paper

  • The central question is which causal policy minimizes directed information while attaining a required level of LQG control performance.The paper frames this as a data-frugal control problem.Source: A. Contributions of this paper · p. 2
  • The optimal policy has a linear sensor with additive Gaussian noise, a Kalman filter, and a certainty-equivalence controller, with an extension to partially observed plants.The paper also reports that the designed linear sensor is optimal among nonlinear Borel-measurable sensor mechanisms.Source: A. Contributions of this paper · p. 2
  • An SDP framework makes the rate-performance trade-off computationally accessible and recovers the mean-square stability data-rate theorem as a special case; its asymptote coincides with Nair and Evans’s critical rate.The paper also gives a single-letter characterization for the time-invariant problem through a finite-dimensional optimization.Source: A. Contributions of this paper · p. 2

B. Organization of this paper

  • The paper proceeds from notation and problem formulation to operational interpretation, main results, a numerical example, derivations, and the partially observable extension.Its notation defines x_t as a sequence through time t and uses N(μ, Σ) for a Gaussian distribution.Source: B. Organization of this paper · p. 2, C. Notational remarks · p. 2

III. OPERATIONAL MEANING

The paper relates the data-rate needed for LQG control over a noiseless binary channel to minimum directed information, then characterizes an optimal policy and its synthesis. For time-varying plants, the policy uses a virtual sensor, Kalman filter, and certainty-equivalence controller, with components constructed by an SDP-based algorithm.

III. OPERATIONAL MEANING

  • For a fully observable, time-invariant MIMO plant sending state information over a noiseless binary channel, the design minimizes data-rate among policies attaining control cost smaller than D; Silva et al. observed R(D) is closely related to DI(D).Source: §III · p. 3

A. Time-varying plants

  • The optimal policy for the full-state, time-varying problem can be realized by a virtual sensor, Kalman filter, and certainty-equivalence controller.The virtual sensor acquires task-relevant state information while discarding less important information; it may be a computational procedure rather than a physical sensor.Source: A. Time-varying plants · p. 4, §1 · p. 4

1. A linear sensor mechanism

  • The synthesis procedure designs the controller first, then schedules covariance matrices through virtual-sensor design, and finally constructs the Kalman filter.The scheduled covariance is realized by the later virtual-sensor and filter designs.Source: §1 · pp. 4–5
  • A max-det problem is feasible exactly when an optimal policy exists, and its optimal value equals the control problem’s value.When the value is finite, an SDP-based algorithm constructs the virtual sensor, Kalman filter, and certainty-equivalence controller.Source: §1 · p. 5

B. Time-invariant plants

For time-invariant plants, the optimal policy exists exactly when a max-det problem is feasible and can be built from a virtual sensor, Kalman filter, and certainty-equivalence controller. The resulting characterization also connects finite-performance data-rate requirements to the mean-square stabilization threshold.

B. Time-invariant plants

  • The time-invariant problem has an optimal policy exactly when the max-det problem is feasible, with matching optimal values and time-invariant virtual-sensor, Kalman-filter, and controller components.The components are constructed through controller, virtual-sensor, and filter design steps.Source: B. Time-invariant plants · p. 5
  • The directed-information rate-performance function has a single-letter characterization through a finite-dimensional optimization problem.The max-det representation also yields a closed-form expression for its limit as the performance bound tends to infinity, interpreted as the minimum rate for mean-square stabilization.Source: B. Time-invariant plants · p. 5, C. Data-rate theorem for mean-square… · p. 5

C. Data-rate theorem for mean-square stabilization

  • The minimum rate for mean-square stabilization is independent of process-noise covariance, whereas achieving a finite performance bound depends on it.The paper also states that a quantized LQG scheme over a noiseless binary channel can approach the stabilization rate arbitrarily closely while achieving mean-square stability.Source: C. Data-rate theorem for mean-square… · p. 5

D. Connections to existing results

The section situates the proposed structure among related rate-distortion and LQG results, then illustrates its rate-performance behavior and outlines why the optimization can be restricted to a separated policy class.

D. Connections to existing results

  • The problem is related to sequential rate-distortion, but the same sensor-filter structure was not known when feedback controllers must be designed simultaneously.The uncontrolled Gaussian source has a two-stage sensor-filter realization; the cited feedback-related formulations do not report the paper's structural result.Source: D. Connections to existing results · p. 6
  • The optimal policy has a three-stage state-space realization beyond the compatible AWGN-channel and linear-filter realization independently reported in.The authors describe the three-stage structure as a new observation to the best of their knowledge.Source: D. Connections to existing results · p. 6
  • The SDP algorithms extend related results to MIMO and time-varying settings, where analytical expressions for optimal policies may be unavailable.The paper develops SDP-based algorithms for problems (4), (6), and (38).Source: D. Connections to existing results · p. 6

V. EXAMPLE

  • As D changes, the rank of SNR(D) drops at phase transitions, changing the optimal sensor-output dimension.Figure 5 plots DI(D), truncated SNR(D) rank, and selected singular-value spectra.Source: §V · p. 6, Figure 5 · p. 7
  • For control performance D = 33, the minimum data rate is 6.133 bits/sample; for D = 40, the required rate is 3.266 bits/sample; and for D = 80, it is 1.602 bits/sample.Source: §V · p. 6

A. Proof outline

  • The proof chain shows that solving the simplified problem (22e) yields an optimal solution to the original problem (22a) within the three-stage class Γ0.This establishes the sensor-filter-controller separation structure.Source: A. Proof outline · p. 7

B. Proof of inequality (22c)

The proof replaces general policies with Gaussian and then linear-sensor constructions while preserving control cost and not increasing information cost.

B. Proof of inequality (22c)

  • A jointly Gaussian law with the same covariance as a feasible policy can be used to construct a Gaussian policy in Γ2.The construction uses the least-mean-square estimate of the control given the state and previous controls, with Gaussian estimation error.Source: B. Proof of inequality (22c) · p. 8
  • Replacing the original policy with the constructed Gaussian policy preserves LQG control cost and does not increase information cost.The proof uses equality of second-order moments and the equality of the relevant joint Gaussian measures.Source: B. Proof of inequality (22c) · p. 8

C. Proof of inequality (22d)

  • The constructed sensor output and the intermediate signal contain statistically equivalent information, allowing the control action to be represented as a linear map of the sensor output.Source: C. Proof of inequality (22d) · p. 8
  • A policy in Γ2 can be converted into a linear sensor and linear deterministic controller in Γ1 with the same joint distribution and control cost.The sensor is yt = Ctxt + vt, with vt Gaussian.Source: C. Proof of inequality (22d) · p. 8

D. Proof of inequality (22e)

For a fixed linear sensor, the information cost depends on its SNR while the control cost is optimized through Kalman filtering and certainty-equivalence control; the resulting optimization is converted to a max-det problem.

D. Proof of inequality (22e)

  • For a fixed linear sensor, conditional mutual information depends on the SNR sequence, while control cost is minimized by a Kalman filter followed by certainty-equivalence control.This establishes that an optimal solution can be found in the three-stage policy class Γ0.Source: D. Proof of inequality (22e) · pp. 8–9

E. Proof of inequality (22f)

F. SDP formulation of problem (22e)

  • The optimization over covariance and SNR variables is reformulated as a max-det problem, and the resulting steps provide an optimal solution to the original problem.The reformulation eliminates SNR variables and rewrites the objective using determinant identities and the matrix inversion lemma.Source: F. SDP formulation of problem (22e) · p. 9

VII. EXTENSION TO PARTIALLY OBSERVABLE PLANTS

For partially observable plants, an optimal policy exists exactly when the associated max-det problem is feasible, and its optimal value matches that problem. The policy has a Kalman-filter, virtual-sensor, and certainty-equivalence structure synthesized by SDP-based algorithms.

VII. EXTENSION TO PARTIALLY OBSERVABLE PLANTS

  • The partially observable optimal policy is realizable in state space and synthesizable by an SDP-based algorithm.Figure 8 identifies matrices ˜L_t, C_t, V_t, L_t, and K_t as determined by that algorithm.Source: §VII · p. 10, Figure 8 · p. 10
  • Theorem 3 equates feasibility of max-det problem (41) with existence of an optimal policy and equates their optimal values.The stated plant model assumes independent Gaussian initial state and noises, with a full-row-rank sensor matrix H_t.Source: §VII · pp. 9–10
  • When the optimum is finite, the policy interconnects a pre-Kalman filter, virtual sensor, post-Kalman filter, and certainty-equivalence controller.The components are constructed by the SDP-based algorithm summarized in Steps 1–4.Source: §VII · p. 10

VIII. CONCLUSION

  • For directly observable plants, the optimal policy uses a linear sensor with additive Gaussian noise, a Kalman filter, and a certainty-equivalence controller; SDP also synthesizes the partially observable extension.The conclusion characterizes the numerical algorithm as efficient.Source: §VIII · pp. 10–11

APPENDIX A. Data-processing inequality for directed information

The appendix establishes a directed-information data-processing inequality using Markov structure, mutual-information chain rules, and telescoping cancellations. Supporting lemmas establish measure and Gaussian properties used in the argument.

APPENDIX A. Data-processing inequality for directed information

  • The proof of the directed-information inequality uses Markov-chain relations and the mutual-information chain rule, then telescopes the resulting sum.The telescoping sum cancels all but its final term.Source: Appendix A · p. 11

B. Some basic lemmas for probability measures

  • Absolute continuity of a joint measure with respect to the product of its marginals implies conditional absolute continuity almost everywhere.The proof identifies the conditional Radon–Nikodym derivative using Fubini’s theorem.Source: B. Some basic lemmas for probability… · p. 11
  • The lemmas show that Gaussian variables with matching covariance preserve specified linear-noise and Markov structures.One lemma gives y_G = Ax_G + v with v Gaussian and independent of x_G; another transfers a linear Markov chain to a jointly Gaussian measure with the same covariance.Source: B. Some basic lemmas for probability… · p. 11

C. Proof of Lemma 2

These proof passages establish distributional properties of policies and use a same-covariance Gaussian measure to bound terms in the directed-information argument.

C. Proof of Lemma 2

  • Under finite conditional mutual information, Lemma 9 supplies density and identity properties used in the proof.The condition is stated as I_P(x_t;u_t|u_{t−1}) < +∞ for all t.Source: C. Proof of Lemma 2 · pp. 12–13
  • For the same-covariance Gaussian measure, the plant’s linear transition law is preserved, and the relevant conditional state distribution admits a density on the stated support.The proof derives these properties from Lemmas 5–7 and Lemma 9(c).Source: C. Proof of Lemma 2 · p. 13
  • Replacing the policy-generated measure P with a zero-mean Gaussian measure G of the same covariance does not increase each of the listed terms.The proof presents the argument for one term and says the same technique applies to the other two.Source: C. Proof of Lemma 2 · pp. 13–14

D. Proof of Lemma 3

The appendix outlines an induction proof, extends the separation result to the infinite-horizon setting, and notes a zero-duality-gap representation for the limiting value.

D. Proof of Lemma 3

  • The Lemma 3 proof proceeds by induction, using the prior-step equality of joint distributions to establish the next one.The proof cites identities (25), (26), and (24), as well as Lemma 10(b), in the induction step.Source: D. Proof of Lemma 3 · p. 14

E. Proof of Theorem 2 (Outline only)

  • In the infinite-horizon setting, a linear-Gaussian policy is at least as good as any policy, and the optimal certainty-equivalence gain is time-invariant.The SDP optimum is attained by a time-invariant sequence P_t|t = P, Π_t = Π.Source: E. Proof of Theorem 2 (Outline only) · p. 14

F. Proof of Corollary 1

  • Strict feasibility gives zero duality gap for the dual representation of v*(A,W).The primal problem is also rewritten in an equivalent form.Source: F. Proof of Corollary 1 · p. 14

1) Case 1: When all eigenvalues of A satisfy |λi| ≥1:

The proof treats unstable, stable, and mixed eigenvalue cases separately to characterize v*(A, W). In the general case, it bounds the value using the eigenvalues of the unstable block.

1) Case 1: When all eigenvalues of A satisfy |λi| ≥1:

2) Case 2: When all eigenvalues of A satisfy |λi| < 1:

  • When all eigenvalues of A satisfy |λi| < 1, v*(A, W) is 0, attained using the positive definite solution of a Lyapunov equation.The proof identifies that solution as the choice of P in (67).Source: 2) Case 2: When all eigenvalues of A… · p. 15

3) Case 3: General case:

  • Riccati-solution ordering under 0 ≺ W1 ⪯ W2 supports the general-case construction of a feasible solution that upper bounds v*(A, W1).The construction uses detectability to obtain a positive definite Riccati solution and then a feasible (P, C, V).Source: 3) Case 3: General case · p. 15
  • For the general case, the proof bounds v*(A, W) above and below by the sum of log |λi| over eigenvalues of the block A1 with |λi| ≥ 1.The decomposition separates A into blocks A1 and A2, whose eigenvalues satisfy |λi| ≥ 1 and |λi| < 1, respectively.Source: 3) Case 3: General case · p. 15

G. Proof of Theorem 3

The proof reduces the partially observable control problem to a fully observable one using the pre-Kalman filter and an innovations-based reformulation. The filter can be introduced without loss of performance under the stated assumptions.

G. Proof of Theorem 3

  • The innovations reformulation turns the partially observable problem into a fully observable problem to which the results for fully observable systems apply.The modified policy observes the transformed state, and the resulting objective differs by terms independent of that policy.Source: G. Proof of Theorem 3 · pp. 15–17
  • The pre-Kalman estimate is recursively computable, and the innovation is a zero-mean white Gaussian variable independent of the estimate, control, and prior innovations.The innovation has covariance Ψt.Source: G. Proof of Theorem 3 · p. 16
  • The pre-Kalman-filter architecture preserves optimality because its causal inverse lets the decision policy reproduce the original policy based on plant outputs.The cited result assumes Wt ≻ 0 and that Ht has full row rank.Source: G. Proof of Theorem 3 · p. 16

Related papers

Loading 1510.04214v3…