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. |