Optimal Quadratic Programming Algorithms

With Applications to Variational Inequalities

By: Zdenek DostÃ¡l

Write A Review

Hardcover | 2 April 2009

At a Glance

Hardcover
304 Pages

Dimensions(cm)
23.39 x 15.6 x 1.75

Hardcover

$210.72

or 4 interest-free payments of $52.68 with

Aims to ship in 7 to 10 business days

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.

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

You Can Find This Book In

Non-Fiction Mathematics Optimisation Linear Programming Business & Management Operational Research Applied Mathematics Calculus & Mathematical Analysis Calculus of Variations Numerical Analysis Computing & I.T.Graphical & Digital Media Applications

Computer-Aided Design CAD Engineering & Technology Technology in General Maths for Engineers

Other Editions and Formats

Paperback

Published: 28th October 2010

View Product

Preface	p. vii
Background
Linear Algebra	p. 3
Vectors	p. 3
Matrices and Matrix Operations	p. 5
Matrices and Mappings	p. 6
Inverse and Generalized Inverse Matrices	p. 8
Direct Methods for Solving Linear Equations	p. 9
Norms	p. 12
Scalar Products	p. 14
Eigenvalues and Eigenvectors	p. 17
Matrix Decompositions	p. 19
Penalized Matrices	p. 22
Optimization	p. 27
Optimization Problems and Solutions	p. 27
Unconstrained Quadratic Programming	p. 28
Quadratic Cost Functions	p. 28
Unconstrained Minimization of Quadratic Functions	p. 29
Convexity	p. 31
Convex Quadratic Functions	p. 32
Local and Global Minimizers of Convex Function	p. 34
Existence of Minimizers	p. 35
Projections to Convex Sets	p. 36
Equality Constrained Problems	p. 38
Optimality Conditions	p. 39
Existence and Uniqueness	p. 41
KKT Systems	p. 42
Min-max, Dual, and Saddle Point Problems	p. 44
Sensitivity	p. 46
Error Analysis	p. 47
Inequality Constrained Problems	p. 49
Polyhedral Sets	p. 49
Farkas's Lemma	p. 50
Necessary Optimality Conditions for Local Solutions	p. 51
Existence and Uniqueness	p. 52
Optimality Conditions for Convex Problems	p. 54
Optimality Conditions for Bound Constrained Problems	p. 55
Min-max, Dual, and Saddle Point Problems	p. 55
Equality and Inequality Constrained Problems	p. 57
Optimality Conditions	p. 58
Existence and Uniqueness	p. 59
Partially Bound and Equality Constrained Problems	p. 59
Duality for Dependent Constraints	p. 61
Duality for Semicoercive Problems	p. 64
Linear Programming	p. 69
Solvability and Localization of Solutions	p. 69
Duality in Linear Programming	p. 70
Algorithms
Conjugate Gradients for Unconstrained Minimization	p. 73
Conjugate Directions and Minimization	p. 74
Generating Conjugate Directions and Krylov Spaces	p. 77
Conjugate Gradient Method	p. 78
Restarted CG and the Gradient Method	p. 81
Rate of Convergence and Optimality	p. 82
Min-max Estimate	p. 82
Estimate in the Condition Number	p. 84
Convergence Rate of the Gradient Method	p. 86
Optimality	p. 87
Preconditioned Conjugate Gradients	p. 87
Preconditioning by Conjugate Projector	p. 90
Conjugate Projectors	p. 90
Minimization in Subspace	p. 91
Conjugate Gradients in Conjugate Complement	p. 92
Preconditioning Effect	p. 94
Conjugate Gradients for More General Problems	p. 96
Convergence in Presence of Rounding Errors	p. 97
Numerical Experiments	p. 98
Basic CG and Preconditioning	p. 98
Numerical Demonstration of Optimality	p. 99
Comments and Conclusions	p. 100
Equality Constrained Minimization	p. 103
Review of Alternative Methods	p. 105
Penalty Method	p. 107
Minimization of Augmented Lagrangian	p. 108
An Optimal Feasibility Error Estimate for Homogeneous Constraints	p. 109
Approximation Error and Convergence	p. 111
Improved Feasibility Error Estimate	p. 112
Improved Approximation Error Estimate	p. 113
Preconditioning Preserving Gap in the Spectrum	p. 115
Exact Augmented Lagrangian Method	p. 116
Algorithm	p. 117
Convergence of Lagrange Multipliers	p. 119
Effect of the Steplength	p. 120
Convergence of the Feasibility Error	p. 124
Convergence of Primal Variables	p. 124
Implementation	p. 125
Asymptotically Exact Augmented Lagrangian Method	p. 126
Algorithm	p. 126
Auxiliary Estimates	p. 127
Convergence Analysis	p. 128
Adaptive Augmented Lagrangian Method	p. 130
Algorithm	p. 131
Convergence of Lagrange Multipliers for Large <$>\varrho<$>	p. 132
R-Linear Convergence for Any Initialization of <$>\varrho<$>	p. 134
Semimonotonic Augmented Lagrangians (SMALE)	p. 135
SMALE Algorithm	p. 136
Relations for Augmented Lagrangians	p. 137
Convergence and Monotonicity	p. 139
Linear Convergence for Large <$>\varrho_0<$>	p. 142
Optimality of the Outer Loop	p. 143
Optimality of SMALE with Conjugate Gradients	p. 145
Solution of More General Problems	p. 147
Implementation of Inexact Augmented Lagrangians	p. 148
Stopping, Modification of Constraints, and Preconditioning	p. 148
Initialization of Constants	p. 148
Numerical Experiments	p. 150
Uzawa, Exact Augmented Lagrangians, and SMALE	p. 150
Numerical Demonstration of Optimality	p. 151
Comments and References	p. 152
Bound Constrained Minimization	p. 155
Review of Alternative Methods	p. 157
KKT Conditions and Related Inequalities	p. 158
The Working Set Method with Exact Solutions	p. 160
Auxiliary Problems	p. 160
Algorithm	p. 161
Finite Termination	p. 164
Polyak's Algorithm	p. 165
Basic Algorithm	p. 165
Finite Termination	p. 166
Characteristics of Polyak's Algorithm	p. 167
Inexact Polyak's Algorithm	p. 167
Looking Ahead and Estimate	p. 167
Looking Ahead Polyak's Algorithm	p. 170
Easy Re-release Polyak's Algorithm	p. 171
Properties of Modified Polyak's Algorithms	p. 172
Gradient Projection Method	p. 173
Conjugate Gradient Versus Gradient Projections	p. 174
Contraction in the Euclidean Norm	p. 175
The Fixed Steplength Gradient Projection Method	p. 177
Quadratic Functions with Identity Hessian	p. 178
Dominating Function and Decrease of the Cost Function	p. 181
Modified Proportioning with Gradient Projections	p. 184
MPGP Schema	p. 184
Rate of Convergence	p. 186
Modified Proportioning with Reduced Gradient Projections	p. 189
MPRGP Schema	p. 189
Rate of Convergence	p. 190
Rate of Convergence of Projected Gradient	p. 193
Optimality	p. 197
Identification Lemma and Finite Termination	p. 198
Finite Termination for Dual Degenerate Solution	p. 201
Implementation of MPRGP with Optional Modifications	p. 204
Expansion Step with Feasible Half-Step	p. 204
MPRGP Algorithm	p. 205
Unfeasible MPRGP	p. 206
Choice of Parameters	p. 208
Dynamic Release Coefficient	p. 209
Preconditioning	p. 210
Preconditioning in Face	p. 210
Preconditioning by Conjugate Projector	p. 212
Numerical Experiments	p. 216
Polyak, MPRGP, and Preconditioned MPRGP	p. 216
Numerical Demonstration of Optimality	p. 217
Comments and References	p. 218
Bound and Equality Constrained Minimization	p. 221
Review of the Methods for Bound and Equality Constrained Problems	p. 222
SMALBE Algorithm for Bound and Equality Constraints	p. 223
KKT Conditions and Projected Gradient	p. 223
SMALBE Algorithm	p. 223
Inequalities Involving the Augmented Lagrangian	p. 225
Monotonicity and Feasibility	p. 227
Boundedness	p. 229
Convergence	p. 233
Optimality of the Outer Loop	p. 235
Optimality of the Inner Loop	p. 237
Solution of More General Problems	p. 239
Implementation	p. 240
SMALBE-M	p. 241
Numerical Experiments	p. 242
Balanced Reduction of Feasibility and Gradient Errors	p. 242
Numerical Demonstration of Optimality	p. 243
Comments and References	p. 244
Applications to Variational Inequalities
Solution of a Coercive Variational Inequality by FETI-DP Method	p. 249
Model Coercive Variational Inequality	p. 250
FETI-DP Domain Decomposition and Discretization	p. 251
Optimality	p. 254
Numerical Experiments	p. 255
Comments and References	p. 256
Solution of a Semicoercive Variational Inequality by TFETI Method	p. 259
Model Semicoercive Variational Inequality	p. 260
TFETI Domain Decomposition and Discretization	p. 261
Natural Coarse Grid	p. 264
Optimality	p. 265
Numerical Experiments	p. 267
Comments and References	p. 269
References	p. 271
Index	p. 281
Table of Contents provided by Ingram. All Rights Reserved.

