Convex Functions

We’ve learned that convex sets create smooth, well-behaved landscapes for optimization. Now, let’s explore the functions that live on these landscapes: convex functions. These functions are the heart of many optimization techniques because they guarantee no traps, no false minima, and a single, clear path to the best solution.

What Is a Convex Function?

A function is convex if its graph curves upward—like a bowl. The key property of a convex function is that the line segment between any two points on the graph lies above or on the graph itself.

Formally:
A function $f:{\mathbb{R}}^n\to \mathbb{R}$ is convex if:

1. The domain $D(f)$ is a convex set.
2. For all $\mathbf{x},\mathbf{y}\in D(f)$ and $\lambda \in [0,1]$, the function satisfies:

This means that for any two points $\mathbf{x}$ and $\mathbf{y}$, the function value at any weighted average of these points is at most the weighted average of the function values. In other words, the function does not "dip" between two points.

Strictly Convex Functions

A function is strictly convex if the inequality is strict for all distinct $\mathbf{x}\ne \mathbf{y}$:

Strict convexity ensures uniqueness of the minimum—there is only ONE lowest point.

Let's compare the formal definitions of convex and strictly convex functions:

• Convex function:

  $$f(\lambda \mathbf{x}+(1-\lambda )\mathbf{y})\le \lambda f(\mathbf{x})+(1-\lambda )f(\mathbf{y})\text{for all }\mathbf{x},\mathbf{y}\text{ and }\lambda \in [0,1]$$

• Strictly convex function:

  $$f(\lambda \mathbf{x}+(1-\lambda )\mathbf{y})<\lambda f(\mathbf{x})+(1-\lambda )f(\mathbf{y})\text{for all }\mathbf{x},\mathbf{y}\text{ and }\lambda \in (0,1)$$

So we can observe that strict convexity is a stronger condition than convexity.

Geometric Interpretation

• Convex function: The line segment between any two points lies above or on the function.
• Strictly convex function: The line segment is always strictly above the function.

This guarantees that there are no multiple minima, which is a key reason why convex functions are fundamental in optimization.

this also called sometimes as chord rule.
The red dotted line is the chord between two points on the graph and it lies above the blue part of the graph.

Examples of Convex Functions

• Linear functions: $f(x)=a^{T}x$
• Affine functions: $f(x)=a^{T}x+b$
• Quadratic functions (if $a>0$): $f(x)=a{x}^2+bx+c$
• Exponential functions: $f(x)=e^{\alpha x}$
• Norm functions: $f(x)=\parallel x\parallel$

Examples of multivariate convex functions

Understanding convex functions is crucial for solving complex optimization problems efficiently! 🚀

Continuity of convex functions

A convex function is automatically continuous if its domain is open:

Theorem: If $f$ is convex and its domain $D(f)$ is open, then $f$ is continuous.

Why is this true?

• Convex functions have no sudden jumps or breaks because their "bowl-shaped" graph must stay smooth to satisfy the chord rule.

How to check if a function is convex using derivatives

First-order condition (gradient test)

If $f$ is differentiable, it is convex if and only if:

What does this mean?

• The tangent line at any point is always below the curve.
• Convex functions never "dip" under their tangents.

Second-order condition (Hessian test)

If $f$ is twice differentiable, it is convex if and only if its Hessian matrix (second derivative) is positive semidefinite:

Explanation:

• The Hessian matrix measures curvature.
• Positive semidefinite means the function curves upward everywhere (like a bowl).

So, according to this test, a function $f$ should has nonnegative second derivative (curvature) everywhere!

this function is NOT a convex! We need only "+"

What's next?