Quadratic programming in Python (2024)

Quadratic programs are a class of numerical optimization problems withwide-ranging applications, from curve fitting in statistics, support vectormachines in machinelearning, to inverse kinematics in robotics. Theyare the first step beyond linear programming in convexoptimization. We will now see how to solve quadratic programs in Python using anumber of available solvers: CVXOPT, CVXPY, Gurobi, MOSEK, qpOASES andquadprog.

Standard form of quadratic programs

A quadratic program (QP) is written in standard form as:

minimize(1/2)xTPx+qTxsubjecttoGxhAx=b\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}\begin{array}{rl}\mathrm{minimize} & (1/2) x^T P x + q^T x \\\mathrm{subject\ to} & G x \leq h \\ & A x = b\end{array}minimizesubjectto(1/2)xTPx+qTxGxhAx=b

Here x\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}xx is the vector of optimization variables x1,,xn\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}x_1, \ldots,x_nx1,,xn. The matrix P\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}PP and vector q\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}qq are used to define a generalquadratic objective function on these variables, while the matrix-vectorpairs (G,h)\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}(G, h)(G,h) and (A,b)\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}(A, b)(A,b) respectively define inequality andequality constraints. Vector inequalities apply coordinate by coordinate, sothat for instance x0\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}x \geq 0x0 means that every coordinate of the vectorx\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}xx is positive.

This mathematical formulation means that a QP finds the minimum of a quadraticfunction over a linear set:

Quadratic programming in Python (1)

In the 2D illustration above, the level sets of the quadratic function aredrawn as dashed ellipses while the linear set of inequality constraintscorresponds to the blue polygon. (The description of a polygon, or moregenerally a polyhedron, by linear inequality constraints is called thehalfspace representation.)Since the global optimal of the objective function is outside of the polygon,the solution x\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}x^*x of the QP lies on the boundary of this polygon. Theset of linear constraints that are saturated at x\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}x^*x is called theactive set, but that's astory for another post...

Back to the standard form, you will notice that there is no constant term inthe objective function. Indeed, it would have no effect on the result of theoptimization, which is the location of the solution x\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}x^*x. For example,the quadratic expression Axb2\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}\| A x - b \|^2Axb2 of a least squaresoptimization is written in standard form with P=2ATA\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}P = 2 A^T AP=2ATA and q=2ATb\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}q= -2 A^T bq=2ATb (see the example below for a small proof of this).

The standard form also assumes, without loss of generality, that the matrixP\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}PP is symmetric. Any matrix M\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}MM can be decomposed as sum of itssymmetric part M+\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}M^+M+ and antisymmetric part M\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}M^-M, and the latteryields zero in xTMx\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}x^T M^- xxTMx. Note that some solvers (like CVXOPT) assumethat you provide a symmetric cost matrix right away: they won't check this, andwill return wrong results if you don't.

Setting up QP solvers

Two readily-available QP solvers in Python are CVXOPT and quadprog. They can beinstalled by:

$ sudo CVXOPT_BUILD_GLPK=1 pip install cvxopt$ sudo pip install quadprog

CVXOPT uses its own matrix type, and it requires the matrix P\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}PP of theobjective function to be symmetric. To be on the safe side, you can wrap it asfollows:

def cvxopt_solve_qp(P, q, G, h, A=None, b=None): P = .5 * (P + P.T) # make sure P is symmetric args = [cvxopt.matrix(P), cvxopt.matrix(q)] args.extend([cvxopt.matrix(G), cvxopt.matrix(h)]) if A is not None: args.extend([cvxopt.matrix(A), cvxopt.matrix(b)]) sol = cvxopt.solvers.qp(*args) if 'optimal' not in sol['status']: return None return numpy.array(sol['x']).reshape((P.shape[1],))

The quadprog module works directly on NumPy arrays so there is no need for typeconversion. Its matrix representation is equivalent to the standard form butcombines inequalities and equalities in a single matrix-vector pair:

