1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Didn't you forget the exponent $-1$ in the operator that should be a contraction? (I think it is, in the $P$ norm). $\endgroup$ Dec 30 '17 at 15:22
  • 1
    $\begingroup$ @JeanDuchon ah yes, of course. Thanks! $\endgroup$ Dec 30 '17 at 22:04
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.