Quadratic Programming
Contents
10.12. Quadratic Programming#
10.12.1. Quadratic Functions#
Definition 10.41 (Quadratic function)
A function \(f : \RR^n \to \RR\) of the form
where \(\bA \in \SS^n\), \(\bb \in \RR^n\) and \(c \in \RR\), is known as a quadratic function.
The matrix \(\bA\) is known as the matrix associated with the quadratic function.
Remark 10.8 (Gradient and Hessian of a quadratic function)
Let
be a quadratic function. Then, the gradient is given by:
And, the Hessian is given by:
See Example 5.8 and Example 5.13 for reference.
10.12.1.1. Stationary Points#
Theorem 10.86 (Stationary points of quadratic functions)
Let a quadratic function \(f : \RR^n \to \RR\) be given by
where \(\bA \in \SS^n\), \(\bb \in \RR^n\) and \(c \in \RR\).
\(\bx \in \RR^n\) is a stationary point if and only if \(\bA \bx = - \bb\).
If \(\bA \succeq \ZERO\), then \(\bx\) is a global minimum point of \(f\) if and only if \(\bA \bx = -\bb\).
If \(\bA \succ \ZERO\), then \(\bx = - \bA^{-1} \bb\) is a strict global minimum point of \(f\).
If \(\bA \succ \ZERO\), then the minimum value of \(f\) is \(c - \frac{1}{2} \bb^T \bA^{-1} \bb\).
Proof. (1) is a direct implication of the fact that \(\nabla f(\bx) = \bzero\) if and only if \(\bA \bx + \bb = \bzero\).
(2) We are given that \(\nabla^2 f(\bx) = \bA \succeq \ZERO\).
Thus, \(\nabla^2 f(\bx) \succeq \ZERO\) for every \(\bx \in \RR^n\).
By Theorem 8.4, if \(\bx\) is a stationary point of \(f\), then it is a global minimum point.
By first part, \(\bx\) is a stationary point if and only if \(\bA \bx = - \bb\).
(3) We are given that \(\bA \succ \ZERO\).
Then, \(\bA\) is invertible.
Hence, \(\bx = - \bA^{-1} \bb\) is the unique solution to the equation \(\bA \bx = - \bb\).
By parts (1) and (2), it is the unique (hence strict) global minimizer of \(f\).
(4) We know that strict global minimum point of \(f\) is given by \(\ba = - \bA^{-1} \bb\) with \(\bA \ba = - \bb\). Therefore,
10.12.1.2. Coerciveness#
Theorem 10.87 (Coerciveness of quadratic functions)
Let a quadratic function \(f : \RR^n \to \RR\) be given by
where \(\bA \in \SS^n\), \(\bb \in \RR^n\) and \(c \in \RR\).
\(f\) is coercive if and only if \(\bA \succ \ZERO\); i.e., \(\bA\) is positive definite.
Proof. Assume that \(\bA\) is positive definite.
Then, all eigenvalues of \(\bA\) are positive.
Let \(\lambda\) be the smallest eigenvalue of \(\bA\).
Then, \(\bx^T \bA \bx \geq \lambda \| \bx \|^2\) for every \(\bx \in \RR^n\).
Thus,
\[\begin{split} f(\bx) &\geq \frac{ \lambda}{2} \| \bx \|^2 + \bb^T \bx + c \\ &\geq \frac{ \lambda}{2} \| \bx \|^2 - \|\bb \| \| \bx \| + c & \text{ Cauchy Schwartz inequality }\\ &= \frac{ \lambda}{2} \| \bx \| \left (\| \bx \| - \frac{2}{\lambda} \| \bb \| \right ) + c. \end{split}\]We can see that \(f(\bx) \to \infty\) as \(\| \bx \| \to \infty\).
Thus, \(f\) is coercive.
Now, assume that \(f\) is coercive.
We need to show that \(\bA\) must be positive definite.
Thus, all eigenvalues of \(\bA\) must be positive.
For contradiction, assume that an eigenvalue of \(\bA\) is negative.
Let \(\lambda < 0\) be such an eigenvalue with the corresponding normalized eigenvector \(\bv\) such that \(\bA \bv = \lambda \bv\).
Then, for any \(t \in \RR\),
\[\begin{split} f(t \bv) &= \frac{t^2}{2} \bv^T \bA \bv + t \bb^T \bv + c \\ &= \frac{\lambda t^2}{2} + t \bb^T \bv + c. \end{split}\]Clearly, \(f(t \bv) \to -\infty\) as \(t \to \infty\) since \(\lambda\) is negative.
Thus, it contradicts the hypothesis that \(f\) is coercive.
We now consider the possibility where there is a 0 eigenvalue.
Then, there exists a normalized eigenvector \(\bv\) such that \(\bA \bv = \bzero\).
Then, for any \(t \in \RR\),
\[ f(t \bv) = t \bb^T \bv + c. \]If \(\bb^T \bv = 0\), then \(f(t\bv) = c\) for every \(t \in \RR\).
If \(\bb^T \bv > 0\), then \(f(t \bv) \to -\infty\) as \(t \to -\infty\).
If \(\bb^T \bv < 0\), then \(f(t \bv) \to -\infty\) as \(t \to \infty\).
In all the three cases, \(f(t \bv)\) does not go to \(\infty\) as \(\| t \bv \| \to \infty\).
Thus, \(f\) is not coercive. A contradiction to the hypothesis.
Hence, the eigenvalues of \(\bA\) must be positive.
Hence, \(\bA\) must be positive definite.
10.12.1.3. Nonnegative Quadratics#
It is useful to work with quadratic functions which are nonnegative on the entire \(\RR^n\).
The basic quadratic form \(f(\bx) = \frac{1}{2} \bx^T \bA \bx\) is nonnegative on entire \(\RR^n\) if \(\bA\) is positive semidefinite.
For the general quadratic function, we need to incorporate the contribution from \(\bb\) and \(c\) terms also.
Theorem 10.88 (Nonnegativity of quadratic function)
Let a quadratic function \(f : \RR^n \to \RR\) be given by
where \(\bA \in \SS^n\), \(\bb \in \RR^n\) and \(c \in \RR\).
The following statements are equivalent.
\(f(\bx) \geq 0\) for every \(\bx \in \RR^n\).
\(\begin{bmatrix} \bA & \bb \\ \bb^T & 2 c \end{bmatrix} \succeq \ZERO\); i.e., this \(n+1 \times n+1\) symmetric matrix is positive semidefinite.
Proof. Assume that (2) is true.
Then, for every \(\bx \in \RR^n\)
\[\begin{split} \begin{bmatrix} \bx \\ 1 \end{bmatrix}^T \begin{bmatrix} \bA & \bb \\ \bb^T & 2 c \end{bmatrix} \begin{bmatrix} \bx \\ 1 \end{bmatrix} \geq 0 \end{split}\]due to positive semidefiniteness.
But
\[\begin{split} \begin{bmatrix} \bx \\ 1 \end{bmatrix}^T \begin{bmatrix} \bA & \bb \\ \bb^T & 2 c \end{bmatrix} \begin{bmatrix} \bx \\ 1 \end{bmatrix} &= \begin{bmatrix} \bx^T & 1 \end{bmatrix} \begin{bmatrix} \bA \bx + \bb \\ \bb^T \bx + 2c \end{bmatrix} \\ & = \bx^T \bA \bx + 2 \bx^T \bb + 2 c \\ &= 2 \left ( \frac{1}{2} \bx^T \bA \bx + \bb^T \bx + c \right ) \\ = 2 f(\bx). \end{split}\]Thus, \(f(\bx) \geq 0\) for every \(\bx \in \RR^n\).
For the converse, assume (1) is true.
We need to show that \(\begin{bmatrix} \bA & \bb \\ \bb^T & 2 c \end{bmatrix}\) is positive semidefinite.
We shall first show that \(\bA\) is positive semidefinite.
For contradiction, assume that \(\bA\) is not positive semidefinite.
Then, there exists a negative eigenvalue \(\lambda < 0\) and corresponding normalized eigenvector \(\bv\) for \(\bA\) such that \(\bA \bv = \lambda \bv\).
Then, for any \(t \in \RR\)
\[ f(t \bv) = \frac{\lambda t^2}{2} + t \bb^T \bv + c. \]Then, \(f(t \bv) \to -\infty\) as \(t \to -\infty\).
This contradicts the hypothesis that \(f\) is nonnegative everywhere.
Thus, \(\bA\) must be positive semidefinite.
We now need to show that for any \(\by \in \RR^n\) and any \(t \in \RR\),
\[\begin{split} \begin{bmatrix} \by \\ t \end{bmatrix}^T \begin{bmatrix} \bA & \bb \\ \bb^T & 2 c \end{bmatrix} \begin{bmatrix} \by \\ t \end{bmatrix} \geq 0. \end{split}\]This condition is equivalent to
\[ \frac{1}{2} \by^T \bA \by + t \bb^T \by + c t^2 \geq 0 \]for every \(\by \in \RR^n\) and \(t \in \RR\).
If \(t = 0\), then this condition reduces to
\[ \by^T \bA \by \geq 0 \Forall \by \in \RR^n. \]This is valid for every \(\by \in \RR^n\) since \(\bA\) is p.s.d.. as established earlier.
For \(t \neq 0\), we have
\[ t^2 f \left ( \frac{\by}{ t} \right ) = t^2 \left ( \frac{1}{2 t^2} \by^T \bA \by + \frac{1}{t} \bb^T \by + c \right ) = \frac{1}{2 } \by^T \bA \by + t \bb^T \by + c t^2. \]By hypothesis, \(t^2 f \left ( \frac{\by}{ t} \right ) \geq 0\) for every \(\by \in \RR^n\) and \(t \neq 0\).
Thus, \(\frac{1}{2 } \by^T \bA \by + t \bb^T \by + c t^2 \geq 0\) for every \(\by \in \RR^n\) and \(t \in \RR\).
Thus, \(\begin{bmatrix} \bA & \bb \\ \bb^T & 2 c \end{bmatrix}\) is indeed p.s.d..
10.12.2. Quadratic Optimization Problems#
We consider the following possibilities:
The objective function is a quadratic function.
Both the objective function as well as the inequality constraints function are quadratic.
10.12.2.1. Quadratic Program#
Definition 10.42 (Quadratic program)
A convex optimization problem is known as a quadratic program (QP) if the objective function is a (convex) quadratic and the constraint functions are affine.
A general quadratic program has the following form:
where
\(\bx \in \RR^n\) is the optimization variable.
\(\bP \in \SS^n_+\) is a symmetric positive semidefinite matrix.
\(\bq \in \RR^n\) and \(r \in \RR\).
\(f(\bx) = \frac{1}{2} \bx^T \bP \bx + \bq^T \bx + r\) is a (convex) quadratic objective function.
\(\bG \in \RR^{m \times n}\) and \(\bh \in \RR^m\) describe the \(m\) affine inequality constraints.
\(\bA \in \RR^{p \times n}\) and \(\bb \in \RR^p\) describe the \(p\) affine equality constraints.
10.12.2.2. Quadratically Constrained Quadratic Program#
Definition 10.43 (Quadratically constrained quadratic program)
A convex optimization problem is known as a quadratically constrained quadratic program (QCQP) if the objective function and the inequality constraint functions are (convex) quadratic while the equality constraint functions are affine.
A general quadratic program has the following form:
where
\(\bx \in \RR^n\) is the optimization variable.
\(\bP_i \in \SS^n_+\) are symmetric positive semidefinite matrices for \(i=0,\dots,m\).
\(\bq_i \in \RR^n\) and \(r_i \in \RR\) for \(i=0,\dots,m\).
\(f_0(\bx) = \frac{1}{2} \bx^T \bP_0 \bx + \bq_0^T \bx + r_0\) is a (convex) quadratic objective function.
\(f_i(\bx) = \frac{1}{2} \bx^T \bP_i \bx + \bq_i^T \bx + r_i\) are (convex) quadratic inequality constraint functions for \(i=1,\dots,m\).
\(\bA \in \RR^{p \times n}\) and \(\bb \in \RR^p\) describe the \(p\) affine equality constraints.