Optimal Quadratic Programming Algorithms: With Applications to Variational Inequalities

front-matter......Page 0
Preface......Page 4
Contents......Page 10
Vectors......Page 15
Matrices and Matrix Operations......Page 17
Matrices and Mappings......Page 18
Inverse and Generalized Inverse Matrices......Page 20
Direct Methods for Solving Linear Equations......Page 21
Norms......Page 24
Scalar Products......Page 26
Eigenvalues and Eigenvectors......Page 29
Matrix Decompositions......Page 31
Penalized Matrices......Page 34
Optimization Problems and Solutions......Page 39
Quadratic Cost Functions......Page 40
Unconstrained Minimization of Quadratic Functions......Page 41
Convexity......Page 43
Convex Quadratic Functions......Page 44
Local and Global Minimizers of Convex Function......Page 46
Existence of Minimizers......Page 47
Projections to Convex Sets......Page 48
Equality Constrained Problems......Page 50
Optimality Conditions......Page 51
Existence and Uniqueness......Page 53
KKT Systems......Page 54
Min-max, Dual, and Saddle Point Problems......Page 56
Sensitivity......Page 58
Error Analysis......Page 59
Polyhedral Sets......Page 61
Farkas's Lemma......Page 62
Necessary Optimality Conditions for Local Solutions......Page 63
Existence and Uniqueness......Page 64
Optimality Conditions for Convex Problems......Page 66
Min-max, Dual, and Saddle Point Problems......Page 67
Equality and Inequality Constrained Problems......Page 69
Optimality Conditions......Page 70
Partially Bound and Equality Constrained Problems......Page 71
Duality for Dependent Constraints......Page 73
Duality for Semicoercive Problems......Page 76
Solvability and Localization of Solutions......Page 81
Duality in Linear Programming......Page 82
Conjugate Gradients for Unconstrained Minimization......Page 83
Conjugate Directions and Minimization......Page 84
Generating Conjugate Directions and Krylov Spaces......Page 87
Conjugate Gradient Method......Page 88
Restarted CG and the Gradient Method......Page 91
Min-max Estimate......Page 92
Estimate in the Condition Number......Page 94
Convergence Rate of the Gradient Method......Page 96
Preconditioned Conjugate Gradients......Page 97
Conjugate Projectors......Page 100
Minimization in Subspace......Page 101
Conjugate Gradients in Conjugate Complement......Page 102
Preconditioning Effect......Page 104
Conjugate Gradients for More General Problems......Page 106
Convergence in Presence of Rounding Errors......Page 107
Basic CG and Preconditioning......Page 108
Numerical Demonstration of Optimality......Page 109
Comments and Conclusions......Page 110
Equality Constrained Minimization......Page 112
Review of Alternative Methods......Page 114
Penalty Method......Page 116
Minimization of Augmented Lagrangian......Page 117
An Optimal Feasibility Error Estimate for Homogeneous Constraints......Page 118
Approximation Error and Convergence......Page 120
Improved Feasibility Error Estimate......Page 121
Improved Approximation Error Estimate......Page 122
Preconditioning Preserving Gap in the Spectrum......Page 124
Exact Augmented Lagrangian Method......Page 125
Algorithm......Page 126
Convergence of Lagrange Multipliers......Page 128
Effect of the Steplength......Page 129
Convergence of Primal Variables......Page 133
Implementation......Page 134
Algorithm......Page 135
Auxiliary Estimates......Page 136
Convergence Analysis......Page 137
Adaptive Augmented Lagrangian Method......Page 139
Algorithm......Page 140
Convergence of Lagrange Multipliers for Large......Page 141
R-Linear Convergence for Any Initialization of......Page 143
Semimonotonic Augmented Lagrangians (SMALE)......Page 144
SMALE Algorithm......Page 145
Relations for Augmented Lagrangians......Page 146
Convergence and Monotonicity......Page 148
Linear Convergence for Large 0......Page 151
Optimality of the Outer Loop......Page 152
Optimality of SMALE with Conjugate Gradients......Page 154
Solution of More General Problems......Page 156
Initialization of Constants......Page 157
Uzawa, Exact Augmented Lagrangians, and SMALE......Page 159
Numerical Demonstration of Optimality......Page 160
Comments and References......Page 161
Bound Constrained Minimization......Page 163
Review of Alternative Methods......Page 165
KKT Conditions and Related Inequalities......Page 166
Auxiliary Problems......Page 168
Algorithm......Page 169
Finite Termination......Page 172
Basic Algorithm......Page 173
Finite Termination......Page 174
Looking Ahead and Estimate......Page 175
Looking Ahead Polyak's Algorithm......Page 178
Easy Re-release Polyak's Algorithm......Page 179
Properties of Modified Polyak's Algorithms......Page 180
Gradient Projection Method......Page 181
Conjugate Gradient Versus Gradient Projections......Page 182
Contraction in the Euclidean Norm......Page 183
The Fixed Steplength Gradient Projection Method......Page 185
Quadratic Functions with Identity Hessian......Page 186
Dominating Function and Decrease of the Cost Function......Page 189
MPGP Schema......Page 192
Rate of Convergence......Page 194
MPRGP Schema......Page 197
Rate of Convergence......Page 198
Rate of Convergence of Projected Gradient......Page 201
Optimality......Page 205
Identification Lemma and Finite Termination......Page 206
Finite Termination for Dual Degenerate Solution......Page 209
Expansion Step with Feasible Half-Step......Page 212
MPRGP Algorithm......Page 213
Unfeasible MPRGP......Page 214
Choice of Parameters......Page 216
Dynamic Release Coefficient......Page 217
Preconditioning in Face......Page 218
Preconditioning by Conjugate Projector......Page 220
Polyak, MPRGP, and Preconditioned MPRGP......Page 224
Numerical Demonstration of Optimality......Page 225
Comments and References......Page 226
Bound and Equality Constrained Minimization......Page 229
Review of the Methods for Bound and Equality Constrained Problems......Page 230
SMALBE Algorithm......Page 231
Inequalities Involving the Augmented Lagrangian......Page 233
Monotonicity and Feasibility......Page 235
Boundedness......Page 237
Convergence......Page 241
Optimality of the Outer Loop......Page 243
Optimality of the Inner Loop......Page 245
Solution of More General Problems......Page 247
Implementation......Page 248
SMALBE--M......Page 249
Balanced Reduction of Feasibility and Gradient Errors......Page 250
Numerical Demonstration of Optimality......Page 251
Comments and References......Page 252
Solution of a Coercive Variational Inequality by FETI--DP Method......Page 254
Model Coercive Variational Inequality......Page 255
FETI--DP Domain Decomposition and Discretization......Page 256
Optimality......Page 259
Numerical Experiments......Page 260
Comments and References......Page 261
Solution of a Semicoercive Variational Inequality by TFETI Method......Page 263
Model Semicoercive Variational Inequality......Page 264
TFETI Domain Decomposition and Discretization......Page 265
Natural Coarse Grid......Page 268
Optimality......Page 269
Numerical Experiments......Page 272
Comments and References......Page 274
References......Page 275
Index......Page 285
rebOOk
......Page 1