About Zonotopes

A special case of the linear dependent bound (dbound) formalization, where the upper and lower bounds have the same slope:

$$\begin{array}{c}{\lambda }_{\mathbf{x}}\odot \mathbf{x}+{\mathbf{lb}}_x\le f(\mathbf{x})\le {\lambda }_{\mathbf{x}}\odot \mathbf{x}+{\mathbf{ub}}_x\\ {\lambda }_{\mathbf{y}}\odot \mathbf{y}+{\mathbf{lb}}_y\le f(\mathbf{y})\le {\lambda }_{\mathbf{y}}\odot \mathbf{y}+{\mathbf{ub}}_y\\ {\lambda }_{\mathbf{\Delta x}}\odot \mathbf{x}+{\lambda }_{\mathbf{\Delta y}}\odot \mathbf{y}+{\mathbf{lb}}_{\Delta }\le f(\mathbf{x})-f(\mathbf{y})\le {\lambda }_{\mathbf{\Delta x}}\odot \mathbf{x}+{\lambda }_{\mathbf{\Delta y}}\odot \mathbf{y}+{\mathbf{ub}}_{\Delta }\end{array}$$

However, this is still not a zonotope, the area for each $(x,y)$ is a hexagon instead of a parallelogram, so to make it a zonotope, we need to further relax the hexagon area to a parallelogram area, which means we need to select one of the two slopes as the slope for both upper and lower bounds. However, there are different ways to loose this bound, it is not trivial to decide which form is better. The method proposed in Bound Propagation can be used to select the best bound, which will give a tighter bound than the standard zonotope formalization.