Conical combination

A conical combination (also known as a conic combination) of a finite collection of vectors x_1, \dots, x_k in a real vector space is a vector expressed as \sum_{i=1}^k \theta_i x_i, where each coefficient \theta_i \geq 0.^[1] This construction differs from a convex combination, which requires the coefficients to sum to 1, by permitting arbitrary non-negative scaling without normalization.^[2] The conic hull (or conical hull) of a set S, denoted \operatorname{cone}(S), is the set of all possible conical combinations of finitely many elements from S, forming the smallest convex cone that contains S.^[1] A convex cone is a set that includes the origin and is closed under conical combinations, meaning it contains all non-negative scalar multiples and sums of its elements.^[2] These structures are foundational in convex analysis, as they generalize rays emanating from the origin and enable the representation of polyhedral cones generated by finite sets of vectors.^[1] Conical combinations underpin key applications in optimization, including linear and conic programming, where feasible regions are often modeled as convex cones such as the non-negative orthant or the positive semidefinite cone.^[1] They also appear in duality theory, generalized inequalities, and interior-point methods, facilitating efficient algorithms for problems in signal processing, machine learning, and operations research.^[2]

Basic Concepts

Definition

In convex analysis, the conical hull (also called the conic hull or positive hull) of a nonempty set S \subseteq V, where V is a real vector space, is the set consisting of all conical combinations of finitely many elements from S. Formally, it is given by

\cone(S) = \left\{ \sum_{i=1}^k \lambda_i s_i \;\middle|\; k \in \mathbb{N},\ s_i \in S,\ \lambda_i \geq 0 \ \forall i = 1, \dots, k \right\},

where the empty sum (when k = 0) is defined as the zero vector $0 \in V. This construction ensures that \cone(S) is itself a convex cone, as it is closed under addition and nonnegative scalar multiplication.^[1] The conical hull possesses the minimal property that it is the smallest convex cone containing S, meaning \cone(S) equals the intersection of all convex cones in V that include S. Consequently, every element s \in S belongs to \cone(S), achieved via the trivial conical combination with k=1, \lambda_1 = 1, and s_1 = s, and the origin $0 is always included as the empty conical combination. Common notations for the conical hull include \cone(S) and \pos(S).^[1]^[3]

Notation

In the context of vector spaces, a conical combination of a finite set of vectors v_1, v_2, \dots, v_n \in V is expressed as

x = \sum_{i=1}^n \lambda_i v_i,

where \lambda_i \geq 0 and \lambda_i \in \mathbb{R} for each i = 1, \dots, n.^[4] This notation emphasizes the nonnegative scalar coefficients \lambda_i, which distinguish conical combinations from general linear combinations. The set of all such conical combinations generated by a set S \subseteq V is known as the conical hull of S, commonly denoted by \operatorname{cone}(S) or \operatorname{pos}(S).^[4] These symbols reflect the positive (nonnegative) nature of the combinations, with \operatorname{pos}(S) sometimes preferred to highlight the "positive span." Terminology for conical combinations includes synonyms such as "nonnegative linear combination" and "conic combination," which are used interchangeably in convex analysis to describe sums with nonnegative coefficients.^[5] For finite sets S, the conical hull is finitely generated, meaning every element arises from a finite sum as above. In finite-dimensional spaces, vectors are conventionally represented as column vectors, facilitating matrix formulations where coefficients form a row vector of nonnegative entries. For infinite sets or infinite-dimensional spaces, combinations are restricted to those with finite support, ensuring only finitely many \lambda_i are nonzero to maintain well-definedness.^[4]

Geometric Interpretation

In Finite-Dimensional Spaces

