Projection of a point onto a simple convex polytope

I have a convex polytope described by the intersection of a hypercube and two parallel lower and upper hyperplanes cutting through the hypercube. I want to find the projection of a point onto the polytope.

I read the question Projection of a point onto a convex polyhedra and see that the general problem of finding a projection onto a convex polytope can be solved with quadratic programming.

However, taken alone, projection onto a hypercube or a hyperplane is trivial. For the hypercube, each dimension is defined by a lower+upper bounds and we just pull each dimension within those bounds, which take $$O(n)$$ time in $$n$$ dimensions. For the hyperplane just find the projection onto it.

So I'm wondering whether there is simpler method for finding such a projection, maybe somehow combining the two independent projections.

• Sure. First, project onto the hypercube. Second, test to see if the point is between the hyperplanes; if so, you're done. If not, project the original point onto the closest hyperplane, and you're done. Or heck, do it the other way around! Project onto the closest hyperplane; if it's not in the hypercube, project onto the hypercube instead. (If I had a proof I'd make this an answer ;-)) May 23, 2017 at 4:41
• @MichaelGrant; ".. If not, project the original point onto the closest hyperplane, and you're done". But that point has to be in the hypercube. It may not be. What your saying is if one projection is not on the polytope, the other one must be? This is not correct. May 23, 2017 at 7:12
• Indeed it is not. That's what I get for answering when I should be in bed. May 23, 2017 at 12:28

You may want to check out Dykstra's projection algorithm (not to be confused with Dijkstra's algorithm). It precisely does what you want: It is an iterative method to compute the projection onto an intersection of convex sets using the projections onto these sets.

Note, that simply projecting onto the sets alone does not work. Consider the hypercube $[-1,1]^2$ and the hyperplane $\{x: x_1+x_2=1\}$. The projection of $(2,1)$ onto the intersection is $(1,0)$. If one first projects onto the cube, then onto the plane yields $(1/2,1/2)$, which is not the wanted projection.

• Yes, this is it. Ignore me above, please! May 23, 2017 at 12:29

From your description, I believe the optimization problem describing your projection is:

\begin{aligned} \min & \quad \frac{1}{2} ||x - y||_2^2 \\ \text{s.t.} & \quad \ell_i \leq x_i \leq u_i &\quad i = 1, \dots, n \\ & \quad \alpha \leq c^T x \leq \beta \end{aligned}

I believe that the best way would be a simple custom interior point method. The objective augmented with log-barriers for the constraints is:

$$A(x; \mu) = \frac{1}{2} ||x - y||_2^2 - \mu \left[ \sum_{i=1}^n \ln(u_i - x_i) + \sum_{i=1}^n \ln(x_i - \ell_i) + \ln(c^T x - \alpha) + \ln(\beta - c^T x) \right]$$

Fortunately, the Hessian has a nice structure of a diagonal matrix + two rank-one matrices, and can be easily inverted in linear time by applying the well-known Sherman–Morrison formula twice. So you get very quick convergence, and each iteration takes only linear time.

• Thanks for the answer. Yes the problem statement is correct. Interesting approach. I'm new at optimization and Dykstra's looks simple enough for even me to understand so going to go with that. I will come back and try to understand this later :). May 23, 2017 at 14:25
• That depends on weather the running time of Dykstra is fast enough. If it is, then use Dykstra. If it is not, then come back and try a different and possibly faster method. May 24, 2017 at 8:18