.md .pdf

repository open issue

Contents

9.12. Quadratic Programming

9.12.1. Quadratic Functions

Definition 9.41 (Quadratic function)

A function $f:{\mathbb{R}}^n\to \mathbb{R}$ of the form

$$f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^T\mathbf{A}\mathbf{x}+{\mathbf{b}}^T\mathbf{x}+c$$

where $\mathbf{A}\in {\mathbb{S}}^n$, $\mathbf{b}\in {\mathbb{R}}^n$ and $c\in \mathbb{R}$, is known as a quadratic function.

The matrix $\mathbf{A}$ is known as the matrix associated with the quadratic function.

Remark 9.8 (Gradient and Hessian of a quadratic function)

Let

$$f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^T\mathbf{A}\mathbf{x}+{\mathbf{b}}^T\mathbf{x}+c$$

be a quadratic function. Then, the gradient is given by:

$$\mathrm{\nabla }f(\mathbf{x})=\mathbf{A}\mathbf{x}+\mathbf{b}.$$

And, the Hessian is given by:

$${\mathrm{\nabla }}^{2}f(\mathbf{x})=\mathbf{A}.$$

See Example 5.8 and Example 5.13 for reference.

9.12.1.1. Stationary Points

Theorem 9.86 (Stationary points of quadratic functions)

Let a quadratic function $f:{\mathbb{R}}^n\to \mathbb{R}$ be given by

$$f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^T\mathbf{A}\mathbf{x}+{\mathbf{b}}^T\mathbf{x}+c$$

where $\mathbf{A}\in {\mathbb{S}}^n$, $\mathbf{b}\in {\mathbb{R}}^n$ and $c\in \mathbb{R}$.

1. $\mathbf{x}\in {\mathbb{R}}^n$ is a stationary point if and only if $\mathbf{A}\mathbf{x}=-\mathbf{b}$.

2. If $\mathbf{A}⪰\mathbf{O}$, then $\mathbf{x}$ is a global minimum point of $f$ if and only if $\mathbf{A}\mathbf{x}=-\mathbf{b}$.

3. If $\mathbf{A}\mathrm{succ}\mathbf{O}$, then $\mathbf{x}=-{\mathbf{A}}^{-1}\mathbf{b}$ is a strict global minimum point of $f$.

4. If $\mathbf{A}\mathrm{succ}\mathbf{O}$, then the minimum value of $f$ is $c-\frac{1}{2}{\mathbf{b}}^T{\mathbf{A}}^{-1}\mathbf{b}$.

Proof. (1) is a direct implication of the fact that $\mathrm{\nabla }f(\mathbf{x})=\mathbf{0}$ if and only if $\mathbf{A}\mathbf{x}+\mathbf{b}=\mathbf{0}$.

(2) We are given that ${\mathrm{\nabla }}^{2}f(\mathbf{x})=\mathbf{A}⪰\mathbf{O}$.

1. Thus, ${\mathrm{\nabla }}^{2}f(\mathbf{x})⪰\mathbf{O}$ for every $\mathbf{x}\in {\mathbb{R}}^n$.

2. By Theorem 7.4, if $\mathbf{x}$ is a stationary point of $f$, then it is a global minimum point.

3. By first part, $\mathbf{x}$ is a stationary point if and only if $\mathbf{A}\mathbf{x}=-\mathbf{b}$.

(3) We are given that $\mathbf{A}\mathrm{succ}\mathbf{O}$.

1. Then, $\mathbf{A}$ is invertible.

2. Hence, $\mathbf{x}=-{\mathbf{A}}^{-1}\mathbf{b}$ is the unique solution to the equation $\mathbf{A}\mathbf{x}=-\mathbf{b}$.

3. 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 $\mathbf{a}=-{\mathbf{A}}^{-1}\mathbf{b}$ with $\mathbf{A}\mathbf{a}=-\mathbf{b}$. Therefore,

$$\begin{array}{rl}f(\mathbf{a})& =\frac{1}{2}{\mathbf{a}}^T\mathbf{A}\mathbf{a}+{\mathbf{b}}^T\mathbf{a}+c\\ & =-\frac{1}{2}{\mathbf{a}}^T\mathbf{b}+{\mathbf{b}}^T\mathbf{a}+c\\ & =c+\frac{1}{2}{\mathbf{b}}^T\mathbf{a}\\ & =c-\frac{1}{2}{\mathbf{b}}^T{\mathbf{A}}^{-1}\mathbf{b}.\end{array}$$

9.12.1.2. Coerciveness

Theorem 9.87 (Coerciveness of quadratic functions)

Let a quadratic function $f:{\mathbb{R}}^n\to \mathbb{R}$ be given by

