# Quadratic programs: is the projection onto constraints optimal?

Consider the Quadratic Program $$x^* := \arg \min_{ x \in X } \ \{ x^\top x + c^\top x \} \ \text{ sub. to: } Ax=b$$ where $X \subset \mathbb{R}^n$ is a non-empty, convex, bounded polyhedron.

Define $$y := \arg \min_{ x \in \mathbb{R}^n } \ \{ x^\top x + c^\top x \} \ \text{ sub. to: } Ax=b$$

Suppose that for all $x$ such that $Ax = b$, it holds $A \left( P_X(x) \right) = b$.

Is it true that $x^*$ is the projection of $y$ onto $X$, i.e., $x^* = P_X\left( y\right)$?

(The projection is defined as $P_X(y) := \arg\min_{x \in X} \left\|x-y\right\|$)

• No, $P_X(y)$ might not satisfy $Ax=b$. – user856 Apr 25 '14 at 18:47
• Thanks for your comment. I adjusted the question accordingly. – user693 Apr 25 '14 at 19:44

$P_X(y):=arg min_{x\in X}\left \|x-y\right \|$ is equalivant to $P_X(y):=arg min_{x\in X}\left \|x-y\right \|^2$.
Expand $\left \|x-y\right \|^2$, we have $x^Tx - 2y^Tx + y^Ty$. Assume $y$ is known, so we only care $x^Tx - 2y^Tx$. Let $c=-2y$, we have $x^Tx +c^Tx$ and $y=-2c$. Therefore, the Quadratic programing you listed is the projection of $-2c$ on the constraint set.