A Polynomial-Space Finite Algorithm
for Solving a Class of Reverse Convex Programs
Takahito Kuno∗ and Yoshiyuki Shiguro
Graduate School of Systems and Information Engineering
University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan
March 2007

Abstract
We develop a new kind of branch-and-bound algorithm to solve a linear program with an additional reverse convex constraint. The proposed algorithm isbased on a polynomial-space pivoting algorithm for enumerating feasible bases ofa linear program. We show that it generates a globally optimal solution after
finitely many pivoting operations with polynomial space.
Key words: Global optimization, reverse convex program, branch-and-boundalgorithm, simplex algorithm, Bland’s pivoting rule.

1

Introduction

A reverse convex program is an optimization problem whose feasible set is the differenceof two convex sets, and hence is also called a d.c. optimization problem. It is known thatany continuous optimization problem over a compact set can be described within thisclass [7, 11, 12]. Included as an important subclass is a linear program with an additional
reverse convex constraint (LPARC), in which a linear function cx is maximized on the
difference of a polyhedron D and an open convex set C. This is certainly a special classbut still contains various optimization problems. In fact, any linear 0-1 integer program
belongs to LPARC because a binary constraint x ∈ {0, 1} is equivalent to a system
including a reverse convex constraint: 0 ≤ x ≤ 1, x2 − x ≥ 0. This also implies that
LPARC is NP-hard in the sense of computational complexity [4].

The author was partially supported by the Grand-in-Aid for Scientific Research (C) 17560050 fromthe Japan Society for the Promotion of Sciences. E-mail: takahito@cs.tsukuba.ac.jp∗

1

Since the feasible set D\C is nonconvex, LPARC usually has multiple locally optimal
solutions, many of which fail to be globally optimal. The algorithms commonly used
to find a globally optimal solution can be classified mainly into two types. The first
type repeatedly computes a locally optimal solution x◦ and checks its global optimality:D ∩ {x ∈ Rn | cx ≥ cx◦ } ⊂ C (or D ∩ {x ∈ Rn | cx = cx◦ } ⊂ C) [5, 8, 10],where C is the closure of C. The second type is branch-and-bound, which recursively
partitions a simpler polyhedron including D and computes lower and upper bounds for
LPARC restricted in each partition set [6, 9, 13]. Both involve enumerating vertices of
the intersection of D with a half space, a plane, or a polyhedral cone for example, andcannot be executed effectively without using branch-and-bound implicitly or explicitly.
Even for an instance of modest scale, therefore, each of these approaches easily suffersfrom combinatorial explosion far before yielding an expected solution.
The branch-and-bound algorithm we propose in this paper is totally different from theabove approaches. It simply enumerates vertices of D in some orderly way, as searchingfor an optimal solution to LPARC. The reason why such a naı̈ve method has not beensucceeded so far is naturally due to the combinatorial explosion in the number of vertices.
However, we will show that it can be realized with polynomial space complexity, using
Bland’s pivoting rule [2] in the simplex algorithm. After some preliminaries in the next
section, we explain in Section 3 a vertex enumeration algorithm proposed by Avis andFukuda [1]. Using it as a procedure for generating a branching tree, we develop a branchand-bound algorithm for solving LPARC exactly in a finite time with space complexity
O(mn), where (m, n) is the size of the linear system defining D. In Section 4, we close
the paper by giving a detailed algorithm description and some remarks.

2

Some preliminaries

The class of problems, LPARC, is generally formulated as follows:
maximize cx
subject to Ax ≤ b, x ≥ 0
f (x) ≥ 0,

(1)

where A ∈ Rm×n , b ∈ Rm and cT ∈ Rn . Let
D = {x ∈ Rn | Ax ≤ b, x ≥ 0},

C = {x ∈ Rn | f (x) < 0}.

We assume that D is nonempty and bounded, and f is a continuous quasiconvex function
defined on an open set including D. Although both D and C are convex, the feasible set
is their difference D \ C, and hence can be nonconvex and even disconnected. Therefore,2(1) is a typical multiextremal global optimization problem. If the last constraint f (x) ≥ 0
is removed, the problem (1) reduces to an ordinary linear program:maximize cx
subject to Ax ≤ b, x ≥ 0,(2)

which is obviously far easier to solve, and has an optimal solution x in D by assumption.
If x happens to lie outside C, then x is also an optimal solution to (1). To exclude suchtrivial cases, we assume throughout the paper that
D \ C 6= ∅,(3)

max {cx | x ∈ D \ C} < max {cx | x ∈ D} .

(4)

Then we have the following well-known result (see e.g., [5, 7, 11] for proof):
Proposition 2.1. Under assumptions (3) and (4), the boundary ∂C of C contains all
optimal solutions to (1), at least one of which lies on some edge of D.
We see immediately from this proposition that (1) can be solved in finite time if wesearch for the optimal solution, say x∗ , along edges of D in some orderly way, because
there are only a finite number of edges. A simple but reliable way to realize it would beenumeration of the vertices of D. The edges can then be examined from their end points.
To give a short sketch of our proposed method, let us recall Bland’s pivoting rule [2],commonly used to avoid cycling in the simplex algorithm for solving linear programs like(2) [3]. Brand’s rule enable us to reach an optimal solution to (2) in finitely many steps
starting from any vertex of D. This implies that there exists a unique path consistingof some edges in D from each vertex to an optimal one. If the optimal solution x to(2) is unique, we can therefore constitute a spanning tree T rooted at x on a graphG associated with the vertices and edges of D (see Figure 1). To be more precise, thenodes of this graph G correspond one-to-one with the feasible bases for (2), not withthe vertices of D. Anyway, we can visit all vertices of D along the feasible bases tree T .
Our algorithm is a kind of combinatorial branch-and-bound using this spanning tree T
as a branching tree.

3

Search for an optimal solution

Let us introduce a vector y ∈ Rm of m slack variables xn+1 , . . . , xn+m into the linear
program (2). Then we have its standard form:
maximize cx
subject to Ax + y = b, x ≥ 0, y ≥ 0,
3

(5)

x
C
c
D

Figure 1: Feasible bases tree T on the polytope D.
whose optimal solution is denoted by (x, y). We assume for simplicity that (5) is bothprimal and dual nondegenerate at (x, y). This implies that x is the unique optimal
solution to (2). Let (x1 , y1 ) be a feasible basic solution to (5) and assume x1 ∈ C. Sucha basic solution must be in D by assumption (4). Let B denote the basis, the index
set of m basic variables in (x1 , y1 ), and let N = {1, . . . , n + m} \ B. Also denote by(AB , AN ), (cB , cN ) and (xB , xN ) the partitions of columns of [A, I], [c, 0] and [xT , yT ],respectively in accordance with the pair (B, N ), where I ∈ Rm×m is the identity matrix.
Then AB ∈ Rm×m is nonsingular and we have a feasible dictionary of (5):xB = b − AN xNz= z 1 + c N xN ,

(6)

where
b = A−1
B b,

AN = A−1
B AN ,

z 1 = cB A−1
B b,cN = cN − cB A−1
B AN .

Letting xN = 0 in (6), then we have the basic solution (x1 , y1 ), whose objective function
value is given by z 1 . To improve (x1 , y1 ) in the simplex algorithm, we have to select anindex r ∈ B and an s ∈ N appropriate to change. Bland’s pivoting rule specifies thispivot (r, s) uniquely in a very simple manner:(a) s ∈ N is the smallest index among all candidates to enter the basis, i.e.,s = min {j ∈ N | cj > 0} ;4

(b) r ∈ B is the smallest index among all candidates to leave the basis, i.e.,r = min i ∈ B | bi = ais d ,where d = min bi /ais | ais > 0, i ∈ B .
We refer to the pivot (r, s) satisfying (a) and (b) as the Bland pivot in dictionary (6).
If (a) is not applicable in (6), then the current basis B is optimal for (5) and we have(x, y) = (x1 , y1 ). Even otherwise, we have the following (see [2, 3] for proof):
Proposition 3.1. If the simplex algorithm is applied to (6), then it generates a finite
sequence of feasible bases of (5) under Bland’s pivoting rule. The last feasible basis in
this sequence is optimal for (5).

Reverse Bland pivot and the feasible bases tree
Let us discuss how to constitute the feasible bases tree T mentioned in Section 2. We
think of each feasible basis of (5) as a node of the graph G, and assume an arc between
any two bases sharing exactly m − 1 indices among {1, . . . , n + m}. By proposition 3.1,
the simplex algorithm traces a unique path on G from each node to the one corresponding
to the basis B of (x, y). Note that B is unique, because (5) is assumed to be primal
nondegenerate at (x, y). Therefore, T consisting of those paths is connected and spans
all nodes in G. Suppose (x1 , y1 ) 6= (x, y) and the basis B is yielded from some feasible
basis B 2 by applying a pivoting operation to the associated dictionary at its Bland pivot(r, s). Such B 2 might not be unique if exists. Avis and Fukuda [1] named (s, r) as areverse Bland pivot in dictionary (6) and proposed to enumerate the feasible bases of(5) recursively in lexicographic order of reverse Bland pivots from B. This is essentiallyequivalent to depth-first search along the spanning tree T from the root node B.
To check if (s, r) is actually a reverse Brand pivot in (6), we have only to perform apivoting operation at (s, r). Assuming asr > 0, then we haveP
xr = bs /asr − 1/asr xs − j∈N \{r} asj /asrPxi = (bi − air bs /asr ) + air /asr xs − j∈N \{r} (aij − air asj /asr )xj , i ∈ B \ {s}P
z = (z 1 + cr bs /asr ) − cr /asr xs + j∈N \{r} (cj − cr asj /asr )xj ,(7)

which is another dictionary of (5) adjacent to (6). We may simply check in (7) if(r, s) satisfies (a) and (b). This brutal method requires O(mn) arithmetic operations.
However, from the following lemma, we can see in time O(m + n) whether it is worth
carrying out or not.

5

Lemma 3.2. If (s, r) is a reverse Bland pivot in (6), thencr < 0,(8)bs = asr d,(9)where d = min bi /air | air > 0, i ∈ B .
Proof. If (9) does not hold, then bi − air bs /asr < 0 for some i ∈ B \ {s}; and hence (7) isinfeasible. Also, r cannot be a candidate to enter the basis in (7) unless (8) holds.
For each (i, j) ∈ B × N in lexicographic order, we test conditions (8) and (9) with(s, r) = (i, j), and perform a pivoting operation if necessary. If (i, j) turns out to be avalid reverse Bland pivot in (6), then we move to the node B 2 = B ∪ {j} \ {i} on G. We
refer to B 2 as a child of B. If no reverse Bland pivots are found in (6), the current basis
B is a leaf of T . In that case, we may backtrack along T according to Bland’s usual
rule. Thus, we can eventually constitute the feasible bases tree T of the linear program(5) with space complexity only O(mn) for a dictionary.

Procedures necessary for branch-and-boundOur purpose is not to enumerate the feasible bases of (5), but to find an optimal solution
to the reverse convex program (1). We need to do some additional computation to locate
the edge of D on which Proposition 2.1 suggests the optimal solution x∗ lies. Suppose(s, r) has passed both tests (8) and (9) in Lemma 3.2, i.e., dictionary (7) is now feasible.
Let B 2 = B ∪ {r} \ {s} and (x2 , y2 ) denote the corresponding basic solution. Since C isa convex set and x1 is assumed to be in C, the segment [x1 , x2 ] does not intersect ∂C if
x2 ∈ C. However, if x2 6∈ C, it might be the edge of D suggested by Lemma 2.1. We
therefore compute an intersection with ∂C, regardless whether (s, r) is a valid reverse
Bland pivot or not in (6).
Lemma 3.3. The segment [x1 , x2 ] intersects ∂C at a unique point if x1 ∈ C and x2 6∈ C.
Proof. Suppose [x1 , x2 ] intersects ∂C at different points v1 and v2 such that cT x1 ≤cT v1 ≤ cT v2 ≤ cT x2 . Since x1 belongs to the open set C, there is some open sphere S
of center x1 such that S ⊂ C. Let Se denote the convex hull of S and v2 . Then we havev1 ∈ Se \ {v2 } ⊂ C, which contradicts v1 ∈ ∂C.
Let v denote the unique intersection point of [x1 , x2 ] with ∂C. If cv > cx◦ for the best
feasible solution x◦ to (1) found so far, we update the incumbent x◦ with v.
Even if (s, r) fails the tests in Lemma 3.2, the basic solution (x2 , y2 ) can be feasible
and [x1 , x2 ] might intersect ∂C. However, we can neglect it without overlooking x ∗ .

