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