Convex functions are crucial in optimization, offering unique properties that simplify problem-solving. They're characterized by their shape, where any line segment between two points on the graph lies above or on the graph itself.

This section dives into convex function definitions, inequalities, and derivatives. We'll explore epigraphs, sublevel sets, Jensen's inequality, and the role of gradients and Hessian matrices in determining convexity and optimizing these functions.

Convex Function Definitions

Understanding Convex and Strictly Convex Functions

• Convex function maintains a line segment between any two points on its graph lies above or on the graph
• Mathematically expressed as $f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)$ for all $x, y$ in the domain and $\lambda \in [0,1]$
• Strictly convex function holds the inequality strictly (line segment lies strictly above the graph except at endpoints)
• Represented by $f(\lambda x + (1-\lambda)y) < \lambda f(x) + (1-\lambda)f(y)$ for all $x \neq y$ and $\lambda \in (0,1)$
• Common convex functions include quadratic functions ($f(x) = x^2$) and exponential functions ($f(x) = e^x$)
• Strictly convex functions have unique global minimums, crucial in optimization problems

Geometric Interpretations: Epigraph and Sublevel Sets

• Epigraph represents the set of points lying on or above the graph of a function
• Defined as $\text{epi}(f) = \{(x,t) \in \mathbb{R}^{n+1} : x \in \text{dom}(f), f(x) \leq t\}$
• Convex functions have convex epigraphs, providing a geometric criterion for convexity
• Sublevel set consists of all points where the function value is less than or equal to a given constant
• Expressed as $S_{\alpha} = \{x \in \text{dom}(f) : f(x) \leq \alpha\}$ for some $\alpha \in \mathbb{R}$
• Convex functions always have convex sublevel sets
• Sublevel sets help visualize the behavior of convex functions and their optimization landscapes

Convex Function Inequalities

Jensen's Inequality and Its Applications

• Jensen's inequality generalizes the notion of convexity to expected values
• States that $f(E[X]) \leq E[f(X)]$ for any convex function $f$ and random variable $X$
• Applies to discrete and continuous probability distributions
• Used in information theory, economics, and probability theory
• Helps derive important inequalities (arithmetic-geometric mean inequality)
• Provides bounds on expectations of nonlinear functions

First-Order and Second-Order Conditions for Convexity

• First-order condition uses the gradient to characterize convexity
• For differentiable functions, $f$ is convex if and only if $f(y) \geq f(x) + \nabla f(x)^T(y-x)$ for all $x, y$ in the domain
• Geometrically interprets as the graph of $f$ lying above its tangent planes
• Second-order condition utilizes the Hessian matrix for twice-differentiable functions
• States that $f$ is convex if and only if its Hessian matrix is positive semidefinite
• Mathematically expressed as $\nabla^2 f(x) \succeq 0$ for all $x$ in the domain
• Provides a local characterization of convexity based on the function's curvature

Convex Function Derivatives

Gradient and Its Role in Convex Optimization

• Gradient represents the vector of partial derivatives of a function
• Denoted as $\nabla f(x) = (\frac{\partial f}{\partial x_1}, \ldots, \frac{\partial f}{\partial x_n})$
• Points in the direction of steepest ascent of the function
• For convex functions, the gradient provides a global lower bound on the function
• Utilized in gradient descent algorithms for finding minima of convex functions
• Gradient of a strictly convex function is one-to-one, ensuring unique solutions in optimization problems

Hessian Matrix and Positive Semidefiniteness

• Hessian matrix contains all second-order partial derivatives of a function
• Represented as $H_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j}$
• Symmetric for twice-continuously differentiable functions
• Positive semidefinite Hessian indicates convexity of the function
• A matrix $A$ is positive semidefinite if $x^TAx \geq 0$ for all non-zero vectors $x$
• Eigenvalues of a positive semidefinite matrix are non-negative
• Positive definiteness (all eigenvalues strictly positive) implies strict convexity
• Used in optimization algorithms to determine the local curvature of functions