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

()

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