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\|$)

  • 1
    $\begingroup$ No, $P_X(y)$ might not satisfy $Ax=b$. $\endgroup$ – user856 Apr 25 '14 at 18:47
  • $\begingroup$ Thanks for your comment. I adjusted the question accordingly. $\endgroup$ – 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.


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.