Misplaced Pages

Hilbert basis (linear programming)

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

The Hilbert basis of a convex cone C is a minimal set of integer vectors in C such that every integer vector in C is a conical combination of the vectors in the Hilbert basis with integer coefficients.

Definition

Hilbert basis visualization. Two rays in the plane define an infinite cone of all the points lying between them. The unique Hilbert basis points of the cone are circled in yellow. Every integer point in the cone can be written as a sum of these basis elements. As you change the cone by moving one of the rays, the Hilbert basis also changes.

Given a lattice L ⊂ Z d {\displaystyle L\subset \mathbb {Z} ^{d}} and a convex polyhedral cone with generators a 1 , … , a n ∈ Z d {\displaystyle a_{1},\ldots ,a_{n}\in \mathbb {Z} ^{d}}

C = { λ 1 a 1 + … + λ n a n ∣ λ 1 , … , λ n ≥ 0 , λ 1 , … , λ n ∈ R } ⊂ R d , {\displaystyle C=\{\lambda _{1}a_{1}+\ldots +\lambda _{n}a_{n}\mid \lambda _{1},\ldots ,\lambda _{n}\geq 0,\lambda _{1},\ldots ,\lambda _{n}\in \mathbb {R} \}\subset \mathbb {R} ^{d},}

we consider the monoid C ∩ L {\displaystyle C\cap L} . By Gordan's lemma, this monoid is finitely generated, i.e., there exists a finite set of lattice points { x 1 , … , x m } ⊂ C ∩ L {\displaystyle \{x_{1},\ldots ,x_{m}\}\subset C\cap L} such that every lattice point x ∈ C ∩ L {\displaystyle x\in C\cap L} is an integer conical combination of these points:

x = λ 1 x 1 + … + λ m x m , λ 1 , … , λ m ∈ Z , λ 1 , … , λ m ≥ 0. {\displaystyle x=\lambda _{1}x_{1}+\ldots +\lambda _{m}x_{m},\quad \lambda _{1},\ldots ,\lambda _{m}\in \mathbb {Z} ,\lambda _{1},\ldots ,\lambda _{m}\geq 0.}

The cone C is called pointed if x , − x ∈ C {\displaystyle x,-x\in C} implies x = 0 {\displaystyle x=0} . In this case there exists a unique minimal generating set of the monoid C ∩ L {\displaystyle C\cap L} —the Hilbert basis of C. It is given by the set of irreducible lattice points: An element x ∈ C ∩ L {\displaystyle x\in C\cap L} is called irreducible if it can not be written as the sum of two non-zero elements, i.e., x = y + z {\displaystyle x=y+z} implies y = 0 {\displaystyle y=0} or z = 0 {\displaystyle z=0} .

References


Stub icon

This applied mathematics–related article is a stub. You can help Misplaced Pages by expanding it.

Categories: