arXiv:1710.02608v2 [math.OC] 3 Nov 2017

The minimum Euclidean-norm point in a convex polytope: Wolfe’s
combinatorial algorithm is exponential
Jesús De Loera
University of California, Davis
deloera@math.ucdavis.edu

Jamie Haddock
University of California, Davis
jhaddock@math.ucdavis.edu

Luis Rademacher
University of California, Davis
lrademac@ucdavis.edu

Abstract
The complexity of Philip Wolfe’s method for the minimum Euclidean-norm point problem
over a convex polytope has remained unknown since he proposed the method in 1974. The
method is important because it is used as a subroutine for one of the most practical algorithms
for submodular function minimization. We present the first example that Wolfe’s method takes
exponential time. Additionally, we improve previous results to show that linear programming
reduces in strongly-polynomial time to the minimum norm point problem over a simplex.

The fundamental algorithmic problem we consider here is: Given a convex polytope P ⊂ Rd ,
to find the point x ∈ P of minimum Euclidean norm, i.e., the closest point to the origin or what
we call its minimum norm point for short. We assume P is presented as the convex hull of finitely
many points p1 , p2 , . . . , pn (not necessarily in convex position). We wish to find
argmin

kxk2

subject to

x =
n
P

n
P

λk pk ,

k=1

λk = 1,

k=1

λk ≥ 0, for k = 1, 2, ..., n.
Finding the minimum norm point in a polytope is a basic auxiliary step in several algorithms
arising in many areas of optimization and machine learning; a subroutine for solving the minimum
norm point problem can be used to compute the projection of an arbitrary point to a polytope (indeed,
argminx∈P kx−ak2 is the same as a+argminy∈P −a kyk2 ). The minimum norm problem additionally
appears in combinatorial optimization, e.g., for the nearest point problem for transportation polytopes
[1, 4] and as a vital subroutine in Bárány and Onn’s approximation algorithm to solve the colorful
linear programming problem [2]. One of the most important reasons to study this problem is because
the minimum norm problem can be used as a subroutine for submodular function minimization
through projection onto the base polytope, as proposed by Fujishige [8]. Submodular minimization
is useful in machine learning, where applications such as large scale learning and vision require
efficient and accurate solutions [16]. The problem also appears in optimal loading of recursive
1

neural networks [6]. The Fujishige-Wolfe algorithm is currently considered an important practical
algorithm in applications [10, 9, 5]. Furthermore, Fujishige et al. first observed that linear programs
may be solved by solving the minimum norm point problem [9], so this simple geometric problem is
also relevant to the theory of algorithmic complexity of linear optimization.
One may ask about the complexity of other closely related problems. First, it is worth remembering that Lp norm minimization over a polyhedron is NP-hard for 0 ≤ p < 1 (see [11] and the
references therein), while for p ≥ 1 the convexity of the norm allows for fast computation. One
can prove that it is NP-hard to find a closest vertex of a convex polytope given by inequalities.
The reduction for hardness is to the directed Hamiltonian path problem: Given a directed graph
G = (V, A) and two distinct vertices s, t ∈ V , one aims to decide whether G contains a directed
Hamiltonian path from s to t. It is well-known there is a polytope represented by inequalities whose
vertices correspond to the characteristic vectors of a directed path joining s to t in G. See e.g.,
Proposition 2.6 in the book [17] for the details, including the explicit inequality description of this
polytope. Finally, by a change of variable yi = 1 − xi , changing zeros to ones and vice versa, the
minimum Euclidean norm vertex becomes precisely the “longest path from s to t”, solving the
directed Hamiltonian path problem.
Since the Euclidean norm is a convex quadratic form, the minimum norm point problem is
a special case of convex quadratic optimization problem. Indeed, it is well-known that a convex
quadratic programming problem can be approximately solved in polynomial time; that is, some
point y within distance ε of the desired minimizing point x may be found in polynomial time with
respect to log 1ε . This can be done either through several iterative (convergent) algorithms, such
as the Ellipsoid method [15] and interior-point method techniques [3]. Each of these are methods
whose complexity depends upon the desired accuracy. However, an approximate numerical solution
is inconvenient when the application requires more information, e.g., if we require to know the face
that contains the minimum norm point. Numeric methods that converge to a solution and require
further rounding are not as convenient for this need.
In this paper, we focus on combinatorial algorithms that rely on the structure of the polytope.
There are several reasons to study the complexity of combinatorial algorithms for the minimum
norm problem. On the one hand, the minimum norm problem can indeed be solved in stronglypolynomial time for some polytopes; most notably in network-flow and transportation polytopes
(see [4, 1, 22], and references therein, for details). On the other hand, while linear programming
reduces to the minimum norm problem, it is unknown whether linear programming can be solved in
strongly-polynomial time [20], thus the complexity of the minimum norm point problem could also
impact the algorithmic efficiency of linear programming and optimization in general. For all these
reasons it is natural to ask whether a strongly-polynomial time algorithm exists for the minimum
norm problem for general polytopes.
Our contributions:
• In 1974, Philip Wolfe proposed a combinatorial method that can solve the minimum-norm point
problem exactly [24, 23]. Since then, the complexity of Wolfe’s method was not understood. In
Section 1 we present our main contribution and give the first example that Wolfe’s method has
exponential behavior. This is akin to the well-known Klee-Minty examples showing exponential
behavior for the simplex method [14]. Prior work by [5] showed that after t iterations, Wolfes
method returns an O(1/t)-approximate solution to the minimum norm point on any polytope.

2

• As we mentioned earlier, an enticing reason to explore the complexity of the minimum norm
problem is its intimate link to the complexity of linear programming. It is known that linear
programming can be polynomially reduced to the minimum norm point problem [10]. In
Section 2, we strengthen earlier results showing that linear optimization is strongly polynomial
time reducible to the minimum norm point problem on a simplex.

1

Wolfe’s method exhibits exponential behavior

For convenience of the reader and to set up notation we start with a brief description of Wolfe’s
method. We will then describe our exponential example in detail, proving the exponential behavior
of Wolfe’s method. First, we review two important definitions. Given a set of points S ⊆ Rd , we
have two minimum-norm points to consider. One is the affine minimizer which is the point of
minimum norm in the affine hull of S, argminx∈aff(S) kxk2 . The second is the convex minimizer
which is the point of minimum norm in the convex hull of S, argminx∈conv(S) kxk2 . Note that solving
for the convex minimizer of a set of points is exactly the problem we are solving, while solving for
the affine minimizer of a set of points is easily computable.

1.1

A brief review of Wolfe’s combinatorial method

Wolfe’s method is a combinatorial method for solving the minimum norm point problem over a
polytope, P = conv(p1 , p2 , ..., pn ) ⊂ Rd , introduced by P. Wolfe in [24]. The method iteratively
solves this problem over a sequence of subsets of no more than d + 1 affinely independent points
from p1 , ..., pn and it checks to see if the solution to the subproblem is a solution to the problem
over P using the following lemma due to Wolfe. We call this Wolfe’s criterion.
Lemma 1 (Wolfe’s criterion [24]). Let P = conv(p1 , p2 , ..., pn ) ⊂ Rd , then x ∈ P is the minimum
norm point in P if and only if
xT pj ≥ kxk22

for all

j ∈ [n].

Note that this tells us that if there exists a point pj so that xT pj < kxk22 then x is not the
minimum norm point in P . We say that pj violates Wolfe’s criterion and using this point should
decrease the minimum norm point of the current subproblem.
It should be observed that just as Wolfe’s criterion is a rule to decide optimality over conv(P ),
one has a very similar rule for deciding optimality over the affine hull, aff(P ).
Lemma 2 (Wolfe’s criterion for the affine hull). Let P = {p1 , p2 , ..., pn } ⊆ Rd be a non-empty
finite set of points. Then x ∈ aff P is the minimum norm point in aff P iff for all pi ∈ P we have
pTi x = kxk22 .
Pn
Pn
Proof. (⇐) Let p =
i=1 ρi pi with
i=1 ρi = 1 be an arbitrary point in aff P and suppose
pTi x = kxk22 for i = 1, 2, ..., n. We have
n
n
X
X
T
p x=
ρi pi x =
ρi kxk22 = kxk22 .
T

i=1

i=1

