Convex relaxation

54 Views Asked by At

I am solving the following problem:

\begin{array}{ll}\min\limits_{{x:\,||x||_2^2\geq 1\\}} x^TAx,\end{array} where $A$ is positive definite.

Since the constraint is not convex ($1-||x||_2^2\leq0$), this problem is not convex. I want to linearize the constraint function.

My attempt: for specific point $x_0$ and $f(x)=1-||x||_2^2$

$L(x_0)=f(x_0)+f'(x_0)(x-x_0)=1-||x_0||_2^2-2x_0^T(x-x_0)=1-||x_0||_2^2-2x_0^Tx+2||x_0||_2^2=1+||x_0||_2^2-2x_0^Tx$

New convex problem:

\begin{array}{ll}\min\limits_{{x:\,1+||x_0||_2^2-2x_0^Tx\leq0\\}} x^TAx,\end{array}

Is it the correct way?