In finite-dimensional real vector spaces, such as \mathbb{R}^n, conical combinations of vectors generate cones that are subsets of the ambient space. For a finite set of vectors S = \{v_1, \dots, v_k\} \subset \mathbb{R}^n, the conical hull \mathrm{pos}(S) = \left\{ \sum_{i=1}^k \lambda_i v_i \;\middle|\; \lambda_i \geq 0, \, i=1,\dots,k \right\} forms a polyhedral cone with its vertex at the origin.^[6] This structure arises because the finite number of generators defines the cone as the intersection of finitely many half-spaces, ensuring it is both convex and closed under nonnegative scaling.^[7] In contrast, if S is an infinite set, the resulting conical hull may not be polyhedral; for instance, it can produce smooth boundaries, as seen in non-polyhedral cones like the Lorentz cone.^[8] The dimensionality of such cones is constrained by the ambient space. In \mathbb{R}^d, the conical hull of any set S has dimension at most d, determined by the linear span of S; specifically, the dimension equals the rank of the matrix whose columns are the vectors in S.^[9] This rank reflects the minimal number of linearly independent directions needed to generate the cone, ensuring that the cone lies within a subspace of dimension equal to that rank. If the generators in S are linearly independent and number exactly d in \mathbb{R}^d, the resulting cone is simplicial, meaning it is combinatorially equivalent to the standard simplicial cone generated by the standard basis vectors.^[10] These properties highlight the role of conical combinations in embedding cone structures within finite-dimensional spaces, where finite generation guarantees polyhedrality and linear independence yields simplicial forms.^[6]

Visualization Examples

To visualize conical combinations, consider simple cases in low-dimensional real vector spaces, where they form rays or wedges emanating from the origin. In one dimension, \mathbb{R}^1, the conical combinations of a single positive basis vector, such as $1, consist of all nonnegative scalar multiples \alpha \cdot 1 with \alpha \geq 0, yielding the ray [0, \infty). Similarly, conical combinations of a negative basis vector, such as -1, generate the ray (-\infty, 0]. These rays illustrate how conical combinations extend indefinitely in one direction from the origin, excluding the opposite direction. In two dimensions, \mathbb{R}^2, the conical combinations of the standard basis vectors \mathbf{e}_1 = (1, 0) and \mathbf{e}_2 = (0, 1) form the nonnegative orthant \mathbb{R}^2_+, consisting of all points (x, y) where x \geq 0 and y \geq 0. This region appears as a quarter-plane bounded by the positive axes. Extending to three dimensions, \mathbb{R}^3, the conical combinations of the standard basis vectors \mathbf{e}_1 = (1, 0, 0), \mathbf{e}_2 = (0, 1, 0), and \mathbf{e}_3 = (0, 0, 1) generate the positive octant, the set of all points (x, y, z) with x \geq 0, y \geq 0, z \geq 0. This forms an infinite pyramid-like region in the first octant. For non-coplanar vectors, such as (1, 0, 0), (0, 1, 0), and (1, 1, 1), the resulting cone resembles a pyramidal wedge, highlighting the volumetric structure in higher dimensions. When considering an infinite set, such as the unit circle S = \{\mathbf{x} \in \mathbb{R}^2 : \|\mathbf{x}\|_2 = 1\} in \mathbb{R}^2, the conical combinations exactly fill the entire plane \mathbb{R}^2. Any nonzero vector \mathbf{y} can be expressed as \|\mathbf{y}\| \cdot (\mathbf{y}/\|\mathbf{y}\|), where \mathbf{y}/\|\mathbf{y}\| lies on the unit circle, using a single finite conical combination to cover all directions and magnitudes.^[11] A concrete computation in \mathbb{R}^2 further clarifies: for vectors \mathbf{v}_1 = (1, 1) and \mathbf{v}_2 = (1, -1), a conical combination is $2\mathbf{v}_1 + 3\mathbf{v}_2 = 2(1, 1) + 3(1, -1) = (5, -1), which lies on the ray from the origin through this point. Note that only nonnegative coefficients are permitted, restricting the set to the half-plane where the first coordinate is at least the absolute value of the second, rather than the full plane.

Properties

Algebraic Properties

Conical combinations exhibit several key algebraic properties that stem from their definition as finite nonnegative linear combinations of vectors. These properties ensure that the structure remains preserved under basic operations, making conical combinations foundational in vector space analysis. One fundamental property is homogeneity. If x = \sum_{i=1}^k \lambda_i v_i is a conical combination of vectors v_1, \dots, v_k with coefficients \lambda_i \geq 0, then for any scalar \alpha > 0, \alpha x = \sum_{i=1}^k (\alpha \lambda_i) v_i is also a conical combination, as the scaled coefficients \alpha \lambda_i \geq 0 satisfy the nonnegativity requirement.^[1] This scaling property reflects the ray-like extension inherent in cones generated by such combinations. Conical combinations are also closed under addition. Suppose x = \sum_{i=1}^m \lambda_i v_i and y = \sum_{j=1}^n \mu_j w_j are conical combinations of the respective sets \{v_1, \dots, v_m\} and \{w_1, \dots, w_n\}, with all coefficients nonnegative. Then their sum is