Then 0 ≤ kp − xk22 = kpk22 − 2pT x + kxk22 = kpk22 − kxk22 and so kxk22 ≤ kpk22 .
3

(⇒) Suppose x ∈ aff P is the minimum norm point in aff P . Suppose that xT (pi − x) 6= 0 for
T
i −x)
some i ∈ [n]. First, consider the case when xT (pi − x) > 0 and define 0 <  < 2xkp (p
2 . Then we
i −xk2
have
k(1 + )x − pi k22 = kx + (x − pi )k22 = kxk22 − 2xT (pi − x) + 2 kpi − xk22 < kxk22
since 0 < 2 kpi − xk22 < 2xT (pi − x). This contradicts our assumption that x is the minimum norm
point in aff P . The case when xT (pi − x) < 0 is likewise proved by considering k(1 − )x + pi k22
T
i −x)
. Thus, we have that xT (pi − x) = 0.
with 0 <  < − 2xkp (p
−xk2
i

2

We say a set of affinely independent points S is a corral if the affine minimizer of S lies in
the relative interior of conv S. Note that singletons are always corrals. Carathéodory’s theorem
implies that the minimum norm point of P will lie in the convex hull of some corral of points among
p1 , ..., pn . The goal of Wolfe’s method is to search for a corral containing the (unique) minimizing
point.
The pseudo-code in Method 1 below presents the iterations of Wolfe’s method. It is worth
noticing that some steps of the method can be implemented in more than one way and Wolfe proved
that all of them lead to a correct algorithm (for example, the choice of the initial point in line 2).
We therefore use the word method to encompass all these variations and we discuss specific choices
when they are relevant to our analysis of the method.
Method 1 Wolfe’s Method [24]
1: procedure Wolfe(p1 , p2 , ..., pn )
2:
Initialize x = pi for some i ∈ [n], initial corral C = {pi }, I = {i}, λ = ei , α = 0.
3:
while x 6= 0 and there exists pj with xT pj < kxk22 do
4:
Add pj to the potential corral: C = C ∪ {pj }, I = I ∪ {j}.
5:
Find the affine minimizer of C, y = argminy∈aff(C) kyk2 , and the affine coefficients, α.
6:
while y is not a strict convex combination of points in C; αi ≤ 0 for some i ∈ I do
i
7:
Find z, closest point to y on [x, y] ∩ conv(C); z = θy + (1 − θ)x, θ = mini∈I:αi ≤0 λiλ−α
.
i
8:
Select pi ∈ {pj ∈ C : θαj + (1 − θ)λj = 0}.
9:
Remove this point from C; C = C − {pi }, I = I − {i}, αi = 0, λi =
P0.
10:
Update x = z and the convex coefficients, λ, of x for C; solve x = pi ∈C λi pi for λ.
11:
Find the affine minimizer of C, y = argminy∈aff(C) kyk2 and the affine coefficients, α.
12:
end while
13:
Update x = y and λ = α.
14:
end while
15:
Return x.
16: end procedure
The subset of points being considered as the potential corral is maintained in the set C. Iterations
of the outer-loop, where points are added to C, are called major cycles and iterations of the innerloop, where points are removed from C, are called minor cycles. The potential corral, C, is named
so because at the beginning of a major cycle it is guaranteed to be a corral, while within the
minor cycles it may or may not be a corral. Intuitively, a major cycle of Wolfe’s method inserts an
improving point which violates Wolfe’s criterion (pj so that xT pj < kxk22 ) into C, then the minor
4

cycles remove points until C is a corral, and this process is repeated until no points are improving
and C is guaranteed to be a corral containing the minimizer.
It can be shown that this method terminates because the norm of the convex minimizer of the
corrals visited monotonically decreases and thus, no corral is visited twice [24]. Like [5], we sketch
the argument in [24]. One may see that the norm monotonically decreases by noting that the convex
minimizer over the polytope may result from one of two updates to x, either at the end of a major
cycle or at the end of a minor cycle. Let C be the corral at the beginning of a major cycle (line 3 of
Method 1) and let x be the current minimizer, then the affine minimizer y has norm strictly less
than that of x by Lemma 2, uniqueness of the affine minimizer and the fact that pTi x < kxk22 where
pi is the added point. Now, either x is updated to y or a minor cycle begins. Let S be the potential
corral at the beginning of a minor cycle (line 6 of 1), let x be the current convex combination of
points of S and let y be the affine minimizer of S. Note that z is a proper convex combination of x
and y and since kyk2 < kxk2 , we have kzk2 < kxk2 . Thus, we see that every update of x decreases
its norm. Note that the number of minor cycles within any major cycle is bounded by d + 1, where
d is the dimension of the space. Thus, the total number of iterations is bounded by the number of
corrals visited multiplied
P bynd + 1. It is nevertheless not clear how the number of corrals grows,
beyond the bound of d+1
i=1 i .
Within the method, there are two moments at which one may choose which points to add to the
potential corral. Observe that at line 2 of the pseudocode, one may choose which initial point to add
to the potential corral. In this paper we will only consider one initial rule, which is to initialize with
the point of minimum norm. Observe that at line 4 of the pseudocode, there are several potential
choices of which point to add to the potential corral. Two important examples of insertion rules
are, first, the minnorm rule which dictates that one chooses, out of the improving points for the
potential corral, to add the point pj of minimum norm. Second, the linopt rule dictates that one
chooses, out of the improving points for the potential corral, to add the point pj minimizing xT pj .
Notice that insertion rules are to Wolfe’s method what pivot rules are to the Simplex Method (see
[21] for a summary).
As with pivot rules, there are advantages and disadvantages of insertion rules. For example, the
minnorm rule has the advantage that its implementation only requires an initial ordering of the
points, then in each iteration it need only to search for an improving point in order of increasing
norm and to add the first found. However, the linopt insertion rule has the advantage that, if
the polytope is given in H-representation (intersection of halfspaces) rather than V-representation
(convex hull of points), one may still perform Wolfe’s method by using linear programming to find
pj minimizing xT pj over the polytope. In other words, Wolfe’s method does not need to have
the list of vertices explicitly given, but suffices to have a linear programming oracle that provides
the new vertex to be inserted. This feature of Wolfe’s method means that each iteration can be
implemented efficiently even for certain polyhedra having too many vertices and facets: specifically,
over zonotopes (presented as a Minkowski sum of segments) [9] and over the base polyhedron of a
submodular function [8].
Now we present examples that show that the optimal choice of insertion rule depends on the
input data. We first present a simple example where the minnorm rule outperforms the linopt rule.
That is, the minnorm insertion rule is not in obvious disadvantage to the linopt rule. In Section 1.2,
we present a family of examples where the minnorm rule takes exponential time, while we expect
the linopt rule to take polynomial time in this family.
The first example shows that instances can have different performance depending on the choice

5

Figure 1: The simplex P = conv{p1 , p2 , p3 , p4 } ⊂ R3 where p1 = (0.8, 0.9, 0), p2 =
(1.5, −0.5, 0), p3 = (−1, −1, 2) and p4 = (−4, 1.5, 2).
Major Cycle

Minor Cycle

C

x

y

0

0

{p1 }

p1

1

0

{p1 , p2 }

p1

(1, 0.5, 0)

2

0

{p1 , p2 , p3 }

(1, 0.5, 0)

(0.3980, 0.199, 0.5473)

3

0

{p1 , p2 , p3 , p4 }

(0.3980, 0.199, 0.5473)

(0, 0, 0)

3

1

{p1 , p2 , p4 }

(0.2878, 0.1439, 0.3957)

(0.1980, 0.0990, 0.4455)

Table 1: iterations for minnorm insertion rule
of insertion rule. Consider the simplex P shown in Figure 1 (we present the coordinates of vertices
in the figure’s caption). We list the steps of Wolfe’s method on P for the minnorm and linopt
insertion rules in Tables 1 and 2 and demonstrate a single step from each set of iterations in Figure
2. Each row lists major cycle and minor cycle iteration number, the vertices in the potential corral,
and the value of x and y at the end of the iteration (before x = y for major cycles). Note that the
vertex p4 is added to the potential corral twice with the linopt insertion rule, as evidenced in Table
2.
Currently, there are examples of exponential behavior for the simplex method for all known
deterministic pivot rules. It is our aim to provide the same for insertion rules on Wolfe’s method. In
the next subsection we will present the first exponential-time example using the minnorm insertion
rule.

1.2

An exponential lower bound for Wolfe’s method

To understand our hard instance, it is helpful to consider first a simple instance that shows an
inefficiency of Wolfe’s method. The example is a set of points where a point leaves and reenters
the current corral: 4 points in R3 , (1, 0, 0), (1/2, 1/4, 1), (1/2, 1/4, −1), (−2, 1/4, 0). If one labels
the points 1, 2, 3, 4, the sequence of corrals with the minnorm rule is 1, 12, 23, 234, 14, where point
1 enters, leaves and reenters (For succintness, sets of points like {a, b, c} may be denoted abc.).
The idea now is to recursively replace point 1 (that reenters) in this construction by a recursively
constructed set of points whose corrals are then considered twice by Wolfe’s method. To simplify
the proof, our construction uses a variation of this set of 4 points with an additional point and
6

Major Cycle

Minor Cycle

C

x

y

0

0

{p1 }

p1

1

0

{p1 , p4 }

p1

(0.2219, 0.9723, 0.2409)

2

0

{p1 , p4 , p3 }

(0.2219, 0.9723, 0.2409)

(0.2848, 0.3417, 0.5810)

2

1

{p1 , p3 }

(0.2835, 0.3548, 0.5739)

(0.2774, 0.3484, 0.5807)

3

0

{p1 , p3 , p2 }

(0.2774, 0.3484, 0.5807)

(0.3980, 0.199, 0.5473)

4

0

{p1 , p2 , p3 , p4 }

(0.3980, 0.199, 0.5473)

(0, 0, 0)

4

1

{p1 , p2 , p4 }

(0.2878, 0.1439, 0.3957)

(0.1980, 0.0990, 0.4455)

Table 2: iterations for linopt insertion rule

Figure 2: Left: Major cycle 1, minor cycle 0 for the linopt rule on P illustrates the end of a major
cycle; the affine minimizer y1 ∈ relint(conv{C}) = relint(conv{p1 , p4 }). Right: Major cycle 2,
minor cycle 0 for the linopt rule on P illustrates the beginning of a minor cycle; the affine minimizer
y2 6∈ relint(conv{C}) = relint(conv{p1 , p4 , p3 }) and the vertex p4 will be removed in the next
minor cycle.
modified coordinates. This modified construction is depicted in Fig. 3, where point 1 corresponds to
a set of points P (d − 2), points 2,3 correspond to points pd , qd and point 4 corresponds to points
rd , sd .
The high-level idea of our exponential lower bound example is the following. We will inductively
define a sequence of instances of increasing dimension of the minimum norm point problem. Given
an instance in dimension d − 2, we will add a few dimensions and points so that, when given to
Wolfe’s method, the number of corrals of the new augmented instance in dimension d has about twice
the number of corrals of the input instance in dimension d − 2. More precisely, our augmentation
procedure takes an instance P (d − 2) in Rd−2 , adds two new coordinates and adds four points,
pd , qd , rd , sd , to get an instance P (d) in Rd .
Points pd , qd are defined so that the method on instance P (d) goes first through every corral
given by the points in the prior configuration P (d − 2) and then goes to corral pd qd . To achieve this
under the minimum norm rule, the four new points have greater norm than any point in P (d − 2)
and they are in the geometric configuration sketched in Fig. 3.
At this time, no point in P (d − 2) is in the current corral and so, if a point in P (d − 2) is part of

7

Figure 3: Left: In this view of P (d), the point labeled P (d − 2) represents all points from
P (d − 2) embedded into Rd . The axis labeled
Rd−2 represents the (d − 2)-dimensional subspace,

∗
span (P (d − 2)) projected into span od−2 . Right: A two-dimensional view of P (d) projected along
the xd coordinate axis.
the optimal corral, it will have to reenter, which is expensive. Points rd , sd are defined so that rd sd
is a corral after pd qd , but now every point in P (d − 2) is improving according to Wolfe’s criterion
and may enter again. Specifically, every corral in P (d − 2), with rd sd appended, is visited again.
Before we start describing the exponential example in detail, we wish to review preliminary
lemmas of independent interest which will be used in the arguments. The first lemma demonstrates
that orthogonality between finite point sets allows us to easily describe the affine minimizer of their
union. Figure 4 shows two such situations, one in which the affine hull of the union of the point sets
span all of R3 and one in which it does not.
Lemma 3. Let A ⊆ Rd be a proper linear subspace. Let P ⊆ A be a non-empty finite set. Let
Q ⊆ A⊥ be another non-empty finite set. Let x be the minimum norm point in aff P . Let y be the
minimum norm point in aff Q. Let z be the minimum norm point in aff(P ∪ Q). We have:
1. z is the minimum norm point in [x, y] and therefore, if x 6= 0 or y 6= 0, then z = λx + (1 − λ)y
kyk22
with λ = kxk2 +kyk
2.
2

2

2. If x 6= 0 and y 6= 0, then z is a strict convex combination of x and y.
3. If x 6= 0, y 6= 0 and P and Q are corrals, then P ∪ Q is also a corral.
Proof. If x = y = 0 then part 1 follows immediately. If at least one of x, y is non-zero, then they
are also distinct by the orthogonality assumption. Given two distinct points a, b, one can show that
the minimum norm point in the line through them is λa + (1 − λ)b where λ = bT (b − a)/kb − ak22 .
For points x, y as in the statement, the minimum norm point in aff(x ∪ y) is z0 = λx + (1 − λ)y
kyk22
0
with λ = kxk2 +kyk
2 ∈ [0, 1]. Thus, z is also the minimum norm point in [x, y]. We will now use the
2

2

optimality condition in Lemma 2 to conclude that z0 = z. Let p ∈ P . Then pT z0 can be computed
in two steps: First project p onto span (x, y) (a subspace that contains z0 ). This projection is x by
optimality of x. Then project onto z0 . This shows that pT z0 = xT z0 = kz0 k22 . A similar calculation
shows qT z0 = kz0 k22 for any q ∈ Q. We conclude that z0 is the minimum norm point in aff(P ∪ Q).
This proves part 1.
8

Figure 4: Examples of Lemma 3. Left: the affine hull of P ∪ Q is not full dimensional, and thus the
affine minimizer lies at z along the line segment connecting x = p and y. Right: the convex hull of
P ∪ Q is full-dimensional and thus the affine hull of P ∪ Q includes O which is the affine minimizer.
Part 2 follows from our expression for λ above, which is in (0, 1) when x 6= 0 and y 6= 0.
Under the assumptions of part 3, we have that x is a strict convex combination of P and y is a
strict convex combination of Q. This combined with the conclusion of part 2 gives that z is a strict
convex combination of P ∪ Q. The claim in part 3 follows.
The following lemma shows conditions under which, if we have a corral and a new point that
only has components along the minimum norm point of the corral and along new coordinates, then
the corral with the new point added is also a corral. Moreover, the new minimum norm point is a
convex combination of the old minimum norm point and the added point. Figure 5 gives an example
of such a situation in R3 . Denote by span (M ) the linear span of the set M .
Lemma 4. Let P ⊆ Rd be a finite set
 of points that is a corral. Let x be the minimum norm point
in aff P . Let q ∈ span x, span (P )⊥ , and assume qT x < min kqk22 , kxk22 . Then P ∪ {q} is a
corral. Moreover, the minimum norm point y in conv(P ∪ {q}) is a (strict) convex combination of
q and the minimum norm point of P : y = λx + (1 − λ)q with λ = qT (q − x)/kq − xk22 .
Proof. Let y be the minimum norm point in aff(P ∪ {q}). Intuitively, y should be the minimum
norm point in the line through x and q. We will characterize y and show that it is a strict convex
combination of P ∪{q} (which implies that it is a corral). Given two points a, b, one can show that the
minimum norm point in the line through them is λa + (1 − λ)b where λ = bT (b − a)/kb − ak22 . Thus,
we define y = λx + (1 − λ)q with λ = qT (q − x)/kq − xk22 . By definition we have y ∈ aff(P ∪ {q}).
The minimality of the norm of y follows from the optimality condition in Lemma 2. It holds by
construction for q. It also holds for p ∈ P : The projection of p onto y can be computed in two
steps. First, project onto span (x, q) (a subspace that contains y), which is x by optimality of x.
Then project onto y. This shows that pT y = xT y = kyk2 (the second equality by optimality of y).
We conclude that y is of minimum norm in aff P ∪ {q}.
9

Figure 5: An example of Lemma 4 in which point q satisfies all assumptions and P ∪ {q} is a
corral. The hyperplanes are labeled with their defining properties and demonstrate that qT x <
min{kxk2 , kqk2 }. The minimizer of P ∪ {q} lies at the intersection of the blue, vertical axis and
conv(P ∪ {q}).
To conclude that P ∪ {q} is a corral, we show that y is a strict convex combination of points
P ∪ {q}. It is enough to show that y is a strict convex combination of x and q. We have
λ = qT (q−x)/kq−xk22 =
kxk22 −qT x
kq−xk22

kqk22 −qT x
kq−xk22

> 0 by assumption. We also have 1−λ = −xT (q−x)/kq−xk22 =

> 0 by assumption.

Our last lemma shows that if we have points in two orthogonal subspaces, A and A⊥ , then
adding a point from A⊥ to a set from A does not cause any points from A that previously did not
violate Wolfe’s criterion (for the affine minimizer) to violate it. Figure 6 demonstrates this situation.
Lemma 5. For a point z define Hz = {w ∈ Rn : wT z < kzk22 }. Suppose that we have an instance
of the minimum norm point problem in Rd as follows: Some points, P , live in a proper linear
subspace A and some, Q, in A⊥ . Let x be the minimum norm point in aff P and y be the minimum
norm point in aff(P ∪ Q). Then Hy ∩ A = Hx ∩ A.
the span of x and Q. We first show y ∈PB. To see this, suppose not. Decompose
Proof. Let B be P
y as y = λv + q∈Q µq q, where v ∈ aff P and λ +
µq = 1. Decompose v as v = u + x
where u ⊥ x and u ∈ A (this is P
possible because v − x is orthogonal toPx, by optimality of x,
Lemma 2). Thus,
P y = λu + λx + q∈Q µq q with λu orthogonal to λx + q∈Q µq q. This implies
that y0 = λx + q∈Q µq q has a smaller norm than y and y0 ∈ aff(P ∪ Q). This is a contradiction.
To conclude, we have Hy ∩ A is a halfspace in A whose normal is parallel to the projection of y
onto A (It is helpful to understand how to compute the intersection of a hyperplane with a subspace.
If Tg = {w : w · g = 1} and S is a linear subspace, then Tg ∩ S = {w ∈ S : w · projS g = 1}. In
other words, in order to intersect a hyperplane with a subspace we project the normal.) That is, it
is parallel to x. But that halfspace must also contain x on its boundary. Thus, that halfspace is
equal to Hx ∩ A.

10

Figure 6: An example of Lemma 5 in which adding points Q from A⊥ to points P from A create a
new affine minimizer, z, but the points satisfying Wolfe’s criterion in A remain the same. Note that
both hyperplanes intersect at the affine minimizer of P , so the halfspace intersections with A are
the same.
We will now describe our example in detail. The simplest version of our construction uses square
roots and real numbers. We present instead a version with a few additional tweaks so that it only
involves rational numbers.
Let P (1) = {1} ⊆ Q. For odd d > 1, let P (d) be a list of points in Qd defined inductively as
follows: Let o∗d denote the minimum norm point in conv P (d). Let Md := maxp∈P (d) kpk1 , which is
a rational upper bound to the maximum 2-norm among the points in P (d). (For a first reading
one can let Md be the maximum 2-norm among points in P (d), which leads to an essentially
equivalent instance except that it is not rational.) Similarly, let md = ko∗d k∞ , which is a rational
lower bound to the minimum norm among points in conv P (d). (Again, for a first reading one can
define md = ko∗d k2 which leads to an essentially equivalent instance, except that it is not rational.)
We finally present the example. If we identify P (d) with a matrix where the points are rows,
then the points in P (d) are given by the following block matrix:


P (d − 2)
0
0
md−2

 1 o∗
Md−2
4
 12 d−2

md−2
∗

−(Md−2 + 1) 
P (d) =  2 od−2
4
.
md−2

0
Md−2 + 2 
0

4
md−2
4

−(Md−2 + 3).

The last four rows of the matrix P (d) are the points pd , qd , rd , sd of the configuration. For a
picture of the case of P (3) see Figure 7.

11

Figure 7: Left: Three-dimensional view of P (3). Right: A two-dimensional view of P (3) projected
along the x3 coordinate axis.
Remark: First note that strictly speaking P (d−2) ⊂ Qd−2 , and that we are defining an embedding
of it into Qd , for which we have to use a recursive process. To avoid unnecessary notation, we
will abuse the notation. The point vd−2 denotes both a point of P (d − 2) and of the subsequent
P (d), i.e., vd−2 = (v, 0, 0) will be the identical copy of vd−2 within P (d), but we add two extra zero
coordinates. Depending on the context vd−2 will be understood as both a (d − 2)-dimensional vector
or as a d-dimensional vector (e.g., when doing dot products). The points of P (d − 2) become a
subset of the point configuration P (d) by padding extra zeros. See Figures 3 and 8 which illustrate
this embedding and address our visualizations of these sets in three dimensions.

Figure 8: As described in Figure 3, the axis labeled Rd−2 represents the (d −
 2)-dimensional subspace
∗
span (P (d − 2)) projected onto the one dimensional subspace span od−2 . Here we illustrate that
the projection of the set P (d − 2) forms a ‘cloud’ of points and the convex hull of this projection
has many fewer faces than the unprojected convex hull.
 For simplicity, we will visualize P (d − 2)
∗
and subsets of P (d − 2) as a single point in span od−2 as in Figure 3.
Theorem 6. Consider the execution of Wolfe’s method with the minnorm point rule on input P (d)
12

where d = 2k − 1. Then the sequence of corrals has length 5 · 2k−1 − 4.
Proof. Points in P (d) are shown in order of increasing norm. Let pd , qd , rd , sd denote the last four
points of P (d), respectively. Let C(d) denote the ordered sequence of corrals in the execution of
Wolfe’s method on P (d). Let O(d) denote the last (optimal) corral in C(d).
The rest of the proof will establish that the sequence of corrals C(d) is
C(d − 2)
O(d − 2)pd
pd q d
q d rd
rd s d
C(d − 2)rd sd
(where a concatenation such as C(d − 2)rd sd denotes every corral in C(d − 2) with rd and sd added).
After this sequence of corrals is established, we solve the resulting recurrence relation: Let T (d)
denote the length of C(d). We have T (1) = 1, T (d) = 2T (d − 2) + 4. This implies T (d) = 5 · 2k−1 − 4
(with d = 2k − 1).
All we must show now to complete the proof of Theorem 6 is that C(d) has indeed the stated
recursive form. We do this by induction on d. The steps of the proof are written as claims with
individual proofs.
By construction, C(d) starts with C(d − 2). This happens because points in C(d) are ordered
by increasing norm and the proof proceeds inductively as follows: The first corral in C(d) is the
minimum norm point in P (d), which is also the first corral in C(d − 2). Suppose now that the first
t corrals of C(d) coincide with the first t corrals of C(d − 2). We will show that corral t + 1 in C(d)
is the same as corral t + 1 in C(d − 2). To see this, it is enough to see that the set of points in
P (d) that can enter (improving points) contains the point that enters in C(d − 2) (with two zeros
appended) and contains no point of smaller norm. This two-part claim is true because the two new
zero coordinates play no role in this and all points in P (d) but not in P (d − 2) have a larger norm
than any point in P (d).
Once O(d − 2) is reached (with minimum norm point o∗d−2 ), the set of improving points, as
established by Wolfe’s criterion, consist of {pd , qd , rd , sd }. Now, because we are using the minimumnorm insertion rule, the next point to enter is pd .
Claim 1. O(d − 2)pd is a corral.
Proof of Claim. This is a special case of Lemma 4. We have pd = (o∗d−2 /2, md−2 /4, Md−2 ). We just
need to verify the two inequalities in Lemma 4:
(o∗d−2 )T pd = ko∗d−2 k22 /2 < ko∗d−2 k22 < kpd k22 .
♦
Claim 2. The next improving point to enter is qd .
Proof of Claim. We first check that no point in P (d − 2) can enter. From Lemma 4 we know the
optimal point y in corral O(d − 2)pd explicitly in terms of the optimal point o∗d−2 of O(d − 2) and
13

kpd k22 −pd T o∗d−2
. Let p ∈ P (d − 2).
kpd −o∗d−2 k22
pT y in two steps: First project p

pd , namely y is a convex combination λo∗d−2 + (1 − λ)pd , with λ =

We check that it cannot
enter via Wolfe’s criterion. We compute

onto span o∗d−2 , pd (a subspace that contains y). This projection is longer than o∗d−2 by optimality
of o∗d−2 . Then project onto y. This shows that pT y ≥ o∗d−2 T y = kyk22 and p cannot enter as it is
not an improving point according to Wolfe’s criterion.
By construction, qd is closer to the origin than rd , sd , so to conclude it is enough to check that
qd is an improving point per Wolfe’s criterion. Compute
yT qd = λ(o∗d−2 )T qd + (1 − λ)pTd qd


λ
1
1
2
≤ ko∗d−2 k22 + (1 − λ) ko∗d−2 k22 + ko∗d−2 k22 − Md−2
− Md−2
2
4
16
λ
≤ ko∗d−2 k22
2
since by construction Md−2 ≥ 1 and ko∗d−2 k2 ≤ 1. On the other hand,
1
kyk22 = λ2 ko∗d−2 k22 + (1 − λ)2 kpd k22 + 2λ(1 − λ) ko∗d−2 k22
2
= λko∗d−2 k22 + (1 − λ)2 kpd k22
≥ λko∗d−2 k22 .
Thus, yT qd < kyk2 , that is, qd is an improving point.

♦

Claim 3. The current set of points, O(d − 2) ∪ {pd , qd }, is not a corral. Points in O(d − 2) leave
one by one. The next corral is pd qd .
Proof of Claim. Instead of analyzing the iterations of Wolfe’s inner loop, we use the key fact, from
Section 1.1, that the inner loop must end with a corral whose distance to the origin is strictly less
than the previous corral. We look at the alternatives: This new corral cannot be O(d − 2) ∪ {pd }
(the previous corral) or any subset of it because it would not decrease the distance. An analysis
similar to that of Claim 1 or basic trigonometry (in three-dimensions) shows that O(d − 2) ∪ {qd } is
a corral whose distance to the origin is larger than the distance for O(d − 2)∪{pd }. See Fig. 9, where
we show a projection, the perpendicular line segments to conv(O(d − 2), pd ) and conv(O(d − 2), qd )
are shown in dotted line after projection. Thus, the new corral cannot be O(d − 2) ∪ {qd } or any
subset of it.
No set of the form S ∪ {pd , qd } with S ⊆ O(d − 2) and S non-empty can be a corral: To see this,
first note that the minimum norm point in conv(S ∪ {pd , qd }) is in the segment [pd , qd ], specifically,
point (o∗d−2 /2, md−2 /4, 0) (minimality follows from Wolfe’s criterion, Lemma 1). This implies that
the minimum norm point in aff(S ∪ {pd , qd }) cannot be in the relative interior of conv(S ∪ {pd , qd })
when S is non-empty (see Figure 10).
The only remaining non-empty subset is {pd , qd }, which is the new corral.
♦
Claim 4. The set of improving points is now {rd , sd }.

14

Figure 9: A projection of the point set in the direction of xd−1 . Any corral of the form Sqd where
S ⊂ O(d − 2) would have distance larger than the previous corral, O(d − 2)pd .

Figure 10: The minimum norm point in conv(S ∪ {pd , qd }) is in the line segment between pd and
qd .

15

Figure 11: The set of improving points is now {rd , sd }.

Figure 12: The set {pd , qd , rd } is not a corral.

Figure 13: The only improving point is sd .

Proof of Claim. Recall that the optimal point in corral {pd , qd } has coordinates (o∗d−2 /2, md−2 /4, 0).
Thus, when computing distances and checking Wolfe’s criterion it is enough to do so in the twodimensional situation depicted in Figure 11. Thus, a hyperplane orthogonal to the segment from
the origin to (o∗d−2 /2, md−2 /4, 0) is shown in the figure. It leaves the points in P (d − 2) above and
both rd and sd below making them the only improving points.
♦
Point rd enters since it has smallest norm.
Claim 5. Point pd leaves and the next corral is qd rd .
Proof of Claim. To start, notice that by construction the four points pd , qd , rd , sd lie on a common
hyperplane, L, parallel to the subspace spanned by o∗d−2 . Thus, one does not need to do distance
calculations but rather Fig. 12 is a faithful representation
of the positions of points. The origin is

facing the hyperplane L, parallel to span o∗d−2 . The closest point to the origin within L is in the
line segment joining rd , sd thus, as we move vertically, the closest point to the origin in triangle
pd , qd , rd must be in the line segment joining rd and qd .
♦

16

Figure 14: The point qd leaves.

Figure 15: The improving points are P (d − 2).

Claim 6. The only improving point now is sd .
Proof of Claim. Once more we rely in two different orthogonal two-dimensional projections of P (d)
to estimates distances and to check Wolfe’s criterion. The line segment from the origin to the
optimum of the corral qd , rd (we could calculate this exactly, but it is not necessary), and its
orthogonal hyperplane are shown in Figure 13. This shows only rd or sd are candidates but rd is in
the current corral, so only sd may be added.
♦
Point sd enters as the closest improving point to the origin.
Claim 7. Point qd leaves. The next corral is rd sd .
Proof of Claim. We wish to find the closest point to the origin in triangle qd , rd , sd . From Figure
14 the optimum is between rd , sd ; this point is (md−2 /4)ed−1 . Clearly this point is below qd , so it
must leave the corral.
♦
Claim 8. The set of improving points is now P (d − 2) (with two zero coordinates appended).
Proof of Claim. Now Wolfe’s criterion hyperplane contains the four points pd , qd , rd , sd by construction leaving P (d − 2) on the same side as the origin (see Figure 15).
♦
The first (and minimum norm) point in P (d) enters and the next corral is this point together
with rd and sd . That is, the next corral is precisely the first corral in C(d − 2)rd sd . We will prove
inductively that the sequence of corrals from now on is exactly all of C(d − 2)rd sd . To see this, we
repeatedly invoke Lemma 5 after every corral with A equal to the subspace spanned by the first
d − 2 coordinate vectors of Rd . Suppose that the current corral is Crd sd , where C is one of the
corrals in C(d − 2) and denote the next corral in C(d − 2) by C 0 . From Lemma 5, we get that the
set of improving points for corral Crd sd is obtained by taking the set of improving points for corral
C and removing {pd , qd , rd , sd }. Thus, the point that enters is the same that would enter after
corral C. Let a denote that point.
Claim 9. The next corral is C 0 rd sd .

17

Proof of Claim. The current set of points is Crd sd a. If Ca is a corral then so is Crd sd a = C 0 rd sd
(by Lemma 3, part 3) and the claim holds. If Ca is not a corral, it is enough to prove that the
sequence of points removed by the inner loop of Wolfe’s method on this set is the same as the
sequence on set Crd sd a. We will show this now by simultaneously analyzing the execution of the
inner loop on Ca and Crd sd a. We distinguish the two cases with the following notation: variables
are written without a bar (¯) and with a bar, respectively.
Let x1 , . . . , xk be the sequence of current points constructed by the inner loop on Ca. Let
p1 , . . . , pk be the sequence of removed points. Let C1 , . . . , Ck be the sequence of current sets of
points at every iteration. Let x̄1 , . . . , x̄k̄ be the corresponding sequence on Crd sd a. Let p̄1 , . . . , p̄k̄
be the corresponding sequence of removed points. Let C̄1 , . . . , C̄k̄ be the corresponding sequence
of current sets of points. We will show inductively: k = k̄, there is a one-to-one correspondence
between sequences (xi ) and (x̄i ), and (pi ) = (p̄i ). More specifically, the correspondence is realized
by maintaining the following invariant in the inner loop: x̄i is a strict convex combination of xi and
the minimum norm point in [rd , sd ].
For the base case, from Lemma 3, part 2, we have that x̄1 is a strict convex combination of x1
(which is the minimum norm point in conv C) and the minimum norm point in segment [rd , sd ],
m
specifically w := d−2
4 ed−1 .
For the inductive step, if xi is a strict convex combination of the current set of points Ci , then so
is x̄i of C̄i and the inner loop ends in both cases with corrals Ci = C 0 and C̄i = C 0 rd sd , respectively.
The claim holds. If xi is not a strict convex combination of the current set of points Ci , then neither
is x̄i of C̄i . The inner loop then continues by computing the minimum norm point y in aff Ci and
ȳ in aff C̄i , respectively. It then finds point z in conv Ci that is closest to y in segment [xi , y]. It
finds z̄, respectively. It then selects a point pi to be removed, and a point p̄i , respectively. From
Lemma 3, part 2, we have that ȳ is a strict convex combination of y and w.
We will argue that z̄ is a strict convex combination of z and w. To see this, we note that segment
[x̄i , ȳ] lies in the hyperplane where the last coordinate is 0. Therefore we only need to intersect it
with the part of conv C̄i that lies in that hyperplane. This part is exactly conv(Ci ∪ {w}), which can
be written in a more explicit way as the union of all segments of the form [b, w] with b ∈ Ci . Even
more, we only need to look at triangle w, xi , y, as all relevant segments lie on it. The intersection of
this triangle with conv Ci is segment [xi , z] and therefore the intersection of the triangle with conv C̄i
is simply triangle xi , z, w. This implies that the intersection between segment [x̄i , ȳ] and conv C̄i is
the same as the intersection between segment [x̄i , ȳ] and triangle xi , z, w. This intersection is an
interval [x̄i , z̄] where z̄ is a strict convex combination of w and z and z̄ is the closest point to ȳ in
that intersection.
It follows that the set of potential points to be removed is the same for the two executions.
Specifically, if z is a strict convex combination of a certain subset C ∗ of Ci , then z̄ is a strict
convex combination of C ∗ ∪ {rd , sd }. The sets of points that can potentially be removed are Ci \ C ∗
and C̄i \ (C ∗ ∪ {rd , sd }) = Ci \ C ∗ (the same), respectively. In particular1 , pi = p̄i . This implies
Ci+1 = C̄i+1 . Also, xi+1 = z and x̄i+1 = z̄ is in [xi+1 , w]. This completes the inductive argument
about the inner loop and proves the claim.
♦
This completes the proof of Theorem 6.
1

Under a mild consistency assumption on the way a point is chosen when there is more than one choice, for example,
“choose the point with smallest index among potential points.”

18

2

Linear optimization reduces to minimum-norm problems on simplices

We reduce linear programming to the minimum norm point problem over a simplex via a series
of strongly polynomial time reductions. The algorithmic problems we will consider are defined
below. We give definitions for the problems of linear programming (LP), feasibility (FP), bounded
feasibility (BFP), V-polytope membership (VPM), zero V-polytope membership (ZVPM), zero
V-polytope membership decision (ZVPMD), distance to a V-polytope (DVP) and distance to a
V-simplex (DVS). (Prefix “V-” means that the respective object is specified as the convex hull of a
set of points.) See [18, 12, 19] for a detailed discussions of strongly polynomial time algorithms.
Definition 7. Consider the following computational problems:
• LP: Given a rational matrix A, a rational column vector b, and a rational row vector cT ,
output rational x ∈ argmax{cT x : Ax ≤ b} if max{cT x : Ax ≤ b} is finite, otherwise output
INFEASIBLE if {x : Ax ≤ b} is empty and else output INFINITE.
• FP: Given a rational matrix A and a rational vector b, if P := {x : Ax = b, x ≥ 0} is
nonempty, output a rational x ∈ P , otherwise output NO.
• BFP: Given a rational d ×Pn matrix A, a rational vector b and a rational value M > 0, if
P := {x : Ax = b, x ≥ 0, ni=1 xi ≤ M } is nonempty, output a rational x ∈ P , otherwise
output NO.
• VPM:
Pn Given a rational d × n matrix A and a rational vector b, if P := {x : Ax = b, x ≥
0, i=1 xi = 1} is nonempty, output a rational x ∈ P , otherwise output NO.
P
• ZVPM: Given a rational d × n matrix A, if P := {x : Ax = 0, x ≥ 0, ni=1 xi = 1} is
nonempty, output a rational x ∈ P , otherwise output NO.
• ZVPMD: Given rational points p1 , p2 , . . . , pn ∈ Rd , output YES if 0 ∈ conv{p1 , p2 , ..., pn }
and NO otherwise.
• DVP: Given rational points p1 , p2 , . . . , pn ∈ Rd defining P = conv{p1 , p2 , ..., pn }, output
d(0, P )2 .
• DVS: Given n ≤ d + 1 affinely independent rational points p1 , p2 , ..., pn ∈ Rd defining
(n − 1)-dimensional simplex P = conv{p1 , p2 , ..., pn }, output d(0, P )2 .
The main result in this section reduces linear programming to finding the minimum norm point
in a (vertex-representation) simplex.
Theorem 8. LP reduces to DVS in strongly-polynomial time.
To prove each of the lemmas below, we illustrate the problem transformation and its strong
polynomiality. The first two reductions are highly classical, while those following are intuitive, but
we do not believe have been written elsewhere.
Below is the sequence of algorithmic reductions that reduce LP to DVS.
Lemma 9. LP reduces in strongly-polynomial time to FP.
19

Proof. Let O denote the FP oracle.
Require: A ∈ Qd×n , b ∈ Qd , c ∈ Qn .
Invoke O on
 +
 +
x

 x−



A −A Id x
= b, x−  ≥ 0.
s
s
If the output is NO, output INFEASIBLE.
Invoke O on
 T
  +    +
−c
cT
bT
x
0
x
−
−
 A −A





0
I
x
b
d+2n+1  

 =   , x  ≥ 0.
 0
 y   c   y 
0
AT
T
0
0 −A
s
−c
s

(1)

(2)

If the output is NO, output INFINITE, else output rational x = x+ − x− .
Claim 10. A solution

 +
x

x̃ := x− 
s

to (1) gives a solution to Ax ≤ b and vice versa.
Proof of Claim. Suppose x̃ satisfies (1). Then Ax+ − Ax− + s = b. Define x = x+ − x− and
note s ≥ 0. Then Ax ≤ b. Now, suppose x satisfies Ax ≤ b. Let x+ be the positive coordinates
of the vector x and x− be the negative components in absolute value, so x+
i = max(xi , 0) and
x−
=
max(−x
,
0).
Define
s
=
b
−
Ax.
Since
Ax
≤
b,
we
have
that
s
≥
0
and
by construction,
i
i


x+ , x− ≥ 0. Note that A −A I x̃ = Ax+ − Ax− + s = A(x+ − x− ) + b − Ax = Ax + b − Ax =
b.
♦
Claim 11. A solution

 +
x
x− 

z̃ := 
y
s

to (2) gives a solution to argmax{cT x|Ax ≤ b} and vice versa.
Proof of Claim. Suppose z̃ is a solution to (2). These are the KKT conditions for the LP
argmax{cT x|Ax ≤ b}, so x = x+ − x− is the optimum. Suppose x ∈ argmax{cT x|Ax ≤ b}.
By strong duality, there exists y so that bT y ≤ cT x and AT y = c, y ≥ 0. Thus, letting x+ and x−
be as above, we have
−cT (x+ − x− ) + bT y ≤ 0, A(x+ − x− ) ≤ b, AT y ≤ c, −AT y ≤ −c.
Now choose s ≥ 0 so that
cT x+ − cT x− + bT y + s1 = 0, Ax+ − Ax− + sm+1
= b, AT y + sn+m+1
= c, −AT y + s2n+m+1
2
m+2
n+m+2 = −c
where sji denotes the subvector of s of coordinates si , si+1 , ..., sj−1 , sj . Thus, z̃ satisfies (2).

20

♦

Clearly, constructing the required FP problems takes strongly polynomial time and we have only
two calls to O, so the reduction is strongly-polynomial time.
Lemma 10. FP reduces in strongly-polynomial time to BFP.
d
Proof. Let O denote the oracle for BFP. Suppose A = (aij /αij )d,n
i,j=1 , b = (bj /βj )j=1 and define
D := max(maxi∈[d],j∈[n] |αij |, maxk∈[d] |βk |) and N := max(maxi∈[d],j∈[n] |aij |, maxk∈[d] |bk |) + 1. If
the entry of A, aij /αij = 0 or the entry of b, bj /βj = 0 define aij = 0 and αij = 1 or bj = 0 and
βj = 1.
Require: A ∈ Qd×n , b ∈ Qd . P
3 3
Invoke O on Ax = b, x ≥ 0, ni=1 xi ≤ nDd(n+1) min(d ,n ) N d(n+1) . If the output is NO, output
NO, else output rational x.
P
Claim 12. The FP Ax = b, x ≥ 0 is feasible if and only if the BFP Ax = b, x ≥ 0, ni=1 xi ≤
3 3
nDd(n+1) min(d ,n ) N d(n+1) is feasible.

Proof of Claim. If the BFP is feasible then clearly the FP is feasible. Suppose the FP is feasible.
By the theory of minimal faces of polyhedra, we can reduce this to a FP defined by a square matrix,
A, in the following way: By [7, Theorem 1.1], there is a solution, x, with no more than min(d, n)
positive entries so that Ax = b and the positive entries of x combine linearly independent columns
of A to form b. Let A0 denote the matrix containing only these linearly independent columns and
x0 denote only the positive entries of x. Then A0 x0 = b. Now, note that A0 ∈ Qd×m where m ≤ d.
Since the column rank of A0 equals the row rank of A0 , we may remove d − m linearly dependent rows
of A0 and the corresponding entries of b, forming A00 and b0 so that A00 x0 = b0 where A00 ∈ Qm×m ,
b0 ∈ Qm and A00 isQa full-rankQ
matrix.
Qm
m
d(n+1) . Define L :=
00
00 |
0
Define M := m
|α
i,j
i,j=1
k=1 |βk | and note that M ≤ D
i,j=1 (|ai,j | +
Qm
1) k=1 (|b0k | + 1) and note that L ≤ N d(n+1) . Define Ā = M A00 and b̄ = M b0 and note that
Āi |
where Āi denotes Ā with
Ā and b̄ are integral. By Cramer’s rule, we known that x0i = |det
|detĀ|
Q
the ith column replaced by b̄. By integrality, |detĀ| ≥ 1, so x0i ≤ |detĀi | ≤ m
i,j=1 M (|aij | +
Qm
3
3 ,n3 )
m
d(n+1)
min(d
d(n+1)
0
1) k=1 M (|bk | + 1) = M L ≤ D
N
. Now, note that x defines a solution, x,
to the original system of equations. Let xi = x0j if the jth column of A0 was the selected ith
P column
of A and xi = 0 if the ith column of A was not selected. Note then that Ax = b, x ≥ 0, ni=1 xi ≤
3 3
nDd(n+1) min(d ,n ) N d(n+1) .
♦
Thus, we have that the FP and BFP are equivalent. To see that this is a strongly-polynomial
time reduction, note that adding this additional constraint takes time for constructing the number
3 3
nDd(n+1) min(d ,n ) N d(n+1) plus small constant time. This number takes d(n + 1) comparisons
and d(n + 1) min(d3 , n3 ) multiplications to form. Additionally, this number takes space which is
polynomial in the size of the input (polynomial in d,n and size of D, N ).
Lemma 11. BFP reduces in strongly-polynomial time to VPM.
Proof. Let O denote the oracle for VPM.
Require: A ∈ Qd×n , b ∈ Qd , 0 < M ∈ Q.
Invoke O on
 
 
n
X

 y
y
MA 0
= b,
≥ 0, z +
yi = 1.
z
z
i=1

21

(3)

If the output is NO, output NO, else output rational x = M y.
Claim 13. A solution
w̃ :=

 
y
z

to (3) gives a solution the BFP instance, Ax = b, x ≥ 0,

Pn

i=1 xi

≤ M and vice versa.

a solution to the BFP instance
since
Proof of Claim. Suppose w̃ satisfies (3). Then x = M y is P
P
AxP
= M Ay = bP
and since y ≥ 0, x = M y ≥ 0 and since ni=1 yi + z = 1, we have ni=1 yi ≤ 1
1
so ni=1 P
x is a solution to the BFP instance. Then y = M
x and
xi = M ni=1 yi ≤ M . Suppose

M
A
0
zP= 1 − ni=1 yi satisfies
(3),
since
w̃
=
M
Ay
=
Ax
=
b,
y
≥
0
since
x
≥
0
and
since
Pn
n
1 Pn
x
≤
M
,
we
have
y
=
x
≤
1
so
z
≥
0.
♦
i=1 i
i=1 i
i=1 i
M
Clearly, this reduction is simply a rewriting, so the reduction is strongly-polynomial time.
Lemma 12. VPM reduces in strongly-polynomial time to ZVPM.
Proof. Let O be the oracle for ZVPM.
Require: A ∈ Qd×n , b ∈ Qd .
Invoke O on
n
X


a1 − b a2 − b · · · an − b x = 0, x ≥ 0,
xi = 1

(4)

i=1

where ai ∈

Qm

is the ith column of A. If the output is NO, output NO, else output rational x.

Claim 14. A solution to (4) gives a solution to the VPM instance and vice versa.
P
P
P
Proof of Claim. Note that x satisfies (4) if and only if 0 = ni=1 xi (ai −b) = ni=1 xi ai −b ni=1 xi =
Ax − b so Ax = b. Thus, x is a solution to the VPM instance if and only if x is a solution to
(4).
♦
Clearly, this reduction is simply a rewriting, so the reduction is strongly-polynomial time.
Lemma 13. ZVPM reduces in strongly-polynomial time to ZVPMD.
Proof idea. The reduction sequentially asks for every vertex whether it is redundant and if so, it
removes it and continues. This process ends with at most d + 1 vertices so that x is a strict convex
combination of them and the coefficients xi can be found in this resulting case by solving a linear
system.

Proof. Let O denote the ZVPMD oracle.
Require: P := {A1 , . . . , An } ⊆ Qd where Ai is the ith column of A.
Invoke O on P . If the output is NO, output NO.
for i = 1, . . . , n do
Invoke O on instance P without Ai . If output is YES, remove Ai from P .
end for
Let m be the cardinality of P .
P
P
Output the solution x1 , . . . , xm to the linear system
xi = 1, pi ∈P xi pi = 0

22

Let P ∗ be the resulting set of points P after the loop in the reduction. Claim: P ∗ contains at
most d + 1 points so that 0 is a strict convex combination of (all of) them. Proof of claim: By
Caratheodory’s theorem there is a subset Q ⊆ P ∗ of at most d + 1 points so that 0 is a strict
convex combination of points in Q. We will see that P ∗ is actually equal to Q. Suppose not, for a
contradiction. Let p ∈ P ∗ \ Q. At the time the loop in the reduction examines p, no point in Q has
been removed and therefore p is redundant and is removed. This is a contradiction.
In our next lemma, we make use of the following elementary fact.
Claim 15. Given A an m × n matrix let B be A with a row of 1s appended. The columns of A are
affinely independent if and only if the columns of B are linearly independent. The convex hull of the
columns of A is full dimensional if and only if rank of B is m + 1.
Lemma 14. ZVPMD reduces in strongly-polynomial time to DVS.
Proof. Clearly ZVPMD reduces in strongly-polynomial time to DVP: Output YES if the distance is
0, output NO otherwise.
Given an instance of distance to a V-polytope, p1 , p2 , . . . , pn , we reduce it to an instance of
DVS as follows: We lift the points to an affinely independent set in higher dimension, a simplex,
by adding small-valued new coordinates. Claim 15 allows us to handle affine independence in
matrix form. Let A be the d × n matrix having columns (pi )ni=1 . Let v1 , . . . , vd be the rows of
A. Let v0 ∈ Rn be the all-ones vector. We want to add vectors vd+1 , . . . , vd+t , for some t, so
that v0 , . . . , vd+t is of rank n. To this end, we construct an orthogonal basis (but not normalized,
to preserve rationality) of the orthogonal complement of span (v0 , . . . , vd ). The basis is obtained
by applying the Gram-Schmidt orthogonalization procedure (without the normalization step) to
the sequence v0 , . . . , vd , e1 , . . . , en . Denote vd+1 , . . . , vd+t the resulting orthogonal basis of the
orthogonal complement of span (v0 , . . . , vd ). The matrix with rows v0 , . . . , vd , vd+1 , . . . , vd+t is of
rank n and so is the matrix with rows
v0 , . . . , vd , vd+1 , . . . , vd+t
for any  > 0 (to be fixed later). Therefore, the n columns of this matrix are linearly independent.
Let B be the matrix with rows
v1 , . . . , vd , vd+1 , . . . , vd+t .
Let w1 , . . . , wn be the columns of B. By construction and Claim 15 they are affinely independent.
Let S denote the convex hull of these (n − 1)-dimensional rational points. Polytope S is a simplex.
Moreover, if Q := conv{p1 , . . . , pn }, then
2

2

2

d(0, S) ≤ d(0, Q) + 

d+t
X

kvi k22 ≤ d(0, Q)2 + 2 n

i=d+1

(where we use that kvi k2 ≤ 1, from the Gram-Schmidt construction).
The reduction proceeds as follows: Let T be the maximum of the absolute values of all numerators
and denominators of entries in (pi )ni=1 (which can be computed in strongly polynomial time2 ). From
2

Equivalently, without loss of generality we can assume that the input is integral, and then take C to be the
maximum of the absolute values of all entries in (pi )n
i=1 , as done in Schrijver’s [18, Section 15.2].

23

Lemma 15, we have d(0, Q)2 ≥
example, let  :=

1
.
nd(dT )d

1
d(dT )2d

if 0 ∈
/ Q. Compute rational  > 0 so that 2 n <

The reduction queries

d(0, S)2

1
.
d(dT )2d

For

for S constructed as above and given by

the choice of  we just made. It then outputs YES if d(0, S)2 <

1
d(dT )2d

and NO otherwise.

Lemma 15. Let P = conv{p1 , . . . , pn } be a V-polytope with pi ∈ Qd . Let T be the maximum
of the absolute values of all numerators and denominators of entries in (pi )ni=1 . If 0 ∈
/ P then
1√
d(0, P ) ≥ (dT )d d .
Proof. The claim is clearly true if P is empty. If P is non-empty, let y = projP (x). We have that
every facet of P can be written as aT x ≤ k, where a(6= 0) is an integral vector, k is an integer and the
absolute values of the entries of a as well as k are less than (dT )d ([13, Theorem 3.6]). By assumption
at least one these facet inequalities is violated by 0. Denote by aT x ≤ k one such inequality. Let
H = {x : aT x = k}. We have kyk2 = d(0, P ) ≥ d(0, H), and d(0, H)2 = k 2 /kak22 ≥ d(dT1 )2d . The
claim follows.

3

Conclusions and open questions

We have seen that Wolfe’s method using a natural point insertion rule exhibits exponential behavior.
We have also shown that the minimum norm point problem for simplices is intimately related to
the complexity of linear programming. Our work raises several very natural questions:
• Are there exponential examples for other insertion rules for Wolfe’s method? Also, at the
moment, the ordering of the points starts with the closest point to the origin, but one could
also consider a randomized initial rule or a randomized insertion rule.
• For applications in submodular function minimization, the polytopes one considers are base
polytopes and our exponential example is not of this kind. Could there be hope that for base
polytopes Wolfe’s method performs better?
• It would be interesting to understand the average performance of Wolfe’s method. How does
it behave for random data? Further randomized analysis of this method would include the
smoothed analysis of Wolfe’s method or at least the behavior for data following a prescribed
distribution.
• We have seen that it is already quite interesting to study the minimum norm point problem
for simplices, when we discussed the connection with linear programming. Is there a family of
simplices where Wolfe’s method takes exponential time?
• Can Wolfe’s method be extended to other convex Lp norms for p > 1?

Acknowledgements
We thank Gilberto Calvillo, Deeparnab Chakrabarty, Antoine Deza, Stephanie Jegelka, Matthias
Köppe, Tamon Stephen, and John Sullivan for useful suggestions, conversations and comments
about this project. This work was partially supported by NSF grant DMS-1440140, while the first
and second authors were in residence at the Mathematical Sciences Research Institute in Berkeley,
California, during the Fall 2017 semester. The first and second author were also partially supported
24

by NSF grant DMS-1522158. The second author was also partially supported by the University
of California, Davis Dissertation Fellowship. The third author was also partially supported by
NSF grants CCF-1657939 and CCF-1422830 while the third author was in residence at the Simons
Institute for the Theory of Computing.

References
[1] Achim Bachem and Bernhard Korte. Minimum norm problems over transportation polytopes.
Linear Algebra and its Applications, 31:103–118, 1980.
[2] Imre Bárány and Shmuel Onn. Colourful linear programming and its relatives. Mathematics of
Operations Research, 22(3):550–567, 1997.
[3] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press,
2004.
[4] Gilberto Calvillo and David Romero. On the closest point to the origin in transportation
polytopes. Discrete Applied Mathematics, 210:88–102, 2016.
[5] Deeparnab Chakrabarty, Prateek Jain, and Pravesh Kothari. Provable submodular minimization
using wolfe’s algorithm. In Advances in Neural Information Processing Systems, pages 802–809,
2014.
[6] Vijay Chandru, Abhi Dattasharma, S Sathiya Keerthi, NK Sancheti, and V Vinay. Algorithms
for the optimal loading of recursive neural nets. In SODA, pages 342–349, 1995.
[7] Sergei Nikolaevich Chernikov. The convolution of finite systems of linear inequalities. USSR
Computational Mathematics and Mathematical Physics, 5(1):1–24, 1965.
[8] Satoru Fujishige. Lexicographically optimal base of a polymatroid with respect to a weight
vector. Math. Oper. Res., 5(2):186–196, 1980.
[9] Satoru Fujishige, Takumi Hayashi, and Shigueo Isotani. The minimum-norm-point algorithm
applied to submodular function minimization and linear programming. Kyoto University.
Research Institute for Mathematical Sciences [RIMS], 2006.
[10] Satoru Fujishige and Shigueo Isotani. A submodular function minimization algorithm based on
the minimum-norm base. Pacific Journal of Optimization, 7:3–17, 2011.
[11] Dongdong Ge, Xiaoye Jiang, and Yinyu Ye. A note on the complexity of Lp minimization.
Mathematical Programming, 129(2):285–299, Oct 2011.
[12] Martin. Grötschel, Lásló Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin, 1988.
[13] Martin. Grötschel, Lásló Lovász, and Alexander Schrijver. The ellipsoid method and its
consequences in combinatorial optimization. Combinatorica, 1(2):169–197, 1981.
[14] Victor Klee and George J. Minty. How good is the simplex algorithm? In Inequalities, III
(Proc. Third Sympos., Univ. California, Los Angeles, Calif., 1969; dedicated to the memory of
Theodore S. Motzkin), pages 159–175. Academic Press, New York, 1972.
25

[15] Mikhail K. Kozlov, Sergei P. Tarasov, and Leonid G. Khachiyan. The polynomial solvability of
convex quadratic programming. USSR Computational Mathematics and Mathematical Physics,
20(5):223–228, 1980.
[16] Kiyohito Nagano, Yoshinobu Kawahara, and Kazuyuki Aihara. Size-constrained submodular
minimization through minimum norm base. In Proceedings of the 28th International Conference
on Machine Learning (ICML-11), pages 977–984, 2011.
[17] George L. Nemhauser and Laurence A. Wolsey. Integer programming and combinatorial
optimization. Wiley, 1988.
[18] Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, Chichester,
England, 1998.
[19] Alexander Schrijver. Combinatorial optimization. Polyhedra and efficiency. Vol. A, volume 24
of Algorithms and Combinatorics. Springer-Verlag, Berlin, 2003. Paths, flows, matchings,
Chapters 1–38.
[20] Steve Smale. Mathematical problems for the next century. The Mathematical Intelligencer,
20(2):7–15, 2000.
[21] Tamás Terlaky and Shuzhong Zhang. Pivot rules for linear programming: A survey on recent
theoretical developments. Annals of Operations Research, 46(1):203–233, 1993.
[22] László A. Végh. A strongly polynomial algorithm for a class of minimum-cost flow problems
with separable convex objectives. SIAM J. Comput., 45(5):1729–1761, 2016.
[23] Philip Wolfe. Algorithm for a least-distance programming problem. Math. Programming Stud.,
1:190–205, 1974. Pivoting and extensions.
[24] Philip Wolfe. Finding the nearest point in a polytope. Mathematical Programming, 11(1):128–
149, 1976.

26

