We have the following two conditions:
$C1.$ $l(x) \geq 0$ for all $x\in \mathbb{R}^n$,
$C2.$ $l(x) \geq 1$ for all $x\in \mathbb{R}^n$ such that $a+b^Tx \leq 0.$
Here $l(x) = \begin{bmatrix} x^T 1 \end{bmatrix} M \begin{bmatrix} x \\ 1 \end{bmatrix}.$
We have to show that $C2.$ is equivalent to
$C3.$: there exists $\tau \geq 0$ such that for every $x$, $l(x) \geq 1-2\tau (a+b^Tx). $
Here is what I have tried:
$C1.$ is equivalent to the fact that $M \succcurlyeq 0$.
If $C3.$ holds then, under $a+b^Tx \leq 0$, $l(x) \geq 1-2\tau (a+b^Tx) \geq 1.$ Hence, $C2.$ holds.
The following exact statement from paper concludes that $C2.$ gives $C3.$
With $C1.$ in force, an application of the classical strong duality result for convex programs under the Slater assumption shows that the above condition is sufficient, provided there exists an $x_0$ such that $a+b^Tx_0 <0.$
I am having trouble here. I tried writing a convex problem $$ \min_{x} l(x)-1 \\ \text{s.t.} a+b^Tx \leq 0. $$ So we get its Lagrange function as $L(x,\tau) = l(x)-1 + \tau (a+b^Tx) $. A KKT point will satisfy $C3.$, but I am unable to show it for every $x$. Moreover I am not using $C1. $ but the statement takes it into account. Any ideas will be greatly appreciated.
This question is asked here.