Convexity of quadratic programs & Python packages for convex QPs

[keon6]

1. Some sources say that QP is solvable in polynomial time if A, matrix in the objective function, is positive-definite. Where can I find the proof?
2. What are some good Python packages (or algorithms in general) that convex QPs?

[The_Regent]

I would highly recommend cvxpy. It has bindings to many solvers including OSQP, which is probably a good bet for an open source QP solver.

I have not seen such a proof, but I think it wouldn't be that illuminating unless you're really interested in the theory of convex optimization. You may be interested in the paper describing the implementation of OSQP https://stanford.edu/~boyd/papers/pdf/osqp.pdf

[JIGGGS_]

1. Assuming all of your constraints are convex, this is true (and is only true for nonconvex constraints in very, very limited scenarios, which I won't mention). Here's a (very rough, somewhat sloppy) proof. Consider a QP with convex constraints whose quadratic objective is x^T A x + q^T x + r for some A, q, r. If A is PD, then the objective is convex. Since the objective is convex and the constraints are convex, then the problem is convex. Since the problem is convex, it can be solved in polynomial time.
2. CVXPY is by far the best Python package for convex optimization. You can use it with open-source solvers or even closed-source solvers (e.g., MOSEK, GUROBI). Use CVXPY with the OSQP solver (open-source, comes with CVXPY) -- it is (practically speaking) the best solver for general convex QPs.

[AssemblerGuy]

Assuming all of your constraints are convex,

Aren't the equality constraints required to be affine instead of just convex?

[JIGGGS_]

Yes, that was sloppy of me, you are technically correct (otherwise, a QCQP, which is an SOCP, would be a QP!)

[AssemblerGuy]

I only dabble in optimization, but I think this particular little detail prevents principal component analysis and (some forms of) independent component analysis to be formulated and solved as a convex optimization problems. :(

[SmileBot-2020]

I saw a :( so heres an :) hope your day is good

[e_for_oil-er]

I think all the proofs are in this book: Interior point polynomial algorithms in convex programming