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.



Norm of solution of quadratic program
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.


