Important Convex Functions

Why This Matters

Convex functions are the backbone of optimization theory—and you'll encounter them constantly in problems involving minimization, duality, and constraint handling. The reason convexity matters so much is that any local minimum of a convex function is automatically a global minimum, which makes optimization tractable. When you're working through problems in convex geometry, you're being tested on your ability to recognize convexity, verify it using second derivatives or other criteria, and apply the right function to model a given scenario.

This guide organizes important convex functions by their structural properties and typical applications: elementary functions with simple curvature, functions built from set geometry, and specialized functions used in optimization algorithms. Don't just memorize definitions—know what makes each function convex and when you'd reach for it in a problem.

---

Elementary Convex Functions

These are the foundational functions you'll use to build intuition about convexity. Their convexity follows directly from calculus—specifically, non-negative second derivatives guarantee convexity for twice-differentiable functions.

Linear Functions

• Form: $f(x) = ax + b$—both convex and concave simultaneously, making them affine functions
• Second derivative equals zero, which satisfies the convexity condition $f''(x) \geq 0$ trivially
• Define hyperplanes and half-spaces in convex optimization; serve as objective functions in linear programming

Quadratic Functions

• Form: $f(x) = ax^2 + bx + c$ with $a > 0$—the positive leading coefficient ensures the parabola opens upward
• Constant positive second derivative $f''(x) = 2a > 0$ confirms strict convexity throughout the domain
• Central to quadratic programming, where objectives are quadratic and constraints are linear; appears in least-squares problems

Exponential Functions

• Form: $f(x) = e^{ax}$—convex for all real values of $a$, with $f''(x) = a^2 e^{ax} > 0$
• Rapid growth property makes it essential for modeling compound growth, decay processes, and risk in economics
• Log-sum-exp function $\log(\sum e^{x_i})$ is a smooth convex approximation to the max function

---

Functions Derived from Concave Building Blocks

Some important convex functions arise by negating concave functions or applying transformations. Understanding this relationship helps you convert between convex and concave formulations in optimization problems.

Negative Log Functions

• Form: $f(x) = -\log(x)$—convex on $x > 0$ since $f''(x) = 1/x^2 > 0$
• Logarithm itself is concave, but its negative gives you a convex function useful for barrier methods
• Models diminishing returns in economics; appears in maximum likelihood estimation and information-theoretic objectives

Entropy Functions

• Form: $f(p) = -\sum p_i \log(p_i)$—this is negative entropy, which is convex in the probability vector $p$
• Strict convexity follows from the strict concavity of $x \log x$ and properties of probability simplices
• Fundamental in information theory for channel capacity problems; used in maximum entropy methods and statistical mechanics

---

Norm-Based Functions

Norms provide a natural way to measure size and distance, and their convexity follows from the triangle inequality and positive homogeneity—not from second derivatives.

Norm Functions

• Form: $f(x) = \|x\|$—convex for any valid norm, including $L_1$, $L_2$, and $L_\infty$
• Triangle inequality $\|x + y\| \leq \|x\| + \|y\|$ directly implies convexity via the definition
• Essential for regularization in machine learning: $L_1$ promotes sparsity (LASSO), $L_2$ prevents large weights (ridge regression)

Support Functions

• Form: $\sigma_C(x) = \sup\{\langle x, y \rangle : y \in C\}$—the supremum of linear functions over a convex set $C$
• Convex because suprema of convex functions are convex; each $\langle x, y \rangle$ is linear (hence convex) in $x$
• Characterizes convex sets completely through duality; critical in Fenchel conjugate theory and geometric optimization

---

Set-Based Convex Functions

These functions encode constraints geometrically, allowing you to incorporate feasibility conditions directly into the objective. They're essential for understanding constrained optimization through an unconstrained lens.

Indicator Functions

• Form: $\delta_C(x) = 0$ if $x \in C$, and $\delta_C(x) = +\infty$ otherwise—an extended real-valued function
• Convex when $C$ is convex because the epigraph $\{(x, t) : x \in C, t \geq 0\}$ is a convex set
• Converts constrained problems to unconstrained: minimizing $f(x) + \delta_C(x)$ enforces $x \in C$ automatically

Barrier Functions

• Approach $+\infty$ as $x$ approaches the boundary of a feasible region; example: $-\sum \log(x_i)$ for $x > 0$
• Self-concordant barriers satisfy special smoothness conditions enabling efficient interior-point algorithms
• Keep iterates strictly feasible during optimization, avoiding boundary issues that plague other methods

---

Transformation-Preserving Functions

These functions maintain convexity under specific operations, allowing you to build complex convex functions from simpler ones while preserving optimization tractability.

Perspective Functions

• Form: $g(x, t) = t \cdot f(x/t)$ for $t > 0$—extends a convex function $f$ to a higher-dimensional domain
• Preserves convexity: if $f$ is convex, then $g$ is jointly convex in $(x, t)$
• Appears in relative entropy $\text{KL}(p \| q) = \sum p_i \log(p_i/q_i)$ and portfolio optimization with scaling

---

Quick Reference Table

---

Self-Check Questions

1. Both linear and quadratic functions have constant second derivatives. Why does a quadratic function have a unique minimizer while a linear function (with $a \neq 0$) does not?

2. Which two functions from this guide would you use to model a constrained optimization problem where you want iterates to stay strictly inside the feasible region? How do they differ in approach?

3. The logarithm is concave, yet entropy-based objectives appear in convex optimization. Explain how convexity is achieved in entropy minimization problems.

4. Compare norm functions and support functions: what geometric property do they share, and what different information do they encode about vectors versus sets?

5. You're given a convex function $f(x)$ and need to create a joint function $g(x, t)$ that remains convex while allowing the input to be scaled by $t$. Which function type accomplishes this, and what condition must $t$ satisfy?