<<

. 57
( 59 .)



>>

GH GH
denote the index i by q and take x to be the entering variable. The column
H O
A will be the entering column for the basis at the (k ; 1)st iteration.
O
Step 4. Either determine that the problem is unbounded or determine the
leaving variable.

(i) Calculate

v :E E . . . E [B(0)]\A
O I I\  O
from right to left. Note that v is as in Section 4.
O
(ii) If all components of v are nonpositive, then the problem is unbounded
O
and no solution exists. The justi¬cation for this conclusion is the same
as the one given in Step 3(ii) of Section 4.
260 SIMPLEX METHOD


(iii) If v : (v . . . v ) has at least one positive component, then as in (21)
O KO
of Section 4 let denote the smallest index r at which

GP : v 9 0
t* : min
P
v
PO O
is attained. Choose x to be the leaving variable.
GM
Step 5. Calculate E as given by the matrix on the right in (5).
I>
Step 6. Update the data for the (k ; 1)st iteration.

(i) x to x by replacing x by x .
Update
GN
Y O
(ii) x to x by replcing x by x .
Update
GN
, PY O
(iii) B to B by replacing A by A .
Update
GM O
(iv) N to N by replacing A by A .
Update
GM
O
(v) ( , ) to ( , ) using (22) from Section 4.
Update
, Y ,Y
(vi) B\ to (B)\ using (9).
Update
(vii) Update b and b to b and b .
, ,Y Y
Step 7. Begin iteration k ; 1 using the updated quantities.

Remark 7.2. If the initial basis consists of the slack variables, then B(0) : I
and (9) becomes

[B(k ; 1)]\ : E E . . . E I.
I> I 
Remark 7.3. The eta ¬le can become very long. In some computer codes, once
the eta ¬le reaches a predetermined length, say k ; 1, then B(k ; 1) is set as
the initial basis B(0), the matrix [B(k ; 1)]\ is set as [B(0)]\, and a new eta
¬le is constructed.

Exercise 7.1. Solve the linear programming problem in Example 1.1 using the
revised simplex method. Start with phase I.

Exercise 7.2. Solve the linear programming problem in Exercises 6.3(a), (b),
and (c) using the revised simplex method.
Convexity and Optimization in n . Leonard D. Berkovitz
Copyright 2002 John Wiley & Sons, Inc.
ISBN: 0-471-35281-0




BIBLIOGRAPHY


Bartle, R. G. and D. R. Sherbert, T he Elements of Real Analysis, 3rd ed., John Wiley & Sons, New
York, 1999.
Bazaraa, M. S., H. D. Sherali, and C. M. Shetty, Nonlinear Programming, T heory and Algorithms,
2nd ed., John Wiley & Sons, New York, 1993.
Beale, E. M. L., ˜˜Cycling in the Dual Simplex Algorithm,™™ Naval Research L ogistics Quarterly 2
(1955), 269”275.
Bland, R. G., ˜˜New Finite Pivoting Rules for the Simplex Method,™™ Mathematics of Operations
Research 2 (1977), 103”107.
Chvatal, V., L inear Programming, W. H. Freeman, New York, 1983.
´
Dantzig, G. B., L inear Programming and Extensions, Princeton University Press, Princeton, N.J.,
1963.
Dresher, M., Games of Strategy: T heory and Applications, Prentice-Hall, Englewood Cliffs, N.J.,
1961.
Farkas, J., ˜˜Uber die Theorie der einfachen Ungleichungen,™™ Journal fur die reine und angewandte
¨
Mathematik 124 (1901), 1”27.
Fiacco, A. V. and G. P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimiz-
ation Techniques, John Wiley & Sons, New York, 1968.
Fleming, W., Functions of Several Variables, 2nd ed., Springer, New York, 1977.
Gale, D., T he T heory of L inear Economic Models, McGraw-Hill, New York, 1960.
Gass, S. I., L inear Programming, Methods and Applications, 5th ed., McGraw-Hill, New York, 1985.
Golub, G. H. and C. F. Van Loan, Matrix Computations, Johns Hopkins University Press,
Baltimore, 1996.
Gordan, P., ˜˜Uber die An¬‚osungen linearer Gleichungen mit reelen coef¬cienten,™™ Mathematische
¨
Annalen 6 (1873), 23”28.
Hahn, S-P. and O. L. Mangasarian, ˜˜Exact Penalty Functions in Nonlinear Programming,™™
Mathematical Programming 17 (1979), 251”269.
John, F., Extremum Problems with Inequalities as Subsidiary Conditions, Studies and Essays:
Courant Anniversary Volume (K. O. Friedricks, O. E. Neugebauer, and J. J. Stoker, Ed.),
Interscience, New York, 1948, pp. 187”204.
Karush, W., ˜˜Minima of Functions of Several Variables with Inequalities as Side Conditions,™™
Masters™ Dissertation, University of Chicago, Chicago, IL, Dec. 1939.
Kuhn, H. W. and A. W. Tucker, Nonlinear Programming, Proceedings of the Second Berkeley
Symposium on Mathematical Statistics and Probability (J. Neyman, Ed.), University of
California Press, Berkeley, CA, 1951, pp. 481”492.

