# How to find projection to polyhedron

I have a problem:

find $min||\overrightarrow{x}||$ where $A\overrightarrow{x} \leqslant \overrightarrow{b}$

Is it possible to get analytic solution? Or which iteration method should I use?

-

It depends what norm you are talking about. If you mean the Euclidian norm, your problem is a quadratic program. It is equivalent to $$\min_x \ \tfrac{1}{2} \|x\|^2 \quad \text{subject to } Ax \leq b.$$ In general, we don't have the analytic solution of inequality-constrained problems. However, as it was mentioned in another answer, if $b \geq 0$, the solution of your problem is $x = 0$. If you knew ahead of time what subset of inequalities in $Ax \leq b$ are satisfied as equalities at the solution, i.e, $a_i^T x = b_i$ for $i \in \mathcal{A} \subseteq \{1, \dots, m\}$, say, then you could equivalently solve the equality-constrained problem $$\min_x \ \tfrac{1}{2} \|x\|^2 \quad \text{subject to } \tilde{A}x = \tilde{b},$$ where $\tilde{A}$ is the matrix with rows $a_i^T$ for $i \in \mathcal{A}$. The optimality conditions are that there exist a vector $y$ such that $$\begin{bmatrix} I & \tilde{A}^T \\ \tilde{A} & 0 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 0 \\ \tilde{b} \end{bmatrix}.$$ If $\tilde{A}$ has full row rank, the latter block matrix is nonsingular and you get a solution in closed form. Here you can use your favorite method for linear systems. You can factorize the coefficient matrix (the recommended factorization here is the so-called $LBL^T$, or Bunch-Parlett-Kaufman, factorization because this matrix is symmetric and indefinite). Or you can use an iterative method for symmetric systems, such as MINRES or SYMMLQ. You can't use the conjugate gradient method here. If $\tilde{A}$ doesn't have full rank, the situation is degenerate.

The problem is that you don't know $\mathcal{A}$ ahead of time. There are essentially two families of methods to solve your problem. The family of so-called "active-set" methods iteratively try to identify $\mathcal{A}$. They do this by generating approximations $x_k$ that solve equality-constrained problems $$\min_x \tfrac{1}{2} \|x\|^2 \quad \text{subject to} \ a_i^T x = b_i, \ i \in \mathcal{W},$$ where $\mathcal{W}$ is an approximation of $\mathcal{A}$ that is refined from iteration to iteration.

The family of interior-point methods will typically transform your problem to the nonlinear (but convex) sequence of subproblems $$\min_x \tfrac{1}{2} \|x\|^2 - \mu \sum_i \log(s_i) \quad \text{subject to} \ Ax + s = b,$$ where $s > 0$ are slack variables and $\mu > 0$ is a parameter. For each fixed value $\mu_k > 0$, an approximate solution $x_k$ is computed. The parameter $\mu$ is progressively decreased. As it approaches zero, your approximations $x_k$ approach a solution of the initial problem.

There's quite a bit of software available in both families of methods. Ask if you need.

You can play the same game for any other elliptic norm, i.e., $\|x\|_M^2 := x^T M x$ where $M = M^T$ is a positive definite matrix. The identity block in the above block matrix should just be changed to $M$.

If you mean to use another norm, e.g., $\|x\|_1$ or $\|x\|_{\infty}$, or any other polyhedral norm, it is possible to convert your problem to a linear program. The latter will have inequality constraints and in general, you won't have a solution in closed form but you can use any algorithm for linear programming to solve it (for instance the Simplex method or an interior-point method). For example, suppose you want to solve $$\min_x \ \|x\|_{\infty} \quad \text{subject to } Ax \leq b.$$ This problem is equivalent to $$\min_{x,t} \ t \quad \text{subject to } Ax \leq b, \ -t \leq x_i \leq t, \ i = 1, \ldots, n.$$ In the problem above, $t$ is a scalar variable.

If you mean to use the $\ell_1$ norm, then $$\min_x \ \|x\|_1 \quad \text{subject to } Ax \leq b.$$ This problem is equivalent to $$\min_{x,s} \ \sum_i s_i \quad \text{subject to } Ax \leq b, \ -s \leq x \leq s.$$ Note that here, $s$ is a vector of the same size as $x$.

-

When the polyedron contains origin $x=(0,0,\ldots,0)$, its obvious solution with optimal value $0$. Whenever its not, one way to approach it is by using Langrange Multipliers, since the minimum of the norm function will be obviously on the boudary of the polyedron, so we care only about equality contraints $Ax=b$.

We wish to find extreme (minimum) value of $\|x\|$ subject to $Ax=b$. We wrote down Langrange's function (assuming L2 norm):

$L(x,\lambda)=\|x\|+\lambda(Ax-b)$

By solving system of equations $\frac{\partial L(x,\lambda)}{\partial x}=0$ and $\frac{\partial L(x,\lambda)}{\partial\lambda}=0$ we find stacionary points where one will state for minimum value of the norm $x$ and second one for the maximum.

-