Convex Sets: Binary Operations

Abstract

• Why. You need the Minkowski sum and the convex hull of the union, two binary operations on convex sets, to solve optimization problems. A convex function f has a minimum at a given point $\widehat x$ iff the origin lies in the subdifferential $\partial f(\widehat x)$, a certain convex set. Now suppose that f is made from two convex functions f ₁, f ₂ with known subdifferentials at $\widehat x$, by one of the following two binary operations for convex functions: either the pointwise sum (f = f ₁ + f ₂) or the pointwise maximum (f = max(f ₁, f ₂) ), and, in the latter case, $f_1(\widehat x)=f_2(\widehat x)$. Then $\partial f(\widehat x)$ can be calculated, and so it can be checked whether it contains the origin or not: $\partial (f_1+f_2)(\widehat x)$ is equal to the Minkowski sum of the convex sets $\partial f_1(\widehat x)$ and $\partial f_2(\widehat x)$ and $\partial (\max (f_1,f_2))(\widehat x)$ is equal to the convex hull of the union of $\partial f_1(\widehat x)$ and $\partial f_2(\widehat x)$ in the difficult case that $f_1(\widehat x)=f_2(\widehat x)$.

• What. The four standard binary operations for convex sets are the Minkowski sum, the intersection, the convex hull of the union and the inverse sum. The defining formulas for these binary operations look completely different, but they can all be generated in exactly the same systematic way by a reduction to convex cones (‘homogenization’). These binary operations preserve closedness for polyhedral sets but not for arbitrary convex sets.

Road Map

• Section 2.1.1 (motivation binary operations convex sets).

• Section 2.1.2 (crash course in working coordinate-free).

• Section 2.2 (construction binary operations +, ∩ for convex cones by homogenization; the fact that the sum map and the diagonal map are each others transpose).

• Section 2.3 (construction of one binary operation for convex sets by homogenization).

• Proposition 2.4.1 and Fig. 2.1 (list for the construction of the standard binary operations +, ∩, co∪, # for convex sets by homogenization; note that not all of these preserve the nice properties closedness and properness).