LinearMatrixInequalitySolver<T>

Models & Types · AiDotNet.Control

Finds a point satisfying a linear matrix inequality F(x) = F₀ + x₁F₁ + … + x_mF_m ⪰ 0.

For Beginners

Some questions in control take the form “is there a matrix making all of these conditions hold at once?” — for instance, is there an energy function proving this system is stable? Written the right way, that question is convex, meaning it has no false summits to get stuck on and a systematic search will find an answer if one exists.

How It Works

Minimizes the largest eigenvalue of −F(x) by the subgradient method (N. Z. Shor, Minimization Methods for Non-Differentiable Functions, Springer 1985), which is feasible exactly when that minimum reaches zero. The formulation of control problems as linear matrix inequalities follows S. Boyd, L. El Ghaoui, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory (SIAM 1994).

Why this is a convex problem despite the matrix. The eigenvalues of a matrix are not linear in its entries, so requiring them all to be non-negative sounds hopeless. But the largest eigenvalue of a symmetric matrix is the maximum of vᵀMv over unit vectors v — a maximum of linear functions of M, and therefore convex. Since F(x) is affine in x, the composition is convex in x, and the set where it is non-positive is convex. That single observation is why an enormous range of control problems — stability, robustness, performance bounds, gain synthesis — can be solved rather than merely searched.

The subgradient. The largest eigenvalue is not differentiable where the top eigenvalue is repeated, so there is no gradient to follow. There is always a subgradient: if v is a unit eigenvector of the largest eigenvalue, then −vᵀF_i v is a valid subgradient component. The step schedule shrinks as one over the square root of the iteration count, which is what makes the method converge for a nonsmooth convex objective.

What the result does and does not claim. A reported Feasible is verified — the returned matrix is factorized to confirm it really is positive semidefinite, so the status is never an inference from convergence behaviour. A failure is reported as IterationLimit and never as “infeasible”, because a search that did not find a point has not shown that none exists.

Example

// Find a diagonal P = diag(x0, x1) that is positive definite:
//   F(x) = -epsilon*I + x0*E00 + x1*E11 >= 0
var constantTerm = Matrix<double>.CreateIdentity(2).Multiply(-1e-6);
var basis = new List<Matrix<double>>
{
    new Matrix<double>(new double[,] { { 1.0, 0.0 }, { 0.0, 0.0 } }),   // E00
    new Matrix<double>(new double[,] { { 0.0, 0.0 }, { 0.0, 1.0 } })    // E11
};
            
var result = new LinearMatrixInequalitySolver<double>().Solve(constantTerm, basis);
if (result.Status == LinearMatrixInequalityStatus.Feasible)
{
    // result.Matrix is positive semidefinite, verified.
}

Constructors

Constructor Summary
LinearMatrixInequalitySolver() Creates a solver with the default options.
LinearMatrixInequalitySolver(LinearMatrixInequalityOptions options) Creates a solver.

Methods

Method Summary
LinearMatrixInequalityResult<T> Solve(Matrix<T> constantTerm, IReadOnlyList<Matrix<T>> basis, Vector<T> initialGuess) Searches for coefficients satisfying F₀ + Σ xᵢFᵢ ⪰ 0.