Feasability checks

The main challenge of the computing discrete equivalents is finding feasible sets of blockable facets and determining whether each facet is controllable. This algorithm does not look for all possible sets of blockable facetes, but instead finds one blockable set with the maximum number of blockable facets for that simplex. It is then checked whether for each facet it can be guaranteed that it is controllable.

Blockable set

To find the largest blockable set all combinations of facets are tested starting with all facets blocked. Each tests consist of determining the feasability of the LMI-system consisting of the LMIs limiting the input to the input-polytope and a set of LMIs ensuring that the derivative points inwards, one for each vertex of the facets to be blocked.

  1. For all facets of the input-polytope add an instance of the input LMI.

  2. For all facets add N instances of the inwards derivative LMI, one for each veretex of the facet.

Controllable facets

To determine if a facet is controllable it is necessary to establish weather a fixed point can be avoided in both configurations for the facet (opened and closed).

The first check is for the closed configuration, where all facets are blocked. The fixed point check is done by finding a vector, d, in which direction the derivatives at all the vertices can point using the all derivatuves in the same direction LMI. It should be noted that the constraints used to determine blockability still has to hold, so the LMIs described in the previous section are added.

There are no methods of uniquely finding this vector but at least the outwards normals to the blocked facets will not yield a result, and neither will convex combinations of them.

As testvectors both the inwards and outwards normals to the facets are chosen as a feasible result will mean that the vector field in general points away from or towards one of the facets.

If no control can be found which ensures fixed points outside the simplex the blockable set is no good and must be thrown away.

Given that the closed configuration is feasible it needs to be established whether the individual facets are controllable.

This is done by using the LMI system used for establising blockability, but reversing the derivative requirement on the facet under examination, l, i.e. changing < to > in the derivative pointing inwards LMI. Furthermore it is still necessary to search for a d where all derivatives point in the same direction, but in this case there is a natural candidate vector, namely n_l, as satisfying the reversed constraints ensures that all but one of the derivatives at the vertices of the simplex points out of facet l.