how to show that the quadratic function strongly convex iff A positive definite and parameter min eigenvalue?

680 Views Asked by At

I have the following question:

Show that the quadratic function $$f(x) = x^T Ax+2b^T x+c$$ with $$A = A^T ∈ R^{n×n}, b ∈ R^n, c ∈ R$$ is strongly convex if and only if $$A ≻ 0$$, and in that case the strong convexity parameter is $$2λ_{min}(A)$$.

I know that strong convexity means $$f(x) - \frac{\sigma}{2} \|x \|^2$$ is also convex.

1

There are 1 best solutions below

0
On BEST ANSWER

A differentiable function $f$ is $\sigma$-strongly convex if and only if

$$ (\nabla f(x) - \nabla f(y))^{\top}(x - y) \geq \sigma \lVert x - y \rVert^2. $$

In your case, $\nabla f(x) = 2Ax + 2b$. Replacing in the above inequality, you obtain

$$ (\nabla f(x) - \nabla f(y)) = 2A(x - y) \Rightarrow (\nabla f(x) - \nabla f(y))^{\top}(x - y) = 2(x - y)^{\top} A (x - y). $$

The only way for this to be strictly positive for all $x, y$ (with $x \neq y$) is if $A \succ 0$. In that case, the modulus of strong convexity follows easily from the definition of the minimum eigenvalue.