Computational Science Asked on February 17, 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?
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$.
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 February 17, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP