- #1
Zerox5f3759df
Homework Statement
Reformulate the noisy linear regression ## y = X \beta + \epsilon## where ## \epsilon ## is the error as a quadratic program, a second order cone program, and a semidefinite program that solves for ## \beta ##. The purpose of this is to use a solver to study the qualitative differences in runtime, etc... under the different formulations.
## \beta \in R^{p} ##
## X \in R^{n \times p} ##
All variables are sampled from appropriate Gaussian distributions to ensure the programs and needed operations are well defined.
Homework Equations
We are given the hint to prove that the quadratic problem
\begin{equation*}
\begin{aligned}
& \underset{\beta \in R^p}{\text{minimize}}
& & ||X\beta - y||^2
\end{aligned}
\end{equation*}
is equivalent to to the following SDP.
\begin{equation*}
\begin{aligned}
& \underset{\beta \in R^p, B\in S^p}{\text{minimize}}
& & \langle
\begin{bmatrix}
y^Ty & -y^TX \\
-X^Ty & X^TX \\
\end{bmatrix}
,
\begin{bmatrix}
1 & \beta^T \\
\beta & B \\
\end{bmatrix}
\rangle
& \text{subject to}
& &
\begin{bmatrix}
1 & \beta^T \\
\beta & B \\
\end{bmatrix}
\succeq 0
\end{aligned}
\end{equation*}
The Attempt at a Solution
I have completed the reformulation of the problem as a quadratic, and second order cone program without issue. However, when I convert the program to a SDP I do not end up with the same form as is given in the hint, nor do my computational solutions agree particularly well with my other solutions.
The process to convert the program I am using is Schur's complement. Expanding out the quadratic ##||X\beta - y||^2## yields ## \beta^TX^TX\beta - 2y^TX\beta + y^Ty ##. I then introduce a variable ## t ##, and let my new objective function be ## t - 2y^TX\beta + y^Ty ##. My constraint is then
##
\begin{bmatrix}
I & X\beta \\
\beta^TX^T & tI \\
\end{bmatrix}
\succeq 0
##
so that by Schur's Complement I have that ## tI - \beta^TX^TX\beta \succeq 0 ## which implies ## tI \succeq \beta^TX^TX\beta ##, which since we are minimizing ## t ##, also minimizes our quadratic term from our original, without having a quadratic constraint.
However, my objective function looks nothing like what was given in the hint, and something seems off about my constraint matrix (specifically the dimensions of the upper right and lower left terms.
Have I missed something obvious? Any suggestions are greatly appreciated.