The Scalability Bottleneck of Linear Matrix Inequalities

35 concepts37 papers1 proposal

In control theory and optimization, Linear Matrix Inequalities (LMIs) are celebrated as a universal solvent. Whether you are verifying the stability of a networked control system, designing a robust observer, or certifying the safety of a neural network, the problem almost always reduces to finding a matrix that satisfies a set of LMIs.

The reason for this ubiquity is convexity. If a problem can be framed as an LMI, we are guaranteed that any local optimum is a global optimum, freeing us from the nightmare of local minima. However, as modern engineering pushes toward large-scale networks, high-dimensional systems, and data-driven control, the field has hit a hard wall: the LMI scalability bottleneck.

To understand why this bottleneck exists, we must look under the hood at how LMIs are solved and how modern system complexities compound their computational cost.


The Anatomy of the Bottleneck

An LMI typically takes the form:

$$F(x) = F_0 + \sum_{i=1}^{m} x_i F_i \succeq 0$$

where $x = [x_1, x_2, \dots, x_m]^T$ is a vector of $m$ decision variables, and $F_i$ are symmetric matrices of size $n \times n$. The notation $\succeq 0$ means the resulting matrix must be positive semi-definite.

To solve these inequalities reliably, standard optimization packages rely on interior-point methods. These solvers are highly robust, but their computational complexity per iteration scales polynomially with both the number of decision variables ($m$) and the size of the matrix ($n$)—often on the order of $O(m^3 n + m^2 n^2 + m n^3)$.

As a system grows, $m$ and $n$ do not increase linearly; they explode. For instance, if you are looking for a Lyapunov matrix $P$ for a system with state dimension $d$, the matrix $P$ must be symmetric, meaning it contains $m = \frac{d(d+1)}{2}$ decision variables. Because $m$ scales quadratically with the state dimension ($O(d^2)$), the $m^3$ term in the solver's complexity translates to a staggering $O(d^6)$ computational scaling.

As Tianrui Li et al. observe in their work on nonlinear observers, this extreme scaling behavior quickly renders high-dimensional systems computationally intractable for standard convex optimization solvers.


The Multipliers of Complexity

The scalability bottleneck is further exacerbated by three major trends in modern control engineering: the push for less conservative bounds, the rise of multi-agent networks, and the integration of data-driven models.

1. The Conservatism Trade-off (Slack Variables)

When dealing with complex phenomena like time-varying delays or model uncertainties, researchers often introduce "free matrices" or "slack variables" to decouple system matrices and find looser, less conservative stability bounds.

While mathematically elegant, this strategy introduces a severe computational penalty. For example, Zeng Hong-bing et al. demonstrate in New stability conditions of neutral delay systems via free-matrix-based integral inequality that adding free matrices drastically increases the dimensionality of the resulting LMIs. Similarly, Yufeng Tian et al. note in their study of truck-trailer systems that the inclusion of these additional decision variables increases optimization complexity to the point where real-time control becomes impossible.

2. The Curse of Network Scale

In distributed systems—such as smart power grids, robotic swarms, or networked filters—the state dimension is multiplied by the number of nodes or agents.

3. Data-Driven Control and Neural Networks

The modern shift toward learning-based control introduces entirely new scaling challenges. Instead of a compact physics-based model, data-driven frameworks must embed experimental data directly into the optimization constraints.

  • Trajectory Length: Anne Koch et al. demonstrate in Verifying dissipativity properties from noise-corrupted input-state data that the matrix size within the LMI scales poorly with the length of the data trajectory, creating a massive bottleneck for long-duration experiments or high-frequency sampling.
  • High-Order Observables: Frameworks that lift nonlinear systems into higher-dimensional linear spaces (like Koopman operator methods) suffer from a similar issue. Robin Strässer et al. point out in SafEDMD that the high-order polynomial complexity of LMI solvers severely limits the number of system observables one can practically use.
  • Neural Network Size: When neural networks are placed "in the loop" for feedback control, enforcing physical constraints like dissipativity requires solving LMIs that scale with the network's depth and width. As S Sivaranjani et al. explain in Learning Dissipative Neural Dynamical Systems, the computational cost grows so rapidly with the number of layers and neurons that standard interior-point methods fail, demanding entirely new compositional approaches.

How the Field is Responding

Because interior-point solvers hit a hard wall when system states exceed a few thousand variables—a boundary discussed explicitly by Nicolas Gillis et al. in Finding the Nearest Positive-Real System—researchers are actively developing workarounds to bypass the $O(d^6)$ explosion.

┌────────────────────────────────────────────────────────┐
│               High-Dimensional System                  │
└───────────────────────────┬────────────────────────────┘
                            │
             How do we bypass the LMI wall?
                            │
      ┌─────────────────────┼─────────────────────┐
      ▼                     ▼                     ▼
┌───────────┐         ┌───────────┐         ┌───────────┐
│First-Order│         │  Model    │         │Network    │
│  Solvers  │         │Reduction  │         │Pruning    │
└───────────┘         └───────────┘         └───────────┘
(Trade accuracy       (Loewner/Koopman      (Sparsification
 for speed; avoid      frameworks; lower     to drop hidden
 Hessian costs)        state dimension)      complexities)
  1. First-Order Optimization Methods: Instead of interior-point methods that compute second-order Hessian information (which causes the $m^3$ complexity), researchers are shifting toward first-order gradient methods. These methods trade off extreme numerical precision for significantly lower per-iteration costs, allowing them to scale to much larger matrix dimensions.
  2. Model Reduction Frameworks: Rather than solving LMIs for the full, high-dimensional system, authors are utilizing data-driven model reduction. For instance, Ion Victor Gosea et al. leverage the Loewner framework to bypass LMI-based simplification entirely, constructing accurate low-order representations that can be processed comfortably by standard solvers.
  3. Network Pruning and Sparsification: In neural feedback loops, authors such as Dhruv Shah et al. suggest using model reduction techniques like pruning to strip away unnecessary neural network weights before controller synthesis, directly reducing the number of decision variables ($m$) before the LMI is ever formulated.

Ultimately, the scalability bottleneck has shifted the focus of modern control theory. The challenge is no longer just proving that a control problem can be formulated as a convex optimization; the challenge is ensuring that the formulation survives the transition from low-dimensional textbook examples to high-dimensional, real-world systems.

Key Foundational Work

Computation of Piecewise Quadratic Lyapunov Functions for Hybrid Systems (1996) — contributed 1 concept elements to this direction.
Robust Constrained Model Predictive Control Based on Parameter-Dependent Lyapunov Functions (2008) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_lmi_scalability_7ac0b275,
  title = {LMI scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/lmi-scalability/rdr_7ac0b275ebda4eb28f220bb312b6e9bc},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_lmi_scalability_7ac0b275_v1,
  title = {LMI scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/lmi-scalability/rdr_7ac0b275ebda4eb28f220bb312b6e9bc/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake