LMIs in Control/pages/Ellipsoidal inequality

Introduction

The simplex algorithm was the first algorithm proposed for linear programming, and although the algorithm is quite fast in practice, no variant of it is known to be polynomial time. The Ellipsoid algorithm is the first polynomial-time algorithm discovered for linear programming. The Ellipsoid algorithm was proposed by the Russian mathematician Shor in 1977 for general convex optimization problems and applied to linear programming by Khachyan in 1979.

The Ellipsoidal inequality constraints are a type of Lyapunov Function. They are important in process identification, parameter estimation, and statistics. Applications include the crystallization process, polymer film extrudes, and paper machines.

The Data

Formulation of the inequality depends upon the coordinates of the ellipsoid $(x_{i})$ and the centre of the ellipsoid $(x_{c})$.

The Ellipsoidal Inequality

An Ellipsoid is described by:

${\begin{aligned}\ (x-x_{c})^{T}P^{-1}(x-x_{c})<1,\\\ where,P=P^{T}>0\\\end{aligned}}$

It can be expressed as an LMI using the Schur complement lemma with $Q(x)=1,R(x)=P,andS(x)=(x-x_{c})^{T}:$
${\begin{bmatrix}1&&(x-x_{c})^{T}\\(x-x_{c})&&P\end{bmatrix}}$ ${\begin{aligned}>=0\end{aligned}}$

Conclusion

Using this inequality, as the algorithm advances to the next step; if the value of P is positive; the volume will keep on shrinking until the LMI is fulfilled.

Implementation

• https://github.com/Margav06/LMI-for-Ellipsoidal-Inequality

External Links

A list of references documenting and validating the LMI.

• https://web.mit.edu/braatzgroup/33_A_tutorial_on_linear_and_bilinear_matrix_inequalities.pdf

• http://www-math.mit.edu/~goemans/18433S09/ellipsoid.pdf

Return to Main Page