线性代数及其在规划中的应用PDF电子书下载

Part Ⅰ 3

Chapter 1 Background and Fundamentals of Mathematics 3

1.1 Basic Concepts 3

1.2 Relations 4

1.3 Functions 5

1.4 The Integers 9

1.4.1 Long Division 9

1.4.2 Relatively Prime 10

1.4.3 Prime 10

1.4.4 The Unique Factorization Theorem 11

Chapter 2 Groups 13

2.1 Groups 13

2.2 Subgroups 15

2.3 Normal Subgroups 17

2.4 Homomorphisms 19

2.5 Permutations 20

2.6 Product of Groups 22

Chapter 3 Rings 24

3.1 Commutative Rings 24

3.2 Units 25

3.3 The Integers Mod N 26

3.4 Ideals and Quotient Rings 27

3.5 Homomorphism 28

3.6 Polynomial Rings 29

3.6.1 The Division Algorithm 30

3.6.2 Associate 31

3.7 Product of Rings 32

3.8 Characteristic 33

3.9 Boolean Rings 34

Chapter 4 Matrices and Matrix Rings 35

4.1 Elementary Operations and Elementary Matrices 35

4.2 Systems of Equations 36

4.3 Determinants 37

4.4 Similarity 40

Part Ⅱ 45

Chapter 5 Vector Spaces 45

5.1 The Axioms for a Vector Space 45

5.2 Linear Independence,Dimension,and Basis 48

5.3 Intersection,Sum and Direct Sum of Subspaces 53

5.4 Factor Space 56

5.5 Inner Product Spaces 58

5.6 Orthonormal Bases and Orthogonal Complements 62

5.7 Reciprocal Basis and Change of Basis 65

Chapter 6 Linear Transformations 71

6.1 Definition of Linear Transformation 71

6.2 Sums and Products of Liner Transformations 75

6.3 Special Types of Linear Transformations 77

6.4 The Adjoint of a Linear Transformation 82

6.5 Component Formulas 89

Chapter 7 Determinants And Matrices 92

7.1 The Generalized Kronecker Deltas and the Summation Convention 92

7.2 Determinants 96

7.3 The Matrix of a Linear Transformation 99

7.4 Solution of Systems of Linear Equation 102

7.5 Special Matrices 103

Chapter 8 Spectral Decompositions 108

8.1 Direct Sum of Endomorphisms 108

8.2 Eigenvectors and Eigenvalues 109

8.3 The Characteristic Polynomial 110

8.4 Spectral Decomposition for Hermitian Endomorphisms 113

8.5 Illustrative Examples 124

8.6 The Minimal Polynomial 127

8.7 Spectral Decomposition for Arbitrary Endomorphisms 130

Chapter 9 Tensor Algebra 144

9.1 Linear Functions,the Dual Space 144

9.2 The Second Dual Space,Canonical Isomorphisms 149

Part Ⅲ 157

Chapter 10 Linear Programming 157

10.1 Basic Properties of Linear Programs 157

10.2 Many Computational Procedures to Simplex Method 162

10.3 Duality 170

10.3.1 Dual Linear Programs 170

10.3.2 The Duality Theorem 172

10.3.3 Relations to the Simplex Procedure 173

10.4 Interior-point Methods 176

10.4.1 Elements of Complexity Theory 176

10.4.2 The Analytic Center 176

10.4.3 The Central Path 177

10.4.4 Solution Strategies 180

Chapter 11 Unconstrained Problems 187

11.1 Transportation and Network Flow Problems 187

11.1.1 The Transportation Problem 187

11.1.2 The Northwest Corner Rule 190

11.1.3 Basic Network Concepts 190

11.1.4 Maximal Flow 191

11.2 Basic Properties of Solutions and Algorithms 197

11.2.1 First-order Necessary Conditions 197

11.2.2 Second-order Conditions 198

11.2.3 Minimization and Maximization of Convex Functions 198

11.2.4 Zeroth-order Conditions 198

11.2.5 Global Convergence of Descent Algorithms 199

11.2.6 Speed of Convergence 202

11.3 Basic Descent Methods 204

11.3.1 Fibonacci and Golden Section Search 204

11.3.2 Closedness of Line Search Mgorithms 205

11.3.3 Line Search 207

11.3.4 The Steepest Descent Method 209

11.3.5 Coordinate Descent Methods 211

11.4 Conjugate Direction Methods 212

11.4.1 Conjugate Directions 212

11.4.2 Descent Properties of the Conjugate Direction Method 214

11.4.3 The Conjugate Gradient Method 214

11.4.4 The C-G Method as an Optimal Process 215

Chapter 12 Constrained Minimization 218

12.1 Quasi-Newton Methods 218

12.1.1 Modified Newton Method 218

12.1.2 Scaling 219

12.1.3 Memoryless Quasi-Newton Methods 222

12.2 Constrained Minimization Conditions 223

12.2.1 Constraints 223

12.2.2 Tangent Plane 224

12.2.3 First-order Necessary Conditions(Equality Constraints) 224

12.2.4 Second-order Conditions 225

12.2.5 Eigenvalues in Tangent Subspace 225

12.2.6 Inequality Constraints 227

12.2.7 Zeroth-order Conditions and Lagrange Multipliers 228

12.3 Primal Methods 231

12.3.1 Feasible Direction Methods 231

12.3.2 Active Set Methods 231

12.3.3 The Gradient Projection Method 232

12.3.4 Convergence Rate of the Gradient Projection Method 233

12.3.5 The Reduced Gradient Method 235

12.4 Penalty and Barrier Methods 237

12.4.1 Penalty Methods 237

12.4.2 Barrier Methods 238

12.4.3 Properties of Penalty and Barrier Functions 239

12.5 Dual and Cutting Plane Methods 243

12.5.1 Global Duality 243

12.5.2 Local Duality 245

12.5.3 Dual Canonical Convergence Rate 247

12.5.4 Separable Problems 248

12.5.5 Decomposition 248

12.5.6 The Dual Viewpoint 249

12.5.7 Cutting Plane Methods 251

12.5.8 Kelley's Convex Cutting Plane Algorithm 253

12.5.9 Modifications 253

12.6 Primal-dual Methods 254

12.6.1 The Standard Problem 254

12.6.2 Strategies 256

12.6.3 A Simple Merit Function 257

12 6 4 Basic Primal-dual Methods 257

12.6.5 Modified Newton Methods 260

12.6.6 Descent Properties 262

12.6.7 Interior Point Methods 263

Bibliography 267