Chapter 1．Introduction 1
1.1．Optimization 1
1.2．Types of Problems 2
1.3．Size of Problems 5
1.4．Iterative Algorithms and Convergence 6
PART Ⅰ Linear Programming 11
Chapter 2．Basic Properties of Linear Programs 11
2.1．Introduction 11
2.2．Examples of Linear Programming Problems 14
2.3．Basic Solutions 19
2.4．The Fundamental Theorem of Linear Programming 20
2.5．Relations to Convexity 22
2.6．Exercises 28
Chapter 3．The Simplex Method 33
3.1．Pivots 33
3.2．Adjacent Extreme Points 38
3.3．Determining a Minimum Feasible Solution 42
3.4．Computational Procedure—Simplex Method 46
3.5．Artificial Variables 50
3.6．Matrix Form of the Simplex Method 54
3.7．The Revised Simplex Method 56
3.8．The Simplex Method and LU Decomposition 59
3.9．Decomposition 62
3.10．Summary 70
3.11．Exercises 70
Chapter 4．Duality 79
4.1．Dual Linear Programs 79
4.2．The Duality Theorem 82
4.3．Relations to the Simplex Procedure 84
4.4．Sensitivity and Complementary Slackness 88
4.5．The Dual Simplex Method 90
4.6．The Primal-Dual Algorithm 93
4.7．Reduction of Linear Inequalities 98
4.8．Exercises 103
Chapter 5．Interior-Point Methods 111
5.1．Elements of Complexity Theory 112
5.2．The Simplex Method is not Polynomial-Time 114
5.3．The Ellipsoid Method 115
5.4．The Analytic Center 118
5.5．The Central Path 121
5.6．Solution Strategies 126
5.7．Termination and Initialization 134
5.8．Summary 139
5.9．Exercises 140
Chapter 6．Transportation and Network Flow Problems 145
6.1．The Transportation Problem 145
6.2．Finding a Basic Feasible Solution 148
6.3．Basis Triangularity 150
6.4．Simplex Method for Transportation Problems 153
6.5．The Assignment Problem 159
6.6．Basic Network Concepts 160
6.7．Minimum Cost Flow 162
6.8．Maximal Flow 166
6.9．Summary 174
6.10．Exercises 175
PART Ⅱ Unconstrained Problems 183
Chapter 7．Basic Properties of Solutions and Algorithms 183
7.1．First-Order Necessary Conditions 184
7.2．Examples of Unconstrained Problems 186
7.3．Second-Order Conditions 190
7.4．Convex and Concave Functions 192
7.5．Minimization and Maximization of Convex Functions 197
7.6．Zero-Order Conditions 198
7.7．Global Convergence of Descent Algorithms 201
7.8．Speed of Convergence 208
7.9．Summary 212
7.10．Exercises 213
Chapter 8．Basic Descent Methods 215
8.1．Fibonacci and Golden Section Search 216
8.2．Line Search by Curve Fitting 219
8.3．Global Convergence of Curve Fitting 226
8.4．Closedness of Line Search Algorithms 228
8.5．Inaccurate Line Search 230
8.6．The Method of Steepest Descent 233
8.7．Applications of the Theory 242
8.8．Newton's Method 246
8.9．Coordinate Descent Methods 253
8.10．Spacer Steps 255
8.11．Summary 256
8.12．Exercises 257
Chapter 9．Conjugate Direction Methods 263
9.1．Conjugate Directions 263
9.2．Descent Properties of the Conjugate Direction Method 266
9.3．The Conjugate Gradient Method 268
9.4．The C-G Method as an Optimal Process 271
9.5．The Partial Conjugate Gradient Method 273
9.6．Extension to Nonquadratic Problems 277
9.7．Parallel Tangents 279
9.8．Exercises 282
Chapter 10．Quasi-Newton Methods 285
10.1．Modified Newton Method 285
10.2．Construction of the Inverse 288
10.3．Davidon-Fletcher-Powell Method 290
10.4．The Broyden Family 293
10.5．Convergence Properties 296
10.6．Scaling 299
10.7．Memoryless Quasi-Newton Methods 304
10.8．Combination of Steepest Descent and Newton's Method 306
10.9．Summary 312
10.10．Exercises 313
PART Ⅲ Constrained Minimization 321
Chapter 11．Constrained Minimization Conditions 321
11.1．Constraints 321
11.2．Tangent Plane 323
11.3．First-Order Necessary Conditions(Equality Constraints) 326
11.4．Examples 327
11.5．Second-Order Conditions 333
11.6．Eigenvalues in Tangent Subspace 335
11.7．Sensitivity 339
11.8．Inequality Constraints 341
11.9．Zero-Order Conditions and Lagrange Multipliers 346
11.10．Summary 353
11.11．Exercises 354
Chapter 12．Primal Methods 359
12.1．Advantage of Primal Methods 359
12.2．Feasible Direction Methods 360
12.3．Active Set Methods 363
12.4．The Gradient Projection Method 367
12.5．Convergence Rate of the Gradient Projection Method 374
12.6．The Reduced Gradient Method 382
12.7．Convergence Rate of the Reduced Gradient Method 387
12.8．Variations 394
12.9．Summary 396
12.10．Exercises 396
Chapter 13．Penalty and Barrier Methods 401
13.1．Penalty Methods 402
13.2．Barrier Methods 405
13.3．Properties of Penalty and Barrier Functions 407
13.4．Newton's Method and Penalty Functions 416
13.5．Conjugate Gradients and Penalty Methods 418
13.6．Normalization of Penalty Functions 420
13.7．Penalty Functions and Gradient Projection 421
13.8．Exact Penalty Functions 425
13.9．Summary 429
13.10．Exercises 430
Chapter 14．Dual and Cutting Plane Methods 435
14.1．Global Duality 435
14.2．Local Duality 441
14.3．Dual Canonical Convergence Rate 446
14.4．Separable Problems 447
14.5．Augmented Lagrangians 451
14.6．The Dual Viewpoint 456
14.7．Cutting Plane Methods 460
14.8．Kelley's Convex Cutting Plane Algorithm 463
14.9．Modifications 465
14.10．Exercises 466
Chapter 15．Primal-Dual Methods 469
15.1．The Standard Problem 469
15.2．Strategies 471
15.3．A Simple Merit Function 472
15.4．Basic Primal-Dual Methods 474
15.5．Modified Newton Methods 479
15.6．Descent Properties 481
15.7．Rate of Convergence 485
15.8．Interior Point Methods 487
15.9．Semidefinite Programming 491
15.10．Summary 498
15.11．Exercises 499
Appendix A．Mathemtical Review 507
A.1．Sets 507
A.2．Matrix Notation 508
A.3．Spaces 509
A.4．Eigenvalues and Quadratic Forms 510
A.5．Topological Concepts 511
A.6．Functions 512
Appendix B．Convex Sets 515
B.1．Basic Definitions 515
B.2．Hyperplanes and Polytopes 517
B.3．Separating and Supporting Hyperplanes 519
B.4．Extreme Points 521
Appendix C．Gaussian Elimination 523
Bibliography 527
Index 541