9
$\begingroup$

In quadratic programming (QP), you encounter an objective of the following form:

$$x^TQx + c^Tx$$

and often it's desirable to know if the QP is convex. One method to check for convexity is by determining whether matrix $Q$ is positive semidefinite (PSD). What are some common algorithms that can quickly check whether matrix $Q$ is PSD?

$\endgroup$
2
  • 3
    $\begingroup$ Is your matrix $Q$ large and sparse? large and dense? small? What kind of tolerance on positive definiteness does your QP solver have? $\endgroup$ Commented Oct 12, 2019 at 22:48
  • $\begingroup$ @BrianBorchers I was thinking for general $Q$, but can accept that this may be too broad of a question. As for tolerances and round-off errors, it would be nice for this to be emphasised when outlining the common algorithms used (say Cholesky decomposition(CD)) and how they are handled (perhaps even with alternative approaches to CD). $\endgroup$
    – Josh Allen
    Commented Oct 13, 2019 at 9:04

2 Answers 2

6
$\begingroup$

You can use Singular Value Decomposition or Cholesky Decomposition. I recommend you read this Verification of Positive Definiteness. On page 9 there is an algorithm in MATLAB.

$\endgroup$
4
$\begingroup$

Some quadratic problems are convex while others may not. This is a nice discussion in the QP by Erwin Kalvelagen.

$\endgroup$

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.