%matplotlib inline
import numpy as np;
import matplotlib
import matplotlib.pyplot as plt
np.random.seed(1337)
kwargs = {'linewidth' : 3.5}
font = {'weight' : 'normal', 'size' : 24}
matplotlib.rc('font', **font)
def error_plot(ys, yscale='log'):
plt.figure(figsize=(8, 8))
plt.xlabel('Step')
plt.ylabel('Error')
plt.yscale(yscale)
plt.plot(range(len(ys)), ys, **kwargs)
$\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 13, 2018
A company has $m$ different resources which can be used to manufacture $n$ different products.
If it helps, assume the amount of each resource available is measured in kilograms, and our profit is measured in euros €. Maybe we're manufacturing rope, so the amount of each product is measured in meters.
Using our rope factory example,
The dual program has the constraint $y^T A \geq c$, which has terms like $y_i a_{ij} \geq c_j$. The units are
$$ \bigg( ? \bigg) \times \bigg( \frac{kg}{m} \bigg) \geq \bigg( \frac{€}{m} \bigg) $$We decided that $y_i$ has units $(€/kg)$, and $y^T r$ has units $(€)$.
Lemma. (Farkas) Let $A \in \R^{m \times n}$ and $b \in \R^m$. Then exactly one of the following two statements is true:
Prove that strong duality holds using the Farkas Lemma (v2). That is, the following two are equal:
$$ \begin{align} \max_{x \in \R^n} &\quad c^T x & \text{such that} &\quad A x \leq b, \quad x \geq 0 \\ = \min_{y \in \R^m} &\quad y^T b & \text{such that} &\quad y^T A \geq c^T, \quad y \geq 0 \\ \end{align} $$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.