Convexity

Definitions

The closure (闭包) of a set \(\text{cl}(C)\) is the collection of its limit points.

A set in a linear space is convex, if any line segment between two vectors in the set is also in the set. {Bertsekas2003, 1.2.1} Convex hull (凸包) \(\text{conv}(C)\) is the smallest (intersection of all) convex set containing a set. Convex combination is a nonnegative weighted average of vectors. In comparison, nonnegative combination is a linear combination with nonnegative coefficients. Convexity is closely related to expectation: If \( P(X \in C) = 1 \) and \( C \sebseteq \mathbb{R}^n \) is convex, then \( \mathbf{E}X \in C \).

A set is a cone, if it is scale invariant. A cone is pointed if it contains no line. A cone is solid if it has nonempty interior. A proper cone (真锥) is a pointed, closed solid, convex cone. Generated cone \(\text{cone}(C)\) is the cone generated by a set is the nonnegative span of it. A vector is a direction of recession of a convex set, if arbitrary shifts of the set along this vector are within the set. The recession cone of a set is the cone generated by its recession directions.

A generalized inequality is the partial ordering on \(\mathbb{R}^n\) associated with a proper cone \(K\). Vector inequality is a special case of generalized inequality where the associated cone is the non-negative cone.

\[\begin{align} x \preceq_K y, y \succeq_K x &\Leftrightarrow y−x \in K \ x \prec_K y, y \succ_K x &\Leftrightarrow y−x \in \text{int}(K) \end{align}\]

An element of a multidimensional set is the minimum element (最小元) w.r.t. a generalized inequality \(\preceq_K\), if it is no greater than any other element in the set in such partial ordering: \(S \subseteq \{x\} + K\). Similarly, An element of a multidimensional set is the maximum element w.r.t. a generalized inequality \(\succeq_K\), if it is no less than any other element in the set in such partial ordering: \(S \subseteq \{x\} - K\).

An element of a multidimensional set is a minimal element (极小元) w.r.t. a generalized inequality \(\preceq_K\), if it is no less than any element in the set in such partial ordering: \((\{x\} - K) \cap S = \emptyset\). Similarly, An element of a multidimensional set is a maximal element w.r.t. a generalized inequality \(\succeq_K\), if it is no greater than any element in the set in such partial ordering: \((\{x\} + K) \cap S = \emptyset\).

The dual generalized inequality associated with a proper cone is the generalized inequality associated with its dual cone. This concept can be used for a dual characterization of the minimum/minimal elements. An element of a multidimensional set is the minimum element w.r.t. a generalized inequality \(\preceq_K\), if for all elements \(\lambda\) in the interior of the dual cone \(K^\) it is the unique minimizer for \(\langle \lambda, \cdot \rangle\) in the set. An element of a multidimensional set is a *minimal element** w.r.t. a generalized inequality \(\succeq_K\), if it minimizes \(\langle \lambda, \cdot \rangle\) over the set for an element \(\lambda\) in the interior of the dual cone.

Affine set is a shifted subspace. Affine hull (仿射包) is the smallest (intersection of all) affine set containing a set. The affine dimension of a set is the dimension of its affine hull. A set of vectors are affinely independent if when picking one as the origin, the rest are linearly independent. The number of affinely independent vectors in a set cannot be more than one plus the affine dimension of these vectors, if finite. The relative interior of a set is the intersection of its interior and its affine hull.

Examples

Common convex sets:

1. Linear family
   • Hyperplane: \({x | \langle a,x \rangle = b}\);
   • Half-space: \({x | \langle a,x \rangle \le b}\);
   • Polyhedron (多面体) \({x | A x \le b}\): polytope (多胞形), a bounded polyhedron; simplex (单纯形), \(\text{conv}(v_0, \dots, v_k), k \in \mathbb{N}\);
2. Norm family
   • Ellipsoids: \(x_c + A B_1(0) \), where \(x_c\) is center of ellipsoid, \(A\) is a linear transformation, \(B_1(0)\) is the unit ball; an alternative definition is \( \{x+x_c | \langle x, P^{−1} x\rangle \le 1\} \) where \(P\) is a positive semidefinite matrix (generalized norm);
   • Norm ball: \(\{x | | x-x_c| ≤ r \}\), where \(| \cdot |\) is any vector norm.
   • Norm cone: \(\{(x,t)~|~| x | ≤ t \}\), where \(| \cdot |\) is any vector norm.
3. Positive semidefinite cone: \(S_+^n = \{X \in S^n | X \succeq 0 \}\), where \(S^n\) is the space of n-by-n symmetric matrices.

Propositions

Set relations: \( C \subseteq \text{cl}(C) \subseteq \text{conv}(C) \subseteq \text{cone}(C) \)

The dual cone of a proper cone is also proper.

Generated cone is convex.

Operations that preserves set convexity: {Bertsekas2003, 1.2.1}

1. Unary operations
   • Closure and relative interior;
   • Affine transformation: scaling, translation, projection, etc;
   • Pre-image (inverse image) of affine transformation;
   • Projective transformation (linear-fractional): \(f(x) = \frac{Ax+b}{\langle c,x \rangle + d}\) where \(\langle c,x \rangle + d > 0\);
     • Perspective transformation: \(P(z,t) = z/t\) where \(t>0, z \in \mathbb{R}^n\);
2. Binary operations
   • Minkowski sum;
   • Cartesian product;
3. Arbitrary operations
   • Intersection;

Properties of convex set: {Bertsekas2003, 1.4.1}

• Any line segment between two vectors in the closure of a (nonempty) convex set is also in the relative interior of the set except the ends.
• (Nonempty) convex set has (nonempty) relative interior.

Recession cone theorem {Bertsekas2003, 1.5.1}: For a (nonempty) closed convex set,

• Its recession cone is closed;
• A direction of recession of one vector is also a direction of recession of the set;
• Its recession cone is nonzero iff it is unbounded;
• Its recession cone is also its relative interior's recession cone;
• For any collection of (nonempty) closed convex sets with nonempty intersection, recession cone and intersection are interchangeable.

Caratheodory's theorem {Bertsekas2003, 1.3.1}: (minimal representation of generated cone and convex hull)

• Every vector in the cone generated by a set can be represented as a positive combination of a linearly independent subset of the set;
• Every vector in the convex hull of a set can be represented as a convex combination of an affinely independent subset of the set;

Properties of generalized inequalities:

• Additive: x ≼_K y, u ≼_K v ⇒ x+u ≼_K y+v
• Nonnegative scaling: x ≼_K y, a ≥ 0 ⇒ ax ≼_K ay
• Transitive: x ≼_K y, y ≼_K z ⇒ x ≼_K z
• Reflexive: x ≼_K x
• Antisymmetric: x ≼_K y, y ≼_K x ⇒ x = y
• Limits: x_i ≼_K y_i, i∈N; \lim_i x_i = x, \lim_i y_i = y ⇒ x ≼_K y

For a generalized inequality, minimum and maximum elements of a set are unique if they ever exist, while a set can have multiple minimal and maximal elements.