# Convexity of a QP

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?

• Is your matrix $Q$ large and sparse? large and dense? small? What kind of tolerance on positive definiteness does your QP solver have? – Brian Borchers Oct 12 '19 at 22:48
• @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). – Josh Allen Oct 13 '19 at 9:04

## 2 Answers

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.

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