On approximate solutions of systems of linear inequalities

By A. Hoffman. 1952

Subfields: Numerical Methods & Scientific Computing

How researchers see this paper

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

In Numerical Methods & Scientific Computing

Citations in the corpus

Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs (2016, methodology): “Lacoste-Julien & Jaggi (2015) showed that the largest possible pyramidal width of a polytope in dimension m (for a fixed diameter) is achieved by the probability simplex and is Θ(1/ √ m).”
Stochastic dual dynamic integer programming (2018, background): “By Hoffman’s lemma [43], there exists a constant Cn(un)”
Strong CHIP, normality, and linear regularity of convex sets (2005, unknown): “3) was proved by Hoffman [23].”
The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth (2015, background): “Almost parallel to work [19], the authors of [18, 11] deﬁned the global error bound (GEB) property in the spirit of Hoﬀman’s celebrated result on error bounds for systems of linear inequalities [7, 10].”
Characterization of local quadratic growth for strong minima in the optimal control of semi-linear elliptic equations (2013, background): “By Hoffman’s Lemma [24] for each x ∈ Ω there exists a smallest possible (finite) non-negative number κx, called the Hoffman constant, such that (4.49) dist(v, Cx) ≤ κx [ |Hu(x)v|+ 1{u(x)=a(x)}(−v)+ + 1{u(x)=b(x)}v+ ] , where for x ∈ R we set (x)+ := max{x, 0}.”
Characterizations of error bounds for lower semicontinuous functions on metric spaces (2004, unknown): “In this case, a constant σ such that (1) holds true is accordingly called a Hoffman constant , and we refine and extend the abstract part of our previous paper [4].”
Asynchronous Gossip-Based Random Projection Algorithms Over Networks (2013, background): “The set-regularity holds, for example, when each of the sets X j i , j ∈ Ii, is a half-space or a hyper-plane [30].”
A survey on error bounds for lower semicontinuous functions (2003, background): “The problem of finding conditions ensuring existence of a global error bound for the distance to a sublevel set of a lower semicontinuous function has been intensively discussed since the seminal work [20] by Hoffman.”
Linearly convergent away-step conditional gradient for non-strongly convex functions (2015, unknown): “Then for any x , y ∈ R n we have Lemma 2.2 (Hoffman’s Lemma [14]) Let X be a polyhedron deﬁned by X = { x ∈ R n : Ax ≤ a } , for some A ∈ R m × n and a ∈ R m , and let S = (cid:4) x ∈ R n : ˜ Ex = ˜ e (cid:5) where ˜ E ∈ R r × n and ˜ e ∈ R r .”
Degenerate Nonlinear Programming with a Quadratic Growth Condition (1999, methodology): “I am grateful to the referees for their suggestions and especially for pointing out reference [16].”
Levenberg–Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints (2004, unknown): “Due to Ho8man’s [12] famous error bound result, there exists (cid:24) ¿ 0 such that dist( x; X ∗ ) 6 (cid:5) F ( x ) (cid:5) + (cid:5) P X ( x ) (cid:5) : If x ∈ B (cid:8) ( x ∗ ) ∩ X for some x ∗ ∈ X ∗ , then P X ( x )=0.”
Error Bounds and Implicit Multifunction Theorem in Smooth Banach Spaces and Applications to Optimization (2004, unknown): “, [1, 10–12, 14, 15, 19, 22, 28, 30, 36, 42, 48, 49], .”
Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity (2018, background): “As a simple special case, if the sets Ci are all halfspaces of the form Ci = {x | 〈ai, x〉 ≤ bi}, then the Hoffman error bound [26] implies that ‖[Ax− b]+‖∞ ≥ cdist(x,X ?) for a constant c > 0; this result also holds in infinite dimensions under a constraint qualification [27].”