17
$\begingroup$

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?

$\endgroup$
3
  • 3
    $\begingroup$ Every constrained linear least-squares problem can be expressed as an instance of quadratic programming, as Joel's answer sort of shows ($Q\gets Q^TQ$, $c\gets Q^Tc$). But not every quadratic programming problem can be expressed as a constrained linear least-squares problem, because $Q$ may not be positive definite. $\endgroup$ Commented Jul 16, 2014 at 18:43
  • $\begingroup$ @Joel does a good job of showing every Linear Least Squares problem is a QP problem. Still looking for a concrete answer in the other direction. Seems to me that a QP problem is LLS only if certain properties of $q$ hold. $\endgroup$ Commented Jan 12, 2016 at 20:47
  • $\begingroup$ A diffference in practice is whether "subject to $Ax \le b ...$" is a hard constraint, vs. minimizing $f()$ and the "subject-to" part together. Afaik Quadratic programming codes treat the s.t. part hard, least squares do them together. (Sometimes one wants hard constraints, sometimes not. The distinction between "goals" and "constraints" is not always clear-cut: consider guns and butter.) $\endgroup$ Commented Nov 7, 2018 at 11:04

2 Answers 2

Reset to default
16
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ The $Q$ isn't meant to be the same in each problem, just to represent a matrix. What you've written shows (I think?) that every LSq problem is a QP problem, but it isn't clear to me that every QP problem is an LSq problem? $\endgroup$ Commented Jul 16, 2014 at 19:01
  • $\begingroup$ You are right. It's been a long day. $\endgroup$ Commented Jul 16, 2014 at 19:09
  • 2
    $\begingroup$ I found a few typos in your derivation, so I fixed them. Please check that my edit is correct. $\endgroup$ Commented Jul 16, 2014 at 19:19
  • $\begingroup$ Your edit is correct. Thank you. $\endgroup$ Commented Jul 16, 2014 at 19:27
  • 1
    $\begingroup$ So looking at this, it seems that the reverse should not be true. You can always factor $A$ into $Q^T Q$ since it is symmetric, but $q^T$ doesn't need to be related to $Q$ or $A$ in the general QP problem. Agree? $\endgroup$ Commented Jul 16, 2014 at 19:30
5
$\begingroup$

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)

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.