def quadprog_solve_qp(P, q, G, h, A=None, b=None): qp_G = .5 * (P + P.T) # make sure P is symmetric qp_a = -q if A is not None: qp_C = -numpy.vstack([A, G]).T qp_b = -numpy.hstack([b, h]) meq = A.shape[0] else: # no equality constraint qp_C = -G.T qp_b = -h meq = 0 return quadprog.solve_qp(qp_G, qp_a, qp_C, qp_b, meq)[0]

In these two functions we assume that the QP has inequality constraints. Formore general functions that handle all combinations of inequality, equality andbox-inequality constraints lbxub\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}lb \leq x \leq ublbxub, or if you want to try outother solvers, you will find a unified solve_qp function with asolver keyword argument in the qpsolvers library.

Example of a linear least squares problem

For a small example, let us see how to solve:

minimizex1,x2,x3[120832011][x1x2x3][323]2subjectto[121201121][x1x2x3][322]\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}\begin{array}{rl}\underset{x_1, x_2, x_3}{\mathrm{minimize}} & \left\| \left[\begin{array}{ccc}1 & 2 & 0 \\-8 & 3 & 2 \\0 & 1 & 1 \end{array}\right] \left[\begin{array}{c} x_1 \\ x_2 \\x_3\end{array}\right] - \left[\begin{array}{c} 3 \\ 2 \\3\end{array}\right] \right\|^2 \\\mathrm{subject\ to} & \left[\begin{array}{ccc}1 & 2 & 1 \\2 & 0 & 1 \\-1 & 2 & -1 \end{array}\right] \left[\begin{array}{c} x_1 \\ x_2 \\x_3\end{array}\right] \leq \left[\begin{array}{c}3 \\ 2 \\ -2 \end{array} \right]\end{array}x1,x2,x3minimizesubjectto180231021x1x2x33232121202111x1x2x3322

This problem is in linear least squares form. Denoting its cost function byMxb2\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}\| M x - b\|^2Mxb2, we can convert it to QP form as follows:

Mxb22=(Mxb)T(Mxb)=xTMTMxxTMTbbTMx+bTb(1/2)xTMTMx(1/2)xTMTb(1/2)bTMx=(1/2)xT(MTM)x+(MTb)Tx\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}\begin{align*}\| M x - b \|_2^2 & = (M x - b)^T (M x - b) \\& = x^T M^T M x - x^T M^T b - b^T M x + b^T b \\& \propto (1/2) x^T M^T M x - (1/2) x^T M^T b - (1/2) b^T M x \\& = (1/2) x^T (M^T M) x + (-M^T b)^T x\end{align*}Mxb22=(Mxb)T(Mxb)=xTMTMxxTMTbbTMx+bTb(1/2)xTMTMx(1/2)xTMTb(1/2)bTMx=(1/2)xT(MTM)x+(MTb)Tx

Multiplying by a positive constant (1/2)\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}(1/2)(1/2) does not change the value ofthe optimum x\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}x^*x. Similarly, the constant offset bTb\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}b^T bbTb does notaffect x\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}x^*x, therefore we can leave it out. Meanwhile, yT=y\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}y^T = yyT=yfor any real number y\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}yy, therefore xTMTb=bTMx\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}x^T M^T b = b^T M xxTMTb=bTMx and we cancombine the two middle terms into a single q=MTb\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}q = -M^T bq=MTb. In Python, wethen write:

M = array([[1., 2., 0.], [-8., 3., 2.], [0., 1., 1.]])P = dot(M.T, M)q = -dot(M.T, array([3., 2., 3.]))G = array([[1., 2., 1.], [2., 0., 1.], [-1., 2., -1.]])h = array([3., 2., -2.]).reshape((3,))

We can finally compute the solution to the least squares problem using eitherof our QP solvers:

In [1]: cvxopt_solve_qp(P, q, G, h)Out[1]: array([ 0.12997347, -0.06498674, 1.74005305])In [2]: quadprog_solve_qp(P, q, G, h)Out[2]: array([ 0.12997347, -0.06498674, 1.74005305])

Comparing solver performances

In the following benchmark, I compared six different solvers. (Edit: thisbenchmark is severely outdated, check out qpbenchmark for a 2022 refresher.) Three ofthem are numerical, which is the approach we have seen so far:

The three others are symbolic, meaning that if you dig into their API theyallow you to construct your problem formally (with variable names) rather thanusing the matrix-vector representation. This is convenient for big sparseproblems, but slower and small problems such as the one we are looking at here.The three symbolic frameworks I tested are:

Note that ECOS and MOSEK are actually SOCP solvers, SOCPbeing a class of problems more general that QP. Here are sample computationtimes on my machine:

  • qpOASES: 10000 loops, best of 3: 31.5 µs per loop
  • quadprog: 10000 loops, best of 3: 34.1 µs per loop
  • CVXOPT: 1000 loops, best of 3: 559 µs per loop
  • Gurobi: 1000 loops, best of 3: 865 µs per loop
  • CVXPY: 100 loops, best of 3: 2.81 ms per loop
  • MOSEK: 100 loops, best of 3: 7.24 ms per loop

For further investigation, let us generate random problems of arbitrary size asfollows:

def solve_random_qp(n, solver): M, b = random.random((n, n)), random.random(n) P, q = dot(M.T, M), dot(b, M).reshape((n,)) G = toeplitz([1., 0., 0.] + [0.] * (n - 3), [1., 2., 3.] + [0.] * (n - 3)) h = ones(n) return solve_qp(P, q, G, h, solver=solver)

The Toeplitz matrix used to generate inequalities is just an upper-tridiagonalmatrix with coefficients 1, 2, 3, all other coefficients being zero. Thismatrix is sparse but represented by (dense) NumPy arrays here. Using thefunction above, I generated a benchmark for problem sizes ranging from 10 to2,000, averaging computation times over 10 runs for each point. Here are theresults:

Quadratic programming in Python (2)

The bottom line of this small comparison is that quadprog, which implementsthe Goldfarb-Idnani dual algorithm, simply rocks on well-conditioned denseproblems. More generally, active-set solvers (quadprog and qpOASES here)perform best on dense problems. To see the benefit of interior-point solverslike Gurobi or MOSEK, one would have to use sparse matrix representation, whichI didn't do in this example. (Edit: it has been done since then in qpsolvers.) Also, the performance ofCVXPY here does not illustrate that of its underlying solver (ECOS), as itturns out calling the solver directly is much faster than going through CVXPY.

One last note on this benchmark is that all performances reported here are forcold start, that is to say, problems are solved from scratch every timewithout a good initial guess. One reason why qpOASES is a bit slow here is thatit is designed (e.g. in terms of memory allocation) for solving series of QPproblems that are close to each other, so that the solution to one can be usedas initial guess to solve the next problem faster (this is known as warmstarting). You might want to give qpOASES a closer look if you are in suchscenarios.

To go further

You can run this benchmark on your own computer: the script was calledbenchmark_random_problems.py and located in the examples folder of theqpsolvers repository. Sincethe publication of this post, the library has grown to include more solvers(OSQP, qpSWIFT, SCS, ...) and features such as box inequalities.

Better benchmark

This benchmark is now severely outdated, but you can check out qpbenchmark for a 2022 refresher. The newerbenchmark includes new solvers and evaluates both computation times and theaccuracy of returned solutions. How do we evaluate the accuracy of a QPsolution, you ask? The best practice as of todayis to set numerical tolerances on optimality conditions.

Discussion

