Convex Learning Problems
Convexity of a set means that every line segment joining two points in the set stays inside the set.
The Segment Test
Convexity asks a geometric question: if you choose any two points from a set, can you travel along the entire line segment joining them without leaving the set? If every such segment stays inside, the set is convex. If at least one segment leaves the set, the set does not satisfy the definition of convexity.
The word every is essential. A set is convex only when the segment test succeeds for every pair of points selected from the set.
Tracing Two Chosen Points
Begin with two points, written as u and v, that are both in the set. The segment joining them contains the points formed by taking a weighted mixture of u and v. The mixture is written as αu + (1 − α)v, where the coefficients are non-negative and add up to 1.
A set is convex when every line segment joining two points in the set remains inside the set. Equivalently, for points u and v in the set, the points αu + (1 − α)v remain in the set for the non-negative coefficients used in a convex combination.
Applying the Segment Test
Suppose u and v are selected from a set. Determine what must be checked to decide whether this pair supports the set's convexity.
Choose the endpoints: Take two points u and v that belong to the set.
Form points between them: Consider αu + (1 − α)v, using non-negative coefficients whose sum is 1.
Check containment: Check whether every point produced along the segment remains in the set.
Repeat the test: The definition requires this containment for every pair of points in the set, not just one selected pair.
The set passes the convexity test only when every segment joining two of its points stays inside the set.
Moving Along a Convex Combination
The expression αu + (1 − α)v describes a point obtained by mixing the two endpoints u and v. The coefficients are non-negative and sum to 1, so the expression represents points on the line segment joining the endpoints. Changing the mixing weight changes which point of that segment is selected.
- A convex combination uses non-negative coefficients.
- The coefficients in a convex combination sum to 1.
- The expression αu + (1 − α)v is the two-point form used to describe points on the joining segment.
- The set definition asks whether all such points remain in the set.
Convex Functions and Their Values
A convex set describes where the points and their connecting segments are allowed to lie. A convex function adds a condition about values: the function value at a convex combination is no greater than the matching convex combination of the function values at the two endpoints.
The inequality defining a convex function is f(αu + (1 − α)v) ≤ αf(u) + (1 − α)f(v), using the same non-negative coefficients that sum to 1. The value at the mixed point is no greater than the corresponding mixture of the endpoint values.
| Object | What is tested | Key expression |
|---|---|---|
| Convex set | Whether every segment joining two points remains inside the set | αu + (1 − α)v |
| Convex function | Whether the value at a convex combination is no greater than the matching endpoint-value combination | f(αu + (1 − α)v) ≤ αf(u) + (1 − α)f(v) |
Common Recognition Errors
Checking only one pair of points
Convexity requires the segment test to succeed for every pair of points in the set.
Fix:
Ask whether any pair could produce a segment that leaves the set.Checking only the endpoints
The definition concerns every point on the line segment joining the endpoints.
Fix:
Check the entire segment, including all points represented by the convex combination.Ignoring the coefficient conditions
Convex combinations use non-negative coefficients that sum to 1.
Fix:
Verify non-negativity and the sum-to-1 condition before applying the convexity test.Confusing a convex set with a convex function
The set condition concerns whether points remain inside a set, while the function condition compares a function value with a weighted combination of endpoint values.
Fix:
First identify whether the question concerns point containment or function values.
Practice the Distinction
For a set containing points u and v, write the convex combination of the two points and state the two conditions its coefficients must satisfy. Then explain what must be checked to decide whether the set is convex. Finally, write the inequality that must hold when a function is convex.
Hints
- Use the form αu + (1 − α)v.
- The coefficients must be non-negative and sum to 1.
- For a set, check whether every point on every joining segment remains inside.
- For a function, compare the value at the mixed point with the matching mixture of endpoint values.
What do you think happens?
A pair of points in a set has a joining segment that remains inside the set. Is that alone enough to establish that the set is convex?
Reveal answer
Answer: No, the test must succeed for every pair of points in the set.
Convexity is defined by every line segment joining two points in the set remaining inside the set.
Key Takeaways
- A convex set contains every line segment joining any two of its points.
- A convex combination has non-negative coefficients that sum to 1.
- The expression αu + (1 − α)v represents points formed between two endpoints.
- A convex function satisfies f(αu + (1 − α)v) ≤ αf(u) + (1 − α)f(v).
- A convex set concerns where points remain; a convex function concerns how values compare at mixed points.
Key Takeaways
- Convexity of a set is a line-segment containment property.
- To test convexity, choose any two points and check every point between them.
- A convex combination uses non-negative coefficients whose sum is 1.
- A convex function's value at a convex combination is no greater than the matching convex combination of endpoint values.
- Convex sets describe point containment, while convex functions describe a value inequality.