Stanford EE364A Convex Optimization I Stephen Boyd I 2023 I Lecture 4

14 Mar 2024 (8 months ago)

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.

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.

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 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 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.

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.