QP and Least Squares

This article covers the problem formulations of quadratic programming and least squares under linear constraints.

Background

When formulating optimization problems in applied settings (e.g., robotics, vision), it may be unclear whether to frame them as a quadratic program (QP) or as a least squares (LS) problem. Typically, this has the structure of an inverse problem; briefly: given a desired output $\mathbf{y}_\mathsf{d}$ and a forward model ${\mathrm{G}: \mathbf{x} \mapsto \mathbf{y}}$, we seek the input $\mathbf{x}^*$ that is mapped closest to $\mathbf{y}_\mathsf{d}$. Sometimes, it is possible to obtain an inverse model $\mathrm{G}^{\mathsf{inv}}$ which fulfills the map $\mathbf{y} \mapsto \mathbf{x}$.

As is often the case, it may be more convenient to solve the associated least squares problem that minimizes the residual $\Vert \mathrm{G}(\mathbf{x}) - \mathbf{y} \Vert_2$. Example scenarios where a least squares problem structure can be used include inverse kinematics and camera calibration (resectioning, i.e., camera extrinsic/intrinsic parameter estimation). Depending on the specific problem instance, the meanings of $(\mathrm{G}, \mathbf{x}, \mathbf{y})$ will vary and may not be immediately obvious.

As will be shown in this article, the LS problem under specific conditions can be framed as a QP problem. We assume a linear forward model $\mathrm{G}$ and linear constraints on the input $\mathbf{x}$.

Problem Structure

Below, we develop the structure and assumptions of the least squares and the quadratic programming problems.

Least squares problem

Let $(\mathsf{LS})$ be our least squares problem having $m$ output variables, $n$ input variables, $p$ linear constraints, and a linear forward model $\mathrm{G}$. This problem can be termed linearly-constrained linear least squares.

$$ (\mathsf{LS}): \begin{dcases} \begin{aligned} \min & \quad J_\mathsf{LS}(\mathbf{x}) = \Vert \mathrm{G} \mathbf{x} - \mathbf{y}\Vert_2^2 \\ \operatorname{s.t.} & \quad \mathrm{A} \mathbf{x} \preceq \mathbf{b} \end{aligned} \end{dcases} $$

Here, $\mathbf{y} \in \mathbb{R}^m$, $\mathrm{G} \in \mathbb{R}^{m × n}$, $\mathbf{x} \in \mathbb{R}^n$, $\mathbf{b} \in \mathbb{R}^p$, and $\mathrm{A} \in \mathbb{R}^{p × n}$.

QP problem

Let $(\mathsf{QP})$ be our quadratic programming problem having $n$ variables and $p$ linear constraints. This problem is specifically linearly-constrained quadratic programming.

$$ (\mathsf{QP}): \begin{dcases} \begin{aligned} \min & \quad J_\mathsf{QP}(\mathbf{x}) = \frac{1}{2} \mathbf{x}^\mathsf{T} \mathrm{Q} \mathbf{x} + \mathbf{c}^\mathsf{T} \mathbf{x} \\ \operatorname{s.t.} & \quad \mathrm{A} \mathbf{x} \preceq \mathbf{b} \end{aligned} \end{dcases} $$ Here, $\mathrm{Q} \in \mathbb{R}^{n × n}$ is a symmetric matrix ($\mathrm{Q}^\mathsf{T} = \mathrm{Q}$), $\mathbf{x} \in \mathbb{R}^n$, $\mathbf{b} \in \mathbb{R}^p$, and ${\mathrm{A} \in \mathbb{R}^{p × n}}$. In general, there are no restrictions on the definiteness of $\mathrm{Q}$.

From $(\mathsf{LS})$ to $(\mathsf{QP})$

To restate our least squares problem as a QP problem, we first rewrite the cost function $J_\mathsf{LS}(\mathbf{x})$ as:

$$ \begin{aligned} J_\mathsf{LS}(\mathbf{x}) &= (\mathrm{G} \mathbf{x} - \mathbf{y})^\mathsf{T} (\mathrm{G} \mathbf{x} - \mathbf{y}) \\ &= (\mathbf{x}^\mathsf{T} \mathrm{G}^\mathsf{T} - \mathbf{y}^\mathsf{T}) (\mathrm{G} \mathbf{x} - \mathbf{y}) \\ &= \mathbf{x}^\mathsf{T} \mathrm{G}^\mathsf{T} \mathrm{G} \mathbf{x} - \mathbf{y}^\mathsf{T} \mathrm{G} \mathbf{x} - \mathbf{x}^\mathsf{T} \mathrm{G}^\mathsf{T} \mathbf{y} + \mathbf{y}^\mathsf{T} \mathbf{y} \\ &= \mathbf{x}^\mathsf{T} \mathrm{G}^\mathsf{T} \mathrm{G} \mathbf{x} - 2\mathbf{y}^\mathsf{T} \mathrm{G} \mathbf{x} + \mathbf{y}^\mathsf{T} \mathbf{y} \end{aligned} $$

Notice that the minimizer $\mathbf{x}^*$ of $\tilde{J}_\mathsf{LS}(\mathbf{x}) = \frac{1}{2}[J_\mathsf{LS}(\mathbf{x}) - \mathbf{y}^\mathsf{T} \mathbf{y}]$ is that of $J_\mathsf{LS}(\mathbf{x})$; however, the minimum value is different. The modified cost function can thus be rewritten into a QP objective function, as follows:

$$ \begin{aligned} \tilde{J}_\mathsf{LS}(\mathbf{x}) &= \frac{1}{2} \mathbf{x}^\mathsf{T} \mathrm{G}^\mathsf{T} \mathrm{G} \mathbf{x} - \mathbf{y}^\mathsf{T} \mathrm{G} \mathbf{x} \\ &= \frac{1}{2} \mathbf{x}^\mathsf{T} \mathrm{Q} \mathbf{x} + \mathbf{c}^\mathsf{T} \mathbf{x} \end{aligned} $$ By setting $\mathrm{Q} = \mathrm{G}^\mathsf{T} \mathrm{G}$ and $\mathbf{c} = -\mathrm{G}^\mathsf{T} \mathbf{y}$, the problem $(\mathsf{LS})$ is restated in the from of $(\mathsf{QP})$. In the scenario where $\mathrm{Q} \succ 0$ (see the above note on definiteness), then $J_\mathsf{QP}(\mathbf{x})$ is strictly convex and its minimizer $\mathbf{x}^*$ is unique.

From $(\mathsf{QP})$ to $(\mathsf{LS})$

Work in progress.
This can be achieved using Cholesky decomposition.