LMIs: Ellipsoid containing other ellipsoids/polyhedra, Yalmip/Sedumi/Matlab (1): minimum major axis

Antonio Sala, UPV

Difficulty: **** ,       Relevance: ,      Duration: 18:43

Summary:

This video presents how to obtain, via linear matrix inequalities (LMI) or semidefinite programming (SDP), according to other texts, the “smallest” ellipse that contains a given polygon and another ellipse.

The approach can be generalized to more ellipses and more polyhedra in more dimensions; the LMI code would be practically identical.

The first part of the video discusses the conditions for an ellipse $x^{T}Px\le 1$ to contain a polyhedron with vertices $v_i$ (that is, $v_i^{T}P{v}_i\le 1$) and to contain another ellipse $x^{T}Mx\le 1$, that is stated as $M-P\succcurlyeq 0$; The second case is detailed and proven in the video [ellip5EN].

The second part of the video discusses what needs to be “optimized” (objective function): in this first video, it is decided to minimize the length of the semimajor axis of the ellipse, that is, we wish to minimize the radius of the smallest sphere that contains the sought ellipse. This is done by minimizing $\rho$, adding the constraint $P-{\rho }^{-2}I\succcurlyeq 0$. Actually, to make the objective function and constraints linear in the decision variables, we change to maximize $\beta$ subject to $P-\beta I\succcurlyeq 0$.

The video details all the YALMIP code that must be entered to solve the problem in a Matlab environment.

Note: by minimizing the size of the semimajor axis of the ellipse, the minor semi-axis is “free” and the solution is not unique. Discussing this topic as well as the minimization of the volume (area in a 2D case) of the desired ellipsoid is the objective of the video [lmielout2EN], a continuation of this one.

*Link to my [ whole collection] of videos in English. Link to larger [ Colección completa] in Spanish.