3.3 Study of unconstrained quadratic programs
As we saw in the previous section
In this section, we study in detail problems of the form
minimize 1 2 x ⊤ Q x − p ⊤ x subject to x ∈ R n \begin{array}{ll}
\minimize& \frac{1}{2}x^\top Q x -p^\top x\\
\st & x \in \mathbb{R}^n
\end{array} minimize subject to 2 1 x ⊤ Q x − p ⊤ x x ∈ R n where Q ∈ R n × n Q \in \mathbb{R}^{n\times n} Q ∈ R n × n Q ⊤ = Q Q^\top = Q Q ⊤ = Q p ∈ R n p \in \mathbb{R}^n p ∈ R n
when does (1) is there a unique solution? how do we express such solutions?
It is useful to keep in mind these identities. In doubt, check the Matrix Cookbook or learn how to re-derivate them easily!
f ( x ) f(x) f ( x ) ∇ f ( x ) \nabla f(x) ∇ f ( x ) ∇ 2 f ( x ) \nabla^2 f(x) ∇ 2 f ( x ) a ⊤ x a^\top x a ⊤ x a a a 0 x ⊤ A x x^\top A x x ⊤ A x ( A + A ⊤ ) x (A + A^\top)x ( A + A ⊤ ) x A + A ⊤ A + A^\top A + A ⊤
Preliminaries ¶ Gradient and Hessian of the objective function of QP
For the objective f 0 ( x ) = 1 2 x ⊤ Q x − p ⊤ x f_0(x) = \frac{1}{2}x^\top Q x -p^\top x f 0 ( x ) = 2 1 x ⊤ Q x − p ⊤ x
∇ f 0 ( x ) = 1 2 ( Q + Q ⊤ ) x − p = Q x − p ∇ 2 f 0 ( x ) = Q \begin{align*}
\nabla f_0(x) &= \frac{1}{2}(Q+Q^\top)x -p = Qx-p\\
\nabla^2 f_0(x) &= Q
\end{align*} ∇ f 0 ( x ) ∇ 2 f 0 ( x ) = 2 1 ( Q + Q ⊤ ) x − p = Q x − p = Q Diagonalization of the Hessian
Since Q Q Q Q Q Q U U U U ⊤ U = U U ⊤ = I n U^\top U = UU^\top = I_n U ⊤ U = U U ⊤ = I n
Q = U ⊤ D U , where D = [ λ 1 ( 0 ) ⋱ ( 0 ) λ n ] with λ 1 ≤ λ 2 ≤ … ≤ λ n . Q = U^\top D U, \text{ where } D = \begin{bmatrix}
\lambda_1 & & (0)\\
& \ddots & \\
(0) & &\lambda_n
\end{bmatrix}\quad \text{ with }\lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n. Q = U ⊤ D U , where D = ⎣ ⎡ λ 1 ( 0 ) ⋱ ( 0 ) λ n ⎦ ⎤ with λ 1 ≤ λ 2 ≤ … ≤ λ n . The properties of the eigenvalues of the Hessian permits to analyze the behavior of QPs.
Typology of solutions ¶ Case 1: λ 1 = λ min ( Q ) < 0 \lambda_1 = \lambda_{\min}(Q) < 0 λ 1 = λ m i n ( Q ) < 0 ¶ Let u 1 ∈ R n u_1 \in \mathbb{R}^n u 1 ∈ R n λ 1 \lambda_1 λ 1 z ∈ R z \in \mathbb{R} z ∈ R
f 0 ( z u 1 ) = λ 1 2 z 2 − z p ⊤ u 1 → ∣ z ∣ → + ∞ − ∞ f_0(zu_1) = \frac{\lambda_1}{2} z^2 - z\, p^\top u_1 \xrightarrow[|z| \to +\infty]{} -\infty f 0 ( z u 1 ) = 2 λ 1 z 2 − z p ⊤ u 1 ∣ z ∣ → + ∞ − ∞ This shows that f f f (1)
Case 2: λ 1 = λ min ( Q ) = 0 \lambda_1 = \lambda_{\min}(Q) = 0 λ 1 = λ m i n ( Q ) = 0 ¶ This case corresponds to Q ⪰ 0 Q \succeq 0 Q ⪰ 0
If p ∉ Im Q p \notin \operatorname{Im} Q p ∈ / Im Q ∇ f 0 ( x ) = 0 \nabla f_0(x) = 0 ∇ f 0 ( x ) = 0 f f f ∇ 2 f 0 ⪰ 0 \nabla^2 f_0 \succeq 0 ∇ 2 f 0 ⪰ 0 (1) If p ∈ Im Q p \in \operatorname{Im} Q p ∈ Im Q ∇ f 0 ( x ) = 0 \nabla f_0(x) = 0 ∇ f 0 ( x ) = 0 x 0 + n x_0 + \mathbf{n} x 0 + n x 0 x_0 x 0 n ∈ ker Q \mathbf{n} \in \ker Q n ∈ ker Q (1) Case 3: λ 1 = λ min ( Q ) > 0 \lambda_1 = \lambda_{\min}(Q) > 0 λ 1 = λ m i n ( Q ) > 0 ¶ This case corresponds to Q ≻ 0 Q \succ 0 Q ≻ 0
The matrix Q Q Q f f f ∇ 2 f ≻ 0 \nabla^2 f \succ 0 ∇ 2 f ≻ 0 x ^ = Q − 1 p \hat{x} = Q^{-1}p x ^ = Q − 1 p
If Q Q Q not positive semidefinite (λ min ( Q ) < 0 \lambda_{\min}(Q) < 0 λ m i n ( Q ) < 0 If Q Q Q positive semidefinite (λ min ( Q ) = 0 \lambda_{\min}(Q) = 0 λ m i n ( Q ) = 0 If p ∉ Im Q p \notin \operatorname{Im} Q p ∈ / Im Q If p ∈ Im Q p \in \operatorname{Im} Q p ∈ Im Q If Q Q Q positive definite (λ min ( Q ) > 0 \lambda_{\min}(Q) > 0 λ m i n ( Q ) > 0 x ^ = Q − 1 p \hat{x} = Q^{-1}p x ^ = Q − 1 p