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.

This question is asked here.


1 Answer 1


Let $$ \begin{array}{lrl} p^\star = &\min& l(x)-1 \\ &\text{s.t.}& a+b^Tx \leq 0. \end{array} $$ Assumption C1 tells us that this is a convex optimization problem, and existence of a Slater point, $x_0$, satisfying $a + b^T x_0 < 0$, tells that this convex optimization problem satisfies strong duality. That is, $$ \max_{\tau \geq 0} \min_x L(x,\tau) = p^\star. $$

where $L(x,\tau) = l(x)-1 + \tau (a+b^Tx)$ is the Lagrange function. By assumption C2, telling us that $p^\star \geq 0$, we thus have that the optimal dual multiplier, $\tau^\star \geq 0$, satisfies $$ \min_x L(x,\tau^\star) \geq 0 $$ and thus we conclude $L(x,\tau^\star) \geq 0$ for all $x \in \mathbb{R}^n$, which is equivalent to C3.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.