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:
m i n i m i z e ( 1 / 2 ) x T P x + q T x s u b j e c t t o G x ≤ h A x = 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} minimize subject to ( 1/2 ) x T P x + q T x G x ≤ h A x = 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}}x x is the vector of optimization variables x 1 , … , x n \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_n x 1 , … , x n . 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}}P P 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}}q q 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 x ≥ 0 \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 0 x ≥ 0 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}}x x is positive.
This mathematical formulation means that a QP finds the minimum of a quadraticfunction over a linear set:
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 ∥ A x − b ∥ 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}}\| A x - b \|^2 ∥ A x − b ∥ 2 of a least squaresoptimization is written in standard form with P = 2 A T A \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 A P = 2 A T A and q = − 2 A T 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}}q= -2 A^T b q = − 2 A T b (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}}P P 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}}M M 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 x T M − 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^T M^- x x T M − x . 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}}P P 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 l b ≤ x ≤ u 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}}lb \leq x \leq ub l b ≤ x ≤ u b , 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:
m i n i m i z e x 1 , x 2 , x 3 ∥ [ 1 2 0 − 8 3 2 0 1 1 ] [ x 1 x 2 x 3 ] − [ 3 2 3 ] ∥ 2 s u b j e c t t o [ 1 2 1 2 0 1 − 1 2 − 1 ] [ x 1 x 2 x 3 ] ≤ [ 3 2 − 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}}\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} x 1 , x 2 , x 3 minimize subject to 1 − 8 0 2 3 1 0 2 1 x 1 x 2 x 3 − 3 2 3 2 1 2 − 1 2 0 2 1 1 − 1 x 1 x 2 x 3 ≤ 3 2 − 2
This problem is in linear least squares form. Denoting its cost function by∥ M x − b ∥ 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}}\| M x - b\|^2 ∥ M x − b ∥ 2 , we can convert it to QP form as follows:
∥ 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 ∝ ( 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 \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*} ∥ 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 ∝ ( 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
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 b T 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}}b^T b b T b 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, y T = 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 = y y T = y for 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}}y y , therefore x T M T b = b T M 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^T M^T b = b^T M x x T M T b = b T M x and we cancombine the two middle terms into a single q = − M T 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}}q = -M^T b q = − M T b . 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:
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 called benchmark_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.
TJ Posted on Mon 09 May 2022
The wrapped function cvxopt_solve_qp
is probably wrong, what if we only have equality constraint? That code won't work.
Stéphane Posted on Sun 27 June 2021
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.
Andreas Posted on Mon 12 December 2022
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}}P P (dense, with sizes up 1 0 5 × 1 0 5 \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^5 1 0 5 × 1 0 5 ). Are the presented solvers still usable?
Stéphane Posted on Tue 13 December 2022
That's an interesting use case. I just tried the following snippet with qpsolvers :
import numpy as np from qpsolvers import available_solvers , solve_qp n = 1000 # change to your liking M = np . random . random (( n , n )) P = np . dot ( M . T , M ) # this is a positive definite matrix q = 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}}M M 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 😉
Andreas Posted on Tue 03 January 2023
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 2 32 − 1 \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} -1 2 32 − 1 entries (roughly dense matrices with dimensions larger than 4.6 ∗ 1 0 4 × 4.6 ∗ 1 0 4 \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^4 4.6 ∗ 1 0 4 × 4.6 ∗ 1 0 4 ) 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?
Stéphane Posted on Wed 04 January 2023
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.