Optimal Quadratic Programming Algorithms: With Applications to Variational Inequalities (Springer Optimization and Its Applications Book 23)

Kurzbeschreibung Quadratic programming (QP) is one advanced mathematical technique that allows for the optimization of a quadratic function in several variables in the presence of linear constraints. This book presents recently developed algorithms for solving large QP problems and focuses on algorithms which are, in a sense optimal, i.e., they can solve important classes of problems at a cost proportional to the number of unknowns. For each algorithm presented, the book details its classical predecessor, describes its drawbacks, introduces modifications that improve its performance, and demonstrates these improvements through numerical experiments. This self-contained monograph can serve as an introductory text on quadratic programming for graduate students and researchers. Additionally, since the solution of many nonlinear problems can be reduced to the solution of a sequence of QP problems, it can also be used as a convenient introduction to nonlinear programming. Synopsis Solving optimization problems in complex systems often requires the implementation of advanced mathematical techniques. Quadratic programming (QP) is one technique that allows for the optimization of a quadratic function in several variables in the presence of linear constraints. QP problems arise in fields as diverse as electrical engineering, agricultural planning, and optics. Given its broad applicability, a comprehensive understanding of quadratic programming is a valuable resource in nearly every scientific field."Optimal Quadratic Programming Algorithms" presents recently developed algorithms for solving large QP problems. The presentation focuses on algorithms which are, in a sense optimal, i.e., they can solve important classes of problems at a cost proportional to the number of unknowns. For each algorithm presented, the book details its classical predecessor, describes its drawbacks, introduces modifications that improve its performance, and demonstrates these improvements through numerical experiments. This self-contained monograph can serve as an introductory text on quadratic programming for graduate students and researchers. Additionally, since the solution of many nonlinear problems can be reduced to the solution of a sequence of QP problems, it can also be used as a convenient introduction to nonlinear programming. The reader is required to have a basic knowledge of calculus in several variables and linear algebra. 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 Solving optimization problems in complex systems often requires the implementation of advanced mathematical techniques. Quadratic programming (QP) is one technique that allows for the optimization of a quadratic function in several variables in the presence of linear constraints. QP problems arise in fields as diverse as electrical engineering, agricultural planning, and optics. Given its broad applicability, a comprehensive understanding of quadratic programming is a valuable resource in nearly every scientific field. __Optimal Quadratic Programming Algorithms__ presents recently developed algorithms for solving large QP problems. The presentation focuses on algorithms which are, in a sense optimal, i.e., they can solve important classes of problems at a cost proportional to the number of unknowns. For each algorithm presented, the book details its classical predecessor, describes its drawbacks, introduces modifications that improve its performance, and demonstrates these improvements through numerical experiments. This self-contained monograph can serve as an introductory text on quadratic programming for graduate students and researchers. Additionally, since the solution of many nonlinear problems can be reduced to the solution of a sequence of QP problems, it can also be used as a convenient introduction to nonlinear programming. The reader is required to have a basic knowledge of calculus in several variables and linear algebra.

advanced Computational Methods Are Often Employed For The Solution Of Modelling And Decision-making Problems. This Book Addresses Issues Associated With The Interface Of Computing, Optimisation, Econometrics And Financial Modelling. Emphasis Is Given To Computational Optimisation Methods And Techniques. The First Part Of The Book Addresses Optimisation Problems And Decision Modelling, With Special Attention To Applications Of Supply Chain And Worst-case Modelling As Well As Advances In The Methodological Aspects Of Optimisation Techniques. The Second Part Of The Book Is Devoted To Optimisation Heuristics, Filtering, Signal Extraction And Various Time Series Models. The Chapters In This Part Cover The Application Of Threshold Accepting In Econometrics, The Structure Of Threshold Autoregressive Moving Average Models, Wavelet Analysis And Signal Extraction Techniques In Time Series. The Third And Final Part Of The Book Is About The Use Of Optimisation In Portfolio Selection And Real Option Modelling.

"This book addresses issues associated with the interface of computing, optimisation, econometrics and financial modelling. Emphasis is given to computational optimisation methods and techniques. The first part of the book addresses optimisation problems and decision modelling, with special attention to applications of supply chain and worst-case modelling as well as advances in the methodological aspects of optimisation techniques. The second part of the book is devoted to optimisation heuristics, filtering, signal extraction and various time series models. The chapter in this part cover the application of threshold accepting in econometrics, the structure of the threshold autoregressive moving average models, wavelet analysis and signal extraction techniques in time series. The third and final part of the book is about the use of optimisation in portfolio selection and real option modelling."--Back cover