Norm of solution of quadratic program

Question

In a quadratic program (QP), do linear equality constraints always reduce the norm of the minimizer? Specifically, let $P \succ 0$, $A \in \mathsf{M}_{m\times n}$ and $q\in\mathbb{R}^n$. Define

$$x^* := \arg\min_x\,\tfrac{1}{2} x^\mathsf{T} P x - q^\mathsf{T}x$$

and

\begin{align} x_c^* &:= \arg\min_x \, \tfrac{1}{2} x^\mathsf{T} P x - q^\mathsf{T}x\\ &\quad\,\,\,\operatorname{subject to} \,\,Ax=0. \end{align}

Intuitively $\|x_c^*\| \leq \|x^*\|$, if not in the standard $\ell^2$ norm in the $P$ (or maybe $P^{-1}$) induced norm $\|x\|_P = \langle Px,x \rangle^{1/2}$, because I'd think that the solution $x_c^*$ is the $\|\cdot\|_P$ metric projection of $x^*$ onto $\ker A$, a closed convex set, and such a projection is a contraction.

Nevertheless, I'm having trouble showing this. Boyd and Vandenberghe [p.546] tell us $x_c^* = (I + P^{-1}A^\mathsf{T}(AP^{-1}A^\mathsf{T})^{-1}A)P^{-1}q$ while $x^* = P^{-1}q$. Hence it suffices to show the operator $I + P^{-1}A^\mathsf{T}(AP^{-1}A^\mathsf{T})^{-1}A$ is a contraction under some metric.

Unfortunately, I just sampled a random $A$ and positive $P$, and the above operator is not a contraction in the $\ell^2$-norm in general.

Questions:

• is $\|x_c^*\|_2 \leq \|x^*\|_2$ in general?
• if not, is this true under a different norm such as $\|\cdot\|_P$?

If possible, a bound not involving $A$ would be helpful.

Answer 1

We can show more, namely that if $K$ is a closed convex set (such as $\ker A$) containing the origin and \begin{align*} x_c^* &= \operatorname*{argmin}_x \,\frac{1}{2}x^\mathsf{T} P x - q^\mathsf{T}x\\ &\quad\,\,\operatorname{subj.to}\,\,x\in K \end{align*} then $\|x_c^*\|_P \leq \|x^*\|_P$. To see this, note that with $x^* = P^{-1}q$, \begin{align*} \frac{1}{2}\|x-x^*\|_P^2 &= \frac{1}{2}(x - x^*)^\mathsf{T} P (x - x^*)\\ &= \frac{1}{2}x^\mathsf{T}Px - (x^*)^\mathsf{T}Px + \frac{1}{2}(x^*)^\mathsf{T}Px^*\\ &= \frac{1}{2}x^\mathsf{T}Px - q^\mathsf{T}P^{-1}Px + \frac{1}{2}q^\mathsf{T}P^{-1}q\\ &= \frac{1}{2}x^\mathsf{T}Px - q^\mathsf{T}x + C \end{align*} where $C=\tfrac{1}{2}q^\mathsf{T}P^{-1}q$ is a constant. Hence \begin{align*} x_c^* &= \operatorname*{argmin}_x \,\,\,\|x - x^*\|_P\\ &\quad\,\,\operatorname{subj.to}\,\,x\in K \end{align*} is the $\|\cdot\|_P$-metric projection of $x^*$ onto $K$. Denote this projection by $\pi : \mathbb{R}^n \to K$. Since $K$ contains $0$ and $\pi$ is a contraction under $\|\cdot\|_P$ (standard result from convex analysis) we know $$ \|x_c^*\|_P = \|\pi(x^*)\|_P = \|\pi(x^*)-0\|_P = \|\pi(x^*)-\pi(0)\|_P \leq \|x^*-0\|_P = \|x^*\|_P $$ as desired.