Finding the nearest point in A polytope

By Philip Wolfe. 1976

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Optimization

Citations in the corpus

On the Equivalence between Herding and Conditional Gradient Algorithms (2012, neutral): “For convex sets with finitely many extreme points, it converges in a finite number of iterations with higher (though still polynomial) iteration computational cost (Wolfe, 1976).”
On the Global Linear Convergence of Frank-Wolfe Optimization Variants (2015, methodology): “The major difference is that standard FCFW optimizes f over conv(A), whereas MNP implements the correction as a sequence of affine projections that potentially yield a different update, but can be computed more efficiently in several practical applications [35].”
Multi-Task Learning as Multi-Objective Optimization (2018, neutral): “It has been studied extensively (Makimoto et al., 1994; Wolfe, 1976; Sekitani and Yamamoto, 1993).”
SparseMAP: Differentiable Sparse Structured Inference (2018, methodology): “For this reason, we consider the active set method for constrained QPs: a generalization of Wolfe’s min-norm point algorithm (Wolfe, 1976), also used in structured prediction for the quadratic subproblems by Martins et al.”
A subgradient-type method for the equilibrium problem over the fixed point set and its applications (2009, background): “This will be the case, for example, when C is a linear variety, a closed ball, a closed cone or a closed polytope [2,7,34].”
Continuous Subdifferential Approximations and Their Applications (2003, methodology): “In numerical experiments, we used the Wolfe terminating algorithm (see [ 60 ]).”
Tight Bounds for Approximate Carathéodory and Beyond (2015, methodology): “is reason, practitioners typically employ the method called minimum-norm point algorithm, devised by Fujishige [10, 11, 1]. Traditionally this has been implemented using variants of Wolfe’s algorithm [32], but no provable convergence analysis has been available until recently. In [7] Chakrabarty et ”
Gradient Estimation with Stochastic Softmax Tricks (2020, background): “(cid:107) (cid:107) Efﬁcient projection algorithms exist for some convex sets [see 83, 23, 49, 13, and references therein], and more generic algorithms exist that only call linear solvers as subroutines [62].”
A finite algorithm for finding the projection of a point onto the canonical simplex of ∝n (1986, background): “Proof. Putx* =pK,(c),andlet i~ L By assumption, i~ L The left-hand side of equality ( 8 ) is strictly positive.”