# A New Technique for Determining Approximate Center of a Polytope

Authors: Syed Inayatullah; Maria Aman; Asma Rani; Hina Zaheer; Tanveer Ahmed Siddiqi
Journal: Advances in Operations Research
 (2019)

---

## Abstract

In this article, we have presented a method for finding the approximate center of a linear programming polytope. This method provides a point near the center of a polytope in few simple and easy steps. Geometrical interpretation and some numerical examples have also been presented to demonstrate the proposed approach and comparison of quality of the center obtained by using the new method with existing methods of finding exact and approximate centers. At the end, we also presented computational results on the randomly generated polytopes to compare the quality of the center obtained by using the new method.


---

## Body

## 1. Introduction

Linear programming (LP) is a mathematical technique for optimizing a linear function subject to a set of linear constraints and nonnegativity restrictions. Linear programs frequently show up in various areas of applied sciences today. The prime reason for this is their manageable, enormous impact in various disciplines; it has become a core research area of many mathematicians, economists, decision scientists, etc. Linear programming was developed during World War II, when a system with which to maximize the efficiency of resources was of utmost importance. Since then, many researchers have strived to advance their ideas and made centering of the polytope as a core step in the major optimization techniques (named as interior point methods) in science and industry.


## 2. Definitions of the Center of a Polytope

There are several ways to define the center of a polytope, it may be the center of gravity i.e.,centroid, mean position of all vertices i.e., vertex centroid, point at the location where product of distances from all boundary lines is maximized i.e., analytic center, center of the least volume ellipsoid that contains the polytope, or the center of the biggest ball inside the polytope. Therefore, the center of a polytope depends on the definition we are using. But, fortunately, all those definitions are equivalent in the sense that, as shown in [1], if we get a polynomial time algorithm for a center of a polytope, then that algorithm could also be used to construct a polynomial time algorithm for solving linear program.Many techniques [2–4] are used for finding the center of a polytope, but they are taking so many iterations, slow in convergence, and require mostly complex computations.Most of the interior point methods for solving LPs depend on the computations of a center finding method, either explicitly or implicitly [3, 5].The analytic center [6–12] is no doubt the most used notion of center of a polytope in linear optimization because of its easy computation, but its disadvantage is that it can be pushed near the boundary of the polytope by using redundant constraints because its position depends on the spatial positions of the half-spaces that define the polytope. So in that case, analytic center may not look like located at a good central position (see also Section 3). The P-center [3], also to be discussed in Section 4, provides a much better center than the analytic center, but it is found in practice that it takes much longer time to obtain a good approximation of the P-center.


## 3. Analytic Center

LetS be a polytope described by a (normalized) system of linear inequalities:(1)∑j=1naijxj≤bi,i=1,2,…,m.The analytic center ofS is the point ξ=ξ1,ξ2,…,ξn∈ℜn which satisfies the following maximization problem:(2)Maximize∏i=1mbi−∑j=1naijxjsubject tox∈S.WhenS is bounded, this maximization problem always has a solution.In general, the analytic center depends on how the set of particular inequalities is defined. The addition of redundant inequalities could push analytic center towards the boundary. In the Sections4 and 5, we discuss two new efficient and alternative methods, which could be used to find a good approximation of the central location of a polytope.


## 4. P-Center [3]

Consider a linear programming polytope described by a setS=x∈ℜn:Ax≤b, where A∈ℜm×n. Let Hi=x:aiTx≤bi be the half-space corresponding to the ith row of A and Gi=x:aiTx=bi be the corresponding hyperplane. The method assumes that the polytope is full dimensional. The overall technique is based on the following definitions of projections.


### 4.1. Orthogonal Feasible Projections

Letxk be some feasible interior point; for each hyperplane Gi, we can easily generate two distinct points (projections) Pi+xk and Pi−xk on the boundary, defined by Pi+xk=xk+θiai and Pi−xk=xk−λiai, where θi=maxt:xk+tai∈S and λi=maxt:xk−tai∈S.


### 4.2. Central Location Using Orthogonal Projections

