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

From MaRDI portal
scientific article
Language Label Description Also known as
English
An algorithm for solving the minimum-norm point problem over the intersection of a polytope and an affine set
scientific article

    Statements

    An algorithm for solving the minimum-norm point problem over the intersection of a polytope and an affine set (English)
    0 references
    0 references
    16 June 2002
    0 references
    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.
    0 references
    minimum-norm point
    0 references
    quadratic programming
    0 references

    Identifiers