Concepts / Convex Learning Problems

Convex Learning Problems

The word every is essential. A set is convex only when the segment test succeeds for every pair of points selected from the set.

  • Programming

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.

Set Asegment stays insideLine segmentinside Set ASet Bsegment leavesLine segmentoutside Set Bany two pointssome two points
What happens to the line segment joining two points in the set?
Key point

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.

uin the setαu + (1 − α)vin the set for everyallowed αvin the setweighted with vweighted with u
How do two points in a set and every point between them demonstrate whether the set is convex?
Definition

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.

Worked example

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.

  1. 1
    Choose the endpoints

    Take two points u and v that belong to the set.

  2. 2
    Form points between them

    Consider αu + (1 − α)v, using non-negative coefficients whose sum is 1.

  3. 3
    Check containment

    Check whether every point produced along the segment remains in the set.

  4. 4
    Repeat the test

    The definition requires this containment for every pair of points in the set, not just one selected pair.

Result

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.

α = 0v0 < α < 1between u and vα = 1uincrease αincrease α
Where does a point lie as the mixing weight changes from 0 to 1 between two endpoints?
  • 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.

Definition

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.

αu + (1 − α)vmixed pointf(αu + (1 − α)v)function valueαf(u) + (1 − α)f(v)weighted endpoint valuesevaluatecompare with
How does the function value at a weighted average compare with the weighted average of the endpoint values?
ObjectWhat is testedKey expression
Convex setWhether every segment joining two points remains inside the setαu + (1 − α)v
Convex functionWhether the value at a convex combination is no greater than the matching endpoint-value combinationf(αu + (1 − α)v) ≤ αf(u) + (1 − α)f(v)

A convex set concerns point containment; a convex function concerns the relationship between function values.

Common Recognition Errors

  • Common mistake

    Checking only one pair of points

    What it looks like

    A single segment stays inside the set, so the set is declared convex.

    Why it fails

    Convexity requires the segment test to succeed for every pair of points in the set.

    Do this instead

    Ask whether any pair could produce a segment that leaves the set.

  • Common mistake

    Checking only the endpoints

    What it looks like

    The two selected points are in the set, so the whole connection is assumed to be in the set.

    Why it fails

    The definition concerns every point on the line segment joining the endpoints.

    Do this instead

    Check the entire segment, including all points represented by the convex combination.

  • Common mistake

    Ignoring the coefficient conditions

    What it looks like

    An expression is called a convex combination without verifying its coefficients.

    Why it fails

    Convex combinations use non-negative coefficients that sum to 1.

    Do this instead

    Verify non-negativity and the sum-to-1 condition before applying the convexity test.

  • Common mistake

    Confusing a convex set with a convex function

    What it looks like

    The set condition and the function inequality are treated as the same statement.

    Why it fails

    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.

    Do this instead

    First identify whether the question concerns point containment or function values.

Practice the Distinction

MEDIUM

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?

  • Yes, because one successful segment proves convexity.

  • No, the test must succeed for every pair of points in the set.

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

  1. 1
    A convex set contains every line segment joining any two of its points.
  2. 2
    A convex combination has non-negative coefficients that sum to 1.
  3. 3
    The expression αu + (1 − α)v represents points formed between two endpoints.
  4. 4
    A convex function satisfies f(αu + (1 − α)v) ≤ αf(u) + (1 − α)f(v).
  5. 5
    A convex set concerns where points remain; a convex function concerns how values compare at mixed points.

At a glance

  • 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.

Related Topics

Related concepts

More concepts starting with C