A vertex centroid of a polytope could be defined as the average of all points on the boundary and [3] defined the P-center as an approximation of vertex centroid, which could be obtained by taking average of some finite number of points on the boundary of a polytope. The main task of the method is to generate points on the boundary as much as possible. For this purpose, an initial feasible interior point is needed and then the method generates the iterates by taking a convex combination of the orthogonal projections into the hyperplanes associated with the inequalities that define the polytope.EachGi could generate two points Pi+xk and Pi−xk on the boundary of S and a midpoint xik=Pi+xk+Pi−xk/2 on the chord joining them. The new iterate xk+1 is obtained by taking the average of all m midpoints xik:i=1,…,m. That is xk+1=∑i=1mxik/m.Ifmaxabsxk+1−xk<ε (where ε is the tolerance value), then stop with the result that “P-center is obtained up to tolerance level of ε.” Otherwise, perform the k+1th iteration taking xk+1 as the initial interior point.Carlos defined it as an approximation to the vertex centroid because in every iteration, he has taken 2 -m distinct points on the boundary in distinct directions. Method looks to be very effective and he has also shown that quality of the center is also very good, even most of the times the centrality of P-center is way better than analytic center, but practically, it is found that it become very slow to converge and to attain a particular tolerance. Sometimes, it requires a huge number of iterations just to reach near about centroid. Computational results are shown in the Section6.


## 4.1. Orthogonal Feasible Projections

Letxk be some feasible interior point; for each hyperplane Gi, we can easily generate two distinct points (projections) Pi+xk and Pi−xk on the boundary, defined by Pi+xk=xk+θiai and Pi−xk=xk−λiai, where θi=maxt:xk+tai∈S and λi=maxt:xk−tai∈S.


## 4.2. Central Location Using Orthogonal Projections

A vertex centroid of a polytope could be defined as the average of all points on the boundary and [3] defined the P-center as an approximation of vertex centroid, which could be obtained by taking average of some finite number of points on the boundary of a polytope. The main task of the method is to generate points on the boundary as much as possible. For this purpose, an initial feasible interior point is needed and then the method generates the iterates by taking a convex combination of the orthogonal projections into the hyperplanes associated with the inequalities that define the polytope.EachGi could generate two points Pi+xk and Pi−xk on the boundary of S and a midpoint xik=Pi+xk+Pi−xk/2 on the chord joining them. The new iterate xk+1 is obtained by taking the average of all m midpoints xik:i=1,…,m. That is xk+1=∑i=1mxik/m.Ifmaxabsxk+1−xk<ε (where ε is the tolerance value), then stop with the result that “P-center is obtained up to tolerance level of ε.” Otherwise, perform the k+1th iteration taking xk+1 as the initial interior point.Carlos defined it as an approximation to the vertex centroid because in every iteration, he has taken 2 -m distinct points on the boundary in distinct directions. Method looks to be very effective and he has also shown that quality of the center is also very good, even most of the times the centrality of P-center is way better than analytic center, but practically, it is found that it become very slow to converge and to attain a particular tolerance. Sometimes, it requires a huge number of iterations just to reach near about centroid. Computational results are shown in the Section6.


## 5. A New Approximation of Central Location: CN-Center

In this section, we describe a recursive version of the method described in Section4. Because of the recursive nature of this method, it uses the most updated value of center for next computation so it has a quick movement towards the central location. We would call the central location obtained by this method as CN-center.Overall, for a problem ofm constraints, each iteration of this procedure holds m steps. Here onward, xik denotes the coordinates of center obtained in ith intermediate step of kth iteration, xk denotes the center obtained after kth iteration, and x0 denotes the coordinates of the initial feasible point. Here, x∧k+1 would be used to represent the midpoint of Pi+xk and Pi−xk, where Pi+xk and Pi−xk on the boundary defined by Pi+xk=xk+θiai and Pi−xk=xk−λiai, where θi=maxt:xk+tai∈S and λi=maxt:xk−tai∈S.For anykth iteration, the method needs an interior feasible point xk−1:Stepk1: compute x∧1k≔1/2P1+xk−1+P1−xk−1. Set x1k≔x∧1k.Stepki: compute x∧ik≔1/2Pi+xi−1k+Pi−xi−1k. Set xik≔1/i∑j=1i−1xjk+x∧ik,∀i=2,…,m.Now, since all hyperplanes have contributed, we can setxk≔xmk. We can terminate the procedure when maxabsxk−xk−1<ε, where ε is the required tolerance. If the tolerance level is not achieved, then the process could proceed to k+1th iteration, taking xk as an initial point.The main difference between computation of P-center and CN-center could simply be illustrated by performing initial two steps of the first iteration.Iteration 1. Step 1: both the methods identically take an interior feasible point, sayx0, as starting point and find two points P1+xk and P1−xk on the boundary of the feasible region using the direction of normal of first constraint. Then, both methods take the average of boundary points to get a new point, say x10.Iteration 1. Step 2: difference of strategy starts from here; the method of P-center now again finds the average of two other boundary points using normal of 2nd constraint and the same starting point x0, and calls it x20.In contrast, method of CN-center takes normal of 2nd constraint and a new point x10 to obtain the average of boundary points, denoting it by x∧20. Now, x20 is obtained by taking the average of x10 and x∧20.