261
262 BIBLIOGRAPHY

Mangasarian, O. L. Nonlinear Programming, McGraw-Hill, New York, 1969.
McShane, E. J., ˜˜The Lagrange Multiplier Rule,™™ American Mathematics Monthly 80 (1973),
922”924.
Motzkin, T. S., ˜˜Beitrage zur Theorie Linearen Ungleichungen,™™ Inaugural Dissertation, Basel,
´
Jerusalem, 1936.
Murtagh, B. A., Advanced L inear Programming: Computation and Practice, McGraw-Hill, New
York, 1981.
Pennisi, L. L., ˜˜An Indirect Suf¬ciency Proof for the Problem of Lagrange with Differential
Inequalities as Side Conditions,™™ Transactions of the American Mathematical Society 74 (1953),
177”198.
Rockafellar, R. T., Convex Analysis, Princeton University Press, Princeton, N.J., 1970.
Rudin, W., Principles of Mathematical Analysis, 3rd ed., McGraw-Hill, New York, 1976.
Convexity and Optimization in n . Leonard D. Berkovitz
Copyright 2002 John Wiley & Sons, Inc.
ISBN: 0-471-35281-0




INDEX


Af¬ne hull, 74 Closed half spaces, 35”36
Af¬ne transformations, 78”114 Closed line segments, 31
Algebra of sets, 4”5 Closed sets, 6”8
Alternative theorems Closest point characterization, 50”51
convex functions, 113”117 Coercive functions, 20
convex sets, linear inequalities, 61”68 Colonel Blotto game, 122”127
Farkas™s lemma, 63”65, 67”68 Compactness, 14”15
Gale™s theorem, 68 convex sets, separation theorem, 54”55
Gordan™s theorem, 65”67 supporting hyperplanes, extreme points, 58”61
Motzkin™s theorem, 66”67 Complementary slackness condition, linear
Anticycling routine, simplex method programming, 141”145
phase I procedure, 254 Completeness property, real numbers, 12”13
termination and cycling, 250, 254 Concave functions
de¬ned, 88
Backward transformation, revised simplex game theory, 117
method, 259 Consistency
Barycentric coordinates, 74 convex programming, perturbation theory,
Basic solution, simplex method, 231 192”200
convex programming, problem II (CPII),
Basic variables
phase II procedure, 235”245 180”181
strong in (CPII), 183”187
simplex method, 230
Bland™s rule, simplex method, termination and Constraint quali¬cations
cycling, 248”250 convex programming
Bolzano”Weierstrass property, 15 necessary conditions, 183”188
Boundary points quadratic programming, 212
convex function optimization, 137 differentiable nonlinear programming,
supporting hyperplanes, 56”57 154”163
Kuhn”Tucker constraint quali¬cation,
Canonical linear programming problem, 162”163
234”260 tangential constraints, 165”178
optimization, 144 Continuity, 8”11
simplex method, 224”225 Convex cones, 44, 62
extreme points, feasible sets, 225”229 Convex functions
phase I, 251”255 alternative theorems, 113”117
revised simplex method, 258”260 de¬nitions and properties, 87”101
Caratheodory theorem, 41”43
´ differentiable functions, 106”113
Cartesian products, 16”18 differentiable nonlinear programming,
Cauchy”Schwarz inequality, 3”4 159”163


263
264 INDEX

Convex functions (Continued) Degenerate basic solution, simplex method,
game theory applications, 117”121 231, 245”247
Jensen™s inequality, 90”91 Derivatives
optimization problems, 137”139 convex functions, 94”96, 99
Euclidean n-space (RL)
partial derivatives, 99, 106”109
subgradients, 102”106 differentiation, 22”29
Convex hulls, 41”43 linear transformation, 22”25
extreme points, 85”86 second derivative test, differentiable
Convex programming, duality unconstrained problems, 130”136
geometric interpretation, 207”210 Differentiability
Lagrangian duality, 200”207 convex functions, 99, 106”113
Euclidean n-space (RL), linear
linear programming, 215”221
quadratic programming, 212 transformation, 24
Convex programming problem I (CPI), Differentiable nonlinear programming
problem statement, 179”180 ¬rst-order conditions, 145”163
Convex programming problem II (CPII) second-order conditions, 163”178
problem dual to (DCPII), 200”207 Differentiable unconstrained problems,
problem statement, 180”181 129”136
Convex sets linear regression, 134”135
af¬ne geometry, 69”80 local minimizer, 131
barycentric coordinates, 74 orthogonal mean-square approximations,
dependence, 71”72 135”136
hull dimensions, 74 positive semide¬nite functions, 131”132
independence, 72”73 second derivative test, 131
linear manifold, 69”71 strict minimizers, 130”136
Differentiation, Euclidean n-space (RL),
linear transformations, 78
nonvoid interiors, 76”77 25”29
parallel subspace, 70 Directional derivatives, convex functions,
simplex dimension, 76 95”96
extreme points, 56”61 Disjoint convex sets, hyperplane separation,
hyperplane support, 56”61 53
linear inequalities, systems of, 61”68 Duality theorems
Farkas™s lemma, 63”65, 67 convex programming
dual quadratic programming (DQP),
Gale™s lemma, 68
Gordan™s lemma, 65”67 214”215
Motzkin™s lemma, 66”67 geometric interpretation, 207”210
nonempty relative interiors, 81”82 Lagrangian duality, 200”207
properties of, 35”45 linear programming, 215”221
Caratheodory theorem, 41”42
´ gaps, convex programming, 202”207
convex cone, 44 quadratic programming, 212
convex hull, 41, 43
half spaces, 35”36 Elementary operations, simplex method,
points, convex combinations, 40”41 232”234
scalar combinations, 37 Empty set, 4”5
relative interior points, 80”81 Entering variable
separation theorems, 45”56 revised simplex method, 256”260
disjoint convex sets, 53”54, 81 simplex method, 239”245
proper separation, 46, 53 Epigraphs, convex functions, 88”89
strict separation, 46 Equality constraints
convex programming problem (CPI), 180
strong separation, 47”49, 54
Current basis, simplex method, 234”245 differentiable nonlinear programming
Current value, simplex method, 234”245 necessary conditions, 146”159, 168”171
Cycling, simplex method, 245”250 suf¬cient conditions, 159”160, 172”177
Equilibrium prices, 196
INDEX 265

Equivalent norms, Euclidean n-space (RL), differentiable convex functions, 110”113
16”18 differentiable unconstrained problems,
Eta ¬le, revised simplex method, 258”260 131”132
Eta matrix, revised simplex method, 257”260 Hyperplanes
Euclidean norm, 2”3 convex functions, subgradients, 102”106
Euclidean n-space (RL) convex programming duality, geometric
de¬ned, 1 interpretation, 208”210
metric topology, 5”8 convex set properties, 35”36
vectors, 1”4 Farkas™s lemma, 65
Extreme points de¬nition, 33”34
convex sets, 56”61, 85 supporting hyperplanes, 56”59, 61, 85
simplex method, feasible sets, 225”230
Implicit function theorem, 163”164

<<

. 57
( 59 .)



>>