1. Quadratic objective
Study $f(x)=\frac12x^TQx-b^Tx$ with a symmetric $2\times2$ matrix $Q$.
Matrix $Q$
Vector $b$
2. Gradient descent path
Contours show the quadratic objective. Dots show gradient descent iterates.
3. Least squares and ridge regression
Fit a line $y=\beta_0+\beta_1t$ to three data points.
4. Line fit visualization
5. Equality constrained quadratic problem
Minimize $\frac12\|x-y\|^2$ subject to $x_1+x_2=d$. This is projection onto a line.
6. Projection geometry
7. Independent-study practice tasks with answers
Task A. For $Q=\begin{bmatrix}4&1\\1&3\end{bmatrix}$ and $b=(1,2)^T$, find the minimizer of $\frac12x^TQx-b^Tx$.
Answer: Solve $Qx=b$. The solution is $x=(1/11,7/11)^T$.
Answer: Solve $Qx=b$. The solution is $x=(1/11,7/11)^T$.
Task B. Why does $\lambda>0$ make ridge regression stable?
Answer: Because $A^TA+\lambda I$ is positive definite: $x^T(A^TA+\lambda I)x=\|Ax\|^2+\lambda\|x\|^2>0$ for $x\neq0$.
Answer: Because $A^TA+\lambda I$ is positive definite: $x^T(A^TA+\lambda I)x=\|Ax\|^2+\lambda\|x\|^2>0$ for $x\neq0$.
Task C. What condition on $\alpha$ makes gradient descent converge for a positive definite quadratic?
Answer: $0<\alpha<2/\lambda_{\max}(Q)$.
Answer: $0<\alpha<2/\lambda_{\max}(Q)$.
Task D. Write the KKT system for minimizing $\frac12\|x-y\|^2$ subject to $Cx=d$.
Answer: $\begin{bmatrix}I&C^T\\C&0\end{bmatrix}\begin{bmatrix}x\\\lambda\end{bmatrix}=\begin{bmatrix}y\\d\end{bmatrix}$.
Answer: $\begin{bmatrix}I&C^T\\C&0\end{bmatrix}\begin{bmatrix}x\\\lambda\end{bmatrix}=\begin{bmatrix}y\\d\end{bmatrix}$.