An algorithm for solving the minimum-norm point problem over the intersection of a polytope and an affine set
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.
scientific article; zbMATH DE number 1506900
scientific article