TransWikia.com

Project to nearest point on convex polyhedron

Computational Science Asked on November 11, 2021

I have a point $y in mathbb{R}^d$ and a convex polyhedron $mathcal{P}$ given as the intersection of half-spaces:

$$mathcal{P} = {x in mathbb{R}^d mid a_1 cdot x le b_1, dots, a_n cdot x le b_n}.$$

I would like to project $y$ onto the polyhedron, i.e., to find the nearest point $z in mathcal{P}$: in other words, to minimize $|y-z|_2$ subject to $z in mathcal{P}$. I know there are algorithms using quadratic programming, but I am hoping for a simple to implement method, even if it is not optimal.

Here is one possible incremental method: pick the halfspace that $y$ is furthest from, i.e., find the index $i$ that maximizes $a_i cdot y – b_i$, then project $y$ onto that halfspace, i.e., replace $y$ with $y’ = y – (a_i cdot y – b_i) a_i$, and repeat. (I have assumed, without loss of generality, the inequalities have been normalized so $|a_i|_2=1$.) While this might not yield the optimal solution, I hope that after it a fixed number of iterations it will get close to the optimal solution.

Is this a good method? Is there a better method that is simple to implement and does reasonably well?

One Answer

Assume that $y$ is not in the polyhedron (it is easy to check whether it is, and we know that the distance is zero in that case). If $y$ is outside then the closest point will be on the surface of the polyhedron.

So I came up with the following (horrible) algorithm, which will give you an upper bound. Let $y^0=y$.

  1. Find distance of point $y^n$ to all planes $a_icdot x = b_i$.
  2. Pick the closest one, save the distance, project $y$ on the plane and get $y^{n+1}$.
  3. Remove the plane from the list for the purposes of steps 1 and 2.
  4. Repeat steps 1-3 with until $y^{n+1}$ is inside the polyhedron.

The sum of the distances you saved during the process will be the upper bound. Since it is a convex polyhedron, this algorithm should terminate in at most 5 iteration. I am not so sure about this last claim, so I am going to remove it.

You can also potentially compute the distance between $y$ and $y^{n+1}$ to get a better upper bound.

Answered by Abdullah Ali Sivas on November 11, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP