For the purpose of drawing, the example cvx code for the regularized least-squares solves the following problem
\begin{align}\text{minimize}\quad &\left\|Ax – b \right\|_2^2;\\ \text{subject to}\; &x{'}x = \alpha\end{align}
It is claimed that the following is a dual
\begin{align}\text{maximize}\quad &-t-u\alpha;\\\text{subject to}\;&\begin{bmatrix}uI & 0 \\ 0 & t\end{bmatrix} + \begin{bmatrix}A & b\end{bmatrix}'\begin{bmatrix}A & b\end{bmatrix} \succeq 0 \end{align}
I don't see how this is the case
The Lagrange function is
$L(u,x) = \begin{pmatrix}
x \\
-1
\end{pmatrix}^T \left(\begin{pmatrix}
uI_n & 0\\
0 & 0
\end{pmatrix} + \begin{pmatrix}
A^T\\
b^T
\end{pmatrix} \begin{pmatrix}
A & b
\end{pmatrix}\right) \begin{pmatrix}
x\\
-1
\end{pmatrix}-u\alpha$
and one can introduce a slack variable $t$, but how does semi definite positivity pops out in the dual ?
Best Answer
The lagrange function that you wrote is slightly incorrect. You have to exchange $b^T$ and $b$. To obtain the dual that you are looking for:
\begin{align} \max_{u\in \mathbb R}\min_{x\in \mathbb R^n} \left\|Ax-b\right\|^2 + u\left(\alpha - \left\|x\right\|^2\right)&=\max_{u\in \mathbb R} \left(\alpha u + \min_{x\in \mathbb R^n} \left\|Ax-b\right\|^2 - u\left\|x\right\|^2\right)\\ \end{align}
Where the last one is obtained by changing the variables $u$, $t$ by $-u$, $-t$.
Since
Now \begin{align} \min_{x\in \mathbb R^n} \left\|Ax-b\right\|^2 - u\left\|x\right\|^2 &= \max_{t\in \mathbb R}\, t; \; \forall x\in\mathbb R^n, \left\|Ax-b\right\|^2 - u\left\|x\right\|^2 \ge t\\ &= \max_{t\in \mathbb R}\, t; \; \forall x\in\mathbb R^n, \left\|Ax-b\right\|^2 - u\left\|x\right\|^2 - t \ge 0\\ &= \max_{t\in \mathbb R}\, t; \; \forall x\in\mathbb R^n, \begin{bmatrix}x\\ -1\end{bmatrix}^T\left(\begin{bmatrix}\\ A & b\\ &\end{bmatrix}^T\begin{bmatrix}\\ A & b\\ &\end{bmatrix}-\begin{bmatrix}uI & 0\\ 0 & t\end{bmatrix}\right)\begin{bmatrix}x\\ -1\end{bmatrix} \ge 0\\ &= \max_{t\in \mathbb R} t;\; \forall x\in\mathbb R^n,\; \forall y\in\mathbb R,\;\begin{bmatrix}-yx\\ y\end{bmatrix}^T\left(\begin{bmatrix}\\ A & b\\ &\end{bmatrix}^T\begin{bmatrix}\\ A & b\\ &\end{bmatrix}-\begin{bmatrix}uI & 0\\ 0 & t\end{bmatrix}\right)\begin{bmatrix}-yx\\ y\end{bmatrix} \ge 0\\ &= \max_{t\in \mathbb R} t;\; \forall z\in \mathbb R^{n+1},\; z^T\left(\begin{bmatrix}\\ A & b\\ &\end{bmatrix}^T\begin{bmatrix}\\ A & b\\ &\end{bmatrix}-\begin{bmatrix}uI & 0\\ 0 & t\end{bmatrix}\right)z \ge 0\\ &= \max_{t\in \mathbb R} t;\; \begin{bmatrix}\\ A & b\\ &\end{bmatrix}^T\begin{bmatrix}\\ A & b\\ &\end{bmatrix}-\begin{bmatrix}uI & 0\\ 0 & t\end{bmatrix} \succeq 0 \end{align}
So
\begin{align} \max_{u\in \mathbb R}\min_{x\in \mathbb R^n} \left\|Ax-b\right\|^2 + u\left(\alpha - \left\|x\right\|^2\right)&=\max_{u\in \mathbb R,\, t\in \mathbb R} \alpha u + t;\; \begin{bmatrix}\\ A & b\\ &\end{bmatrix}^T\begin{bmatrix}\\ A & b\\ &\end{bmatrix}-\begin{bmatrix}uI & 0\\ 0 & t\end{bmatrix} \succeq 0\\ &=\max_{u\in \mathbb R,\, t\in \mathbb R} -\alpha u - t;\; \begin{bmatrix}\\ A & b\\ &\end{bmatrix}^T\begin{bmatrix}\\ A & b\\ &\end{bmatrix}+\begin{bmatrix}uI & 0\\ 0 & t\end{bmatrix} \succeq 0\\ \end{align}