x + y = \sum_{i=1}^m \lambda_i v_i + \sum_{j=1}^n \mu_j w_j,

which forms a conical combination of the combined set \{v_1, \dots, v_m, w_1, \dots, w_n\}, as the coefficients remain nonnegative.^[1] This closure ensures that the sum of elements from the cone generated by conical combinations stays within the cone. By definition, conical combinations are restricted to finite sums, even when the generating set is infinite. This finiteness requirement distinguishes them from infinite series or integrals, limiting representations to a finite number of terms k in the expression \sum_{i=1}^k \lambda_i v_i.^[1]

Closure and Convexity

The conical hull of a set S, defined as the set of all conical combinations of elements from S, is both convex and forms a convex cone. This means it contains all line segments between any two of its points and is closed under addition and positive scalar multiplication. Specifically, if x, y belong to the conical hull, then for any \theta \in [0, 1], the point \theta x + (1 - \theta) y also lies within the conical hull, confirming its convexity. Furthermore, the origin is included, as the zero combination (all coefficients equal to zero) is a conical combination.^[12] To see why the conical hull is convex, consider two points x and y in the hull, expressed as conical combinations: x = \sum_{i} \alpha_i s_i and y = \sum_{j} \beta_j s_j, where \alpha_i \geq 0, \beta_j \geq 0, and s_i, s_j \in S. Their convex combination is \theta x + (1 - \theta) y = \sum_{i} (\theta \alpha_i) s_i + \sum_{j} ((1 - \theta) \beta_j) s_j, where the new coefficients \theta \alpha_i \geq 0 and (1 - \theta) \beta_j \geq 0. Thus, \theta x + (1 - \theta) y is itself a conical combination of elements from S. This coefficient multiplication preserves non-negativity, ensuring the result remains in the conical hull.^[12] The conical hull is also closed under positive scaling, which reinforces its cone property: for any point z in the hull and \lambda > 0, \lambda z is obtained by scaling the coefficients in z's conical combination by \lambda, yielding another conical combination. This allows rays from the origin through any point in the hull to lie entirely within the set.^[12] Conical combinations generate convex cones, which are typically unbounded and extend infinitely along rays from the origin, in contrast to the bounded nature of many convex hulls formed by convex combinations. While both structures are convex, the absence of a normalization constraint (like coefficients summing to 1) in conical combinations leads to this ray-like extension, distinguishing convex cones from more general bounded convex sets.^[12]

Conical Hull

Definition

\cone(S) = \left\{ \sum_{i=1}^k \lambda_i s_i \;\middle|\; k \in \mathbb{N},\ s_i \in S,\ \lambda_i \geq 0 \ \forall i = 1, \dots, k \right\},

Characterization

The conical hull of a finite set S in a finite-dimensional Euclidean space is a polyhedral cone, generated by the elements of S. If the elements of S are in general position—meaning no element lies in the conical hull of the others—they form the extreme rays of the cone, which are its one-dimensional faces.^[13] The Weyl-Minkowski theorem establishes that in finite dimensions, a cone is polyhedral if and only if it is the conical hull of finitely many extreme rays (or generators).^[7] When S is infinite, the conical hull need not be polyhedral. For instance, the second-order (Lorentz) cone in \mathbb{R}^3, known as the ice-cream cone and given by \{ (x, y, z) \in \mathbb{R}^3 \mid z \geq \sqrt{x^2 + y^2} \}, is the conical hull of the infinite set consisting of the ray along (0, 0, 1) and all directions (x, y, 1) with x^2 + y^2 = 1; this cone is convex and closed but not polyhedral due to its infinitely many extreme rays.^[14] The dual cone of a cone C, denoted C^*, is the set

C^* = \{ y \mid \langle y, x \rangle \geq 0 \ \forall x \in C \}.

This set is always a closed convex cone. For the conical hull of a set S, the dual cone is the intersection of half-spaces defined by the generators:

