Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 38 ยท Convex Sets and Functions

Convex Sets

Learn what a convex set is, see examples such as balls, half-spaces and polyhedra, and test convexity numerically by sampling line segments in Python.

Convex optimization has two ingredients: convex sets (where you are allowed to search) and convex functions (what you minimize). We start with sets because they are easier to picture. A set is convex when it has no dents, holes or separate islands: if you pick any two points inside it and draw the straight segment between them, the whole segment stays inside.

Definition

A set C is convex if for every x, y โˆˆ C and every number ฮธ with 0 โ‰ค ฮธ โ‰ค 1, the point

Text
ฮธx + (1 - ฮธ)y

is also in C. When ฮธ = 1 you get x, when ฮธ = 0 you get y, and values in between slide along the segment. The expression is called a convex combination of x and y.

A filled circle is convex. A crescent moon is not: two points on the tips can be joined by a segment that leaves the shape. A set made of two separate disks is not convex either.

Common convex sets

Set Formula Notes
Line or plane (hyperplane) aแต€x = b all points satisfying one linear equation
Half-space aแต€x โ‰ค b one side of a hyperplane
Ball โ€–x - cโ€– โ‰ค r uses the Euclidean norm
Box l โ‰ค x โ‰ค u (each coordinate) product of intervals
Polyhedron Ax โ‰ค b intersection of finitely many half-spaces
Non-negative orthant x โ‰ฅ 0 each coordinate at least zero
Positive semidefinite matrices X = Xแต€, X โชฐ 0 a cone of matrices, used in advanced topics

Two quick rules give many more examples. The intersection of any number of convex sets is convex. And an image of a convex set under a linear map x โ†ฆ Ax + b is convex.

Testing convexity by sampling

A numerical test cannot prove convexity, but it can find a counterexample quickly. The idea: draw random pairs of points inside the set, and check that points on the segment between them are also inside.

Python Sampling test for convexity

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The disk passes. The ring fails quickly: two points on opposite sides of the hole have a midpoint inside the hole.

Seeing the sets

Python A disk, a ring and a segment

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why optimizers care

Suppose you minimize over a convex set C. Starting from a feasible point and moving toward another feasible point keeps you feasible. That is why algorithms such as projected gradient descent (coming later) can take straight steps without worrying about leaving the region. If C had a hole in it, no such guarantee would exist.

Polyhedra and linear constraints

A system of linear inequalities Ax โ‰ค b describes a polyhedron. Each row cuts the space with a half-space, and the intersection of half-spaces is convex. Linear programs optimize over exactly these sets. Checking if a point is feasible is just a matrix-vector product and a comparison.

Python Membership in a polyhedron

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The point (3, 2) violates 3x + 4y โ‰ค 12 (the left side is 17), so it is outside; (1, 1) and the corner (4, 0) are inside.

A convex combination of several points uses non-negative weights that add up to 1. The set of all such combinations of a finite point set is called its convex hull, the smallest convex set that contains the points.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A set C is convex if

    That is the definition: every convex combination of two points of C stays in C.
  2. 2. Which set is NOT convex?

    A segment between two points on opposite sides of the hole passes through the hole.
  3. 3. The intersection of two convex sets is

    If both points lie in both sets, the segment lies in each set, hence in the intersection.
  4. 4. The set {x : Ax โ‰ค b} is called a

    It is an intersection of finitely many half-spaces.

Summary

  • A set is convex when it contains the segment between any two of its points.
  • Balls, boxes, half-spaces and polyhedra are convex; intersections of convex sets stay convex.
  • Sampling can reveal non-convexity but cannot prove convexity.
  • Convex feasible sets let algorithms move in straight lines without leaving the region.

Next: Convex Functions