An algorithm for finding the minimum-norm point in the intersection of a convex polyhedron and a hyperplane (Q1335567)

This paper considers the following problem: Minimize \(|x|\), subject to \(x= \sum_{i\in I} v_i p_i+ \sum_{j\in J} w_j d_j\), \(\sum_{i\in I} v_i= 1\), \(v_i\geq 0\) \((i\in I)\), \(w_j\geq 0\) \((j\in J)\), \(x\in H= \{x= (x(1),\dots, x(n)\}\in \mathbb{R}^n\mid x(n)= 0\}\), where \(P= \{p_i|i\in I\}\subset \mathbb{R}^n\) is a finite point set, \(D= \{d_j||d_j|= 1, j\in J\}\subset \mathbb{R}^n\}\) is a finite direction vector set. Assume that the problem is feasible. This is a problem of finding the minimum-norm point in the intersection of a convex polyhedron, which is the sum of the convex hull of \(P\) and the conical hull of \(D\), and a hyperplane \(H\). Its optimality condition is that \(x_0= (x_0(1),\dots, x_0(n- 1), 0)\) is an optimal solution iff there exists a real number \(\alpha\) such that \[ \begin{aligned} \forall i\in I, & \qquad (x_0(1),\dots, x_0(n- 1), \alpha) p_i\geq |x_0|^2,\\ \forall j\in J, & \qquad (x_0(1),\dots, x_0(n- 1), \alpha) d_j\geq 0.\end{aligned} \] Based on this condition, the authors construct an algorithm, which is practically efficient by computational experiments.