../
CVXOPT HW4
$\newcommand{\R}{\mathbb{R}}$
1) Consider the Support Vector Machine primal optimization problem from class. Here we have data $x_i \in \R^d$ with corresponding labels $y_i \in \{-1, 1\}$, for $i = 1,\ldots, N$. The goal is to find a weight vector $w\in\R^d$ and $b\in\R$. The $\zeta_i$ are slack variables.
$$ \begin{align*} \text{minimize}\quad&\frac{1}{2}\|w\|_2^2 + C \sum_i \zeta_i\\ \text{subject to}\quad&y_i(w^Tx_i + b) \ge 1 - \zeta_i\quad i=1, \ldots, N\\ &\zeta \succeq 0 \end{align*} $$Derive the dual optimization problem
Converting this to standard optimization problem form
$$ \begin{align*} \text{minimize}\quad & \frac{1}{2}\|w\|_2^2 + C \sum_i \zeta_i\\ \text{subject to}\quad & 1 - y_i (w^T x_i - b) - \zeta_i \le 0\quad i=1, \ldots, N\\ & -\zeta \preceq 0 \end{align*} $$We have a function in $w, \zeta$ that we want to minimize with $2N$ constraints.
Lagrangian is
$$ \begin{align*} \mathcal{L}(w, b, \lambda, \zeta) &= \frac{1}{2}\|w\|_2^2 + C \sum_i^N \zeta_i + \sum_{i}^N \lambda_i (1 - y_i (w^T x_i - b) - \zeta_i) - \sum_i^N \lambda_{2i}\zeta_i \\ &= \frac{1}{2}\|w\|_2^2 + C \sum_i^N \zeta_i + \sum_{i}^N( \lambda_i - \lambda_i y_i (w^T x_i - b) - \lambda_i\zeta_i) - \sum_i^N \lambda_{2i}\zeta_i\\ &= \frac{1}{2}\|w\|_2^2 + C \sum_i^N \zeta_i + \sum_{i}^N( \lambda_i - \lambda_i y_i w^T x_i +\lambda_i y_i b - \lambda_i\zeta_i) - \sum_i^N \lambda_{2i}\zeta_i\\ &= \frac{1}{2}\|w\|_2^2 + C \sum_i^N \zeta_i + \sum_{i}^N\lambda_i -\sum_{i}^N \lambda_i y_i w^T x_i + \sum_{i}^N \lambda_i y_i b -\sum_{i}^N \lambda_i\zeta_i - \sum_i^N \lambda_{2i}\zeta_i\\ &= \frac{1}{2}\|w\|_2^2 + C \sum_i^N \zeta_i + \sum_{i}^N\lambda_i -\sum_{i}^N \lambda_i y_i w^T x_i + b\sum_{i}^N \lambda_i y_i -\sum_{i}^N \lambda_i\zeta_i - \sum_i^N \lambda_{2i}\zeta_i\\ &= \frac{1}{2}\|w\|_2^2 + C \sum_i^N \zeta_i + \sum_{i}^N\lambda_i -\sum_{i}^N \lambda_i y_i w^T x_i + b\sum_{i}^N \lambda_i y_i -\sum_{i}^N (\lambda_i -\lambda_{2i})\zeta_i\\ \end{align*} $$TODO(dbk): Differentiate w.r.t w, b, $\zeta$