Notes - Continuous Mathematics HT23, Convexity
Flashcards
What does mean for a set $D \subseteq \mathbb{R}^n$ to be convex?
What does it mean for a function $f : D \to \mathbb{R}$ to be convex where $D$ is also convex?
What’s the intuitive definition of a function being convex, in terms of secant lines?
Any secant line between two points on the surface is above the surface.
A function $f : D \to \mathbb{R}$ is convex on a convex domain $D$ if
\[\forall \pmb x_1, \pmb x_2 \in D, \forall \alpha \in (0, 1): f((1 - \alpha)\pmb x_1 + \alpha \pmb x_2) \le (1-\alpha)f(\pmb x_1) + \alpha f(\pmb x_2)\]
Can you turn this into the definition of being strictly concave?
A function $f : D \to \mathbb{R}$ is convex if
\[\forall \pmb x_1, \pmb x_2 \in D, \forall \alpha \in (0, 1): f((1 - \alpha)\pmb x_1 + \alpha \pmb x_2) \le (1-\alpha)f(\pmb x_1) + \alpha f(\pmb x_2)\]
Why is it necessary that $D$ is a convex set?
Otherwise $(1 - \alpha)\pmb x _ 1 + \alpha \pmb x _ 2$ might not be defined.
When, in terms of the Hessian, is some $f : D \to \mathbb R$ convex?
(i.e. positive semidefinite)
What functions are both convex and concave?
Linear functions
When is $f(\pmb x) = \pmb x^\intercal \mathbf A \pmb x$ convex or concave?
- Convex: $\mathbf A$ positive semidefinite.
- Concave: $\mathbf A$ negative semidefinite
If $f$ and $g$ are convex, is $f \times g$?
No.
Suppose $f$ and $g$ are functions. What rules let you remember if $f \circ g$ is convex/concave depending on the convexity of $f$ and $g$?
- $f$ convex increasing of convex is convex
- $f$ convex decreasing of concave is convex
- $f$ concave increasing of concave is concave
- $f$ concave decreasing of convex is concave.
If $g : \mathbb R \to \mathbb R$ is a strictly increasing function, what trick can you use to find
\[\text{argmin } f(x)\]
?
If you’re optimising against some objective function $f$, which is a tricky expression involving a large product, what might it be easier to optimise instead?
If $g : \mathbb{R} \to \mathbb{R}$ is a 1-1 function, what trick can you use to find
\[\text{argmin } f(x)\]
?
How could you solve
\[\min f(x, y) \text{ s.t. } x + y + 1 = 0\]
without resorting to the method of Lagrange multipliers?
Notice that the condition would imply $y = -1 - x$ and then solve
\[\min f(x, -1 - x)\]How could you solve
\[\min f(x, y) \text{ s.t. } x^2 + y^2 = 1\]
without resorting to the method of Lagrange multipliers?
Reparameterize
\[\min f(\cos \theta, \sin \theta)\]