6Lemma 3.4. Suppose (s, r) fails (8), (9) or both. Then no optimal solutions lie on thesegment [x1 , x2 ] unless x2 is optimal for (1).
Proof. If (s, r) fails (9), then dictionary (7) is infeasible as shown in the proof of Lemma
3.2, and so [x1 , x2 ] ∩ D = {x1 } ⊂ C. Suppose (s, r) fails only (8) and [x1 , x2 ] intersects∂C at v. Since cr ≥ 0 and asr > 0, we havecx1 = z 1 ≤ cv ≤ cx2 = z 1 + cr bs /asr ,but cx2 < cx∗ if x2 is not optimal for (1).
Then what should we do if x2 is an optimal solution to (1) in this lemma? In that case,
we may continue pivoting operations as usual at valid reverse Bland pivots. Then wemust reach B 2 in finite steps from B via some different path than including B because(x2 , y2 ) is a feasible basic solution to (5) and B 2 ∈ T . In either case, we can ignore thesegment [x1 , x2 ] completely unless (s, r) passes both tests (8) and (9).
In addition to the above observations, we have the following:
Lemma 3.5. Suppose (s, r) passes both (8) and (9). If for the incumbent x◦ we havez 1 + cr d ≤ cx◦ ,(10)where d = min bi /air | air > 0, i ∈ B , then B 2 and all its descendants in T have nosolutions better than x◦ .
Proof. The value of x2 corresponding to B 2 is given by z 1 + cr d, as seen in dictionary(7). It is never improved as long as we follow (8) and (9).
We also see from this lemma that if (10) holds, there are no solutions better than x◦ on
the segment connecting two points given by each adjacent descendants of B 2 . Therefore,
we need not move to B 2 from B on T even if (s, r) is a valid reverse Bland pivot in (6)and B 2 is a legitimate child of B. In other words, the value z 1 + cr d serves as an upperbound on cx∗ to fathom the node B 2 of the branching tree T . It is worth noting that
this bounding operation spends little time if dictionary (7) is in hand.

Treatments for degenerate case
Since Bland’s pivoting rule terminates the simplex algorithm once an optimal basis isfound, the above procedure might not work when the linear program (5) has multiple
optimal bases. This can actually occur if (5) is primal or dual degenerate at (x, y).
Even in that case, each path to an optimal basis on G is still unique under Bland’srule. However, the union T of those paths becomes a spanning forest, not a spanning
7

tree, of G. Therefore, to search for the optimal solution x∗ to (1), we have to collect all
optimal bases for (5) and then start our algorithm from each. It is possible to generate
all optimal bases for (5) if we enumerate feasible bases of a degenerate system:
Ax + y = b, x ≥ 0, y ≥ 0
cx = cx,
using a dual form of Bland’s rule. The details are omitted, because they are technicallysomewhat involved, but introduced in [1]. A more practical method would be, however,to avoid degeneracy itself by giving a little perturbation to b and c.

4

Algorithm and remarks

Finally, let us summarize the discussion of the previous sections into an algorithm.
algorithm TREE SEARCH
begin
solve the linear program (5) to obtain an optimal solution (x, y);
let x◦ denote any feasible solution to (1);for each feasible basis B of value cx in (5) do begin
let N := {1, . . . , n} \ B;call procedure REVERSE BLAND to update x◦
end;
output x∗ := x◦ as an optimal solution to (1)end;procedure REVERSE BLAND
begin
let (x1 , y1 ) denote the basic solution for dictionary (6) associated with (B, N );let z 1 := cB A−1
B b;for each (s, r) ∈ B × N in lexicographic order do begin
if cr < 0 in (6) then begin
let d := min bi /air | air > 0, i ∈ B ;if bs /asr = d then begin
perform a pivoting operation at (s, r) in (6) and obtain dictionary (7);let (x2 , y2 ) denote the basic solution for (7);if x2 6∈ C then begin
compute the intersection point v of [x1 , x2 ] with ∂C;
if cv > cx◦ then x◦ := v;

