Are "constrained linear least squares" and "quadratic programming" the same thing?

Question

A Quadratic Programming problem is to minimize:

$f(\mathbf{x}) = \tfrac{1}{2} \mathbf{x}^T Q\mathbf{x} + \mathbf{c}^T \mathbf{x}$

subject to $A\mathbf{x} \leq \mathbf b$; $C\mathbf{x} = \mathbf d$; and $ \mathbf{s} \leq \mathbf{x} \leq \mathbf t$ and $Q$ is symmetric.

---

A Constrained Linear Least Squares problem is to minimize:

$\frac{1}{2}| Q\mathbf{x} - \mathbf{c}|_2^2$

subject to $A\mathbf{x} \leq \mathbf b$; $C\mathbf{x} = \mathbf d$; and $ \mathbf{s} \leq \mathbf{x} \leq \mathbf t$.

---

Matlab has two different functions for solving these, quadprog and lsqlin, hinting that these are different problems; but they seem like the same thing under the hood. Could someone explain whether these are the same problem, in particular is it correct to describe a "Constrained Linear Least Squares" problem as a "Quadratic Programming" problem? If not, what is an example of a problem expressible in one form but not the other?

Answer 1

As Rahul has shown, both problems are equivalent from a mathematical point of view: the Constrained Linear Least Squares problem is a specific instance of the Quadratic Programming (QP) problem.

There are some practical differences, however. For the QP problem, if $Q$ is not positive definite (in addition to symmetric), the unconstrained problem will not be convex and it is possible that there is no nonfinite global minimizer (depending on the constraints).

By design however, the CLLS problem will always be convex. This is also shown by Rahul, as

$$ \frac{1}{2}|Q\mathbf{x} - \mathbf{b}|^2 = \frac{1}{2}\mathbf{x}^\top Q^\top Q\mathbf{x} - \mathbf{b}^\top Q \mathbf{x} + \frac{1}{2}\mathbf{b}^\top\mathbf{b}\,, $$ and $Q^\top Q$ of the impossible QP problem is always positive definite.

Note that the exact implementations in Matlab also likely differ: if $Q$ in a CLLS problem is 'wide' (few rows, but many columns), $Q^\top Q$ will be huge, so the naive QP will be computationally demanding while the CLLS version can be solved more efficiently (if cleverly implemented).

Please consult the excellent textbook of Boyd and Vandenberghe for a more in-depth discussion.

Boyd, Stephen and Vandenberghe, Lieven 'Convex Optimization'. Cambridge University Press (2004)

Answer 2

It can be shown that every Linear Least Squares problem is in fact a Quadratic Programming Problem as follows: $$\frac12 \| Q x - c \|^2 = \frac12 (Qx-c)^T(Qx-c) =\frac12 \left( x^T Q^T Q x - x^T Q^T c - c^T Q x + c^T c\right)$$ $$= \frac12 \left( x^T Q^T Q x - 2 x^T Q^T c + c^T c\right)$$

Since $c^Tc$ is a fixed quantity, it is sufficient to solve the Quadratic Programming problem: $$f(x) = \frac12 x^T A x + q^Tx$$ where $A=Q^TQ$ and $q = -Q^Tc$.