$$f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^T\mathbf{A}\mathbf{x}+{\mathbf{b}}^T\mathbf{x}+c$$

where $\mathbf{A}\in {\mathbb{S}}^n$, $\mathbf{b}\in {\mathbb{R}}^n$ and $c\in \mathbb{R}$.

$f$ is coercive if and only if $\mathbf{A}\mathrm{succ}\mathbf{O}$; i.e., $\mathbf{A}$ is positive definite.

Proof. Assume that $\mathbf{A}$ is positive definite.

1. Then, all eigenvalues of $\mathbf{A}$ are positive.

2. Let $\lambda$ be the smallest eigenvalue of $\mathbf{A}$.

3. Then, ${\mathbf{x}}^T\mathbf{A}\mathbf{x}\ge \lambda \Vert \mathbf{x}{\Vert }^2$ for every $\mathbf{x}\in {\mathbb{R}}^n$.

4. Thus,

   $$\begin{array}{rl}f(\mathbf{x})& \ge \frac{\lambda }{2}\Vert \mathbf{x}{\Vert }^2+{\mathbf{b}}^T\mathbf{x}+c\\ & \ge \frac{\lambda }{2}\Vert \mathbf{x}{\Vert }^2-\Vert \mathbf{b}\Vert \Vert \mathbf{x}\Vert +c& \text{ Cauchy Schwartz inequality }\\ & =\frac{\lambda }{2}\Vert \mathbf{x}\Vert (\Vert \mathbf{x}\Vert -\frac{2}{\lambda }\Vert \mathbf{b}\Vert )+c.\end{array}$$

5. We can see that $f(\mathbf{x})\to \mathrm{\infty }$ as $\Vert \mathbf{x}\Vert \to \mathrm{\infty }$.

6. Thus, $f$ is coercive.

Now, assume that $f$ is coercive.

1. We need to show that $\mathbf{A}$ must be positive definite.

2. Thus, all eigenvalues of $\mathbf{A}$ must be positive.

3. For contradiction, assume that an eigenvalue of $\mathbf{A}$ is negative.

4. Let $\lambda <0$ be such an eigenvalue with the corresponding normalized eigenvector $\mathbf{v}$ such that $\mathbf{A}\mathbf{v}=\lambda \mathbf{v}$.

5. Then, for any $t\in \mathbb{R}$,

   $$\begin{array}{rl}f(t\mathbf{v})& =\frac{t^2}{2}{\mathbf{v}}^T\mathbf{A}\mathbf{v}+t{\mathbf{b}}^T\mathbf{v}+c\\ & =\frac{\lambda t^2}{2}+t{\mathbf{b}}^T\mathbf{v}+c.\end{array}$$

6. Clearly, $f(t\mathbf{v})\to -\mathrm{\infty }$ as $t\to \mathrm{\infty }$ since $\lambda$ is negative.

7. Thus, it contradicts the hypothesis that $f$ is coercive.

8. We now consider the possibility where there is a 0 eigenvalue.

9. Then, there exists a normalized eigenvector $\mathbf{v}$ such that $\mathbf{A}\mathbf{v}=\mathbf{0}$.

10. Then, for any $t\in \mathbb{R}$,

    $$f(t\mathbf{v})=t{\mathbf{b}}^T\mathbf{v}+c.$$

11. If ${\mathbf{b}}^T\mathbf{v}=0$, then $f(t\mathbf{v})=c$ for every $t\in \mathbb{R}$.

12. If ${\mathbf{b}}^T\mathbf{v}>0$, then $f(t\mathbf{v})\to -\mathrm{\infty }$ as $t\to -\mathrm{\infty }$.

13. If ${\mathbf{b}}^T\mathbf{v}<0$, then $f(t\mathbf{v})\to -\mathrm{\infty }$ as $t\to \mathrm{\infty }$.

14. In all the three cases, $f(t\mathbf{v})$ does not go to $\mathrm{\infty }$ as $\Vert t\mathbf{v}\Vert \to \mathrm{\infty }$.

15. Thus, $f$ is not coercive. A contradiction to the hypothesis.

16. Hence, the eigenvalues of $\mathbf{A}$ must be positive.

17. Hence, $\mathbf{A}$ must be positive definite.

9.12.1.3. Nonnegative Quadratics

It is useful to work with quadratic functions which are nonnegative on the entire ${\mathbb{R}}^n$.

The basic quadratic form $f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^T\mathbf{A}\mathbf{x}$ is nonnegative on entire ${\mathbb{R}}^n$ if $\mathbf{A}$ is positive semidefinite.

For the general quadratic function, we need to incorporate the contribution from $\mathbf{b}$ and $c$ terms also.

