Optimal Quadratic Programming Algorithms (eBook)

Preface 7
Part I Background 18
Linear Algebra 19
Vectors 19
Matrices and Matrix Operations 21
Matrices and Mappings 22
Inverse and Generalized Inverse Matrices 24
Direct Methods for Solving Linear Equations 25
Norms 28
Scalar Products 30
Eigenvalues and Eigenvectors 33
Matrix Decompositions 35
Penalized Matrices 38
Optimization 43
Optimization Problems and Solutions 43
Unconstrained Quadratic Programming 44
Quadratic Cost Functions 44
Unconstrained Minimization of Quadratic Functions 45
Convexity 47
Convex Quadratic Functions 48
Local and Global Minimizers of Convex Function 50
Existence of Minimizers 51
Projections to Convex Sets 52
Equality Constrained Problems 54
Optimality Conditions 55
Existence and Uniqueness 57
KKT Systems 58
Min-max, Dual, and Saddle Point Problems 60
Sensitivity 62
Error Analysis 63
Inequality Constrained Problems 65
Polyhedral Sets 65
Farkas's Lemma 66
Necessary Optimality Conditions for Local Solutions 67
Existence and Uniqueness 68
Optimality Conditions for Convex Problems 70
Optimality Conditions for Bound Constrained Problems 71
Min-max, Dual, and Saddle Point Problems 71
Equality and Inequality Constrained Problems 73
Optimality Conditions 74
Existence and Uniqueness 75
Partially Bound and Equality Constrained Problems 75
Duality for Dependent Constraints 77
Duality for Semicoercive Problems 80
Linear Programming 85
Solvability and Localization of Solutions 85
Duality in Linear Programming 86
Part II Algorithms 87
Conjugate Gradients for Unconstrained Minimization 88
Conjugate Directions and Minimization 89
Generating Conjugate Directions and Krylov Spaces 92
Conjugate Gradient Method 93
Restarted CG and the Gradient Method 96
Rate of Convergence and Optimality 97
Min-max Estimate 97
Estimate in the Condition Number 99
Convergence Rate of the Gradient Method 101
Optimality 102
Preconditioned Conjugate Gradients 102
Preconditioning by Conjugate Projector 105
Conjugate Projectors 105
Minimization in Subspace 106
Conjugate Gradients in Conjugate Complement 107
Preconditioning Effect 109
Conjugate Gradients for More General Problems 111
Convergence in Presence of Rounding Errors 112
Numerical Experiments 113
Basic CG and Preconditioning 113
Numerical Demonstration of Optimality 114
Comments and Conclusions 115
Equality Constrained Minimization 117
Review of Alternative Methods 119
Penalty Method 121
Minimization of Augmented Lagrangian 122
An Optimal Feasibility Error Estimate for Homogeneous Constraints 123
Approximation Error and Convergence 125
Improved Feasibility Error Estimate 126
Improved Approximation Error Estimate 127
Preconditioning Preserving Gap in the Spectrum 129
Exact Augmented Lagrangian Method 130
Algorithm 131
Convergence of Lagrange Multipliers 133
Effect of the Steplength 134
Convergence of the Feasibility Error 138
Convergence of Primal Variables 138
Implementation 139
Asymptotically Exact Augmented Lagrangian Method 140
Algorithm 140
Auxiliary Estimates 141
Convergence Analysis 142
Adaptive Augmented Lagrangian Method 144
Algorithm 145
Convergence of Lagrange Multipliers for Large 146
R-Linear Convergence for Any Initialization of 148
Semimonotonic Augmented Lagrangians (SMALE) 149
SMALE Algorithm 150
Relations for Augmented Lagrangians 151
Convergence and Monotonicity 153
Linear Convergence for Large 0 156
Optimality of the Outer Loop 157
Optimality of SMALE with Conjugate Gradients 159
Solution of More General Problems 161
Implementation of Inexact Augmented Lagrangians 162
Stopping, Modification of Constraints, and Preconditioning 162
Initialization of Constants 162
Numerical Experiments 164
Uzawa, Exact Augmented Lagrangians, and SMALE 164
Numerical Demonstration of Optimality 165
Comments and References 166
Bound Constrained Minimization 168
Review of Alternative Methods 170
KKT Conditions and Related Inequalities 171
The Working Set Method with Exact Solutions 173
Auxiliary Problems 173
Algorithm 174
Finite Termination 177
Polyak's Algorithm 178
Basic Algorithm 178
Finite Termination 179
Characteristics of Polyak's Algorithm 180
Inexact Polyak's Algorithm 180
Looking Ahead and Estimate 180
Looking Ahead Polyak's Algorithm 183
Easy Re-release Polyak's Algorithm 184
Properties of Modified Polyak's Algorithms 185
Gradient Projection Method 186
Conjugate Gradient Versus Gradient Projections 187
Contraction in the Euclidean Norm 188
The Fixed Steplength Gradient Projection Method 190
Quadratic Functions with Identity Hessian 191
Dominating Function and Decrease of the Cost Function 194
Modified Proportioning with Gradient Projections 197
MPGP Schema 197
Rate of Convergence 199
Modified Proportioning with Reduced Gradient Projections 202
MPRGP Schema 202
Rate of Convergence 203
Rate of Convergence of Projected Gradient 206
Optimality 210
Identification Lemma and Finite Termination 211
Finite Termination for Dual Degenerate Solution 214
Implementation of MPRGP with Optional Modifications 217
Expansion Step with Feasible Half-Step 217
MPRGP Algorithm 218
Unfeasible MPRGP 219
Choice of Parameters 221
Dynamic Release Coefficient 222
Preconditioning 223
Preconditioning in Face 223
Preconditioning by Conjugate Projector 225
Numerical Experiments 229
Polyak, MPRGP, and Preconditioned MPRGP 229
Numerical Demonstration of Optimality 230
Comments and References 231
Bound and Equality Constrained Minimization 234
Review of the Methods for Bound and Equality Constrained Problems 235
SMALBE Algorithm for Bound and Equality Constraints 236
KKT Conditions and Projected Gradient 236
SMALBE Algorithm 236
Inequalities Involving the Augmented Lagrangian 238
Monotonicity and Feasibility 240
Boundedness 242
Convergence 246
Optimality of the Outer Loop 248
Optimality of the Inner Loop 250
Solution of More General Problems 252
Implementation 253
SMALBE--M 254
Numerical Experiments 255
Balanced Reduction of Feasibility and Gradient Errors 255
Numerical Demonstration of Optimality 256
Comments and References 257
Part III Applications to Variational Inequalities 259
Solution of a Coercive Variational Inequality by FETI--DP Method 260
Model Coercive Variational Inequality 261
FETI--DP Domain Decomposition and Discretization 262
Optimality 265
Numerical Experiments 266
Comments and References 267
Solution of a Semicoercive Variational Inequality by TFETI Method 269
Model Semicoercive Variational Inequality 270
TFETI Domain Decomposition and Discretization 271
Natural Coarse Grid 274
Optimality 275
Numerical Experiments 277
Comments and References 279
References 280
Index 290