convex functions
(6 hours to learn)
Summary
Intuitively, convex functions are bowl-shaped. They are significant in optimization, because it is often possible to efficiently find the global optimum of a convex function.
Context
This concept has the prerequisites:
- convex sets (The domain of a convex function must be a convex set.)
- vectors (Convex functions are defined in terms of vectors.)
- linear approximation (The first-order condition for convexity is that the linear approximation lie below the function.)
- gradient (The first-order condition for convexity is that the linear approximation lie below the function.)
- higher-order partial derivatives (The second-order condition for convexity is that the second-derivative matrix be positive semidefinite.)
- positive definite matrices (The second-order condition for convexity is that the second-derivative matrix be positive semidefinite.)
Goals
- Know the definition of a convex function (in multiple dimensions)
- Know and be able to apply alternative characterizations of convex functions
- first-order condition (linear approximation lies below the function)
- second-order condition (second derivative matrix is positive semidefinite)
- Know some examples of convex functions
- Why can the value of the function outside its domain be taken to be infinity?
Core resources (read/watch one of the following)
-Free-
→ Convex Optimization
A graduate-level textbook on convex optimization.
Location:
Section 3.1, "Basic properties and examples" of Chapter 3, "Convex functions," pages 67-78
Other notes:
- Some of the examples may use concepts you haven't seen. If so, just try to get the gist.
See also
- Convex functions are part of the definition of convex optimization problems , a broad framework for optimization where the global optimum can often be found.
- Some important examples of convex functions:
- vector norms
- utility functions are typically assumed to be concave
- regularization penalties in machine learning are often convex
- likelihood functions for exponential families