Projection onto $\{x \in \mathbb{R}^n: Ax \leq b\}$

300 Views Asked by At

Consider the set $C = \{x \in \mathbb{R}^n: Ax \leq b\}$ where $A$ is an $m \times n$ real matrix, $b \in \mathbb{R}^m$ and the inequality is meant componentwise.

Is there a closed form to express $P_C(x)$, $P_C$ being the orthogonal projection onto $C$?

If not in general, is there at least a closed form in the particular case where $C$ has the form $\{x \in \mathbb{R}^n: x_i \in [l_i,u_i] \forall i, \sum_i x_i \in [l,u] \}$?

EDIT: To be precise, $P_C(x) := \arg \inf_{c \in C}||x-c||$.

1

There are 1 best solutions below

1
On

To see the difficulty with this request, notice that the set $C$ is defined by linear equalities, so that you could study the Lagrangian, $$ \mathcal{L} = ||x-c|| + \sum_{k=1}^K \mu_k (A_k'x - b_k) $$ which will have FONC's $$ D_{x_j} ||x-c|| + \sum_{k=1}^K \mu_k A_{kj} = 0 $$ for $j=1,...,n$, and complementary slackness conditions $\mu_k (A_k'x-b_k) =0$ for all $k=1,...,K$. Since $||\cdot||$ is strictly convex and the constraint set is presumably convex if the problem is well-posed, the KKT conditions are sufficient. Strict convexity of the norm implies a unique solution. It will occur on the interior of a face of the convex polytope defined by $A$ and $b$, or at a vertex where one or more constraints intersect.

If you knew which constraint(s) was the binding one, I think you could just solve the FONC's by hand (min norm subject to one linear constraint). But because you don't know which $\mu_k$ are positive and which are zero, there won't be a simple closed form solution. You could solve for a closed form solution for each of the $K$ constraints, I guess, depending on what your particular question is, but different solutions will depend on the different coefficients of the hyperplane you are minimizing the distance to.