8

end;
if (r, s) is the Bland pivot in (7) and z 1 + cr d > cx◦ then begin
let B := B ∪ {r} \ {s} and N := N ∪ {s} \ {r};call procedure REVERSE BLAND to update x◦ ;let B := B ∪ {s} \ {r} and N := N ∪ {r} \ {s};end;perform a pivoting operation at (r, s) in (7)
end
end
end;
return x◦ ;end;
In practice, it might not be so easy to compute the intersection point v of [x1 , x2 ]with ∂C, depending on the function f defining C, but we assume here that it can be done
in finite time. Then finiteness of this recursive algorithm is guaranteed by Proposition
3.1 and Lemma 3.2, and optimality of the output x∗ is by Proposition 2.1 and Lemmas
3.3–3.5. These, together with the fact that it is not necessary to keep anything otherthan a dictionary and the incumbent x◦ , lead to the following:
Theorem 4.1. Algorithm TREE SEARCH occupies O(mn) space and yields a globally
optimal solution x∗ to problem (1) after finitely many pivoting operations.
Since algorithm TREE SEARCH has not yet been implemented nor compared withother existing algorithms, we cannot make a definitive conclusion regarding the practical
efficiency. However, we should remark that TREE SEARCH visits only vertices of D
contained in C. Therefore, it is expected to work well on instances of (1) where C cuts
off only a few vertices from D. In contrast to this, for instances where C contains alarger number of vertices of D, the performance of TREE SEARCH could get worse, andin the worst case, it might visit all vertices but one. To put algorithm TREE SEARCH
into practical use, we need to devise some sort of procedure for reducing the volume of
D ∩ C. A promising one is to cut off a portion of D ∩ C using a plane which passes
through intersection points of ∂C with n extreme rays of a full-dimensional simplicial
cone vertexed in C and including D. The details will be reported elsewhere, withnumerical results for comparison with some other algorithms.

References[1] Avis, D. and K. Fukuda, “A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra”, Discrete and Computational Geometry
8 (1992), 295–313.
9[2] Bland, R.G., “New finite pivoting rules for the simplex method”, Mathematics ofOperations Research 2 (1977), 103–107.
[3] Chvátal, V., Linear Programming, Freeman (N.Y., 1983).
[4] Garey, M.R. and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman (San Francisco, 1979).
[5] Hillestad, R.J. and S.E. Jacobsen, “Linear programs with an additional reverse
convex constraint”, Applied Mathematics and Optimization 6 (1980), 257–269.
[6] Horst, R., “Deterministic global optimization with partition sets whose feasibility
is not known: application to concave minimization, reverse convex constraints, dcprogramming, and Lipschitzian optimization”, Journal of Optimization Theory andApplications 58 (1988), 11–37.
[7] Horst, R. and H. Tuy, Global Optimization: Deterministic Approaches, 2nd ed.,Springer-Verlag (Berlin, 1993).
[8] Kuno, T. and J. Shi, “Linear programs with an additional separable concave constraint”, Journal of Applied Mathematics and Decision Sciences 8 (2004), 155–174.
[9] Nagai, H. and T. Kuno, “A conical branch-and-bound algorithm for a class ofreverse convex programs”, Proceedings of the Fourth International Conference on
Nonlinear Analysis and Convex Analysis (2007), 417–426.
[10] Pferschy, U. and H. Tuy, “Linear programs with an additional rank two reverse
convex constraint”, Journal of Global Optimization 4 (1994), 441–454.
[11] Tuy, H., “D.c. optimization: theory, methods and algorithms”, Handbook of Global
Optimization, Kluwer Academic Publishers (Dordrecht, 1995), 149–216.
[12] Tuy, H., Convex Analysis and Global Optimization, Kluwer Academic Publishers(Dordrecht, 1998).
[13] Tuy, H. and R. Horst, “Convergence and restart in branch and bound algorithms
for global optimization. Application to concave minimization and d.c. optimization
problems”, Mathematical Programming 41 (1988), 161–183.

10