Linear and Nonlinear Optimization
Linear and Nonlinear Optimization
SECOND EDITION
Igor Griva
Stephen G. Nash
Ariela Sofer
George Mason University
Fairfax, Virginia
Contents
Preface xiii
I Basics 1
1 Optimization Models 3
1.1 Introduction . 3
1.2 Optimization: An Informal Introduction 4
1.3 Linear Equations . 7
1.4 Linear Optimization . 10
Exercises . 12
1.5 Least-Squares Data Fitting . 12
Exercises . 14
1.6 Nonlinear Optimization . 14
1.7 Optimization Applications 18
1.7.1 Crew Scheduling and Fleet Scheduling 18
Exercises . 22
1.7.2 Support Vector Machines . 22
Exercises . 24
1.7.3 Portfolio Optimization . 25
Exercises . 27
1.7.4 Intensity Modulated Radiation Treatment Planning 28
Exercises . 31
1.7.5 Positron Emission Tomography Image Reconstruction 32
Exercises . 34
1.7.6 Shape Optimization 35
1.8 Notes . 40
2 Fundamentals of Optimization 43
2.1 Introduction . 43
2.2 Feasibility and Optimality 43
Exercises . 47
2.3 Convexity 48
2.3.1 Derivatives and Convexity . 50
vvi Contents
Exercises . 52
2.4 The General Optimization Algorithm 54
Exercises . 58
2.5 Rates of Convergence 58
Exercises . 61
2.6 Taylor Series . 62
Exercises . 65
2.7 Newton’s Method for Nonlinear Equations . 67
2.7.1 Systems of Nonlinear Equations 72
Exercises . 74
2.8 Notes . 76
3 Representation of Linear Constraints 77
3.1 Basic Concepts 77
Exercises . 82
3.2 Null and Range Spaces . 82
Exercises . 84
3.3 Generating Null-Space Matrices . 86
3.3.1 Variable Reduction Method 86
3.3.2 Orthogonal Projection Matrix . 89
3.3.3 Other Projections . 90
3.3.4 The QR Factorization . 90
Exercises . 91
3.4 Notes . 93
II Linear Programming 95
4 Geometry of Linear Programming 97
4.1 Introduction . 97
Exercises . 98
4.2 Standard Form 100
Exercises . 105
4.3 Basic Solutions and Extreme Points . 106
Exercises . 114
4.4 Representation of Solutions; Optimality 117
Exercises . 123
4.5 Notes . 124
5 The Simplex Method 125
5.1 Introduction . 125
5.2 The Simplex Method 126
5.2.1 General Formulas . 129
5.2.2 Unbounded Problems . 134
5.2.3 Notation for the Simplex Method (Tableaus) . 135
5.2.4 Deficiencies of the Tableau 139Contents vii
Exercises . 141
5.3 The Simplex Method (Details) . 144
5.3.1 Multiple Solutions . 144
5.3.2 Feasible Directions and Edge Directions . 145
Exercises . 148
5.4 Getting Started—Artificial Variables 149
5.4.1 The Two-Phase Method 150
5.4.2 The Big-M Method 156
Exercises . 159
5.5 Degeneracy and Termination 162
5.5.1 Resolving Degeneracy Using Perturbation 167
Exercises . 170
5.6 Notes . 171
6 Duality and Sensitivity 173
6.1 The Dual Problem 173
Exercises . 177
6.2 Duality Theory 179
6.2.1 Complementary Slackness . 182
6.2.2 Interpretation of the Dual . 184
Exercises . 185
6.3 The Dual Simplex Method 189
Exercises . 194
6.4 Sensitivity 195
Exercises . 201
6.5 Parametric Linear Programming . 204
Exercises . 210
6.6 Notes . 211
7 Enhancements of the Simplex Method 213
7.1 Introduction . 213
7.2 Problems with Upper Bounds 214
Exercises . 221
7.3 Column Generation . 222
Exercises . 227
7.4 The Decomposition Principle 227
Exercises . 238
7.5 Representation of the Basis . 240
7.5.1 The Product Form of the Inverse . 240
7.5.2 Representation of the Basis—The LU Factorization . 248
Exercises . 256
7.6 Numerical Stability and Computational Efficiency . 259
7.6.1 Pricing . 260
7.6.2 The Initial Basis 264
7.6.3 Tolerances; Degeneracy 265
7.6.4 Scaling . 266viii Contents
7.6.5 Preprocessing . 267
7.6.6 Model Formats . 268
Exercises . 269
7.7 Notes . 270
8 Network Problems 271
8.1 Introduction . 271
8.2 Basic Concepts and Examples 271
Exercises . 280
8.3 Representation of the Basis . 280
Exercises . 287
8.4 The Network Simplex Method . 287
Exercises . 294
8.5 Resolving Degeneracy 295
Exercises . 299
8.6 Notes . 299
9 Computational Complexity of Linear Programming 301
9.1 Introduction . 301
9.2 Computational Complexity . 302
Exercises . 304
9.3 Worst-Case Behavior of the Simplex Method 305
Exercises . 308
9.4 The Ellipsoid Method 308
Exercises . 313
9.5 The Average-Case Behavior of the Simplex Method 314
9.6 Notes . 316
10 Interior-Point Methods for Linear Programming 319
10.1 Introduction . 319
10.2 The Primal-Dual Interior-Point Method . 321
10.2.1 Computational Aspects of Interior-Point Methods 328
10.2.2 The Predictor-Corrector Algorithm 329
Exercises . 330
10.3 Feasibility and Self-Dual Formulations . 331
Exercises . 334
10.4 Some Concepts from Nonlinear Optimization . 334
10.5 Affine-Scaling Methods . 336
Exercises . 343
10.6 Path-Following Methods 344
Exercises . 352
10.7 Notes . 353Contents ix
III Unconstrained Optimization 355
11 Basics of Unconstrained Optimization 357
11.1 Introduction . 357
11.2 Optimality Conditions 357
Exercises . 361
11.3 Newton’s Method for Minimization . 364
Exercises . 369
11.4 Guaranteeing Descent 371
Exercises . 374
11.5 Guaranteeing Convergence: Line Search Methods . 375
11.5.1 Other Line Searches 381
Exercises . 385
11.6 Guaranteeing Convergence: Trust-Region Methods 391
Exercises . 398
11.7 Notes . 399
12 Methods for Unconstrained Optimization 401
12.1 Introduction . 401
12.2 Steepest-Descent Method 402
Exercises . 408
12.3 Quasi-Newton Methods . 411
Exercises . 420
12.4 Automating Derivative Calculations . 422
12.4.1 Finite-Difference Derivative Estimates 422
12.4.2 Automatic Differentiation . 426
Exercises . 429
12.5 Methods That Do Not Require Derivatives . 431
12.5.1 Simulation-Based Optimization 432
12.5.2 Compass Search: A Derivative-Free Method . 434
12.5.3 Convergence of Compass Search . 437
Exercises . 440
12.6 Termination Rules 441
Exercises . 445
12.7 Historical Background 446
12.8 Notes . 448
13 Low-Storage Methods for Unconstrained Problems 451
13.1 Introduction . 451
13.2 The Conjugate-Gradient Method for Solving Linear Equations 452
Exercises . 459
13.3 Truncated-Newton Methods . 460
Exercises . 465
13.4 Nonlinear Conjugate-Gradient Methods . 466
Exercises . 469
13.5 Limited-Memory Quasi-Newton Methods . 470x Contents
Exercises . 473
13.6 Preconditioning . 474
Exercises . 477
13.7 Notes . 478
IV Nonlinear Optimization 481
14 Optimality Conditions for Constrained Problems 483
14.1 Introduction . 483
14.2 Optimality Conditions for Linear Equality Constraints . 484
Exercises . 489
14.3 The Lagrange Multipliers and the Lagrangian Function 491
Exercises . 493
14.4 Optimality Conditions for Linear Inequality Constraints 494
Exercises . 501
14.5 Optimality Conditions for Nonlinear Constraints 502
14.5.1 Statement of Optimality Conditions 503
Exercises . 508
14.6 Preview of Methods . 510
Exercises . 514
14.7 Derivation of Optimality Conditions for Nonlinear Constraints 515
Exercises . 520
14.8 Duality 522
14.8.1 Games and Min-Max Duality . 523
14.8.2 Lagrangian Duality 526
14.8.3 Wolfe Duality . 532
14.8.4 More on the Dual Function 534
14.8.5 Duality in Support Vector Machines 538
Exercises . 542
14.9 Historical Background 543
14.10 Notes . 546
15 Feasible-Point Methods 549
15.1 Introduction . 549
15.2 Linear Equality Constraints . 549
Exercises . 555
15.3 Computing the Lagrange Multipliers 556
Exercises . 561
15.4 Linear Inequality Constraints 563
15.4.1 Linear Programming 570
Exercises . 572
15.5 Sequential Quadratic Programming . 573
Exercises . 580
15.6 Reduced-Gradient Methods . 581
Exercises . 588Contents xi
15.7 Filter Methods 588
Exercises . 597
15.8 Notes . 598
16 Penalty and Barrier Methods 601
16.1 Introduction . 601
16.2 Classical Penalty and Barrier Methods . 602
16.2.1 Barrier Methods 603
16.2.2 Penalty Methods 610
16.2.3 Convergence 613
Exercises . 617
16.3 Ill-Conditioning . 618
16.4 Stabilized Penalty and Barrier Methods . 619
Exercises . 623
16.5 Exact Penalty Methods . 623
Exercises . 626
16.6 Multiplier-Based Methods 626
16.6.1 Dual Interpretation . 635
Exercises . 638
16.7 Nonlinear Primal-Dual Methods . 640
16.7.1 Primal-Dual Interior-Point Methods 641
16.7.2 Convergence of the Primal-Dual Interior-Point Method . 645
Exercises . 647
16.8 Semidefinite Programming . 649
Exercises . 654
16.9 Notes . 656
V Appendices 659
A Topics from Linear Algebra 661
A.1 Introduction . 661
A.2 Eigenvalues . 661
A.3 Vector and Matrix Norms 662
A.4 Systems of Linear Equations 664
A.5 Solving Systems of Linear Equations by Elimination 666
A.6 Gaussian Elimination as a Matrix Factorization . 669
A.6.1 Sparse Matrix Storage . 675
A.7 Other Matrix Factorizations . 676
A.7.1 Positive-Definite Matrices . 677
A.7.2 The LDLT and Cholesky Factorizations 678
A.7.3 An Orthogonal Matrix Factorization 681
A.8 Sensitivity (Conditioning) 683
A.9 The Sherman–Morrison Formula 686
A.10 Notes . 688xii Contents
B Other Fundamentals 691
B.1 Introduction . 691
B.2 Computer Arithmetic 691
B.3 Big-O Notation, O(·) 693
B.4 The Gradient, Hessian, and Jacobian 694
B.5 Gradient and Hessian of a Quadratic Function . 696
B.6 Derivatives of a Product . 697
B.7 The Chain Rule . 698
B.8 Continuous Functions; Closed and Bounded Sets 699
B.9 The Implicit Function Theorem . 700
C Software 703
C.1 Software . 703
Bibliography 707
Index
Index
An italic e or f following a page number indicates that an example or a figure appears on that page.
Abadie, J., 547, 598
Ablow, C.M., 657
active constraint, 44
active set, 44, 563
active-set method, 565e, 565f, 567e,
569f, 563–573, 598, 601
algorithm, 566–567
for linear programming, 570–572
adaptive algorithm, 433
adjacent extreme point, see extreme
point, adjacent
Adler, Ilan, 315, 324, 354
affine-scaling direction
dual, 341
primal, 338
affine-scaling matrix, 336
affine-scaling method, 320, 336–344
dual, 340–343
primal, 339e, 337–343
primal-dual, 342–343
affine-scaling transformation, 336
Ahuja, Ravindra K., 293, 299, 300
Aizerman, M., 547
Al-Baali, M., 479
al-K¯aš¯ı, 448
Andersen, Erling D., 267, 354
Andersen, Knud D., 267
Anstreicher, Kurt M., 354
arc, 271
Archimedes, 16
Archimedes’ problem, 16, 16f
Armijo condition, 377
artificial variable, 149–162, see also
big-M method; two-phase
method
assignment problem, 276e, 277f,
275–277
augmented Lagrangian function, 627
augmented Lagrangian method, 628e,
626–640, 657
algorithm, 627–628
convergence, 631–634
dual interpretation, 635–638
automatic differentiation, see
differentiation, automatic
average-case cost, 301–302, see also
complexity
Avriel, Mordecai, 501, 502, 547
backsubstitution, 667
backtracking line search, see line search,
backtracking
Barnes, Earl R., 354
Barnhart, Cynthia, 40
barrier function, 319, 603
inverse, 604
logarithmic, 320, 335, 344, 604
barrier method, 319–320, 335, 344,
604e, 602–610, 656–657
convergence, 613–617
dual, 353
ill-conditioning, 608e, 608–609,
618–619, 657
727728 Index
Lagrange multiplier estimate, 607e,
606–608
stabilized, 622e, 619–623, 657
barrier parameter, 604
barrier term, 602
barrier trajectory, 345, 605, see also
central path
Bartels, Richard H., 252
basic feasible solution, 98, 107, 108e,
125, 126, see also extreme
point
adjacent, 112
degenerate, 110, 117
extended, 215–216
network model, 285–286
basic solution, 106–117
basic variable, 86, 107
basis, 107
adjacent, 112
basis matrix, 107
for the null space, see null-space
matrix, basic matrix
product form, see product form of
the inverse
representation, 240–259
representation in network, 280–287
basis recovery procedure, 329
Bau, David, III, 93
Bazaraa, Mikhtar S., 171
Beale, E.M.L., 171, 211
Bellman, Richard E., 657
Bernoulli, Jacob, 41
Bernoulli, John, 35, 544
Bertsekas, Dimitri P., 657, 701
BFGS update, see quasi-Newton
method, BFGS
Bicani ´ c N., 447 ´
Biegler, Lorenz T., 657
big-M method, 149, 156–162, 237, 292
big-O notation, 691, 693–694
binding constraint, see active constraint
Bixby, Robert E., 41, 265
Bland’s rule, 166–167, 171
Bland, Robert G., 166, 167, 171, 313,
316
Bliss, Gilbert A., 545, 546
block angular problem, 227, 238
Boggs, Paul T., 598
Bolza, O., 546
bordered-inverse formula, 621
Borgwardt, Karl-Heinz, 315–317
Borisov, W.W., 449
Bosch, Robert A., 354
Boser, B.E., 547
boundary of a constraint, 44
boundary of a set, 44
bounded set, 699
brachistochrone problem, 544
Braverman, E., 547
Brearly, A.L., 267
Brigham, G., 657
Broyden class, see quasi-Newton
method, Broyden class
Broyden, C.G., 417
Buck, R. Creighton, 691, 700
Burges, Christopher J.C., 41
Byrd, Richard H., 420, 449, 479, 657
calculus of variations, 543–546
canonical form for linear programming,
see linear programming,
canonical form
Carpentier, J., 598
Carson, R., 41
catenary problem, 35, 41, 705
Cauchy, Augustin-Louis, 448, 545
centering direction, 347
central path, 320, 344, 345f, 345–346,
see also barrier trajectory
central trajectory, see central path
chain rule, 698e, 698–699
characteristic equation, 661
Charnes, Abraham, 171
Chen, Ke, 479
Cheriyan, J., 299
Cholesky factorization, 448, 680e,
678–680
incomplete, 479
Chvátal, Vašek, 124, 171, 238, 300, 316
closed set, 699
coincidence event, 32
coincidence line, 32Index 729
Coleman, Thomas F., 657
column generation, 214, 222–227, 270
compass search, 435e, 436f, 434–441
algorithm, 437
convergence, 437–441
complementary slackness
linear programming, 183e,
182–184, 188
strict, 183, 189
nonlinear optimization, 496, 506
strict, 497, 506
complexity, 59, 301–305, 316
ellipsoid method, see ellipsoid
method, complexity
linear programming, see linear
programming, complexity
simplex method, see simplex
method, complexity
smoothed analysis, 317
computational complexity, see
complexity
computer arithmetic, 691–693, see also
floating-point arithmetic
IEEE standard, 691
Concus, Paul, 479
condition number, 664
conditioning, 683–686
cone, 117, 516
second-order, 655, 656f
cone programming, 649, 658
convex, 649
second-order, 655
conjugate vectors, 453
conjugate-gradient method
linear, 455e, 451–460, 478
algorithm, 454
preconditioned, 476e, 475–476
nonlinear, 451, 452, 467e,
466–470, 479
algorithm, 466
comparison with other methods,
469
Fletcher–Reeves, 469, 479
Hestenes–Stiefel, 469
Polak–Ribiére, 469, 479
Conn, Andrew R., 400, 657
connected network, 281, 282f
constraint
linear, 77–93, 125
nonlinear, 483–547
constraint matrix, 101
constraint qualification, 546
Conte, Samuel D., 412
continuous function, 691, 699–700
control systems, 653
control theory, 543
convergence rate, 43, 60e, 58–62
r-linear, 439
linear, 59
quadratic, 60
superlinear, 59, 399
convex combination, 50
convex function, 49f, 52f, 48–54
strictly, 49
convex optimization problem, 49
convex set, 48f, 48–54
convexity, 48–54, see also convex
function; convex set
Corliss, George F., 449
Courant, Richard, 546, 656, 691
course outline, xvii–xxi
introduction to optimization,
xx–xxi
linear programming, xvii–xviii
nonlinear optimization, xviii–xx
Cramer’s rule, 287
crash procedure, 265, see simplex
method, initialization
crew scheduling, 18–20, 40
Cristianini, Nello, 41
Cullum, Jane K., 478
Curtis, A.R., 449
cut in a network, 279e, 279
cutting plane, 651
cutting stock problem, 223f, 225e,
223–227, 270
cycle in a network, 281, 282f, 287
cycling, 164–171, 211
Dantzig, George B., 124, 171, 211, 270
data fitting, see least-squares data fitting
Davidon, William C., 419, 448730 Index
Davis, Timothy A., 689
de Boor, Carl W., 412
Deasy, Joseph O., 41
decomposition principle, 214, 233e,
227–240, 270
algorithm, 232
initialization, 236–237
degeneracy, 112, 115, 117, 125, 155,
155e, 195, 211, 222, 259,
265–266, 294, 497e, 498e,
497–499, 506
in network model, 295–299
demand in a network, 273
Dembo, Ron S., 478
den Hertog, D., 353, 657
Dennis, John E., Jr., 394, 399, 449,
700
dependent variable, 86
derivative, see differentiation
derivative of a product, 697e, 697–698
derivative-free method, 450, see also
compass search
descent direction, 56
feasible, 58
Devex pricing, see pricing, Devex
differentiation
automatic, 366, 401, 422, 426–431,
449
forward mode, 429
reverse mode, 429
finite difference, 423e, 422–426,
429–430, 449
central difference, 425
complex difference, 426, 449
deficiencies, 432–434
forward difference, 423
sparse, 449
of product, see also chain rules
gradient; Hessian; Jacobian
Dijkstra, Edsger W., 299
Dikin, I.I., 336, 354
direction of a set, see direction of
unboundedness
direction of negative curvature, see
negative curvature
direction of unboundedness, 98,
112–115, 117–124
directional derivative, 382
discrete optimization, see integer
programming
dogleg strategy, see trust-region method,
dogleg strategy
dose-volume histogram, 31
double precision arithmetic, 693
Dow Jones Industrial average, 27
Drud, Arne S., 599
dual feasibility, 529
dual function, 524, 528
derivatives, 538e, 537–538
dual linear program, 173–179, see also
duality, linear programming
canonical form, 173–176
formation, 173–179
general form, 177e, 176–177
interpretation, 184–185
solution, 181, 182e
standard form, 177
dual nonlinear program, see duality,
nonlinear optimization
dual price, 492
dual simplex method, 192e, 189–195,
211, 264, 300
algorithm, 191
big-M method, 195
phase-1 problem, 195
dual variable, 8, 125, see also Lagrange
multiplier
duality, 538, 545–547
linear programming, 279, see also
dual linear program
strong, 179–181, 185
theory, 179–189, 211
weak, 179e, 179–180
nonlinear
conjugate, 527
nonlinear optimization, 177, 179,
484, 522–543, 547
convex, 532
Lagrangian, 526–532
local, 536e, 534–537
min-max, 523–526Index 731
strong, 525–526, 531–532
weak, 524, 529e, 529–531
Wolfe, 533e, 532–533
support vector machine, 538–543,
547
duality gap, 530, 530e
edge direction, 147e, 145–148
Edmonds, Jack, 299
efficient frontier, 27, 28f
eigenvalue, 662e, 661–662
eigenvector, 662e, 661–662
Eisemann, K., 270
Eisenstat, Stanley C., 478
elementary matrix, 240–248, 257, 258
elementary permuation matrix, see
permutation matrix,
elementary
elimination, see Gaussian elimination
ellipsoid, 309e, 310f, 309–310
ellipsoid method, 312e, 312f, 308–314,
316, 319
algorithm, 311
complexity, 313
entering variable, 130, see also pricing
mach, see machine epsilon
equality-constrained problem
linear, 79e, 79–80
Eskow, Elizabeth, 400
eta file, 241
eta vector, 241–247, 258
Euclid’s problem, 490
Euler, Leonhard, 544, 545
evaluation graph, 427, 427f
exact line search, see line search, exact
exact penalty function, 623
exact penalty method, see penalty
method, exact
Excel, 703
excess variable, 102
exponent in scientific notation, 692
exponential algorithm, 304–305, see
also complexity
extended basic feasible solution, see
basic feasible solution,
extended
extreme point, 106–124, 228–240, 270
adjacent, 112
relation to basic feasible solution,
110–112
Fan, Ky, 657
Farkas’ lemma, 188, 211
Farkas, Julius, 211
Farvolden, Judith M., 270
feasible arc, 520
feasible curve, 484, 516e, 516f, 515–517
feasible descent direction, see descent
direction, feasible
feasible direction, 78f, 78–80, 147e,
145–148, 483, 484
feasible point, 43, 44
feasible region, see feasible set
feasible set, 44, 45f
feasible spanning tree solution, 285–286
feasible-point method, 78–79, 126,
549–599
Fermat, 3
Ferris, Michael C., 41
Fiacco, Anthony V., 353, 617, 618, 656,
657
fill-in, 673
filter, 513–514, 589, 590f
filter method, 588–599
finite-difference derivative, see
differentiation, finite
difference
finite-precision arithmetic, see
floating-point arithmetic
first-order conditions for optimality, see
optimality conditions
fixed variable, 269
fleet assignment, 40
fleet scheduling, 18, 20–21
Fletcher, Roger, 417, 419, 448, 469, 542,
599
floating-point arithmetic, 691
Floudas, Christodoulos A., 76
fluence map, 29
fluence matrix, 29
Fomin, S.V., 41
Ford, Jr., L.R., 270, 279, 299, 300732 Index
Forrest, John J.H., 256, 264
Forrest–Tomlin update, 256
forward arc, 294
Fourer, Robert, 41
Fredman, M.L., 299
free constraint, 268
free variable, 102, 269
Freedman, B.A., 354
Frisch, K.R., 656, 657
Fritz–John conditions, 522, see also
optimality conditions,
constrained
Fulkerson, D.R., 270, 279, 299, 300
full pricing, see pricing, full
Gács, P., 309, 317
Gal, T., 211
Gale, David, 211
game theory, 185, 523–526
Gass, Saul I., 211
Gauss, Carl Friedrich, 448, 545, 666
Gaussian elimination, 302, 303,
666–676
accuracy, 685–686, 688
as matrix factorization, 669–676
costs, 667–668
for sparse matrix, 674e, 672–676
Gay, David M., 41, 354, 400
Gelfand, I.M., 41
general optimization algorithm, xiii, 56f,
54–58, 365
generalized inverse, see Penrose–Moore
generalized inverse
George, Alan, 689
Gilbert, Jean Charles, 479
Gill, Philip E., 93, 400, 443, 448, 449,
598
Gilmore, Phillis C., 270
Givens rotation, 681
global optimum, see optimum, global
globalization strategy, 375, 511
Goldberg, A.V., 299
golden ratio, 412
Goldfarb, Donald, 264, 313, 316, 417
Goldman, Alan J., 211
Golub, Gene H., 93, 252, 479, 558, 661,
682
Gomory, Ralph E., 270
Gondzio, J., 354
Gopalan, Ram, 40
Gould, F.J., 547
Gould, Nicholas I.M., 400, 599, 657
gradient, 691, 694e, 694–697
of a quadratic function, 696e,
696–697
gradient search, see steepest-descent
method
gradient-related direction, 377
Gram–Schmidt orthogonalization, 681
Gregory, John, 545
Gregory, John W., 41
Griewank, Andreas, 449, 479
Griva, Igor, 41
Guignard, Monique, 547
Güler, Osman, 354
Guyon, Isabel M., 547
Hager, William W., 689
Haimovich, M., 315
Halley, Edmond, 448
Hansen, Eldon, 76
hard constraint, 29
Harris, Paula M.J., 264
Herman, Gabor T., 41
Heron’s problem, 490
Hessian, 691, 694e, 694–697
of a quadratic function, 696e,
696–697
Hestenes, Magnus R., 456, 478, 479, 657
Hestenes–Stiefel, 469
Higham, N.J., 689
Hilbert, David, 546, 691
Ho, J.K., 270
Hoffman, Alan J., 171, 305
Horn, Roger A., 661
Horner, William George, 448
Horst, Reiner, 76
Householder reflection, 681
Hribar, Mary E., 657
Hung, P.F., 354
Huygens, Christian, 35Index 733
ill-conditioned problem, 684
ill-conditioning, 265
implicit function theorem, 691,
700–701
IMRT (intensity modulated radiation
treatment) planning, 18,
28–32, 41
inactive constraint, 44
incomplete Cholesky factorization, see
Cholesky factorization,
incomplete
independent variable, 86
inequality-constrained problem
linear, 79e, 79–80
infeasible linear program, 153e, 154f,
153–154
infimum, 523
integer programming, 19, 20, 286, 704,
see also knapsack problem
intensity modulated radiation treatment
(IMRT) planning, 18, 28–32,
41
interior of a constraint, 44
interior point, 44, 320, 699
interior-point method, 125, 173, 302,
602
complexity, 321
computational aspects, 328–329,
354
dual, 320
linear programming, 319–354, see
also affine-scaling method;
Karmarkar’s method;
path-following method;
potential-reduction method
primal, 320
primal-dual, 325e, 320–331
nonlinear, see primal-dual
method, nonlinear
inverse barrier function, see barrier
function, inverse
Jacobian, 691, 695e, 694–695
Jain, A., 598
Jarvis, John J., 171
John, Fritz, 522
Johnson, Calvin A., 41
Johnson, Charles R., 661
Johnson, Ellis L., 40
Johnson, K.H., 447
Jones, Kim L., 270
Kantorovich, Leonid V., 171, 354
Karmarkar’s method, 301, 319, 321,
336, 353, 609, 640
Karmarkar, Narendra, 301, 319, 353
Karp, Richard M., 299
Karush, W., 545, 546
Karush–Kuhn–Tucker conditions, 545,
see also optimality conditions,
constrained
kernel of a support vector machine, 541,
547
Kernighan, Brian W., 41
Khachiyan’s method, see ellipsoid
method
Khachiyan, Leonid G., 308, 317
KKT conditions, 506, see also
optimality conditions,
constrained
Klee, Victor, 211, 306
Klee–Minty problem, 306e, 307f,
306–308, 313, 314, 316
Kleinschmidt, Peter, 211
knapsack problem, 225, 270
Kojima, M., 354
Kolda, Tamara G., 450
Krylov subspace, 458
Kuhn, Harold W., 211, 545, 546
Kuhn–Tucker conditions, 506
Kuhn-Tucker conditions, see also
optimality conditions,
constrained
1 exact penalty function, 623
Lagrange multiplier, 125, 177, 484,
488e, 488f, 487–494
computation of, 554–563
least-squares estimate, 558
via QR factorization, 559
via nonorthogonal projection,
559734 Index
via orthogonal projection,
558–559
via variable reduction, 558
first-order estimate, 557
Lagrange, Joseph Louis, 493, 544–546
Lagrangian function, 484, 491–494, 504
Lanczos algorithm, 478
Lanczos, Cornelius, 478
Lange, K., 41
Lapack, 686
Lasdon, L.S., 598
LDLT factorization, 679e, 678–680
least-squares data fitting, 7, 12–14, 357
nonlinear, 14
least-squares problem, 682e, 681–683
leaving variable, 130
Lee, Eva K., 41
Lee, T.C., 270
Leibniz, Gottfried, 35
Lemaréchal, Claude, 479, 657
Lemke, C.E., 211
length of the input data (L), 303–305
level set, 378
Levenburg, K., 400
Lewis, Robert Michael, 450
lexicographic method, see perturbation
lexicographic ordering, 168e, 167–171
Leyffer, Sven, 599
Liberti, Leo, 76
limited-memory quasi-Newton method,
see quasi-Newton method,
limited memory
Lin, Cantian, 545
line search, 57, 57f, 375e
backtracking, 378
exact, 382
naive, 376e
line search method, 375–391, 400, 401
convergence theorem, 378–381
linear conjugate-gradient method, see
conjugate-gradient method,
linear
linear constraint, 77–93, 125
linear convergence, see convergence
rate, linear
linear equations, 7–9, 664–668
linear matrix inequality, 651
linear optimization, see linear
programming
linear programming, 8, 10–12, 41, 43,
86, 95–354
canonical form, 174e, 173–176
complexity, 211, 301–317
degeneracy, 112
duality, 173–211
geometry, 97–124
graphical solution, 98f, 97–100
multiple solutions, 145e, 144–145,
146f, 148, 149
self-dual formulation, 331–334,
354
sensitivity, 173, 196e, 195–204
general rules, 201
software, 704
standard form, 97, 98, 101e, 102e,
100–106
Lipschitz continuous function, 700
Liu, D.C., 479
Liu, J.W., 689
local optimum, see optimum, local
logarithmic barrier function, see barrier
function, logarithmic
Lovász, L., 309, 317
LU factorization, 240, 250e, 258, 259,
669–676
updating, 253e, 253f, 248–259
Lu, Peihuang, 479
Luenberger, David G., 405, 406
Lustig, Irvin J., 41, 267, 270, 354, 657
Lyapunov function, 653
Lyapunov, Aleksandr M., 657
Lyness, James N., 449
Mathematica, 703
machine epsilon, 265, 692
Mackie, T. Rockwell, 41
Maclaurin, Colin, 448
Maculan, Nelson, 76
Magnanti, Thomas L., 211, 293, 299,
300
Maheshwari, S.N., 299
Mangasarian, Olvi L., 25, 547Index 735
Manne, A.S., 270
Mannos, M., 305
mantissa, 692
Maratos effect, 581
Maratos, N., 657
Markowitz, Harry M., 25, 41, 673
Marquardt, D., 400
Marsten, Roy E., 41, 267, 354, 657
master problem, 229, 229e
MATLAB®, 703
matrix, 661
dense, 665
indefinite, 677
negative definite, 677
negative semidefinite, 677
nonsingular, 665
positive definite, 677e, 677–678
positive semidefinite, 677
singular, 665
sparse, 665
square, 661
symmetric, 661
triangular, 667
upper triangular, 667
matrix inequality, 651
matrix norm, see norm, matrix
maximum flow problem, 278e, 279f,
277–280
dual, 279
maximum likelihood estimation, 32
Mayer, A., 545, 546
Mayne, D.Q., 657
McCormick, Garth P., 353, 617, 656,
657
Mead, R., 450
mean-value theorem, 65
Megiddo, Nimrod, 354
Mehrotra, Sanjay, 330, 354
Meijerink, J.A., 479
Meketon, M.S., 354
merit function, 513–514, 577e, 577–580
Meszaros, C., 354
method of multipliers, 631, see also
augmented Lagrangian
method
min-max duality, see duality, nonlinear
optimization, min-max
minimax problem, 510
minimizer
global, 45, 45f, 49, 358
strict, 45, see also optimum,
global
local, 46, 46f, 49, 358
strict, 46, 358
minimum cost network flow problem,
see network flow problem
Minty, George J., 306
Mitra, G., 267
Mizuno, S., 354
model format, 260, 268–269
modeling language, 422, see also
modeling software
modeling software, 703–704
modified barrier function, 634
modified barrier method, 634–635
modified matrix factorization, 373e,
372–373, 399
Moler, Cleve B., 449
Monteiro, R.D.C., 324, 354
Moore–Penrose generalized inverse, see
Penrose–Moore generalized
inverse
Moré, Jorge J., 395, 399, 400, 449
multidirectional search, see compass
search
multiplier-based method, see method of
multipliers
Murray, Walter, 93, 400, 443, 448, 449,
598, 657
Murty, Katta G., 124, 171, 299
Nash, Stephen G., 469, 478, 479, 657
Nazareth, J.L., 270
necessary conditions for optimality, see
optimality conditions
negative curvature, 374–375
Nelder, J.A., 450
Nelder–Mead method, 450
Nemhauser, George L., 40, 270, 286
Nemirovskii, Arkadii S., 317, 658736 Index
NEOS server for optimization software,
704
Nesterov, Yurii, 658
Netlib, 478
network flow problem, 272e, 271–280
network model, 10, 16–17, 167, 227,
272f, 295f, 271–300
balanced, 274, 274e, 274f
network problem, see network model
network simplex method, 271, 287–295,
299–300
algorithm, 292
entering variable, 289, 290f
initialization, 292, 293f
operation counts, 292–293
New York Times, 308
Newton decrement, see proximity
measure
Newton direction, 323, 335
projected, 555
reduced, 551e, 550–552
Newton equations, 365
reduced, 550
Newton’s method
history, 446–448
minimization, 8, 335, 357,
364–375, 401–403, 422, 452
classical, 365
computational costs, 365–366
convergence rate, 365–369, 399
modified, 371–375
reduced, 550–552, 582
nonlinear equations, 43, 67e, 69f,
73e, 67–76, 323–324, 335,
364
convergence, 69, 74
failure, 70, 71e, 74
multiple zeroes, 70, 70e, 72f, 76
Newton, Isaac, 446–448, 544
Newton–Raphson method, 447, see also
Newton’s method
Nocedal, Jorge, 400, 420, 448, 449, 469,
479, 657
node, 271
nonbasic variable, 86, 107
nonbinding constraint, see inactive
constraint
nonconvex set, 48f
nonlinear conjugate-gradient method,
see conjugate-gradient
method, nonlinear
nonlinear optimization, 8, 14–18, 43, 86,
125, 357, 481–658
software, 704
within interior-point method, 319,
321, 334–336
nonlinear optimization problem, 125,
177
nonlinear programming, see nonlinear
optimization
nonorthogonal projection
to compute Lagrange multiplier,
559
norm, 662–664
1-norm, 663–664
2-norm, 662–664
Euclidean, 662–664
infinity, 663–664
matrix, 664e, 662–664
induced, 663
vector, 663e, 662–664
null space, 80, 83f, 82–93
null-space equation, 550
null-space matrix, 83
basis matrix, 83
generation of, 86–93
numerical factorization, 328, 674
O’Leary, Dianne P., 479
Olivera, Gustavo C., 41
open set, 699
optimal basic feasible solution, 107,
117, 121–122, 125
optimality conditions, 44–48
constrained, 483–547
first-order necessary, 486e,
485–491, 495–497, 504,
506–508, 519
linear constraints, 484–491,
499e, 494–502Index 737
nonlinear constraints, 505e,
506e, 502–510, 515–522
second-order necessary, 486e,
485–491, 496–497, 504,
506–508, 519–520
second-order sufficient,
486–491, 497–502, 504,
506–508, 519–520
unconstrained, 360e, 357–364
first-order necessary, 359
second-order necessary, 359
second-order sufficient, 359
optimization model, 3–41
optimum
global, 43, 76, see also minimizer,
global
local, 43, 76, see also minimizer,
local
optimum, global, 76
OR/MS Today, 704
Orchard-Hays, William, 171, 270
Orden, Alex, 171
Orlin, James B., 211, 293, 299, 300
Ortega, James M., 74, 358, 400, 691,
700
orthogonal matrix factorization, see QR
factorization
orthogonal projection
to compute Lagrange multiplier,
558–559
orthogonal projection matrix, 89f, 89–93
orthogonal subspace, 83
Ostrovskii, G.M., 449
Oughtred, William, 447
out-of-kilter method, 300
overflow, 692
Paige, Chris C., 478
Panier, Eliane R., 598
Papadimitriou, Christos H., 316, 352
parallel computing, 270, 432, 478
parametric linear programming, 205e,
209f, 204–211, 315
Pardalos, Panos M., 76
Parlett, Beresford N., 478
partial pricing, see pricing, partial
partial separability, 479
path, 281, 282f
path-following method, 320, 344–354
complexity, 347–352
long-step, 348
primal, 346e, 346–348
primal-dual, 345–346, 352, 354
short-step, 348–349
pattern classification, 18, 22
pattern search, see compass search
penalization method, 601
penalty function, 601, 611
exact, 623, 624f
ill-conditioning, 611–613
penalty method, 602–603, 612e,
610–613, 656–657
exact, 624e, 623–626, 657
exterior, 603, see also penalty
method
for inequality constraints, 613
ill-conditioning, 657
interior, 603, see also barrier
method
stabilized, 619–623, 657
penalty term, 602
Penrose–Moore generalized inverse, 559
permutation matrix, 248, 669
elementary, 249
Perry, A., 479
perturbation, 167–171, see also
degeneracy
PET (positron emission tomography)
image reconstruction, 18, 33f,
32–35, 41
PET image reconstruction, see positron
emission tomography (PET)
image reconstruction
phase-1 problem, 150–157, 159–161
phase-2 problem, 152, 154–156, 160,
161
Pietrzykowski, T., 657
pivot entry, 137
pivoting, 137, 668
complete, 668
Markowitz, 673–674
partial, 668738 Index
Plotkin, Serge A., 300
Polak–Ribiére, 469, 479
polyhedral set, 77
polyhedron, 77
polynomial algorithm, 304–305, see
also complexity
portfolio optimization, 18, 25–28, 41
positive-definite matrix, see matrix,
positive definite
positron emission tomography (PET)
image reconstruction, 18,
32–35, 41
potential-reduction method, 320
Powell, Michael J.D., 400, 419, 448,
449, 618, 657
Powell, Warren B., 270
preconditioning, 459, 475e, 474–479
preconditioning matrix, 475
predictor-corrector method, 321,
329–330, 354
preprocessing, 260, 267
pricing, 140, 260–264, 270
Devex, 264
full, 260
partial, 260
steepest-descent, 261
steepest-edge, 263e, 260–264, 269
primal function, 524, 527
primal linear program, 173
primal-dual method, see also
interior-point method,
primal-dual
nonlinear, 643e, 640–649, 657
algorithm, 642–643
convergence, 645–647
primal-dual simplex method, 300
principle of least action, 543
product form of the inverse, 244e,
240–247, 257, 270
projected gradient, 485
projected gradient method, 556
projected Hessian, 485
projection matrix, 90
projective method, see Karmarkar’s
method
proximity measure, 348–349
pseudoinverse, see Penrose–Moore
generalized inverse
QR factorization, 86, 90–93, 683e,
681–683
to compute Lagrange multiplier,
559
quadratic convergence, see convergence
rate, quadratic
quadratic function, 8, 9f
gradient, 696e, 696–697
Hessian, 696e, 696–697
quadratic penalty function, 577
quadratic program, 18, 574
quadratic programming software, 704
quadratic-loss function, 611
quasi-convex function, 53
quasi-Newton method, 401–402, 413e,
411–422, 448–449, 451
algorithm, 415
BFGS, 418e, 417–420, 445, 448,
449, 470
Broyden class, 419
convergence, 419–420
DFP, 419
for constrained optimization, 553
inverse update, 449
limited memory, 451, 452, 471e,
469–474, 477, 479
for constrained optimization, 553
symmetric rank-one, 416e,
414–417, 448
update formula, 414
radiotherapy, 28
range space, 83f, 82–86
Raphson, Joseph, 447
ratio test, 81, 81e, 131
Ratner, M., 598
reduced cost, 125, 130
reduced function, 485, 485e
reduced gradient, 485
reduced gradient method, 549, 583e,
581–588, 598–599
convergence, 585–588
reduced Hessian, 485Index 739
reduced Newton method, see Newton’s
method, minimization
Reeves, C.M., 469
refactorization, 252, see also LU
factorization, updating
regularity, 489, 496, 503e, 503–504,
508e, 518–519, 546–547
regularization, 644
Reid, John K., 264, 449
relative error, 692
relative interior point, 44
relaxation, 7, 20, 651
Renegar, James, 354
representation theorem, 120, 228
restart procedure, 479
reverse arc, 294
revised simplex method, see simplex
method, revised
Rheinboldt, Werner C., 74, 358, 400,
691, 700
right inverse, 559e, 557–563
Rinnooy Kan, A.H.G., 76
Rockafellar, Tyrrell R., 547
Roos, C., 353, 354
root node, 292
Rosen, J.B., 598
rounding error, 693, see floating-point
arithmetic
Rozonoer, L., 547
Ruszczynski, Andrzej, 41
Saad, Yousef, 478, 689
Saaty, Thomas, 211
saddle point, 486
saddle-point condition, 525
Saigal, Romesh, 657
SAS, 703
Sauer, Timothy, 691
Saunders, Michael A., 478
scaling, 260, 266–267, 270, 444e,
444–445
Schnabel, Robert B., 394, 400, 449, 700
Schölkopf, Bernhard, 41
Schrader, R., 316
Schrijver, Alexander, 124, 171, 316
SDP, see semidefinite programming
search direction, 55
secant condition, 412
secant method, 412e, 411–412, see also
quasi-Newton method
second-order conditions for optimality,
see optimality conditions
second-order cone, see cone,
second-order
second-order Lorenz cone, 655, 656, see
cone, second-order
selective orthogonalization, 478
self-concordance, 658
semidefinite programming, 649–658
complementarity, 654
dual standard form, 650
duality, 653–654
primal standard form, 650
semidefinite relaxation, 651
sensitivity, 489, 492e, 683–686, 704, see
also linear programming,
sensitivity
separating hyperplane, 22, 23, 24f
separation margin, 22
sequential quadratic programming
(SQP), 549, 575e, 573–581,
598
computational costs, 576
convergence, 576–580
filter method, 594e, 591–597
algorithm, 593–594
convergence, 596–597
set constraint, 527
shadow price, 125, 173, 492, see also
dual variable
shadow vertex method, 210, 211, 315,
see also parametric linear
programming
Shanno, David F., 41, 267, 354, 417,
479, 657
shape optimization, 18, 35–41
Shawe-Taylor, John, 41
Shepard, David M., 41
Shepp, Larry A., 41
Sherali, Hanif D., 171
Sherman–Morrison formula, 470, 687e,
686–689740 Index
Sherman–Morrison–Woodbury formula,
688–689
Shor, N.Z., 317
shortest path problem, 277e, 277, 278f,
280, 299
simplex method, 8, 97, 127f, 125–171,
301–302
algorithm, 131, 132e
bounded variable, 213, 219e
algorithm, 218
comparison with interior-point
method, 328–329
complexity, 302
average case, 316, 317
average-case, 314
worst case, 305–308
computational efficiency, 259–270
degeneracy, 162e, 162–171
dual form, see dual simplex method
enhancements, 213–270
general formulas, 129e, 129–134
implementation, 214
initialization, 149–162, 260,
264–265
interpreted as active-set method,
570–572
operation counts, 140–141
primal-dual form, see primal-dual
simplex method
revised, 139, 171
software, 260, 267, 269
stability, 259–270
tableau, 135–141
deficiencies, 139–141
termination, 162–171
tolerance, 260, 265–266
upper bound, 214–222
simplex multipliers, 129
Simpson, Thomas, 447, 448
simulation-based optimization, 432–434
single precision arithmetic, 693
singularity, 665
sink node, 272
Skeel, Robert, 267
skew symmetric matrix, 331
slack variable, 102
Slater condition, 547
Smola, Alexander J., 41
smoothed analysis, see complexity,
smoothed analysis
Sofer, Ariela, 41, 478, 657
soft constraint, 29
software, 703–705
Sokolowsky, D., 305
Sorensen, D.C., 400
source node, 272
spanning tree, 283f, 280–287
spanning tree solution, 285–287
sparse matrix storage, 675–676, 689
sparsity, 126, 213, 247–248, 256, 275,
366, 401, 449, 452, 456, 665,
689
spectral decomposition, 662
Spielman, Daniel A., 317
SQP, see sequential quadratic
programming
Squire, William, 449
stalling, 167, 294
standard form for linear programming,
see linear programming,
standard form
stationary point, 46, 358, 359f, 486
steepest-descent direction
reduced, 552e, 552–553
steepest-descent for linear
programming, 261
steepest-descent method, 336, 404e,
401–411, 445
convergence, 406e, 407f, 405–407,
408f
reduced, 552–553
steepest-descent pricing for linear
programming, see pricing,
steepest-descent
steepest-edge pricing, see pricing,
steepest-edge
Steiglitz, Kenneth, 316, 352
Steihaug, Trond, 400, 478
step length, 55
Stiefel, E., 456, 478, 479
Stirling’s formula, 305
Street, W. Nick, 25Index 741
strong duality, see duality
strongly feasible basis, 295f, 295–299
strongly feasible tree, see strongly
feasible basis
strongly polynomial algorithm, 300
subnetwork, 281, 281f
sufficient conditions for optimality, see
optimality conditions
sufficient decrease condition, 57, 378f
sufficient descent condition, 377–378
Suhl, L.M., 673
Suhl, Uwe H., 673
Sundarraj, R.P., 270
superlinear convergence, see
convergence rate, superlinear
supply in a network, 273
support vector, 23
support vector machine, 18, 22–25, 41
duality, see duality, support vector
machine
supremum, 523
surface, 515
´ Swietanowski, Artur, 264
symbolic factorization, 328, 674
symmetric rank-one update, see
quasi-Newton method,
symmetric rank-one
Talluri, Kalyan T., 40
tangent cone, 517f, 517–519
Tapia, Richard A., 354
Tardos, Éva, 300
Tarjan, Robert E., 299
Taylor series, 63e, 64e, 64f, 62–66, 358,
483
remainder form, 65
Taylor, Brook, 448
Ten, Shang-Hua, 317
Terlaky, T., 353
termination rules for unconstrained
minimization, 441–446
Thoai, Nguyen V., 76
Thomas, S.W., 400
Thuente, David, 400
time-line network, 20, 21f
Timmer, G.T., 76
Tits, André L., 598
Todd, G. Peter, 41
Todd, Michael J., 313, 316, 354, 657,
658
Toint, Philippe L., 400, 449, 478, 479,
599, 657
Tolle, Jon W., 547, 598
Tomlin, John A., 256
Torczon, Virginia, 450
totally unimodular, 287
training data, 22
transportation problem, 275e, 275, 276f,
280
transshipment node, 272
Trapp, George, 449
tree, 283f, 281–286
Trefethen, Lloyd N., 93
triangular matrix, 667
truncated-Newton method, 451, 452,
463e, 460–466, 469, 477–479,
657
for constrained optimization, 553,
554
truncation error, 423
trust-region method, 392f, 393e,
391–401
algorithm, 392–393
convergence theorem, 395–398,
400
dogleg strategy, 400
trust-region subproblem, 391
Tucker, Albert W., 211, 354, 545, 546
Turing machine, 303
Turing, Alan M., 303
two-phase method, 149–156, 159–162,
237–238, 256, 292
unbounded linear program, 134e, 135f,
134–135
unconstrained minimization, 14, 549
unconstrained optimization, 355–479
underflow, 692
unimodular, 287
unrestricted variable, see free variable
URL for this book, xiv742 Index
Van Der Vorst, H.A., 479
Van Loan, Charles, 93, 558, 661, 682
Vance, Pamela H., 40
Vandenberghe, Lieven, 657
Vanderbei, Robert J., 41, 270, 353, 354,
657
Vapnik, Vladimir, 41, 547
Vardi, Yehuda, 41
variable reduction, 87e, 86–88, 91
to compute Lagrange multiplier,
558
variable reduction method
to compute Lagrange multiplier,
558, 663e, 662–664
vector, 661
vector norm, see norm, vector
vertex, 107
degenerate, 112
Vial, J.-Ph., 353, 354
Viète, Francois, 447
von Neumann, John, 171, 211
voxel, 29, 32
Wächter, Andreas, 599, 657
Walster, G. Wilson, 76
Waren, A.D., 598
weak duality, see duality
Web site for this book, xiv
Weierstrass, Karl, 545, 546, 700
Wengert, R.E., 449
Whiteside, D. T., 446–448
Wiegmann, N., 305
Williams, H.P., 267
Willoughby, Ralph A., 478
Wilson, R.B., 598
Wisconsin Diagnosis Breast Cancer
database, 25
Wolberg, William H., 25
Wolfe condition, 378, 383f, 384e,
383–385, 387, 388, 400
weak, 388, 389
Wolfe dual, 532
Wolfe, Philip, 171, 270, 400
Wolin, Ju.M., 449
Wolkowicz, Henry, 657
Wolsey, Laurence A., 40, 270, 286
working set, 564e, 563–564
worst-case cost, 301–302, see also
complexity
Wright, Margaret H., 93, 400, 443, 449,
598, 618, 656, 657
Wright, Stephen J., 353
Xu, X., 354
Yabe, Hiroshi, 657
Yamashita, Hiroshi, 657
Ye, Yinyu, 353, 354
Yoshise, A., 354
Ypma, Tjalling J., 447
Yuan, Ya-Xiang, 420, 449
Yudin, D.B., 317
Zadeh, N., 300
Zangwill, Willard I., 657
zero-sum game, 523, 524e, see also
game theory
Zhang, Yin, 354
Zhu, Ciyou, 479
zigzagging, 570, 570f
كلمة سر فك الضغط : books-world.net
The Unzip Password : books-world.net
تعليقات