Convexity and Concavity
- Convex functions and sets are fundamental concepts in optimization.
- Convexity and concavity can be determined by the signs of the zeroth, first, and second derivatives.
- The sum of two convex functions is convex.
- Pre-composing a convex function with an affine function preserves convexity.
- The point-wise maximum of a set of convex functions is convex.
- A piece-wise linear function defined as the maximum of a set of affine functions is convex.
- The sum of the k largest entries of a vector is a convex function.
- The supremum of a family of convex functions is convex.
- The support function of a set is convex.
- The farthest distance to a set is a convex function.
Composition Rule for Convexity
- The composition rule states that a function f(G(x)) is convex if the outer function H is convex and the inner function G satisfies certain conditions.
- There are three cases for the inner function G:
- H is increasing in all arguments and G is convex.
- H is decreasing in all arguments and G is concave.
- No conditions on monotonicity of H, but all arguments of G are affine.
- The composition rule can be used to prove that the sum of convex functions is convex and the maximum of convex functions is convex.
- The composition rule can be applied to more complex functions, such as the log-sum-exp of convex functions.
- The converse of the composition rule is false, meaning that a function can be convex even if it does not satisfy the composition rule.
Other Properties of Convex Functions
- The maximum of two convex functions is convex, and the minimum of two concave functions is concave.
- Partial minimization preserves convexity, meaning that if f(x, y) is jointly convex in x and y and we minimize over y over a convex set, then the resulting function g(x) is convex.
- Joint convexity is stronger than convexity in each variable separately.
- The perspective of a function is obtained by dividing each entry of the function by a positive scalar. If a function is convex, its perspective is also convex.
- The conjugate function of a function f(x) is defined as the supremum of the inner product of y and x minus f(x) over all x in the domain of f.
- The conjugate of a non-convex function is convex.
- The conjugate of a conjugate function is the original function.
- The convex envelope of a function is the largest convex function that fits under it.
Quasi-Convex Functions
- Quasi-convex functions are functions whose sublevel sets are all convex.
- Quasi-convex functions are also known as unimodal functions.
- Quasi-convex functions are not necessarily convex or concave but have properties that make them useful in optimization problems.
- Examples of quasi-convex functions include the square root, absolute value, and ceiling function.
Integer-Valued Convex Functions
- Integer-valued convex functions are functions that take only integer values and are convex.
- Examples of integer-valued convex functions include the constant function, the negative direct Delta function, and the step function.
- The number of non-zero elements in a vector is an integer-valued convex function.
- Convex integer-valued functions are rare and mostly limited to constant functions and a few specific examples.
Applications
- The internal rate of return (IRR) of a cash flow is an example of a practical application of integer-valued convex functions.
- The present value of a cash flow is the sum of all future cash payments discounted at a given interest rate.
- The internal rate of return (IRR) is the interest rate at which the net present value of a cash flow is zero.
- The IRR is quasi-concave, which means that the super level sets of the IRR are convex.
- For quasi-convex functions, Jensen's inequality is modified such that the function value of a mixture is less than or equal to the maximum of the function values of the individual components.
