Concavity and convexity

What is a convex linear combination of two vectors x, y ∈ ℝⁿ?

It is αx + (1 − α)y, where α ∈ [0,1].

When is a set C ⊆ ℝⁿ convex?

C is convex if, for every x, y ∈ C and every α ∈ [0,1], αx + (1 − α)y ∈ C. Equivalently, the entire line segment joining any two points of C lies in C.

When is a function f: I → ℝ concave on an interval I ⊆ ℝ?

f is concave if, for all x, y ∈ I and every α ∈ [0,1], f(αx + (1 − α)y) ≥ αf(x) + (1 − α)f(y).

When is a function f: I → ℝ convex on an interval I ⊆ ℝ?

f is convex if, for all x, y ∈ I and every α ∈ [0,1], f(αx + (1 − α)y) ≤ αf(x) + (1 − α)f(y).

When is a function f: I → ℝ strictly concave?

f is strictly concave if, for all distinct x, y ∈ I and every α ∈ (0,1), f(αx + (1 − α)y) > αf(x) + (1 − α)f(y).

When is a function f: I → ℝ strictly convex?

f is strictly convex if, for all distinct x, y ∈ I and every α ∈ (0,1), f(αx + (1 − α)y) < αf(x) + (1 − α)f(y).

What is the epigraph of a function f: I → ℝ?

epi(f) = {(x,y) ∈ ℝ² : x ∈ I and y ≥ f(x)}. It is the region on or above the graph of f.

What is the hypograph of a function f: I → ℝ?

hypo(f) = {(x,y) ∈ ℝ² : x ∈ I and y ≤ f(x)}. It is the region on or below the graph of f.

How can convexity be characterized using the epigraph?

A function is convex if and only if its epigraph is a convex set.

How can concavity be characterized using the hypograph?

A function is concave if and only if its hypograph is a convex set.

What is the relationship between the concavity of f and the convexity of −f?

f is concave if and only if −f is convex. Likewise, f is strictly concave if and only if −f is strictly convex.

What is an affine function in terms of concavity and convexity?

An affine function is a function that is both concave and convex.

How are affine functions f: ℝ → ℝ characterized?

f is affine if and only if there exist m, q ∈ ℝ such that f(x) = mx + q.

When is a function f: C → ℝ concave on a convex set C ⊆ ℝⁿ?

f is concave if, for all x, y ∈ C and every α ∈ [0,1], f(αx + (1 − α)y) ≥ αf(x) + (1 − α)f(y).

When is a function f: C → ℝ convex on a convex set C ⊆ ℝⁿ?

f is convex if, for all x, y ∈ C and every α ∈ [0,1], f(αx + (1 − α)y) ≤ αf(x) + (1 − α)f(y).

When is a function f: C → ℝ strictly concave on a convex set C ⊆ ℝⁿ?

f is strictly concave if, for all distinct x, y ∈ C and every α ∈ (0,1), f(αx + (1 − α)y) > αf(x) + (1 − α)f(y).

When is a function f: C → ℝ strictly convex on a convex set C ⊆ ℝⁿ?

f is strictly convex if, for all distinct x, y ∈ C and every α ∈ (0,1), f(αx + (1 − α)y) < αf(x) + (1 − α)f(y).

When is a function f: C → ℝ affine on a convex set C ⊆ ℝⁿ?

f is affine if, for all x, y ∈ C and every α ∈ [0,1], f(αx + (1 − α)y) = αf(x) + (1 − α)f(y).

What happens when two concave functions are added?

The sum of two concave functions is concave.

What happens when two convex functions are added?

The sum of two convex functions is convex.

How does multiplication by a non-negative scalar affect concavity?

If f: C → ℝ is concave and λ ≥ 0, then λf is concave.

How does multiplication by a non-negative scalar affect convexity?

If f: C → ℝ is convex and λ ≥ 0, then λf is convex.

What can be said about non-negative linear combinations of concave or convex functions?

A non-negative linear combination of concave functions is concave, and a non-negative linear combination of convex functions is convex.

What is an ordinal property?

An ordinal property is a property preserved under every strictly increasing transformation.

What is a cardinal property?

A cardinal property is a property preserved under strictly increasing affine transformations of the form g(t) = at + b, where a > 0 and b ∈ ℝ.

What is the relationship between ordinal and cardinal properties?

Every ordinal property is also cardinal, but a cardinal property need not be ordinal.

Is concavity an ordinal or cardinal property?

Concavity is cardinal but not ordinal: strictly increasing affine transformations preserve it, but arbitrary strictly increasing transformations may not.

What does Fenchel’s theorem state for concave functions?

Let f: C ⊆ ℝⁿ → ℝ be concave on a convex set C. Every local maximizer of f is also a global maximizer.

What is the analogous form of Fenchel’s theorem for convex functions?

Let f: C ⊆ ℝⁿ → ℝ be convex on a convex set C. Every local minimizer of f is also a global minimizer.

What does concavity imply about the set of maximizers?

If C ⊆ ℝⁿ is convex and f: C → ℝ is concave, then arg max over x ∈ C of f(x) is a convex set.

What are the possible forms of the maximizer set of a concave function on a convex set?

The set of maximizers can be empty, a singleton, or an infinite convex set; it cannot contain a finite number greater than one.

What does strict concavity imply about the set of maximizers?

If C ⊆ ℝⁿ is convex and f: C → ℝ is strictly concave, then arg max over x ∈ C of f(x) is at most a singleton; therefore, there is at most one maximizer.