(\cone(S))^* = \bigcap_{s \in S} \{ y \mid \langle y, s \rangle \geq 0 \}.

The equality holds because any conical combination in \cone(S) yields non-negative inner products if and only if the generators do.^[15] For closed convex cones, the polar cone coincides with the dual cone under the standard definition using non-negative inner products; the polar is equivalently C^\circ = \{ y \mid \langle y, x \rangle \leq 0 \ \forall x \in C \} = -C^*, but the duality properties align such that biduality recovers the original cone: (C^*)^* = C. This relation underscores the self-dual nature of certain polyhedral cones, like the non-negative orthant.^[15] The Weyl-Minkowski theorem complements this by characterizing finite-dimensional polyhedral cones precisely as those expressible as conical combinations of finitely many generators, linking generation to duality in optimization contexts.^[7]

Convex Combinations

A convex combination of points v_1, v_2, \dots, v_n in a real vector space is given by \sum_{i=1}^n \lambda_i v_i, where each coefficient satisfies \lambda_i \geq 0 and the normalization condition \sum_{i=1}^n \lambda_i = 1. This construction ensures that the resulting point lies within the affine hull of the original points, specifically on the line segments connecting them, forming a bounded set.^[12] The primary distinction from conical combinations lies in this normalization: conical combinations employ non-negative coefficients \lambda_i \geq 0 without requiring their sum to equal 1, permitting arbitrary positive scaling that generates unbounded rays emanating from the origin in the direction of the points. In contrast, the sum-to-1 constraint in convex combinations anchors the result in an affine subspace, yielding bounded segments rather than rays. This difference underscores the affine nature of convex combinations versus the conical (or radial) structure of their unnormalized counterparts.^[12] The two concepts are closely related, as every convex combination constitutes a conical combination by setting the scale such that the coefficients sum to 1. Conversely, for any nonzero conical combination \sum_{i=1}^n \lambda_i v_i where \sum_{i=1}^n \lambda_i > 0, normalization yields a convex combination: divide by the total weight to obtain \sum_{i=1}^n \mu_i v_i, with \mu_i = \lambda_i / \sum \lambda_j \geq 0 and \sum \mu_i = 1. More generally, such a conical combination can be factored as \alpha \left( \sum_{i=1}^n \mu_i v_i \right), where \alpha = \sum \lambda_i > 0 is the scaling factor and \sum \mu_i v_i is the associated convex combination.^[12]

Positive Spans

The positive span of a set S in a finite-dimensional real vector space is defined as the set of all points expressible as finite sums \sum_{i=1}^k \lambda_i s_i, where each s_i \in S, k is finite, and the coefficients satisfy \lambda_i \geq 0 for all i. This construction is equivalent to the conical hull of S, as it generates all non-negative linear combinations, including the origin and boundary rays.^[16] Unlike general linear spans, which allow negative coefficients, the positive span enforces non-negativity, making it a convex cone. It is particularly relevant in optimization and geometry for describing the closure under positive scaling and addition. For instance, the positive span of the vectors (1,0) and (0,1) in \mathbb{R}^2 consists of all points (x,y) with x \geq 0 and y \geq 0, forming the closed first quadrant, which is the conical hull generated by the same vectors.

Applications

In Optimization

