2.2 Convex functions and their characteristics

Convex functions are a cornerstone of optimization theory. They have unique properties that make them ideal for finding global minima. Understanding these functions is crucial for solving complex problems in various fields, from economics to machine learning.

This section dives into the definition, types, and identification methods of convex functions. We'll explore their key properties, mathematical formulations, and practical applications. By mastering these concepts, you'll be well-equipped to tackle optimization challenges in your future studies and career.

Convex Functions

Definition and Key Properties

Top images from around the web for Definition and Key Properties

• 

  Derivatives and the Shape of a Graph · Calculus View original

  Is this image relevant?

• 

  Jensen's inequality - Wikipedia View original

  Is this image relevant?

• 

  Jensen's inequality - Wikipedia View original

  Is this image relevant?

• 

  Derivatives and the Shape of a Graph · Calculus View original

  Is this image relevant?

• 

  Jensen's inequality - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition and Key Properties

• 

  Derivatives and the Shape of a Graph · Calculus View original

  Is this image relevant?

• 

  Jensen's inequality - Wikipedia View original

  Is this image relevant?

• 

  Jensen's inequality - Wikipedia View original

  Is this image relevant?

• 

  Derivatives and the Shape of a Graph · Calculus View original

  Is this image relevant?

• 

  Jensen's inequality - Wikipedia View original

  Is this image relevant?

1 of 3

• Convex function value at midpoint of interval does not exceed arithmetic mean of values at interval ends
• Epigraph of convex function forms convex set
• Convex functions have unique global minimum (if it exists) which is also local minimum
• Jensen's inequality states function of expected value ≤ expected value of function for convex functions
• Closed under addition, nonnegative scalar multiplication, and pointwise maximum operations
• Composition with affine function preserves convexity
• Continuous on interior of domain with one-sided derivatives at boundary points

Mathematical Formulation and Examples

• Satisfy inequality $f(tx + (1-t)y) ≤ tf(x) + (1-t)f(y)$ for all x, y in domain and t in [0,1]
• Common convex functions
  • Exponential function: $f(x) = e^x$
  • Logarithmic function: $f(x) = -\log(x)$ for x > 0
  • Quadratic function: $f(x) = ax^2 + bx + c$ where a > 0
• Applications in optimization
  • Minimize convex objective function subject to convex constraints (linear programming)
  • Portfolio optimization using convex risk measures

Convexity Types

Strict Convexity

• Satisfy strict inequality $f(tx + (1-t)y) < tf(x) + (1-t)f(y)$ for all x ≠ y and t in (0,1)
• At most one minimum point
• Examples
  • Strictly convex quadratic function: $f(x) = x^2$
  • Negative entropy: $f(x) = x\log(x)$ for x > 0

Strong Convexity

• Satisfy inequality $f(tx + (1-t)y) ≤ tf(x) + (1-t)f(y) - (m/2)t(1-t)||x-y||^2$ for some m > 0
• Always have unique global minimum
• Second derivative bounded below by positive constant
• Examples
  • Strongly convex quadratic function: $f(x) = ax^2 + bx + c$ where a > m > 0
  • Logarithmic barrier function: $f(x) = -\log(x) + mx^2$ for x > 0 and m > 0

Comparison and Implications

• Strongly convex functions always strictly convex, but not vice versa
• Distinction crucial in optimization algorithms
  • Affects convergence rates (faster for strongly convex functions)
  • Influences solution uniqueness (guaranteed for strongly convex functions)
• Examples of functions in each category
  • Convex but not strictly convex: $f(x) = |x|$
  • Strictly convex but not strongly convex: $f(x) = e^x$
  • Strongly convex: $f(x) = x^2 + 1$

Identifying Convexity

First-Order Condition

• Differentiable function f is convex if and only if $f(y) ≥ f(x) + \nabla f(x)^T(y-x)$ for all x, y in domain
• Geometric interpretation
  • Tangent line at any point lies below graph of function
• Examples
  • Exponential function: $f(x) = e^x$ satisfies first-order condition
  • Linear function: $f(x) = ax + b$ satisfies condition with equality

Second-Order Condition

• Twice-differentiable function f is convex if and only if Hessian matrix is positive semidefinite for all points in domain
• For univariate functions, simplifies to $f''(x) ≥ 0$ for all x in domain
• Strict convexity requires positive definite Hessian matrix
• Examples
  • Quadratic function: $f(x) = ax^2 + bx + c$ has constant second derivative 2a
  • Logarithmic function: $f(x) = \log(x)$ has second derivative $1/x^2 > 0$ for x > 0

Applications and Extensions

• Essential in identifying convex optimization problems
• Can be used to prove convexity of common functions (exponential, logarithmic, power functions)
• Extended to analyze convexity of vector-valued functions and functionals
• Examples
  • Proving convexity of log-sum-exp function: $f(x) = \log(\sum_{i=1}^n e^{x_i})$
  • Analyzing convexity of norm functions in vector spaces

Convex Sets and Functions

Epigraphs

• Epigraph of function f defined as $epi(f) = \{(x,t) | x \text{ in domain of } f, t ≥ f(x)\}$
• Function is convex if and only if its epigraph is convex set
• Provides geometric interpretation of function convexity
• Examples
  • Epigraph of linear function is half-space
  • Epigraph of quadratic function is paraboloid

Sublevel Sets

• Sublevel set of function f defined as $\{x | f(x) ≤ \alpha\}$ for any real number α
• Sublevel sets of convex function are convex sets
• Intersection of convex sublevel sets of multiple convex functions is convex
• Applications in constraint formulation for convex optimization problems
• Examples
  • Sublevel sets of norm functions are balls in respective norm
  • Sublevel sets of linear functions are half-spaces

Relationships and Properties

• Projection of epigraph of convex function onto domain is entire domain (convex set)
• Level sets of strictly convex functions are empty or single points
• Allows application of convex analysis techniques in geometric and functional contexts
• Examples
  • Using sublevel set convexity to prove convexity of solution set in linear programming
  • Analyzing convergence of optimization algorithms using properties of epigraphs and sublevel sets