Computing the closest point inside an intersection of half-spaces

Question

Is there an efficient way to compute, given a point, the closest point to it that's on the inside of an intersection of half-spaces?

For example, given the half-spaces a & b, the closest point to p that's "inside" the half-spaces is x. + denotes which side is "inside" the half-spaces a and b.

.p
       ^
       |
       |
       | x
   <---.--------------> b
       |       +
       |
       | +
       |
       v a

I'm particularly interested in an algorithm for half-spaces in 3D (planes)

My current line of thinking leads me to have to compute intersections of each half space, and then find the shortest point by picking from the shortest distance to each half-space and each intersection (line, point) that's within all the half-spaces. Is there a better way?

Answer 1

This can be modeled as a convex program $$\begin{align} \text{min.} \qquad & ||x-p||_2^2,\\ \text{s.t.} \qquad & Ax\leq b,\\ & x\in\mathbb{R}^3. \end{align}$$ and solved (in reasonable time) by standard solvers. Here's example code in julia

using Convex, SCS

# generate random problem data
m = 5;  n = 3
A = randn(m,n); b = randn(m,1); p=randn(3,1)

# define problem
x = Variable(n)
problem = minimize(sumsquares(x-p), [A*x<=b])

# solve
solve!(problem, SCSSolver())
println("Status $(problem.status) distance $(problem.optval)")