Theorem 9.88 (Nonnegativity of quadratic function)

Let a quadratic function $f:{\mathbb{R}}^n\to \mathbb{R}$ be given by

$$f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^T\mathbf{A}\mathbf{x}+{\mathbf{b}}^T\mathbf{x}+c$$

where $\mathbf{A}\in {\mathbb{S}}^n$, $\mathbf{b}\in {\mathbb{R}}^n$ and $c\in \mathbb{R}$.

The following statements are equivalent.

1. $f(\mathbf{x})\ge 0$ for every $\mathbf{x}\in {\mathbb{R}}^n$.

2. $\left[\begin{array}{cc}\mathbf{A}& \mathbf{b}\\ {\mathbf{b}}^T& 2c\end{array}\right]⪰\mathbf{O}$; i.e., this $n+1\times n+1$ symmetric matrix is positive semidefinite.

Proof. Assume that (2) is true.

1. Then, for every $\mathbf{x}\in {\mathbb{R}}^n$

   $$\begin{array}{r}{\left[\begin{array}{c}\mathbf{x}\\ 1\end{array}\right]}^T\left[\begin{array}{cc}\mathbf{A}& \mathbf{b}\\ {\mathbf{b}}^T& 2c\end{array}\right]\left[\begin{array}{c}\mathbf{x}\\ 1\end{array}\right]\ge 0\end{array}$$

   due to positive semidefiniteness.

2. But

   $$\begin{array}{rl}{\left[\begin{array}{c}\mathbf{x}\\ 1\end{array}\right]}^T\left[\begin{array}{cc}\mathbf{A}& \mathbf{b}\\ {\mathbf{b}}^T& 2c\end{array}\right]\left[\begin{array}{c}\mathbf{x}\\ 1\end{array}\right]& =\left[\begin{array}{cc}{\mathbf{x}}^T& 1\end{array}\right]\left[\begin{array}{c}\mathbf{A}\mathbf{x}+\mathbf{b}\\ {\mathbf{b}}^T\mathbf{x}+2c\end{array}\right]\\ & ={\mathbf{x}}^T\mathbf{A}\mathbf{x}+2{\mathbf{x}}^T\mathbf{b}+2c\\ & =2(\frac{1}{2}{\mathbf{x}}^T\mathbf{A}\mathbf{x}+{\mathbf{b}}^T\mathbf{x}+c)\\ =2f(\mathbf{x}).\end{array}$$

3. Thus, $f(\mathbf{x})\ge 0$ for every $\mathbf{x}\in {\mathbb{R}}^n$.

For the converse, assume (1) is true.

1. We need to show that $\left[\begin{array}{cc}\mathbf{A}& \mathbf{b}\\ {\mathbf{b}}^T& 2c\end{array}\right]$ is positive semidefinite.

2. We shall first show that $\mathbf{A}$ is positive semidefinite.

3. For contradiction, assume that $\mathbf{A}$ is not positive semidefinite.

4. Then, there exists a negative eigenvalue $\lambda <0$ and corresponding normalized eigenvector $\mathbf{v}$ for $\mathbf{A}$ such that $\mathbf{A}\mathbf{v}=\lambda \mathbf{v}$.

5. Then, for any $t\in \mathbb{R}$

   $$f(t\mathbf{v})=\frac{\lambda t^2}{2}+t{\mathbf{b}}^T\mathbf{v}+c.$$

6. Then, $f(t\mathbf{v})\to -\mathrm{\infty }$ as $t\to -\mathrm{\infty }$.

7. This contradicts the hypothesis that $f$ is nonnegative everywhere.

8. Thus, $\mathbf{A}$ must be positive semidefinite.

9. We now need to show that for any $\mathbf{y}\in {\mathbb{R}}^n$ and any $t\in \mathbb{R}$,

   $$\begin{array}{r}{\left[\begin{array}{c}\mathbf{y}\\ t\end{array}\right]}^T\left[\begin{array}{cc}\mathbf{A}& \mathbf{b}\\ {\mathbf{b}}^T& 2c\end{array}\right]\left[\begin{array}{c}\mathbf{y}\\ t\end{array}\right]\ge 0.\end{array}$$

10. This condition is equivalent to

    $$\frac{1}{2}{\mathbf{y}}^T\mathbf{A}\mathbf{y}+t{\mathbf{b}}^T\mathbf{y}+c{t}^2\ge 0$$

    for every $\mathbf{y}\in {\mathbb{R}}^n$ and $t\in \mathbb{R}$.

11. If $t=0$, then this condition reduces to

    $${\mathbf{y}}^T\mathbf{A}\mathbf{y}\ge 0\mathrm{\forall }\mathbf{y}\in {\mathbb{R}}^n.$$

