Composition Of Convex Functions Is Convex

Composition of Convex Functions is Convex: A Comprehensive Guide

Meta Description: Learn the conditions under which the composition of two convex functions remains convex. This guide provides a clear explanation with examples and proofs, ideal for those studying optimization or convex analysis.

The composition of functions is a fundamental concept in mathematics, particularly relevant in optimization and convex analysis. Understanding when the composition of convex functions remains convex is crucial for various applications, from machine learning algorithms to economic modeling. This article delves into the conditions that guarantee the convexity of a composite function, offering both intuitive explanations and rigorous proofs.

What are Convex Functions?

Before exploring the composition of convex functions, let's establish a firm understanding of what defines a convex function. A function f: ℝⁿ → ℝ is considered convex if, for any two points x, y in its domain and any scalar λ ∈ [0, 1], the following inequality holds:

f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y)

This inequality essentially states that the function's value at a weighted average of two points is less than or equal to the weighted average of the function's values at those two points. Geometrically, this means that a line segment connecting any two points on the function's graph lies above the graph itself.

Composition of Functions: The Setup

Let's consider two functions: g: ℝⁿ → ℝ^m and h: ℝ^m → ℝ. The composition of these functions, denoted as (h ◦ g)(x), is defined as h(g(x)). Our goal is to determine under what conditions the composition (h ◦ g)(x) is convex, given that g and h are convex.

Conditions for Convex Composition

The composition of two convex functions is not always convex. A crucial condition for guaranteeing convexity of the composition is the convexity of g and the convexity and non-decreasing nature of h. More precisely:

• g(x) must be convex. This is a straightforward requirement.

• h(x) must be convex and non-decreasing. The convexity of h is intuitive; however, the non-decreasing condition is critical. A non-decreasing function means that if a ≤ b, then h(a) ≤ h(b). This condition prevents situations where the convexity of g is "reversed" by a decreasing h.

Proof of Convexity

We can prove the convexity of (h ◦ g)(x) under these conditions. Let x and y be points in the domain of g, and let λ ∈ [0, 1].

1. Convexity of g: Since g is convex, we have: g(λx + (1 − λ)y) ≤ λg(x) + (1 − λ)g(y)

2. Non-decreasing and Convexity of h: Let's define a = g(λx + (1 − λ)y), b = λg(x), and c = (1 − λ)g(y). From step 1, we have a ≤ λb + (1 − λ)c. Because h is non-decreasing, we get h(a) ≤ h(λb + (1 − λ)c).

3. Convexity of h: Since h is convex, we have: h(λb + (1 − λ)c) ≤ λh(b) + (1 − λ)h(c)

4. Combining inequalities: Substituting back, we get: h( g(λx + (1 − λ)y) ) ≤ λh(g(x)) + (1 − λ)h(g(y)) This is equivalent to: (h ◦ g)(λx + (1 − λ)y) ≤ λ*(h ◦ g)(x) + (1 − λ)(h ◦ g)*(y)

This inequality confirms that (h ◦ g)(x) is convex.

Examples

Example 1 (Convex): Let g(x) = x² (convex) and h(x) = e^x (convex and non-decreasing). Then (h ◦ g)(x) = e^x² is also convex.

Example 2 (Not necessarily convex): Let g(x) = x² (convex) and h(x) = -x (convex but decreasing). The composition (h ◦ g)(x) = -x² is concave, not convex.

Conclusion

The composition of two convex functions is convex only under specific conditions: g must be convex, and h must be both convex and non-decreasing. Understanding this theorem is essential for anyone working with convex optimization problems and related fields. This knowledge allows for the construction and analysis of more complex convex functions from simpler building blocks. Remember to always verify that both conditions are satisfied before concluding that the composition is convex.