Skip to content
Glacius
OptimizationConcept reference

Convex sets

A convex set contains every weighted mixture θa+(1−θ)b of its members when 0≤θ≤1.

1 min read1 figureSources & further reading
On this page 7 sections
  1. Overview
  2. A set is convex when every segment between two of its points stays inside the set
  3. A circular boundary is connected, but a chord can pass through its empty interior
  4. One pair of members with a segment point outside the set disproves convexity
  5. Key takeaway
  6. Sources & further reading
  7. Concept connections

01A set is convex when every segment between two of its points stays inside the set#

A set is convex when every segment between two of its points stays inside the set. Every weight from 0 to 1 must work:

θa+(1−θ)b∈C\theta a+(1-\theta)b\in C

The endpoints a and b must belong to C.

With a=(2,6), b=(6,2) and θ=0.25, the segment point is (5,3). A convex set containing both endpoints must contain this point.

Endpoints a=(2,6), b=(6,2). The point .25a+.75b=(5,3) lies three quarters of the way from a to b. The whole segment shows mixtures of these two endpoints; this single segment does not prove a set convex.Endpoints a=(2,6), b=(6,2). The point .25a+.75b=(5,3) lies three quarters of the way from a to b. The whole segment shows mixtures of these two endpoints; this single segment does not prove a set convex.
Figure 1Endpoints a=(2,6), b=(6,2). The point .25a+.75b=(5,3) lies three quarters of the way from a to b. The whole segment shows mixtures of these two endpoints; this single segment does not prove a set convex.
Link to this figure ↗Download SVGDownload PNG
Check your reasoning

Segment endpoints a=(1,5)(1, 5), b=(5,1)(5, 1), θ=0.25. Find θa+(1−θ)b.

  1. A(4,3)(4, 3)
  2. B(4,2)(4, 2)
  3. C(5,2)(5, 2)
Show answer and explanation
(4,2)(4, 2)

Weights 0.25 and 0.75.

02A circular boundary is connected, but a chord can pass through its empty interior#

A circular boundary is connected, but a chord can pass through its empty interior. The filled disk includes those chord points; the boundary alone does not.

For x²+y²=R², membership requires equality. For the filled disk x²+y²≤R², a smaller squared norm also belongs.

Check your reasoning

C: x²+y²=289. a=(8,15), b=(-8,15). Give (midpoint norm²; in C?).

  1. A225; Yes
  2. B225; No
  3. C289; No
Show answer and explanation
225; No

Midpoint (0,15); 225≠289.

03One pair of members with a segment point outside the set disproves convexity#

One pair of members with a segment point outside the set disproves convexity. It is a concrete counterexample to an all-pairs claim.

Two separate intervals can each be convex while their union has a gap. Passing some segment checks does not fill that gap.

Check your reasoning

C=[−2,0]∪[4,6][-2,0]\cup[4,6]. Draft: C is convex. Endpoints 0,4 belong to C. Give (midpoint; in C?).

  1. A2; Yes
  2. B0; No
  3. C2; No
Show answer and explanation
2; No

2∉C: not convex.

Key takeaway

Use the same weights for every coordinate; one missing segment point disproves convexity.

  • Check whether a line segment between feasible points remains feasible.

Sources & further reading

  1. [1]
    Boyd & Vandenberghe §2.1.4 ↗Boyd & Vandenberghe §2.1.4 · Article

Reference this concept

Link to this page, a section, or an individual figure.

Glacius. “Convex sets.” Math behind ML. /learn/o-convex-set