An algorithm for solving the minimum-norm point problem over the intersection of a polytope and an affine set
type: Item
instance of: scholarly article
title: An algorithm for solving the minimum-norm point problem over the intersection of a polytope and an affine set
zbMATH Open document ID: 0986.90028
DOI: 10.1023/A:1004666028951
author: N. Delaunay
published in: Journal of Optimization Theory and Applications
publication date: 2002-06-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C20
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 1506900
zbMATH Keywords: minimum-norm point
zbMATH Keywords: quadratic programming
reviewed by: I. M. Stancu-Minasian
describes a project that uses: ZQPCVX
MaRDI profile type: Publication
cites work: Linearly constrained estimation by mathematical programming
cites work: A Nearest Point Algorithm for Convex Polyhedral Cones and Applications to Positive Linear Approximation.
cites work: An Efficient Computational Procedure for a Generalized Quadratic Programming Problem
cites work: Finding the Point of a Polyhedron Closest to the Origin
cites work: Submodular functions and optimization
cites work: An interior point algorithm for large scale portfolio optimization
cites work: An algorithm for finding the minimum-norm point in the intersection of a convex polyhedron and a hyperplane
cites work: A DUAL ALGORITHM FOR FINDING THE MINIMUM-NORM POINT IN A POLYTOPE
cites work: A DUAL ALGORITHM FOR FINDING A NEAREST PAIR OF POINTS IN TWO POLYTOPES
cites work: Finding the nearest point in A polytope
cites work: On structures of bisubmodular polyhedra
cites work: A FAST ALGORITHM FOR SOLVING LARGE SCALE MEAN-VARIANCE MODELS BY COMPACT FACTORIZATION OF COVARIANCE MATRICES
cites work: A numerically stable dual method for solving strictly convex quadratic programs
cites work: On the quadratic programming algorithm of Goldfarb and Idnani
cites work: A dual-active-set algorithm for positive semi-definite quadratic programming
cites work: Simplicial decomposition in nonlinear programming algorithms
cites work: An extension of the frank and Wolfe method of feasible directions
cites work: Restricted simplicial decomposition for convex constrained problems
cites work: Equivalence of some quadratic programming algorithms
cites work: Resolving degeneracy in quadratic programming
cites work: A practical anti-cycling procedure for linearly constrained optimization
full work available at URL: a:1004666028951
OpenAlex ID: W2128478726
description: scientific article; zbMATH DE number 1506900