Convexity of quadratic functions

Question

I am new to the field of optimization and keep encountering objective functions of the form

$$f(x) = \frac 12 x^T A x - b^T x + c$$

Just wanted to know the reasoning behind some properties of the function above.

I know if $A$ is symmetric and positive semidefinite (PSD), then $f(x)$ is convex. Can $A$ be PSD and non-symmetric and $f(x)$ still be convex? How is being symmetric related to being convex? For example $$A = \begin{bmatrix} 1 & 1 \\-1 & 2\end{bmatrix}$$ is positive definite (PD) but not symmetric. Is $f(x)$ convex still? Most books list Hessian of the function being PSD to be a sufficient condition for $f$ to be a convex function.
If $A$ is not symmetric and PSD, then does $f(x)$ still have a global minimum?

If $A$ is not symmetric then consider equivalent representation for the quadratic form $x^TAx=0.5x^T(A+A^T)x$ with the symmetric matrix. — A.Γ., Sep 4 '17 at 5:38
@A.Γ.do you mean we can have a convex function with only $A$ being psd/pd and $A$ not being symmetric? — rotating_image, Sep 4 '17 at 5:47
Normally the matrix $A$ is assumed to be symmetric, it is a part of the definition of being sign definite e.g. psd. No need to work with nonsymmetric matrices in context of quadratic forms as you can easily symmetrize it. — A.Γ., Sep 4 '17 at 6:04

Jeremy Upsal · Accepted Answer · 2017-09-04 05:47:13Z

2

If $A$ is not symmetric, $x^TAx = \frac12 x^T (A + A^T)x$, so the problem is equivalent.
For convex functions, a local minimum is a global minimum, so yes, there still exists a global minimum.

answered Sep 4 '17 at 5:47

Jeremy Upsal

1,3036 silver badges22 bronze badges

$\begingroup$ Almost correct. There is no guarantee a global minimum exists without stronger conditions; e.g., $A$ is positive definite. It's possible $f(x)$ is unbounded below if $b^Tv\neq 0$ for any $v$ in the null space of $A$. $\endgroup$ – Michael Grant Sep 4 '17 at 23:52
$\begingroup$ @Michael Grant can you please elaborate on the boundness of this function. For instance if $A$ is both symmetric and positive definite, is it possible for $f(x)$ to be unbounded below? $\endgroup$ – Faroq AL-Tam Jun 27 '18 at 12:47
$\begingroup$ If it is positive definite, then $f(x)$ is definitely bounded. If it is positive semidefinite, then it may be unbounded below, but it depends on whether or not $b$ is in the range of $A$. $\endgroup$ – Michael Grant Jun 27 '18 at 16:17

Add a comment |

1 Answer 1