In quadratic programming, is the projection onto constraints optimal?

644 Views Asked by At

Consider the following quadratic program

$$ x^* := \arg \min_{ x \in X } \ \left\{ x^\top x + c^\top x \right\} \text{ subject 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 } \left\{ x^\top x + c^\top x \right\} \ \text{ subject 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

There are 1 best solutions below

0
On BEST ANSWER

$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^\top x - 2y^\top x + y^\top y$. Assume $y$ is known, so we only care $x^\top x - 2y^\top x$. Let $c=-2y$, we have $x^\top x +c^\top x$ and $y=-c/2$. Therefore, the Quadratic programing you listed is the projection of $-c/2$ on the constraint set.