ABSTRACT

The existence of strongly polynomial algorithm for linear programming (LP) has been widely sought after for decades. Recently, a new approach called Gravity Sliding algorithm [1] has emerged. It is a gradient descending method whereby the descending trajectory slides along the inner surfaces of a polyhedron until it reaches the optimal point. In R³, a water droplet pulled by gravitational force traces the shortest path to descend to the lowest point. As the Gravity Sliding algorithm emulates the water droplet trajectory, it exhibits strongly polynomial behavior in R³. We believe that it could be a strongly polynomial algorithm for linear programming in Rⁿ too. In fact, our algorithm can solve the Klee-Minty deformed cube problem in only two iterations, irrespective of the dimension of the cube. The core of gravity sliding algorithm is how to calculate the projection of the gravity vector g onto the intersection of a group of facets, which is disclosed in the same paper [1] . In this paper, we introduce a more efficient method to compute the gradient projections on complementary facets, and rename it the Sliding Gradient algorithm under the new projection calculation.

Keywords:

Linear Programming, Mathematical Programming, Complexity Theory, Optimization

1. Introduction

The simplex method developed by Dantiz [2] has been widely used to solve many large-scale optimizing problems with linear constraints. Its practical performance has been good and researchers have found that the expected number of iterations exhibits polynomial complexity under certain conditions [3] [4] [5] [6] . However, Klee and Minty in 1972 gave a counter example showing that its worst case performance is $\mathcal{O}\left(2^n\right)$ [7] . Their example is a deliberately constructed deformed cube that exploits a weakness of the original simplex pivot rule, which is sensitive to scaling [8] . It is found that, by using a different pivot rule, the Klee-Minty deformed cube can be solved in one iteration. But for all known pivot rules, one can construct a different deformed cube that requires exponential number of iterations to solve [9] [10] [11] . Recently, the interior point method [12] has been gaining popularity as an efficient and practical LP solver. However, it was also found that such method may also exhibit similar worse case performance by adding a large set of redundant inequalities to the Klee-Minty cube [13] .

Is it possible to develop a strongly polynomial algorithm to solve the linear programming problem, where the number of iterations is a polynomial function of only the number of constraints and the number of variables? The work by Barasz and Vempala shed some light in this aspect. Their AFFINE algorithm [14] takes only $\mathcal{O}\left(n^2\right)$ iterations to solve a broad class of deformed products defined by Amenta and Ziegler [15] which includes the Klee-Minty cube and many of its variants.

In certain aspect, the Gravity Sliding algorithm [1] is similar to the AFFINE algorithm as it also passes through the interior of the feasible region. The main difference is in the calculation of the next descending vector. In the gravity falling approach, a gravity vector is first defined (see Section 3.1 for details). This is the principle gradient descending direction where other descending directions are derived from it. In each iteration, the algorithm first computes the descending direction, then it descends from this direction until it hits one or more facets that forms the boundary of the feasible region. In order not to penetrate the feasible region, the descending direction needs to be changed. The trajectory is likened a water droplet falling from the sky but is blocked by linear planar structures (e.g. the roof top structure of a building) and needs to slide along the structure. The core of gravity sliding algorithm is how to calculate the projection of the gravity vector g onto the intersection of a group of facets. This projection vector lies on the intersection of the facets and hence lies on the null space defined by these facets. Conventional approach is to compute the null space first and then find the projection of g onto this null space. An alternative approach is disclosed in [1] which operates directly from the subspace formed by the intersecting facets. This direct approach is more suitable to the Gravity Sliding algorithm. In this paper, we further present an efficient method to compute the gradient projections on complementary facets and also introduce the notion of selecting the steepest descend projection among a set of candidates. With these refinements, we rename the Gravity Sliding algorithm as the Sliding Gradient algorithm. We have implemented our algorithm and tested it on the Klee-Minty cube. We observe that it can solve the Klee-Minty deformed cube problem in only two iterations, irrespective of the dimension of the cube.

