| # Convex Sets Convex Optimization > Convex sets | Convex functions | Convex optimization problems | Algorithms | DCP Definition Operations that preserve convexity Separation theorems Separating hyperplanes Supporting hyperplanes ## Definitions A subset of is said to be convex if and only if it contains the line segment between any two points in it: Subspaces and affine sets, such as lines, planes and higher-dimensional ‘‘flat’’ sets, are obviously convex, as they contain the entire line passing through any two points, not just the line segment. That is, there is no restriction on the scalar anymore in the above condition. Examples: A convex and a non-convex set. Convex and conic hull of a set of points. A set is said to be a convex cone if it is convex, and has the property that if , then for every . ## Operations that preserve convexity ### Intersection The intersection of a (possibly infinite) family of convex sets is convex. This property can be used to prove convexity for a wide variety of situations. Examples: The second-order cone. The semidefinite cone. ### Affine transformation If a map is affine, and is convex, then the set is convex. In particular, the projection of a convex set on a subspace is convex. Example: Projection of a convex set on a subspace. ## Separation theorems Separation theorems are one of the most important tools in convex optimization. They convex the intuitive idea that two convex sets that do not intersect can be separated by a straight line. There are many versions of separation theorems. One of them is the separating hyperplane theorem: Theorem: Separating hyperplane If , are two convex subsets of that do not intersect, then there is an hyperplane that separates them, that is, there exit , , and , such that for every , and for every .
| When two convex sets do not intersect, it is possible to find a hyperplane that separates them. In two dimensions, we can picture the hyperplane as a straight line. The proof of the separation theorem relies on finding the two points in each set that are closest to each other.
Another result involves the separation of a set from a point on its boundary: Theorem: Supporting hyperplane If is convex and non-empty, then for any at the boundary of , there exist a supporting hyperplane to at , meaning that there exist , , such that for every .
| It is always possible to separate (not strictly) a convex set from any point on its boundary. The separating hyperplane contains the point and the whole set lies on one side of the hyperplane. The supporting hyperplane may not be unique.