线性和非线性规划 第3版 英文PDF电子书下载

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