Convex Optimization · Problem 10.1

Interior-point methods — Boyd & Vandenberghe

Mathematics — Optimization · nonsingularity-of-kkt-matrix

Problem

Nonsingularity of the KKT matrix. Consider the KKT matrix [PATA0],\begin{bmatrix} P & A^T \\ A & 0 \end{bmatrix}, where P∈S+nP \in \mathbf{S}^n_+, A∈Rp×nA \in \mathbf{R}^{p \times n}, and rank A=p<n\mathbf{rank}\, A = p < n. ((a)) Show that each of the following statements is equivalent to nonsingularity of the KKT matrix. • N(P)∩N(A)={0}\mathcal{N}(P) \cap \mathcal{N}(A) = \{0\}. • Ax=0, x≠0⟹xTPx>0Ax = 0,\, x \neq 0 \Longrightarrow x^T P x > 0. • FTPF≻0F^T P F \succ 0, where F∈Rn×(n−p)F \in \mathbf{R}^{n \times (n-p)} is a matrix for which R(F)=N(A)\mathcal{R}(F) = \mathcal{N}(A). • P+ATQA≻0P + A^T Q A \succ 0 for some Q⪰0Q \succeq 0. ((b)) Show that if the KKT matrix is nonsingular, then it has exactly nn positive and pp negative eigenvalues.

Related theory

Browse the problem library