An algorithm for finding the minimum-norm point in the intersection of a convex polyhedron and a hyperplane
type: Item
instance of: scholarly article
title: An algorithm for finding the minimum-norm point in the intersection of a convex polyhedron and a hyperplane
zbMATH Open document ID: 0830.90118
DOI: 10.1007/BF03167224
author: Satoru Fujishige
author: H. Sato
author: Ping Zhan
published in: Japan Journal of Industrial and Applied Mathematics
publication date: 1994-10-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 650935
zbMATH Keywords: minimum-norm point
zbMATH Keywords: convex polyhedron
zbMATH Keywords: algorithm
MaRDI profile type: Publication
cites work: An Efficient Computational Procedure for a Generalized Quadratic Programming Problem
cites work: Submodular functions and optimization
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: A FAST ALGORITHM FOR SOLVING LARGE SCALE MEAN-VARIANCE MODELS BY COMPACT FACTORIZATION OF COVARIANCE MATRICES
cites work: Linearly constrained estimation by mathematical programming
cites work: Finding the Point of a Polyhedron Closest to the Origin
cites work: Convex Analysis
cites work: A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes
cites work: Q5603731
cites work: A Nearest Point Algorithm for Convex Polyhedral Cones and Applications to Positive Linear Approximation.
cites work: Finding the nearest point in A polytope
full work available at URL: https://doi.org/10.1007/bf03167224
OpenAlex ID: W1964877955
Recommended article: An algorithm for solving the minimum-norm point problem over the intersection of a polytope and an affine set
Recommended article: An efficient algorithm for finding the minimum norm point in the convex hull of a finite point set in the plane
Recommended article: A DUAL ALGORITHM FOR FINDING THE MINIMUM-NORM POINT IN A POLYTOPE
Recommended article: A RECURSIVE ALGORITHM FOR FINDING THE MINIMUM NORM POINT IN AN UNBOUNDED POLYHEDRON
Recommended article: A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes
Recommended article: An interior-point method for minimizing convex functions on the convex hull of a point set
Recommended article: A finite algorithm for concave minimization over a polyhedron
Recommended article: An algorithm for concave integer minimization over a polyhedron
Recommended article: An optimal algorithm for computing a minimum nested nonconvex polygon
Recommended article: Minimization of convex functions on the convex hull of a point set
description: scientific article; zbMATH DE number 650935