$\LaTeX \text{ commands here} \newcommand{\R}{\mathbb{R}} \newcommand{\im}{\text{im}\,} \newcommand{\norm}[1]{||#1||} \newcommand{\inner}[1]{\langle #1 \rangle} \newcommand{\span}{\mathrm{span}} \newcommand{\proj}{\mathrm{proj}} \newcommand{\OPT}{\mathrm{OPT}} $
Georgia Tech, CS 4540
Jake Abernethy & Benjamin Bray
Thursday, September 5, 2019
Let $w$ be an $n$-dim vector. Calculate the first derivatives of the following functions:
Let $w$ be an $n$-dim vector. Calculate the derivatives of the following functions:
Definition: A matrix $M \in \R^{n\times n}$ is positive semidefinite (PSD) if $x^\top M x \geq 0\; \forall x \in \R^n$
Commonly, we work with matrices $M$ that are symmetric (that is, $M = M^\top$). In this case, the following are equivalent:
Show that (3) $\implies$ (1) $\implies$ (2)
The fact that $0 \leq \lambda \| v \|^2$ can only occur if $\lambda \geq 0$.
We often use the notation $M \succcurlyeq 0$ to denote that $M$ is PSD. The notation $M \succcurlyeq N$ is equivalent to $M - N \succcurlyeq 0$, i.e. $M - N$ is PSD.
Let $M \in \R^{n \times n}$ be an arbitrary symmetric matrix. Let $P \in \R$ be any nonsingular matrix. Show that $$M \succcurlyeq 0 \Longleftrightarrow P^\top M P \succcurlyeq 0$$
Show that the set $S_+^n := \{ M \in \R^{n\times n}: M = M^\top, M \succcurlyeq 0 \}$ forms a convex cone.
which is nonnegative since both terms are nonnegative
A function $f : \R^d \to \R$ is convex if, for any $x,y \in \text{dom}(f)$ and any $\theta \in [0,1]$, we have $$f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta) f(y)$$
First-order Condition When $f$ is differentiable, then $f$ is convex if and only if $$f(y) \geq f(x) + \nabla f(x)^\top(y - x) \quad \text{ for any } x,y \in \text{dom}(f)$$
First-order Condition When $f$ is differentiable, then $f$ is convex if and only if $$f(y) \geq f(x) + \nabla f(x)^\top(y - x) \quad \text{ for any } x,y \in \text{dom}(f)$$
Use the first order condition to show that, for any convex and differentiable $f$, we have $$(\nabla f(y) - \nabla f(x))^\top(y - x) \geq 0 \text{ for any } x,y \in \text{dom}(f)$$
Let's apply the first order condition twice, once at $x$ and once at $y$: \begin{eqnarray*} f(y) & \geq & f(x) + \nabla f(x)^\top(y - x) \\ f(x) & \geq & f(y) + \nabla f(y)^\top(x - y). \end{eqnarray*} Add these two inequalities together, and subtract $f(x) + f(y)$ from both sides and you are done!
Second-order Condition When $f$ is twice differentiable, then $f$ is convex if and only if the hessian satisfies $\nabla^2f(x) \succcurlyeq 0$.
Find conditions under which the following function is convex $f(x) = \frac 1 2 x^\top A x$ for a symmetric matrix $A \in \R^{d \times d}$
As we computed earlier in lecture, for $f(x) = \frac 1 2 x^\top A x$, the hessian is $\nabla^2 f(x) = A$. We know that a twice-differentiable function is convex if its hessian is positive semi-definite. Therefore, $f$ is convex if and only if $A$ is positive semi-definite.