Optimal Quadratic Programming Algorithms

With Applications to Variational Inequalities

At a Glance

Hardcover

Shipping

How to return your order

Defective items

You Can Find This Book In

Other Editions and Formats

Paperback

More in Mathematics

Nelson WAmaths Mathematics Applications

11th Edition

Oxford Maths for Australian Schools Year 3 Value Pack

3rd Edition

The Art of Uncertainty

How to Navigate Chance, Ignorance, Risk and Luck

Maths Sequences for the Early Years F-2

Challenging Children to Reason Mathematically

Oxford Maths for Australian Schools Year 1 Value Pack

3rd Edition

Oxford Maths for Australian Schools Year 2 Value Pack

3rd Edition

Oxford Maths for Australian Schools Year 4 Value Pack

3rd Edition

Oxford Maths for Australian Schools Year 6 Value Pack

3rd Edition

Primary Mathematics

4th Edition - Integrating Theory with Practice

How to Win At Chess

The Ultimate Guide for Beginners and Beyond

Nelson WAmaths Mathematics Methods

11th Edition

Calculus, Metric Edition

9th edition

Discovering Statistics Using IBM SPSS Statistics

(Paperback plus Ebook) 5ed

Oxford Maths for Australian Schools Value Pack Year 5

Oxford Maths

The Game Changers

How Playing Games Changed the World and Can Change You Too

Basic Technical Mathematics with Calculus, SI Version

11th edition

Aristotle's Organon in Old and New Logic

1800-1950

Fuzzy Methods for Assessment and Decision Making

Math-ish

Finding Creativity, Diversity, and Meaning in Mathematics

Modelling and Control of Dynamic Spatially Distributed Systems

Pharmaceutical Processes

Homotopy Theory of Enriched Mackey Functors

Closed Multicategories, Permutative Enrichments, and Algebraic Foundations for Spectral Mackey Functors

Genetic and Evolutionary Computing

Proceedings of the Sixteenth International Conference on Genetic and Evolutionary Computing, August 28-30, 2024, Miyazaki, Japan (Volume 2)

ODE/IM Correspondence and Quantum Periods

Nelson WAmaths Mathematics Applications 12

1st Edition

This product is categorised by