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?
Best Answer
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$.