Convex FunctionsConvex Optimization > Convex sets | Convex functions | Convex optimization problems | Algorithms | DCP
DefinitionDomain of a functionThe domain of a function is the set over which is well-defined, in other words: Here are some examples:
Definition of convexityA function is convex if
Note that the convexity of the domain is required. For example, the function defined as is not convex, although is it linear (hence, convex) on its domain . We say that a function is concave if is convex. Examples:
Alternate characterizations of convexityLet . The following are equivalent conditions for to be convex. EpigraphA function is convex if and only if its epigraph is convex. Example: We can us this result to prove for example, that the largest eigenvalue function , which to a given symmetric matrix associates its largest eigenvalue, is convex, since the condition is equivalent to the condition that . First-order conditionIf is differentiable (that is, is open and the gradient exists everywhere on the domain), then is convex if and only if The geometric interpretation is that the graph of is bounded below everywhere by anyone of its tangents. Restriction to a lineThe function is convex if and only if its restriction to /any} line is convex, meaning that for every , and , the function is convex. Examples: Second-order conditionIf is twice differentiable, then it is convex if and only if its Hessian is positive semi-definite everywhere on the domain of . This is perhaps the most commonly known characterization of convexity. Examples: Operations that preserve convexityComposition with an affine functionThe composition with an affine function preserves convexity: if , and is convex, then the function with values is convex. Point-wise maximumThe pointwise maximum of a family of convex functions is convex: if is a family of convex functions index by , then the function is convex. This is one of the most powerful ways to prove convexity. Examples:
This function is convex, as the maximum of convex (in fact, linear) functions (indexed by the vector ). The dual norm earns its name, as it satisfies the properties of a norm.
Here, each function (indexed by ) is convex, since it is the composition of the Euclidean norm (a convex function) with an affine function . Nonnegative weighted sumThe nonnegative weighted sum of convex functions is convex. Example: Negative entropy function. Partial minimumIf is a convex function in , then the function is convex. (Note that joint convexity in is essential.) Example:
Composition with monotone convex functionsThe composition with another function does not always preserve convexity. However, if , with convex and increasing, then is convex. Indeed, the condition is equivalent to the existence of such that The condition above defines a convex set in the space of -variables. The epigraph of is thus the projection of that convex set on the space of -variables, hence it is convex. Example: proving convexity via monotonicity. More generally, if the functions , are convex and is convex and non-decreasing in each argument, with , then is convex. For example, if 's are convex, then also is. |