Finding the nearest neighbor of a vector in a set

151 Views Asked by At

Given a set $P = \{ \textbf{x} \in \mathbb{R}^n \mid \mathrm{A}\textbf{x} \leq \textbf{b} \}$ and a vector $\textbf{y} \in \mathbb{R}^n$, where all of $\textbf{x}$'s and $\textbf{y}$'s coordinates are non-negative, and $\mathrm{A}$ is a matrix, $\textbf{b}$ is a vector forming a linear inequality.

How can I find $\textbf{y}$'s nearest neighbor in $P$, that is a $\textbf{z} \in P$ vector with minimal Euclidean distance from $\textbf{y}$?

1

There are 1 best solutions below

0
On

Your problem is equivalent to

$$\min \|x-y\|^2$$

s.t. $$Ax \le b, x \ge 0.$$

This is a quadratic programming problem. Do check out the solvers on the site.