Dantzig G., Thapa M. Linear programming. Vol.1. Introduction

Подождите немного. Документ загружается.

122 INTERIOR-POINT METHODS

We pick an arbitrary

=(1111)

Then we compute the quantity b − Ax

b − Ax





−



1110

2301



















Hence we create the following linear program with M = 1000:

Minimize −2x

− x

+ 1000x

= z

subject to x

+ x

+2x

+3x

+ x

+6x

=12

and x

≥ 0 for j =1,...,4 and x

≥ 0.

Then a starting feasible solution is x

= e, where e =(1, 1,...,1)

, and x

=1.

 Exercise 4.3 Solve the problem in Example 4.2 using the Primal Affine / Dikin

software option.

See Problems 4.4 and 4.5 and Section 4.4 for a further discussion of the Big-M

Method.

4.4 NOTES & SELECTED BIBLIOGRAPHY

Interior-point methods are not recent, they have been around for a very long time. For

example, in chronological order, von Neumann [1947], Dantzig [1995] (based on an idea

of von Neumann, 1948), Hoﬀman, Mannos, Sokolowsky, & Wiegmann [1953], Tompkins

[1955, 1957], Frisch [1957], Dikin [1967]. (Fiacco & McMormick [1968] further developed

Frisch’s Barrier Method approach to nonlinear programming.) None of these earlier meth-

ods, including Khachian’s [1979] ellipsoidal polynomial-time method, turned out to be

competitive in speed to the Simplex Method on practical problems.

Interior-point methods became quite a popular way to solve linear programs in the late

1970s and early 1980s. However interior-point (and polynomial-time) methods have been

around for a very long time. For example, in chronological order, von Neumann [1947],

Hoﬀman, Mannos, Sokolowsky, & Wiegmann [1953], Tompkins [1955, 1957], Frisch [1957],

Dikin [1967], and Khachian [1979]. (Fiacco & McMormick [1968] further developed Frisch’s

Barrier Method approach to nonlinear programming.) None of these earlier methods

turned out to be competitive in speed on practical problems to the Simplex Method.

In 1979, Khachian presented an algorithm, based on a nonlinear geometry of shrinking

ellipsoids, with a worst-case polynomial-time bound of O(n

) (where L

is the number

of bits required to represent the input data on a computer). Given an open set of inequal-

ities of the form Ax<b, where A is m × n with m ≥ 2, n ≥ 2, Khachian’s algorithm

either ﬁnds a feasible point if the system is nonempty or demonstrates that no feasible

point exists. Assuming that the inequalities have a feasible solution, the method starts by

drawing a ball that is large enough to contain a suﬃciently large volume of the feasible

space deﬁned by the inequalities Ax<b. If the center of the ball is within the open set of

4.5 PROBLEMS 123

inequalities, a feasible solution has been found and the algorithm terminates. If a feasible

solution is not obtained, the method proceeds to the next iteration by constructing an

ellipsoid of smaller volume that contains the feasible space of the inequalities contained in

the previously drawn ball. If the center of the ellipsoid is in the feasible space of Ax<b,

we have found a feasible solution; otherwise the method proceeds to the next iteration

by constructing another ellipsoid of smaller volume, and so on. The theory developed by

Khachian states that if a feasible solution exists, then the center of some ellipsoid will lie

in the feasible space within a number of iterations bounded by some polynomial expression

in the data. Although Khachian’s ellipsoid method has nice theoretical properties, unfor-

tunately it performs poorly in practice. First, the number of iterations tend to be very

large; and second, the amount of computation associated with each iteration is much more

than that with the Simplex Method. Khachian’s work specialized to linear programming

is based on earlier work done by Shor [1971a, 1971b, 1972a, 1972b, 1975, 1977a, 1977b] for

the more general case of convex programming. Other work that was inﬂuenced by Shor

and preceded Khachian was due to Judin & Nemirovskii [1976a,b,c]. Predating all this

was an article by Levin [1965] for convex programming.

In 1984, Karmarkar presented his interior point ellipsoid method with a worst-case

polynomial-time bound of O(n

3.5

), where L

, as deﬁned above, is the number of bits

required to represent the input data on a computer. Claims by Karmarkar that his method

is much faster (in some cases 50 times faster) than the Simplex Method stimulated improve-

ments in the simplex-based algorithms and the development of alternative interior-point

methods. Up to 1996, no method has been devised to our knowledge that is superior for all

problems encountered in practice. Since the publication of Karmarkar’s [1984] paper there

have as of 1996 been well over a thousand papers published on interior-point methods. See

Kranich [1991] for a bibliography, M. Wright [1992] for a review of interior-point methods.

Also see Lustig, Marsten, & Shanno [1994] for a review of the computational aspects of

interior-point methods.

The primal aﬃne method presented in this chapter (which is the same as Dikin’s

method) was rediscovered by Barnes [1986] and Vanderbei, Meketon, & Freedman [1986].

Dikin [1974] proved convergence of his method under primal nondegeneracy. Proofs of

convergence of Dikin’s iterates can also be found in Adler, Resende, Veiga, & Karmakar

[1989], Barnes [1986], Dantzig [1988a], Dantzig & Ye [1990], Monma & Morton [1987],

Vanderbei, Meketon, & Freedman [1986], and, under somewhat weaker assumptions, in

Vanderbei & Lagarias [1988].

A projected Newton Barrier method is described and related to Karmarkar’s method in

Gill, Murray, Saunders, Tomlin, & Wright [1986]. Dual approaches of both these methods

have also been developed, see Adler, Resende, Veiga, & Karmarkar [1989] and Renegar

[1988]. Megiddo [1988, 1986] ﬁrst devised the theory for primal-dual interior-methods (see

Linear Programming 2 for details of the method) which has performed very well in practice.

Lustig, Marsten, & Shanno [1990, 1991a, 1991b, 1992a, 1992b, 1992c, 1994] implemented

and reported promising results for various versions of a primal-dual algorithm. For a

review of methods with a focus on computational results, see, for example, Gill, Murray,

& Saunders [1988] and Lustig, Marsten, & Shanno [1994].

For a description of various interior-point methods see Linear Programming 2. Also,

see Linear Programming 2 for a discussion on what to do in the event that M is not suﬃ-

ciently large that the vector x

goes to zero. Computational techniques (QR factorization,

Cholesky factorization) for solving linear progams by interior-point methods are dicsussed

in Linear Programming 2.

124 INTERIOR-POINT METHODS

4.5 PROBLEMS

4.1 Consider the linear program

Minimize 2x

+ x

= z

subject to x

+ x

≥ 0,x

≥ 0.

(a) Plot the feasible region.

(b) Starting with an initial interior feasible solution x

=1,x

= 1, solve the

problem by hand by the primal aﬃne method described in this chapter.

Plot each iteration and clearly show the direction of steepest descent that

was used.

(d) Solve it by the DTZG Simplex Primal software option and compare the

solution obtained to that obtained by the primal aﬃne method.

4.2 Consider the linear program

Maximize x

+ x

= z

subject to 2x

+ x

≤ 3

≤ 1

≥ 0,x

≥ 0.

(a) Plot the feasible region.

(b) Starting with an initial interior feasible solution x

=0.5, x

=0.5, solve

the problem by hand by the primal aﬃne method described in this chapter.

Plot each iteration.

(d) Solve it by the DTZG Simplex Primal software option and compare the

solution obtained to that obtained by the primal aﬃne method.

4.3 Consider the linear program

Minimize x

− 2x

= z

subject to x

+2x

≥ 1

≥ 0,x

≥ 0.

(a) Plot the feasible region.

(b) Starting with an initial interior feasible solution x

=2,x

=1.5, solve

the problem by hand by the primal aﬃne method described in this chapter.

Plot each iteration.

(d) Solve it by the DTZG Simplex Primal software option and compare the

solution obtained to that obtained by the primal aﬃne method.

4.5 PROBLEMS 125

4.4 Use the primal aﬃne method to solve

Minimize 2x

+3x

= z

subject to 2x

+ x

≤ 6

≥ 1

≥ 0,x

≥ 0

as follows:

(a) Plot the feasible region of the problem.

(b) Use the Big-M method of Section 4.3 to generate an initial feasible interior-

point solution.

4.5 Apply the Big-M method of Section 4.3 to generate an initial feasible solution

to the linear program

Minimize x

+ x

= z

subject to x

+2x

≥ 2

+2x

≤ 1

≥ 0,x

≥ 0.

(a) Apply the primal aﬃne method of this chapter and demonstrate that the

problem is infeasible.

(b) Solve the problem using the Primal Affine / Dikin software option.

how do you think the choice of M makes a diﬀerence in determining whether

the problem is infeasible.

4.6 Consider the following linear program:

Minimize −x

= z

subject to x

+ x

≥ 4

≥ 0,x

≥ 0.

(a) Use the Big-M method of Section 4.3 to generate an initial feasible interior-

point solution.

(b) Apply the primal aﬃne method of this chapter and demonstrate that the

problem is unbounded.

4.7 Solve the following problem by the primal aﬃne method (software option Primal

Affine / Dikin) described in this chapter:

Minimize 3x

+2x

+4x

= z

subject to x

+ x

+3x

− x

and x

≥ 0,x

≥ 0.

(4.28)

(a) Use the Big-M method of Section 4.3 to generate an initial feasible interior-

point solution.

126 INTERIOR-POINT METHODS

(b) Solve the problem by a two-phase procedure (similar to the Simplex Method)

as follows. Start by introducing an artiﬁcial variable as for the Big-M

method.

• Use a Phase I objective of the form min x

to solve the problem.

• Do Phase II. That is, drop the artiﬁcial variable and restart the method

with the feasible solution obtained at the end of Phase I and the real

objective of the problem.

4.8 Solve the following linear program with a redundant constraint by hand with

the primal-aﬃne method.

Minimize 3x

− 2x

= z

subject to x

+ x

+2x

and x

≥ 0,x

≥ 0.

(4.29)

4.9 Consider the following linear program with a redundant constraint:

Minimize x

+ x

= z

subject to x

+2x

+ x

+2x

− x

+ x

+2x

≥ 0,j=1,...,5.

(a) Solve the linear program by hand using primal-aﬃne method. (You may

want to use mathematical software or spreadsheets to help with matrix

multiplications and solving of systems of equations.)

(b) Apply the Primal Affine / Dikin software option to solve the problem.

Explore the solution of the problem using diﬀerent values of α (consider

at least 5 diﬀerent values between 0.5 and 0.99, with 0.95 being one of the

values). Comment on your results.

4.10 Solve the following linear program:

Minimize −x

= z

subject to x

+ x

≥ 4

≥ 0,x

≥ 0.

(a) Plot the feasible region.

(b) Apply the primal-aﬃne method and display the iterates on your plot.

4.11 Consider the following linear program due to Klee & Minty [1972]:

Minimize



j=1

−10

m−j

subject to



i−1



j=1

i−j



+ x

+ z

= 100

i−1

, for i =1,...,m

≥ 0,z

≥ 0, for j =1,...,m.

(4.30)

4.5 PROBLEMS 127

If we apply the Simplex Method (using the largest coeﬃcient rule) to solve

the problem (4.30), then it can be shown that the Simplex Method performs

−1) iterations before ﬁnding the optimal solution. Apply the Primal Affine

/ Dikin software option for m ≥ 8 to solve the problem. Explore the solution

of the problem using diﬀerent values of α (consider at least 5 diﬀerent values

between 0.5 and 0.99). Comment on your results.

4.12 Solve the following problem using the Primal Affine / Dikin software option:

Minimize c

subject to Ax = b

x ≥ 0,

where A, b, and c are deﬁned as follows:

i + j − 1

, for i, j =1,...,10,



j=1

, for i =1,...,10,

=1, for j =1,...,10.

Comment on your solution.

4.13 Use the Primal Affine / Dikin software option to solve the transportation

problem (1.4) on page 5.

4.14 How would you modify the primal aﬃne method to handle upper and lower

bounds on the variables, assuming that on each variable at least one bound is

ﬁnite. Discuss how you would handle the case when a variable is unrestricted

in value. Hint: Replace each unrestricted variable by the diﬀerence of two

nonnegative variables (see Section 6.2).

This page intentionally left blank

CHAPTER 5

DUALITY

Earlier, see (1.6) and (1.8), we deﬁned the dual of a linear program in standard

form, min z = c

x, Ax = b, x ≥ 0, as max v = b

π, A

π ≤ c. The original problem

in relation to its dual is called the primal. It is easy to prove, by rewriting the dual

in standard form, that the dual of the dual is the primal; see Exercise 5.2. Feasible

solutions to the primal and to the dual may appear to have little relation to one

another. Actually, there is a strong relationship between their objective values;

moreover, their optimal basic feasible solutions are such that it is possible to use

one to obtain the other readily. Commercial software is written using the primal

Simplex Method; as a result, it may sometimes be more convenient to use the dual

to obtain the solution to a linear programming problem than the primal.

5.1 DUAL AND PRIMAL PROBLEMS

5.1.1 VON NEUMANN SYMMETRIC FORM

Given the linear program in the form

PRIMAL: Find min z such that Ax ≥ b, x ≥ 0,c

x = z, (5.1)

von Neumann deﬁned its dual as

DUAL: Find max v such that A

y ≤ c, y ≥ 0,b

y = v. (5.2)

This deﬁnition is equivalent to the one given above when the primal problem is

stated in standard form; see also Section 5.1.4.

 Exercise 5.1 Based on the above deﬁnition of a dual, prove that the dual of a dual is

a primal problem.

129

130 DUALITY

Primal

Variables x

≥ 0 x

≥ 0 ··· x

≥ 0 Relation Constants

≥ 0 a

··· a

≥ b

≥ 0 a

··· a

≥ b

Dual

≥ 0 a

··· a

≥ b

Relation ≤ ≤ ··· ≤ ≤

Max v

Constants c

··· c

≥ Min z

Table 5-1: Tucker Diagram

5.1.2 TUCKER DIAGRAM

To see more clearly the connection between the primal and dual problems, we shall

use Tucker’s detached coeﬃcient array, Table 5-1. The primal problem reads across,

the dual problem down. A simple way to remember the direction of inequality is to

write the primal inequalities ≥ to correspond to the z-form being always ≥ min z,

and to write the dual inequalities ≤ to correspond to the v-form being always

≤ max v.

5.1.3 DUALS OF MIXED SYSTEMS

It is always possible to obtain the dual of a system consisting of a mixture of

equations, inequalities (in either direction), nonnegative variables, or variables un-

restricted in sign by changing the system to an equivalent inequality system in the

form (5.1). However, an easier way is to apply certain rules, displayed in Table 5-2,

which we will now discuss. Both the primal and dual systems can be viewed as con-

sisting of a set of variables with their sign restrictions and a set of linear equations

and inequalities, such that the variables of the primal are in one-to-one correspon-

dence with the equations and inequalities of the dual, and such that the equations

and inequalities of the primal are in one-to-one correspondence with the variables

of the dual. When the primal relation is a linear inequality (≥), the corresponding

dual variable of the dual is nonnegative; note in Table 5-2 that if the primal relation

is an equation, the corresponding dual variable will be unrestricted in sign.

As an illustration of these rules, consider the following example:

Example 5.1 (Dual of a Mixed Primal System) Suppose we have the following

mixed primal system ﬁnd min z, x

≥ 0, x

≤ 0, x

unrestricted, subject to

+ x

= z (min)

− 3x

+4x

− 2x

≥ 3

− x

≤ 4

(5.3)

5.1 DUAL AND PRIMAL PROBLEMS 131

Primal Dual

Minimize Primal Objective Maximize Dual Objective

Objective Coeﬃcients RHS of Dual

RHS of Primal Objective Coeﬃcients

Coeﬃcient Matrix Transposed Coeﬃcient Matrix

Primal Relation: Dual Variable:

(ith) Inequality: ≥ y

≥ 0

(ith) Inequality: ≤ y

≤ 0

(ith) Equation: = y

unrestricted in sign

Primal Variable: Dual Relation:

≥ 0 (jth) Inequality: ≤

≤ 0 (jth) Inequality: ≥

unrestricted in sign (jth) Equation: =

Table 5-2: Correspondence Rules Between Primal and Dual LPs

The above primal system in detached coeﬃcient form is displayed by reading across Ta-

ble 5-3. Its dual, obtained by applying the rules in Table 5-2, is displayed by reading down

in Table 5-3.

To see why this is the case, suppose we rewrite system (5.3) in its equivalent von

Neumann inequality form:

+(−x



)+ (x



− x



) ≥ min z

− 3(−x



)+ 4(x



− x



) ≥ 5(x

≥ 0,x



≥ 0,x



≥ 0,x



≥ 0)

−



− 3(−x



)+4(x



− x



)



≥−5

− 2(−x



) ≥ 3

−



2(−x



) − (x



− x



)



≥−4.

(5.4)

We write x



= −x

≥ 0; this changes the sign of x

. Also, we have written x

= x



−x



the diﬀerence of two nonnegative variables (see Section 6.2), and we have written the ﬁrst

equation of (5.3) as equivalent to two inequalities, x

−3x

+4x

≥ 5 and x

−3x

+4x

≤ 5.

The relationship between the primal of (5.4) and its dual is displayed in Table 5-4.

Here it is convenient to let y



≥ 0 and y



≥ 0 be the dual variables corresponding

to the ﬁrst two inequalities. Since coeﬃcients of y



and y



diﬀer only in sign in every

inequality, we may set y



− y



= y

, where y

can have either sign. Note next that the

coeﬃcients in the inequalities of the dual corresponding to x



and x



diﬀer only in sign,

which implies the equation

4(y



− y



) − y

=1, or 4y

− y

=1.

From these observations it is clear that Table 5-3 is stating more concisely the relations of

Table 5-4.