Pivotal Interior-Point Method
The same idea of the face method can be applied to the dual problem to derive a dual variant. The resulting method seems to be even more efficient than its primal counterpart.
- PDF / 289,919 Bytes
- 24 Pages / 439.36 x 666.15 pts Page_size
- 93 Downloads / 241 Views
Pivotal Interior-Point Method
The simplex method and the interior-point method are two diverging and competitive types of methods for solving LP problems. The former moves on the underlying polyhedron, from vertex to adjacent vertex, along edges until an optimal vertex is reached while the latter approaches an optimal point by moving across interior of the polyhedron. Although the basic ideas, motivations and development tracks of the two methods appear quite different, attempts will be made in this chapter to combine the two methods to take advantages of both, in a natural manner. In view of that the interior-point method has been seriously restricted in applications since it can not be “warmly started”, and provides only an approximate optimal solution (see Sect. 9.5), three pivotal interior-point algorithms will be derived. These algorithms yield from standard interior-point algorithms by adding inner steps. Presented in the last section of this chapter, on the other hand, the socalled “feasible-point simplex algorithm” is established along another line, which might be the first simplex-like algorithm that acrosses the interior of the polyhedron.
24.1 Pivotal Affine Interior-Point Method In this section, firstly an interior-point algorithms is designed by forming a search direction based on affine-scaling. This search direction is equivalent to that used in Dikin’s affine algorithm in theory. However, the new framework allows to introduce inner pivotal steps to create a better interior-point algorithm. Let xN be the current interior-point. Consider the dual problem of (9.25), i.e., max g D b T y; : y T : N D XN c; z 0: s:t: .X A : I / z
P.-Q. PAN, Linear Programming Computation, DOI 10.1007/978-3-642-40754-3__24, © Springer-Verlag Berlin Heidelberg 2014
(24.1)
623
624
24 Pivotal Interior-Point Method
Note that there is a 1-to-1 correspondence between columns of the unit matrix I and indices of z. At first, we will realize the “dual elimination” by orthogonal transformations (Sect. 25.1.3). Since A is of full row rank, hence XN AT is of full column rank, there exists the QR factorization R1 T N (24.2) X A D .Q1 ; Q3 / D Q1 R1 ; 0 where .Q1 ; Q3 / is orthogonal, partitioned as Q1 2 Rnm and Q3 2 Rn.nm/ , and R1 2 Rmm is nonsingular upper triangular. The following result reveals that the search direction in x 0 -space, used in the Dikin’s affine algorithm, can be obtained alternatively by using the matrix Q3 . Proposition 24.1.1. x 0 , defined by (9.27), is equal to Q3 Q3T XN c. Proof. Substituting (24.2) to (9.27) and noting Q1T Q1 D I and Q1 Q1T CQ3 Q3T D I gives x 0 D .I Q1 R1 .R1T Q1T Q1 R1 /1 R1T Q1T /XN c D .I Q1 Q1T /XN c D Q3 .Q3T XN c/: (24.3) t u Thereby, we are led to the following variant of the affine algorithm. Algorithm 24.1.1 (Variant of Algorithm 9.2.1). The same as Algorithm 9.2.1, except for its step 1 replaced by 1. Compute x 0 by (24.3). As they differ only in the way to compute the same search direction, Algorithm 24.1.1 and Dikin’s algorithm are equivalent. The c
Data Loading...
