Convex Functions

Topics: Convex Optimization

Definition

A function $f$ is convex if and only if:

• its domain $\text{dom} \, f$ is a convex set
• $f$ lies below the line segment connecting any two of its points

That is

$$f(\alpha x + (1-\alpha)y) \leq \alpha f(x) + (1-\alpha) f(y)$$

First-Order Conditions

If $f$ is differentiable, then $f$ is convex if and only if its domain $\text{dom} \, f$ is a convex set and

$$f(x) + \nabla f(x)^{\top} (y-x) \leq f(y)$$

holds for all $x, y \in \text{dom} f$.

This condition also constitutes a useful property for algorithm design with convex functions: a differentiable convex function is lower-bounded by its local first-order approximation.

Second-Order Conditions

If $f$ is twice-differentiable, then $f$ is convex if and only if its domain $\text{dom} \, f$ is a convex set and its Hessian is positive semidefinite

$$\nabla^2 f(x) \succeq 0 \qquad \forall x \in \text{dom } f$$

Operations Preserving Convexity

• Positive scaling
• Sum
• Composition with affine mapping: $(f \circ g)(x) = f(Ax+b)$
• Special compositions: $f(x) = h(g(x))$
  • $g$ convex, $h$ non-decreasing & convex
  • $g$ concave, $h$ non-increasing & convex
• Pointwise maximum: $F(x) = \max (f_1(x), f_2(x), \, \dots \,, f_n(x))$
• Pointwise supremum: $\underset{a \in \mathcal{A}}{sup} \; f(x,a)$

References

1. S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge: Cambridge University Press, 2004.
2. Convex Optimization for Trajectory Generation - A Tutorial on Generating Dynamically Feasible Trajectories Reliably and Efficiently