Efstratios N. Pistikopoulos - Multi-parametric Optimization and Control

The solution of problem ( 1.32) identifies the largest Euclidean ball which on the set , i.e. which lies on the th constraint. Thus, the solution can be understood as the center of the th constraint with respect to .

One of the operations used in this book is the (orthogonal) projection:

Let be a polytope. Then the projection of onto is defined as:

(1.33)

Projecting polytopes is one of the fundamental operations in computational geometry and has many applications in control theory. Two commonly encountered strategies for the calculation of the projection are the following:

Solving a multi‐parametric linear programming (mp‐LP) problem (see e.g. [8])

Performing a Fourier–Motzkin (FM) elimination (see, e.g. [9])

In addition, the concept of a hybrid projection is introduced:

Consider the set . Then, the hybrid projection of onto is defined as

(1.34)

By inspection it is clear that (i) is obtained by performing at most projections, one for each combination of the binary variables and consequently (ii) is generally a union of at most possibly overlapping polytopes.

A hybrid projection can thereby be performed by solving a multi‐parametric mixed‐integer programming problem purely based on feasibility requirements.

The aim is to represent a union of polytopes as a single set of linear inequality constraints in order to seamlessly include them within multi‐parametric programming problems. However, in order to address the possible non‐convexity within unions of polytopes, the introduction of suitable binary variables is required. First, consider that a point if and only if there exists at least one such that . Thus, one binary variable is defined such that

(1.35a)

(1.35b)

Let and denote the th row and element of and , respectively. Then, the statement holds if and only if , . Thus, one binary variable per row of , is defined such that