## 6. Computational Experiences

We performed numerical experiences to compare the CN-center against P-center, analytic center, and centroid in several polytopes in MATLAB and convergence with a suitable tolerance level. First, we show pictures of polytopes in 2D space to illustrate the convergence of the CN-center, P-center, analytic center, and centroid. Second, we present the numerical results in tables for randomly generated polytope.To visualize the convergence of P-center and CN-center, we have taken some examples from [13]. Figures 1–4 represent four polytopes with convergences to their P-center and CN-center, respectively.Figure 1
Polytope 1, P-center is obtained in 56 iterations but CN-center is obtained in just 11 iterations. Centrality wise both looked equivalent.Figure 2
Polytope 2, convergence towards center.Figure 3
Polytope 3, convergence towards center.Figure 4
Polytope 4, convergence towards center.Table1 shows the measure of coordinates of center x, number of iterations, and measure of centrality Cx for P-center and CN-center for each polytope illustrated in Figures 1–4Table 1
A comparison of number of iterations and quality of P-center and CN-center.
Polytope number
P-center
CN-center
C
x
X
Iterations
C
x
X
Iterations
1
0.7597
(1.4453, 3.4772)
56
0.6903
(1.3980, 3.6719)
11
2
0.9272
(0.9790, 3.0236)
38
0.9262
(0.9843, 3.0236)
7
3
0.3332
(0.3602, 0.7120)
16
0.3311
(0.3585, 0.7503)
2
4
0.1594
(0.1947, 0.3126)
12
0.1656
(0.2014, 0.3064)
3As we see in Table1 as well as in Figures 1–4, centrality Cx of CN-center and P-center is almost equal but convergence towards CN-center is multiplex faster than P-center.Now, we are taking other four different polytopes and presenting the comparison between observable quality of analytic center, P-center, centroid, and CN-center. Table2 and Figure 5 represent numerical and graphical results. Based on Figures 1–5, it is easy to see that location-wise CN-center is almost equal to P-center but with a less number of iterations.Table 2
A numerical comparison between coordinates of analytic center, P-center, CN-center, and centroid.
Polytope number
Analytic center
P-center
CN-center
Centroid
1
(2.3932, 2.8696)
(1.4453, 3.4772)
(1.3980, 3.6719)
(1.4364, 0.6318)
2
(0.6340, 3.5490)
(0.9790, 3.0236)
(0.984, 3.0236)
(1.0000, 3.0000)
3
(0.3732, 0.8454)
(0.3602, 0.7120)
(0.358, 0.7503)
(0.3524, 0.7403)
4
(0.2152, 0.3704)
(0.1947, 0.3126)
(0.2014, 0.3064)
(0.2644, 0.2738)Figure 5
Graphical comparison of quality between analytic center (denoted by yellow square), P-center (denoted by blue asterisk), CN-center (denoted by black dot), and centroid (denoted by green diamond).Our calculation shows that if we take the initial point near a narrow corner of the region, then there is a huge difference in the number of iterations for P-center and CN-center as shown in Figure6, and if we take the initial point near a wide corner of the region (see Figure 7), difference in the number of iterations for P-center and CN-center would not be so significant.Figure 6
When initial point lies near a narrow corner, convergence of CN-center is much quicker than P-center.Figure 7
When initial point lies near a wide corner, both P-center and CN-center bear almost equal number of iterations.Now, Table3 presents some computational results on number of iterations needed for obtaining P-center and CN-center of randomly generated 2D LPs with higher number of constraints.Table 3
Computational results of randomly generated LPs using MATLAB.
Number of constraint
P-center
CN-center
Coordinates of center
Number of iteration
Coordinates of center
Number of iteration
25
(0.0965, 0.0752)
6
(0.1122, 0.0793)
1
(0.0465, 0.0746)
8
(0.0469, 0.1064)
1
(0.3132, 0.7748)
12
(0.3187, 0.8938)
1
(0.4704, 0.0892)
24
(0.4837, 0.0898)
2
(0.5839, 0.1610)
21
(0.5442, 0.1541)
2
(0.0686, 0.2428)
32
(0.0731, 0.3027)
5
(0.1244, 0.3280)
12
(0.1294, 0.3847)
1
(0.3476, 0.0421)
24
(0.3151, 0.0403)
4
(0.2793, 0.1585)
12
(0.2714, 0.1569)
2
(0.2134, 0.0223)
2
(0.2255, 0.0221)
3
(0.1856, 0.0341)
23
(0.2183, 0.03257)
3
50
(0.0346, 0.0922)
13
(0.0328, 0.1205)
1
(0.0761, 0.0101)
19
(0.0943, 0.0098)
2
(0.1607, 0.2225)
6
(0.1714, 0.2511)
1
(0.1092, 0.0408)
17
(0.1538, 0.0368)
2
(0.1669, 0.0229)
19
(0.1592, 0.0229)
1
(0.2277, 0.0482)
28
(0.2159, 0.0479)
2
(0.4047, 0.03670)
31
(0.3385, 0.0342)
3
(0.1925, 0.3076)
14
(0.1881, 0.3085)
1
(0.1546, 0.1301)
12
(0.1678, 0.1517)
1
(0.2142, 0.0126)
89
(0.3065, 0.0111)
10
(0.3657, 0.2198)
16
(0.370951, 0.2122)
1Finally, results for higher dimensional random LPs are presented in Table4. Here, we have taken the average of number of iterations of 20 random LPs of each order with ε=0.001. Results showed that the new approach is still superior in efficiency even in higher dimensional problems.Table 4
Comparison of average number of iterations for higher dimensional random LPs.
Order
P-center
CN-center
3 × 5
62.71
16.57
5 × 3
35.85
8.23
5 × 5
85.5
55.33
10 × 5
136.8
34.4
10 × 10
476.44
77.22
15 × 15
650.71
249.85
15 × 10
348.6
96.34
20 × 20
331.44
258.88
30 × 20
213.2
162.7
20 × 30
508.2
236
30 × 30
206.75
193.125
Note: here,ε=0.001 is more than enough. If we observe the convergence pattern of CN-center, we can see that convergence is initially fast and gets slower in later iterations. Generally, we do not need exact central point; for practical purposes, any good central location is enough for working. So a good central point is obtainable by CN-center within just a few iterations for a 100 × 100 or even a very high dimensional problem.


## 7. Applications

There are a lot of areas where approximate center finding methods for LPs could be used, for example, solving both linear and general convex programming [13], the support vector machine (SVM) solution that corresponds to the center of the largest sphere inscribed in version space [9, 14], computing cubature formulae [15], and sphere method for linear programming [16].


## 8. Conclusion

In this paper, we have presented a modified form of P-center [3] and called it as CN-center. Our experimental results show that quality of centrality of P-center and CN-center is almost same, but in terms of number of iterations,CN-center is much faster in computation of a good central location in the feasible region in lower and as well as in higher dimensional problems.Generally, finding the central location of an LP is the main crucial step for most of the interior point methods. Usually, we do not need the exact center instead a good central location would be enough if it is obtained in less number of computations. So, in this sense, CN-center is a better option to use instead of P-center or analytic center.



---

*Source: 8218329-2019-11-15.xml*