You can subscribe to this Discussion's atom feed to stay tuned.

  • Quadratic programming in Python (3)

    Permalink

    TJ

    Posted on

    The wrapped function cvxopt_solve_qp is probably wrong, what if we only have equality constraint? That code won't work.

    • Quadratic programming in Python (4)

      Permalink

      Stéphane

      Posted on

      Thank you for pointing this out. Handling all cases is a bit verbose and notadding to the points made in this post, so I've updated the inline code toassume clearly that G and h are set. For a general solution, all casesare handled in qpsolvers, whichstarted from this blog post but has evolved to include fixes, features (such asbox inequalities) and new solvers.

  • Quadratic programming in Python (5)

    Permalink

    Andreas

    Posted on

    Hi, thanks very much for the interesting blog post! I am interested in large scale unconstrained quadratic optimization with positive definite, symmetric P\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}PP (dense, with sizes up 105×105\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}10^5 \times 10^5105×105). Are the presented solvers still usable?

    • Quadratic programming in Python (6)

      Permalink

      Stéphane

      Posted on

      That's an interesting use case. I just tried the following snippet with qpsolvers:

      import numpy as npfrom qpsolvers import available_solvers, solve_qpn = 1000 # change to your likingM = np.random.random((n, n))P = np.dot(M.T, M) # this is a positive definite matrixq = np.dot(np.ones(n, dtype=float), M)for solver in available_solvers: try: found_solution = solve_qp(P, q, solver=solver) is not None except Exception: found_solution = False if found_solution: print(f"Potential solver: {solver}")

      I have no assumption as to the conditioning of your problem, so M\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}MM is a random matrix here. Running with n = 1000 gives us a first set of candidate solvers for this kind of problems: CVXOPT, ECOS, HiGHS, OSQP, ProxQP (dense backend) and quadprog. Those are only six out of the eleven available solvers.

      • At n = 5000 ECOS and HiGHS don't return after one minute of runtime on my laptop, so I assume they won't scale up to your problem sizes. The other four solvers still pass.
      • At n = 10_000 OSQP and quadprog don't return after one minute of runtime, so I assume they won't scale either. The remaining two solvers still pass.

      This leaves us with CVXOPT and ProxQP as the best candidates so far. Your problem is large but it should be fit in RAM with double precision on a beefy machine (128 GB of RAM). My laptop has 8 GB of RAM, so I can only extrapolate and let you try things out by yourself from there on 😉

      • Quadratic programming in Python (7)

        Permalink

        Andreas

        Posted on

        Thanks very much for the explanation. Indeed it seems that cvxopt is fastest for this problem. Unfortunately, I realized however that cvxopt cannot handle (very) large matrices with more than 2321\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}2^{32} -12321 entries (roughly dense matrices with dimensions larger than 4.6104×4.6104\def\bfA{\boldsymbol{A}}\def\bfB{\boldsymbol{B}}\def\bfC{\boldsymbol{C}}\def\bfD{\boldsymbol{D}}\def\bfE{\boldsymbol{E}}\def\bfF{\boldsymbol{F}}\def\bfG{\boldsymbol{G}}\def\bfH{\boldsymbol{H}}\def\bfI{\boldsymbol{I}}\def\bfJ{\boldsymbol{J}}\def\bfK{\boldsymbol{K}}\def\bfL{\boldsymbol{L}}\def\bfM{\boldsymbol{M}}\def\bfN{\boldsymbol{N}}\def\bfO{\boldsymbol{O}}\def\bfP{\boldsymbol{P}}\def\bfQ{\boldsymbol{Q}}\def\bfR{\boldsymbol{R}}\def\bfS{\boldsymbol{S}}\def\bfT{\boldsymbol{T}}\def\bfU{\boldsymbol{U}}\def\bfV{\boldsymbol{V}}\def\bfW{\boldsymbol{W}}\def\bfX{\boldsymbol{X}}\def\bfY{\boldsymbol{Y}}\def\bfZ{\boldsymbol{Z}}\def\bfalpha{\boldsymbol{\alpha}}\def\bfa{\boldsymbol{a}}\def\bfbeta{\boldsymbol{\beta}}\def\bfb{\boldsymbol{b}}\def\bfcd{\dot{\bfc}}\def\bfchi{\boldsymbol{\chi}}\def\bfc{\boldsymbol{c}}\def\bfd{\boldsymbol{d}}\def\bfe{\boldsymbol{e}}\def\bff{\boldsymbol{f}}\def\bfgamma{\boldsymbol{\gamma}}\def\bfg{\boldsymbol{g}}\def\bfh{\boldsymbol{h}}\def\bfi{\boldsymbol{i}}\def\bfj{\boldsymbol{j}}\def\bfk{\boldsymbol{k}}\def\bflambda{\boldsymbol{\lambda}}\def\bfl{\boldsymbol{l}}\def\bfm{\boldsymbol{m}}\def\bfn{\boldsymbol{n}}\def\bfomega{\boldsymbol{\omega}}\def\bfone{\boldsymbol{1}}\def\bfo{\boldsymbol{o}}\def\bfpdd{\ddot{\bfp}}\def\bfpd{\dot{\bfp}}\def\bfphi{\boldsymbol{\phi}}\def\bfp{\boldsymbol{p}}\def\bfq{\boldsymbol{q}}\def\bfr{\boldsymbol{r}}\def\bfsigma{\boldsymbol{\sigma}}\def\bfs{\boldsymbol{s}}\def\bftau{\boldsymbol{\tau}}\def\bftheta{\boldsymbol{\theta}}\def\bft{\boldsymbol{t}}\def\bfu{\boldsymbol{u}}\def\bfv{\boldsymbol{v}}\def\bfw{\boldsymbol{w}}\def\bfxi{\boldsymbol{\xi}}\def\bfx{\boldsymbol{x}}\def\bfy{\boldsymbol{y}}\def\bfzero{\boldsymbol{0}}\def\bfz{\boldsymbol{z}}\def\defeq{\stackrel{\mathrm{def}}{=}}\def\p{\boldsymbol{p}}\def\qdd{\ddot{\bfq}}\def\qd{\dot{\bfq}}\def\q{\boldsymbol{q}}\def\xd{\dot{x}}\def\yd{\dot{y}}\def\zd{\dot{z}}4.6 * 10^4 \times 4.6 * 10^44.6104×4.6104) as it uses a BLAS version with 32-bit integers cvxopt#126. According to the discussion, it seems currently impossible to avoid this, or do you know any workaround?

        • Quadratic programming in Python (8)

          Permalink

          Stéphane

          Posted on

          For CVXOPT not really. According to the feedback in that issue, the solver is unlikely to move to a different version of BLAS, which makes some sense from a maintainer perspective as the project is in a stable state.

          In that case, I would probably switch gears to ProxQP, which is under active development (especially its sparse backend) and uses more recent software. (Disclaimer: I've just started working in the same team as the ProxQP developers 😉) If you face a limitation and open an issue there, ideally with a sample problem illustrating what doesn't work as expected, developers are more likely to act on it.

Feel free to post a comment by e-mail using the form below. Your e-mail address will not be disclosed.

Quadratic programming in Python (2024)

References

Top Articles
Latest Posts
Article information

Author: Saturnina Altenwerth DVM

Last Updated:

Views: 5378

Rating: 4.3 / 5 (44 voted)

Reviews: 83% of readers found this page helpful

Author information

Name: Saturnina Altenwerth DVM

Birthday: 1992-08-21

Address: Apt. 237 662 Haag Mills, East Verenaport, MO 57071-5493

Phone: +331850833384

Job: District Real-Estate Architect

Hobby: Skateboarding, Taxidermy, Air sports, Painting, Knife making, Letterboxing, Inline skating

Introduction: My name is Saturnina Altenwerth DVM, I am a witty, perfect, combative, beautiful, determined, fancy, determined person who loves writing and wants to share my knowledge and understanding with you.