Math 2.0

Convex and discrete geometry Convex sets: basic notions Theorem

Minkowski–Carathéodory theorem

Builds on Euclidean spaceConvex setCompact setExtreme pointConvex hullConvex combinationSupporting hyperplane theoremCarathéodory's theoremKrein–Milman theoremFace of a convex set

Statement

Let n≥1n \ge 1 and let K⊆ℝnK \subseteq \R^n be a nonempty compact convex set. Let ext⁡K\operatorname{ext} K be the set of extreme points of KK. Then KK is the convex hull of ext⁡K\operatorname{ext} K: K=conv⁡(ext⁡K).K = \operatorname{conv}(\operatorname{ext} K). Moreover, every point of KK is a convex combination of at most n+1n + 1 extreme points of KK.

Remarks

Proof idea: induct on the dimension of KK. If xx lies on the relative boundary of KK, the supporting hyperplane theorem gives a hyperplane HH through xx. Then K∩HK \cap H is a face of lower dimension whose extreme points are extreme points of KK. If xx lies in the relative interior, a line through xx meets KK in a segment with both endpoints on the relative boundary. Then xx is a convex combination of these endpoints. The bound n+1n + 1 then follows from Carathéodory's theorem.

Example: a filled triangle is the convex hull of its three vertices, and a closed disc is the convex hull of its boundary circle.

Both hypotheses on KK are needed. The closed half-plane {(x,y):y≥0}\set{(x, y) : y \ge 0} is closed and convex but has no extreme points. The open disc is bounded and convex but has no extreme points either.

Going deeper

For a student

This is the finite-dimensional case of the Krein–Milman theorem. In ℝn\R^n no closure is needed: the convex hull of ext⁡K\operatorname{ext} K is already all of KK, although ext⁡K\operatorname{ext} K itself need not be closed when n≥3n \ge 3. It explains why a linear function on a compact convex set attains its maximum at an extreme point, which is the basis of the simplex method in linear programming. Applied to polytopes, it says that a bounded intersection of finitely many half-spaces is the convex hull of its vertices.

Reading path

To understand this page from the ground up, read these 20 pages in order. The foundations come first.

Show the path as a graph
Affine combination, concept, no evidence levelAffine combinationconceptBoundary, concept, no evidence levelBoundaryconceptClosed set, concept, no evidence levelClosed setconceptClosure, concept, no evidence levelClosureconceptCompact set, concept, no evidence levelCompact setconceptContinuous dual space, concept, no evidence levelContinuous dual spaceconceptConvex combination, concept, no evidence levelConvex combinationconceptConvex hull, concept, no evidence levelConvex hullconceptConvex set, concept, no evidence levelConvex setconceptDot product, concept, no evidence levelDot productconceptEuclidean space, object, no evidence levelEuclidean spaceobjectExtreme point, concept, no evidence levelExtreme pointconceptFace of a convex set, concept, no evidence levelFace of a convex setconceptLocally convex space, concept, no evidence levelLocally convex spaceconceptSupporting hyperplane, concept, no evidence levelSupporting hyperplaneconceptCarathéodory's theorem, statement, no evidence levelCarathéodory's theoremstatementHahn–Banach separation theorem, statement, no evidence levelHahn–Banach separatio…statementKrein–Milman theorem, statement, no evidence levelKrein–Milman theoremstatementSupporting hyperplane theorem, statement, no evidence levelSupporting hyperplane…statementMinkowski–Carathéodory theorem, statement, no evidence levelMinkowski–Carathéodor…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Affine combination concept
  2. Boundary concept
  3. Closed set concept
  4. Closure concept
  5. Compact set concept
  6. Continuous dual space concept
  7. Convex combination concept
  8. Convex hull concept
  9. Convex set concept
  10. Dot product concept
  11. Euclidean space object
  12. Extreme point concept
  13. Face of a convex set concept
  14. Locally convex space concept
  15. Supporting hyperplane concept
  16. Carathéodory's theorem statement
  17. Hahn–Banach separation theorem statement
  18. Krein–Milman theorem statement
  19. Supporting hyperplane theorem statement
  20. Minkowski–Carathéodory theorem statement

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Krein%E2%80%93Milman_theorem
About this page
TagNT4SKSYKG9
URIm2://NT4SKSYKG9
Kindstatement, theorem
WritingW0 stub
MSC52A20
StatusThis copy of the site has no build data. Run m2 status NT4SKSYKG9.
AboutExtreme point, Convex hull
UsesEuclidean space, Convex set, Compact set, Extreme point, Convex hull, Convex combination, Supporting hyperplane theorem, Carathéodory's theorem, Krein–Milman theorem, Face of a convex set

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by