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?

Improve this question
$\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$
    – Brian Borchers
    Oct 12 '19 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
    Oct 13 '19 at 9:04
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.

Improve this answer
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$

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.