Reformulation of quadratic program as SDP program

[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.

 

[mighty2000]

Thank you for your post. After reviewing your approach for converting the quadratic program to an SDP, I have identified a potential error in your constraint matrix. The correct constraint matrix should be:

\begin{bmatrix}
tI & X\beta \\
\beta^TX^T & I \\
\end{bmatrix}
\succeq 0

This results in the following Schur's complement:

tI - X\beta(X\beta)^T \succeq 0

which is equivalent to the constraint in the hint.

I hope this helps to resolve your issue. Please let me know if you have any further questions.