Distance of a point to a subset of a metric space is the smallest distance between the point and any point in the subset: $d_C(x) = \min_{y \in C} d(x, y)$. Projection of a vector on a closed subset of a normed vector space is the set of vectors in the subset closest to the vector: $P_C(x) = \arg\min_{y \in C} \| y - x \|$.
Nonnegative combination of vectors is a linear combination where the scalars are nonnegative: $\sum_{i=1}^k a^i v_i$ where $a^i \ge 0$. Convex combination of vectors is a normalized nonnegative combination: $\sum_{i=1}^k a^i v_i$ where $a^i \ge 0$ and $\sum_{i=1}^k a^i = 1$. Line segment $\overline{pq}$ between two vectors is the set of all their convex combinations: $\overline{pq} = \{\lambda p + (1-\lambda) q: \lambda \in [0,1]\}$. Convex subset in a vector space is a subset that includes the line segment between any two of its elements [@Bertsekas2003, 1.2.1]: $A = \cup_{p, q \in A} \overline{pq}$. Convexity is closely related to expectation of random vector: a random vector supported within a convex subset has its expectation within that subset. A subset is closed and convex if and only if it is the intersection of all closed half-spaces containing the subset. Extreme point of a convex subset is a vector not between any two other vectors on the subset. Extreme direction of a convex set is the direction of one of its extreme points.
Convex hull (凸包) $\text{conv}(C)$ of a subset in a vector space is the intersection of all convex sets containing a subset. Affine hull (仿射包) $\text{aff}(X)$ is the intersection of all affine subspaces containing a set. Affine dimension of a subset 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. Relative interior $\text{ri}(C)$ of a subset is the intersection of its interior and its affine hull.
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 cone is finitely generated, if it is generated by a finite set of vectors. 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 $R_C$ is the cone generated by its recession directions. The lineality space of a set is the set of directions of recession whose oppose are also direction of recession: $L_C = R_C \cap -R_C$.
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 nonnegative 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}$$
The minimum element (最小元) of a multidimensional set w.r.t. a generalized inequality $\preceq_K$ is an element no greater than any other element in the set in such partial ordering: $S \subseteq \{x\} + K$. Similarly, the maximum element of a multidimensional set w.r.t. a generalized inequality $\succeq_K$ is an element no less than any other element in the set in such partial ordering: $S \subseteq \{x\} - K$.
A minimal element (极小元) of a multidimensional set w.r.t. a generalized inequality $\preceq_K$ is an element no less than any element in the set in such partial ordering: $(\{x\} - K) \cap S = \emptyset$. Similarly, a maximal element of a multidimensional set w.r.t. a generalized inequality $\succeq_K$ is an element no greater than any element in the set in such partial ordering: $(\{x\} + K) \cap S = \emptyset$.
The polar cone of a set is its shade, which is a cone: $C^∗ = \{ x | \langle x, y \rangle \le 0, \forall y \in C \}$. Dual cone of a set is the negative polar cone: $\hat{C} = -C^∗$. A set is polyhedral (多面的) if it is the intersection of finitely many closed half-spaces: ${x | A x \le b}$. A cone is polyhedral if it is the polar cone of some finite set.
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. The minimum element of a multidimensional set w.r.t. a generalized inequality $\preceq_K$ is an element such that 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. A minimal element of a multidimensional set w.r.t. a generalized inequality $\succeq_K$ is an element that minimizes $\langle \lambda, \cdot \rangle$ over the set for an element $\lambda$ in the interior of the dual cone.
An extended real-valued function is a function whose range is the extended real line. The extended-value extension $\tilde{f}: \mathbb{R}^n → \mathbb{R} ∪ \{+\infty\}$ of a convex function $f : C \to \mathbb{R}$ is the function defined in its containing (Euclidean) space that takes value $+\infty$ outside its original domain.
The graph of a function is the collection of point-value pairs: $\{ (x, f(x)) | x \in \text{dom}f \}$. The epigraph (supergraph) of a function is the collection of points on and above its graph: $\text{epi}f = \{ (x, y) | x \in \text{dom}f, y \ge f(x) \}$.
Consistent definitions of convex functions:
A function is concave if its negative is a convex function. While concave set is simply any non-convex set, concave functions exactly mirror convex functions.
Level curve is the feasible set of an equality constraint: $\{x \mid h(x) = 0\}$. Level set or sub-level set is the feasible set of an inequality constraint: $\{x \mid f(x) \le 0\}$. Quasi-convex function is one whose sub-level sets (and thus its domain) are all convex. Quasi-concave function is one whose negative is quasi-convex. Unimodal function is one which is quasi-convex or quasi-concave. Quasilinear function is one whis is both quasi-convex and quasi-concave.
Log-concave/log-convex function is a positive function whose logarithm is concave/convex.
Given a proper cone $K$ in its domain space, a real-valued function is $K$-nondecreasing if it is dominated by values in its K-cone: $\forall x, y, x \preceq_K y : f(x) \le f(y)$. The function is $K$-increasing if it is strictly dominated by values in its K-cone other than the vertex: $\forall x \ne y, x \preceq_K y : f(x) < f(y)$. $K$-nonincreasing and $K$-decreasing are similarly defined. As a special case, a real-valued function on the space of symmetric matrices is matrix increasing (decreasing) if it is increasing (decreasing) with respect to the positive semidefinite cone.
Given a proper cone $K$ in its range space, a vector-valued function is $K$-convex if every line segment of the function is K-dominated by its linear interpolation: $\mathbf{f}(\boldsymbol\lambda \cdot \mathbf{x}) \preceq_K \boldsymbol\lambda \cdot \mathbf{f}(\mathbf{x})$. The function is strictly K-convex if the inequality is strict except on the endpoints. As a special case, a symmetric matrix valued function is matrix convex if it is convex with respect to the positive semidefinite cone.
Given the dual pair of vector spaces $X, Y$ w.r.t a bilinear form $\langle \cdot, \cdot \rangle$, functions $f: X \to \mathbb{R}$ and $f^\star: Y \to \mathbb{R}$ are conjugate if their sum is supported from below by the bilinear form pointwise in the dual space: $f(x) + f^\star(y) \ge \langle y,x \rangle$ (Young's inequality), and $\forall y \in Y, \exists x \in X: f(x) + f^\star(y) = \langle y,x \rangle$. Equivalently, $f^\star(y) = \sup_{x \in X} \{ \langle y,x \rangle - f(x) \}$, also known as Fenchel transformation [@Fenchel1949]. If a function is smooth, strictly convex, and increases at infinity faster than a linear function, its conjugate is equivalent to its Legendre transformation [@Legendre1789]: $f^\star(y) = \langle x^\star, \nabla f(x^\star) \rangle − f(x^\star)$, where $y = \nabla f(x^\star)$.
Common convex sets:
Common convex functions:
Common non-trivial log-concave and log-convex functions:
Common matrix monotone functions: (Real-valued functions over the symmetric matrix space.)
Common matrix convex/concave functions:
Set relations: $C \subseteq \text{cl}(C) \subseteq \text{conv}(C) \subseteq \text{cone}(C)$
Operations that preserves set convexity: [@Bertsekas2003, 1.2.1]
Properties of convex set: [@Bertsekas2003, 1.4.1]
If a set is closed with nonempty interior and has a supporting hyperplane at every point in its boundary, it is convex.
The dual cone of a proper cone is also proper.
Generated cone is convex.
Recession cone theorem [@Bertsekas2003, 1.5.1]: For a (nonempty) closed convex set,
Caratheodory's theorem [@Bertsekas2003, 1.3.1]: (minimal representation of generated cone and convex hull)
Projection theorem [@Bertsekas2003, 2.2.1]: For a (nonempty) closed convex set $C$,
Supporting hyperplane theorem: Any non-interior point of a (nonempty) convex set has some hyperplane that contains the set in one of its closed half-spaces. [@Bertsekas2003, 2.4.1]
Separating hyperplane theorem: Any two disjoint (nonempty) convex sets can be separated by some hyperplane. [@Bertsekas2003, 2.4.2]
Strict separation theorem [@Bertsekas2003, 2.4.3]: Two disjoint (nonempty) convex sets $C_1, C_2$ can be strictly separated by some hyperplane if any of the following holds:
Polar cone is closed and convex.
Polar cone of a set is also polar cone of the cone generated by the set: $C^∗ = \text{cone}(C)^∗$. [@Bertsekas2003, 3.1.1]
Polar cone theorem: Twice polar cone of a cone is the closure of its convex hull: $C^{ ** } = \text{cl}(\text{conv}(C))$. In particular, closed convex cones are self-dual to polarity: $C^{ ** } = C$.
Cone generated by a finite set is closed. (Nontrivial) The polyhedral cone and the cone generated by the same finite set of vectors are polar to each other: for a finite set $A$, $A^∗ = \text{cone}(A)^∗$, and (Farkas' Lemma) $A^{**} = \text{cone}(A)$. [@Bertsekas2003, 3.2.1]
Minkowski-Weyl Theorem: Any polyhedral cone can be represented as a finitely generated cone, and the converse is also true: $A^∗ = \text{cone}(B)$.
Minkowski-Weyl representation: Given finite sets $A, B$, a polyhedral set can be represented as the Minkowski sum of the convex hull of a finite set and a finitely generated cone; the converse is also true: $P = \text{conv}(A) + \text{cone}(B)$. [@Bertsekas2003, 3.2.2]
[@Bertsekas2003, 3.3.1] For a (nonempty) convex set, extreme points on a supporting hyperplane are also extreme points of the set. A closed convex set has at least one extreme point iff it does not have two opposing recession direction. For a bounded convex set, all extreme points form the minimal set that reproduce the set by convex hull: $C = \text{conv}(E)$, where $E$ is the set of extreme points of $C$.
For a polyhedral set with Minkowski-Weyl representation $P = \text{conv}(A) + \text{cone}(B)$, its extreme points are in $A$. [@Bertsekas2003, 3.3.2]
[@Bertsekas2003, 3.3.3]
Polyhedral proper separation theorem [@Bertsekas2003, 3.5.1]
Properties of generalized inequalities:
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.
Non-decreasing in each argument is equivalent to K-nondecreasing where $K$ is the nonnegative cone.
First-order conditions for K-monotonicity: A differentiable function on a convex domain is K-nondecreasing iff its gradient is nonnegative in K-dual inequality: $\nabla f(x) \succeq_{K^\star} 0$; It is K-increasing if its gradient is positive in K-dual inequality: $\nabla f(x) \succ_{K^\star} 0$;
First-order conditions for K-convexity: A differentiable function on a convex domain is K-convex iff the function globally K-dominates its linear expansion: $f(y) \succeq_K f(x) + Df(x)(y−x)$, here $f: \mathbb{R}^n \to \mathbb{R}^m$ and $Df(x) \in \mathbb{R}^{m \times n}$. This proposition also holds when both sides are strict.
Composition theorem: A K-nondecreasing convex function of a K-convex function is convex. Note the monotonicity restriction is on the extended-value extension of the outer function.
A convex function can only be discontinuous on its relative boundary.
A function is affine iff it is simultaneously convex and concave.
Operations that preserves (vector-valued) function convexity (or concavity): [@Bertsekas2003, 1.2.4]
Characterization of differentiable convex functions:
Operations that preserve quasi-convexity:
A quasilinear function has convex level sets; the converse does not hold.
A quasi-convex function $f(x)$ can be represented by a family of convex functions $\phi_t(x)$, where the t-sublevel set of $f$ is the 0-sublevel set of $\phi_t$. Such representation is not unique.
Relations:
Properties:
Transformation properties of conjugation:
A function is closed if its epigraph is a closed set; or equivalently, if all its sub-level sets are closed. The conjugate function of any function is closed and convex. Almost every convex function can be expressed as the conjugate of some function.
An extended real-valued function is lower semi-continuous at a point if the function values in the point's neighborhood are either close to or greater than the function value at that point: $\liminf_{x \to x_0} f(x) \ge f(x_0)$. The conjugate of a function is always lower semi-continuous.
The convex closure of a function is the function whose epigraph is the closure of the convex hull of the original function. The conjugate of the conjugate (twice conjugate) of a function is its convex closure: $\text{epi}f^{\star\star} = \text{cl}(\text{conv}(\text{epi}f))$, note that $f^{\star\star} \le f$. Fenchel–Moreau theorem: If a function is convex and closed, its twice conjugate is itself: $f^{\star\star} = f$.