2
$\begingroup$

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.

  1. 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.

  2. If $A$ is not symmetric and PSD, then does $f(x)$ still have a global minimum?

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$ – A.Γ. Sep 4 '17 at 5:38
  • $\begingroup$ @A.Γ.do you mean we can have a convex function with only $A$ being psd/pd and $A$ not being symmetric? $\endgroup$ – rotating_image Sep 4 '17 at 5:47
  • 2
    $\begingroup$ 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. $\endgroup$ – A.Γ. Sep 4 '17 at 6:04
2
$\begingroup$
  1. If $A$ is not symmetric, $x^TAx = \frac12 x^T (A + A^T)x$, so the problem is equivalent.

  2. For convex functions, a local minimum is a global minimum, so yes, there still exists a global minimum.

$\endgroup$
3
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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