An algorithm for solving the minimum-norm point problem over the intersection of a polytope and an affine set (Q1579636): Difference between revisions

Considered is the problem of finding the minimum-norm point (problem P) over the intersection of a polytope and an affine set, where the polytope is expressed as the convex hull of a finite point set \(P= \{p_i\mid i\in I\}\) and the affine set is expressed as the intersection of \(k\) hyperplanes \(H_i= \{x\mid x\in\mathbb{R}^n, a^T_i x= b_i\}\), \(i= 1,\dots, k\), in the \(n\)-dimensional Euclidean space \(\mathbb{R}^n\). The authors propose an efficient algorithm for solving the problem (P) by using directly the original points and the hyperplanes, rather than treating the problem as a special case of the general quadratic programming problem. They prove the validity of the algorithm under a nondegeneracy assumption and give an algorithm for avoiding degeneracy. Finally, they give computational experiments to show the behavior of the proposed algorithm which validate the practical effectiveness of the algorithm.