12. This is valid for every $\mathbf{y}\in {\mathbb{R}}^n$ since $\mathbf{A}$ is p.s.d.. as established earlier.

13. For $t\ne 0$, we have

    $$t^{2}f\left(\frac{\mathbf{y}}{t}\right)=t^2(\frac{1}{2t^2}{\mathbf{y}}^T\mathbf{A}\mathbf{y}+\frac{1}{t}{\mathbf{b}}^T\mathbf{y}+c)=\frac{1}{2}{\mathbf{y}}^T\mathbf{A}\mathbf{y}+t{\mathbf{b}}^T\mathbf{y}+c{t}^2.$$

14. By hypothesis, $t^{2}f\left(\frac{\mathbf{y}}{t}\right)\ge 0$ for every $\mathbf{y}\in {\mathbb{R}}^n$ and $t\ne 0$.

15. Thus, $\frac{1}{2}{\mathbf{y}}^T\mathbf{A}\mathbf{y}+t{\mathbf{b}}^T\mathbf{y}+c{t}^2\ge 0$ for every $\mathbf{y}\in {\mathbb{R}}^n$ and $t\in \mathbb{R}$.

16. Thus, $\left[\begin{array}{cc}\mathbf{A}& \mathbf{b}\\ {\mathbf{b}}^T& 2c\end{array}\right]$ is indeed p.s.d..

9.12.2. Quadratic Optimization Problems

We consider the following possibilities:

1. The objective function is a quadratic function.

2. Both the objective function as well as the inequality constraints function are quadratic.

9.12.2.1. Quadratic Program

Definition 9.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:

(9.30)$$\begin{array}{rlrl}& \text{minimize }& & \frac{1}{2}{\mathbf{x}}^T\mathbf{P}\mathbf{x}+{\mathbf{q}}^T\mathbf{x}+r\\ & \text{subject to }& & \mathbf{G}\mathbf{x}⪯\mathbf{h}\\ & & & \mathbf{A}\mathbf{x}=\mathbf{b}\end{array}$$

where

1. $\mathbf{x}\in {\mathbb{R}}^n$ is the optimization variable.

2. $\mathbf{P}\in {\mathbb{S}}_{+}^n$ is a symmetric positive semidefinite matrix.

3. $\mathbf{q}\in {\mathbb{R}}^n$ and $r\in \mathbb{R}$.

4. $f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^T\mathbf{P}\mathbf{x}+{\mathbf{q}}^T\mathbf{x}+r$ is a (convex) quadratic objective function.

5. $\mathbf{G}\in {\mathbb{R}}^{m\times n}$ and $\mathbf{h}\in {\mathbb{R}}^m$ describe the $m$ affine inequality constraints.

6. $\mathbf{A}\in {\mathbb{R}}^{p\times n}$ and $\mathbf{b}\in {\mathbb{R}}^p$ describe the $p$ affine equality constraints.

9.12.2.2. Quadratically Constrained Quadratic Program

Definition 9.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:

(9.31)$$\begin{array}{rlrl}& \text{minimize }& & \frac{1}{2}{\mathbf{x}}^T{\mathbf{P}}_0\mathbf{x}+{\mathbf{q}}_0^T\mathbf{x}+r_0\\ & \text{subject to }& & \frac{1}{2}{\mathbf{x}}^T{\mathbf{P}}_i\mathbf{x}+{\mathbf{q}}_i^T\mathbf{x}+r_i\le 0& i=1,\dots ,m\\ & & & \mathbf{A}\mathbf{x}=\mathbf{b}\end{array}$$

where

1. $\mathbf{x}\in {\mathbb{R}}^n$ is the optimization variable.

2. ${\mathbf{P}}_i\in {\mathbb{S}}_{+}^n$ are symmetric positive semidefinite matrices for $i=0,\dots ,m$.

3. ${\mathbf{q}}_i\in {\mathbb{R}}^n$ and $r_i\in \mathbb{R}$ for $i=0,\dots ,m$.

4. $f_0(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^T{\mathbf{P}}_0\mathbf{x}+{\mathbf{q}}_0^T\mathbf{x}+r_0$ is a (convex) quadratic objective function.

5. $f_i(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^T{\mathbf{P}}_i\mathbf{x}+{\mathbf{q}}_i^T\mathbf{x}+r_i$ are (convex) quadratic inequality constraint functions for $i=1,\dots ,m$.

6. $\mathbf{A}\in {\mathbb{R}}^{p\times n}$ and $\mathbf{b}\in {\mathbb{R}}^p$ describe the $p$ affine equality constraints.

previous

9.11. Linear Programming

next

10. Subgradient Methods