In convex optimization, conical combinations play a fundamental role in defining feasible sets through cone programming, where the constraints are formulated over convex cones generated by nonnegative linear combinations of vectors or matrices. Semidefinite programming (SDP), a prominent class of cone programs, involves optimizing a linear objective over the intersection of the positive semidefinite cone and affine constraints; the positive semidefinite cone consists of symmetric matrices that can be expressed as conic combinations of rank-one matrices, enabling applications in control theory, structural design, and machine learning. Similarly, second-order cone programming (SOCP) uses Lorentz cones, which are quadratic cones closed under conic combinations, to model constraints like \|Ax + b\| \leq c^Tx + d for robust optimization and portfolio management. These structures generalize linear programming while preserving solvability via interior-point methods.^[17]^[18] In linear programming (LP), nonnegativity constraints on decision variables \lambda_i \geq 0 directly enforce conical combinations, allowing the feasible region to be represented as the conical hull of generating points or rays, which approximates polyhedral sets in problems like production planning or network flow. For instance, a point x lies in the polyhedron if it can be written as x = A\lambda with \lambda \geq 0, where A contains the extreme rays, ensuring the problem remains tractable under duality. This formulation highlights how conical combinations provide a geometric interpretation of LP feasibility, bridging algebraic constraints to convex geometry. Conical hulls appear in optimization duality, particularly through Lagrangian formulations and Karush-Kuhn-Tucker (KKT) conditions, where the tangent cone at an optimal point—defined as the conical hull of feasible directions—characterizes stationarity and constraint qualifications. In conic programs, the dual problem involves maximizing over the dual cone, which is the set of vectors nonnegative with respect to conic combinations in the primal, ensuring strong duality under Slater's condition. For example, consider minimizing c^T x subject to x \in \mathrm{cone}(A), where \mathrm{cone}(A) is the conical hull generated by columns of A; the dual recovers supporting hyperplanes via conic duals, aiding in sensitivity analysis. Algorithmically, interior-point methods exploit the conical interior—the relative interior of the cone generated by strict conic combinations—to maintain feasibility while approaching optimality, using barrier functions like -\log\det(X) for SDP or -\log(t^2 - \|x\|^2) for SOCP to penalize boundary proximity. These methods, polynomial-time in problem size, iteratively solve Newton systems to navigate the cone's interior, achieving high precision in large-scale problems such as sensor network localization.^[19]

In Polyhedral Combinatorics

In polyhedral combinatorics, conical combinations form the foundation for describing polyhedral cones, which are unbounded polyhedral sets containing the origin and closed under non-negative scaling. A polyhedral cone C \subseteq \mathbb{R}^n is defined as the conical hull of a finite set of vectors V = \{v_1, \dots, v_m\}, meaning C = \{ \sum_{i=1}^m \lambda_i v_i \mid \lambda_i \geq 0 \ \forall i \}. This V-representation (vertex-ray description) captures the combinatorial structure through extreme rays, where each v_i generates a one-dimensional face. Equivalently, by the Minkowski-Weyl theorem, every polyhedral cone admits an H-representation as the intersection of finitely many half-spaces \{ x \mid A x \leq 0 \} passing through the origin, linking the generating vectors to facet-defining hyperplanes. This duality underpins algorithms for cone optimization and polyhedral projection in combinatorial problems.^[6] Conical combinations extend naturally to general polyhedra, which are Minkowski sums of a polytope (bounded convex hull) and a polyhedral cone, i.e., P = \operatorname{conv}(Y) + \operatorname{cone}(R) for finite sets Y of points and R of rays. The recession cone \operatorname{rec}(P) = \{ d \mid x + \lambda d \in P \ \forall x \in P, \lambda \geq 0 \} is the polyhedral cone generated by conical combinations of rays in R, determining the directions of unboundedness and ensuring the polyhedron's structure remains finite-dimensional. This decomposition is vital for analyzing faces and vertices in polyhedral graphs, as well as for separation oracles in ellipsoid methods applied to combinatorial optimization. For instance, in matching polytopes, the recession cone encodes capacity constraints via non-negative combinations of edge directions.^[20] Further applications arise in integer polyhedral combinatorics, where the Hilbert basis of a polyhedral cone C is a minimal finite set of integer vectors such that every integer point in C is a conical combination with non-negative integer coefficients. Computing this basis reveals the monoid structure of lattice points, aiding in the resolution of integer linear programs and the study of toric ideals. Carathéodory's theorem for cones ensures that any point in \operatorname{cone}(S) can be expressed as a conical combination of at most n linearly independent vectors from S in \mathbb{R}^n, bounding the complexity of such representations and facilitating enumerative algorithms in polyhedral enumeration. Polar duality further connects these structures: the polar cone C^* = \{ y \mid y^T x \leq 0 \ \forall x \in C \} is itself polyhedral, with faces corresponding inversely to those of C.^[6]

Conical combination

Basic Concepts

Definition

Notation

Geometric Interpretation

In Finite-Dimensional Spaces

Visualization Examples

Properties

Algebraic Properties

Closure and Convexity

Conical Hull

Definition

Characterization

Related Concepts

Convex Combinations

Positive Spans

Applications

In Optimization

In Polyhedral Combinatorics

References