This paper is organized as follows: Section 2 gives an overview of the Cone-Cutting Theory [16] , which is the intuitive background of the Gravity Sliding algorithm. Section 3 discusses the Sliding Gradient algorithm in details. The pseudo-code of this algorithm is summarized in Section 4 and Section 5 gives a walk-through of this algorithm using the Klee-Minty as an example. This section also discusses the practical implementation issues. Finally, Section 6 discuss about future work.

2. Cone-Cutting Principle

The cone-cutting theory [16] offers a geometric interpretation of a set of inequality equations. Instead of considering the full set constraint equations in a LP problem, the cone-cutting theory enables us to consider a subset of equations, and how an additional constraint will shape the feasible region. The geometric insight forms the basis of our algorithm development.

2.1. Cone-Cutting Principle

In an m-dimension space ${ℝ}^m$ , a hyperplane $y^{\text{T}}\tau =c$ cuts ${ℝ}^m$ into two half spaces. Here $\tau$ is the normal vector of the hyperplane and c is a constant. We denote the positive half space $\left\{y|y^{\text{T}}\tau \ge c\right\}$ the accepted zone of the hyperplane and the negative half space where $\left\{y|y^{\text{T}}\tau <c\right\}$ is rejected zone. Note that the normal vector $\tau$ points to accepted zone area and we call the hyperplane with such orientation a facet $\alpha :\left(\tau ,c\right)$ . When there are m facets in ${ℝ}^m$ and $\left\{{\tau }_1,{\tau }_2,\cdots ,{\tau }_m\right\}$ are linear independent, this set of linear equations has a unique solution which is a point V in ${ℝ}^m$ . Geometrically, $\left\{{\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_m\right\}$ form a cone and V is the vertex of the cone. We now give a formal definition of a cone, which is taken from [1] .

Definition 1. Given m hyperplanes in ${ℝ}^m$ , with rank $r\left({\alpha }_1,\cdots ,{\alpha }_m\right)=m$ and intersection V, $C=C\left(V;{\alpha }_1,\cdots ,{\alpha }_m\right)={\alpha }_1\cap \cdots \cap {\alpha }_m$ is called a cone in ${ℝ}^m$ . The area $\left\{y|y^{\text{T}}{\tau }_i\ge c_i\left(i=1,2,\cdots ,m\right)\right\}$ is called the accepted zone of C. The point V is the vertex and α_j is the facet plane, or simply the facet of C.

A cone C also has m edge lines. They are formed by the intersection of (m − 1) facets. Hence, a cone can also be defined as follows.

Definition 2. Given m rays $R_j=\left\{V+t{r}_j|0\le t<+\infty \right\}\left(j=1,\cdots ,m\right)$ shooting from a point V with rank $r\left(r_1,\cdots ,r_m\right)=m$ , $C=C\left(V;r_1,\cdots ,r_m\right)=c\left[R_1,\cdots ,R_m\right]$ , the convex closure of m rays is called a cone in ${ℝ}^m$ . $R_j$ is the edge, $r_j$ the edge direction, and $R_j^{+}=\left\{V+t{r}_j|\infty <t<+\infty \right\}$ the edge line of the cone C.

The two definitions are equivalent. Furthermore, P.Z. Wang [11] has observed that $R_i^{+}$ and ${\alpha }_i$ are opposite to each other for $i=1,\cdots ,m$ . Edge-line $R_i^{+}$ is the intersection of all C-facets except ${\alpha }_i$ , while facet ${\alpha }_i$ is bounded by all C-edges except $R_i^{+}$ . This is the duality between facets and edges. For $i=1,\cdots ,m,\left\{{\tau }_i,R_i\right\}$ is called a pair of cone C.

It is obvious that $r_j^{\text{T}}{\tau }_i=0$ (for $i\ne j$ ) since $r_j$ lies on ${\alpha }_i$ . Moreover, we have

$r_i^{\text{T}}{\tau }_i\ge 0\left(\text{for}i=1,\cdots ,m\right)$ (1)

2.2. Cone Cutting Algorithm

Consider a linear programming (LP) problem and its dual:

(Primary): $\max \left\{{\tilde{c}}^{\text{T}}x|Ax\le b;x\ge 0\right\}$ (2)

(Dual): $\min \left\{y^{\text{T}}b|y^{\text{T}}A\ge \tilde{c};y\ge 0\right\}$ (3)

In the following, we focus on solving the dual LP problem. The standard simplex tableau can be obtained by appending an $m\times m$ identity matrix $I_{m\times m}$ which represents the slack variables as shown below:

$\left[\begin{array}{ccc}\begin{array}{ccc}{a}_{11}& \dots & a_{1n}\\ ⋮& \ddots & ⋮\\ a_{m1}& \cdots & a_{mn}\end{array}& \begin{array}{ccc}1& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & 1\end{array}& \begin{array}{c}{b}_1\\ ⋮\\ b_m\end{array}\\ \begin{array}{ccc}{\tilde{c}}_1& \cdots & {\tilde{c}}_n\end{array}& \begin{array}{ccc}0& \cdots & 0\end{array}& 0\end{array}\right]$

We can construct a facet tableau whereby each column is a facet denoted as ${\alpha }_j:\left({\tau }_j,c_j\right)$ , where ${\tau }_i={\left(a_{1i},a_{2i},\cdots ,a_{mi}\right)}^{\text{T}}$ and

$c_i=\{\begin{array}{l}{\tilde{c}}_i\text{for}1\le i\le n\\ 0\text{for}n<i\le m+n\end{array}$ (4)

The facet tableau is depicted as follow. The last column ${\left(b_1,b_2,\cdots ,b_m,0\right)}^{\text{T}}$ is not represented in this tableau.

$\begin{array}{l}\begin{array}{cccc}{\alpha }_1& {\alpha }_2& \cdots & {\alpha }_{m+n}\end{array}\\ \left[\begin{array}{llll}{\tau }_1\hfill & {\tau }_2\hfill & \cdots \hfill & {\tau }_{m+n}\hfill \\ c_1\hfill & c_2\hfill & \cdots \hfill & c_{m+n}\hfill \end{array}\right]\end{array}$

When a cone $C=C\left(V;{\alpha }_1,\cdots ,{\alpha }_m\right)=C\left(V;r_1,\cdots ,r_m\right)$ is intersected by another facet ${\alpha }_j$ , the i^th edge of the cone is intersected by ${\alpha }_j$ at certain point $q_{ij}$ . We call ${\alpha }_j$ cuts the cone C and the cut points $q_{ij}$ can be obtained by the following equations:

$q_{ij}=V+t_i{r}_i\text{where}{t}_i=\left(c_i-V^{\text{T}}{\tau }_j\right)/r_i^{\text{T}}{\tau }_j$ (5)

The intersection is called real if $t_i\ge 0$ and fictitious if $t_i<0$ . Cone cutting greatly alters the accepted zone, as can be seen from the simple 2-dimension example as shown in Figures 1(a)-(e). In 2-dimension, a facet $\alpha :\left(\tau ,c\right)$ is a line. The normal vector $\tau$ is perpendicular to this line and points to the accepted zone of this facet. Furthermore, a cone is formed by two non-parallel facets in 2-dimension. Figure 1(a) shows such a cone $C\left(V;{\alpha }_1,{\alpha }_2\right)$ . The accepted zone of the cone is the intersection of the two accepted zones of facets α₁ and α₂. This is represented by the shaded area A in Figure 1(a). In Figure 1(b), a new facet α₃ intersects the cone at two cut points $q_{13}$ and $q_{23}$ . They are both real cut points. Since the arrow of normal vector ${\tau }_3$ points to the same general direction of the cone, V lies in the rejected zone of α₃ and we say α₃ rejects V. Moreover, the accepted zone of α₃ intersects with the accepted zone of the cone so that the overall accepted zone is reduced to the shaded area marked as B. In Figure 1(c), ${\tau }_3$ points to the opposite direction. α₃ accepts V and the overall

accepted zone is confined to the area marked as C. As the dual feasible region

上一篇:Compact Model for the Obnoxiou 下一篇:The Pivot Adaptive Method for