Optimal Quadratic Programming and QCQP Algorithms with Applications

2025
Buch

Verfasst von: Zdeněk Dostál
Buchreihe: Springer Optimization and Its Applications
Verlag: Springer Nature Switzerland
Enthalten in: Springer Professional "Wirtschaft+Technik"; Springer Professional "Technik"; Springer Professional "Wirtschaft"

Über dieses Buch

Dieses Buch präsentiert hochmoderne Algorithmen zur Lösung großflächiger quadratischer Programmierung (QP) und / oder QCQP. Während diese Algorithmen auf die Klasse der QP-Probleme angewandt werden, bei denen das Spektrum auf ein positives Intervall beschränkt ist, garantiert die Theorie, die vorgeschriebene Präzisionslösung durch eine einheitlich begrenzte Anzahl einfacher Iterationen wie Matrix-Vektor-Multiplikationen zu finden. Zu den untersuchten Schlüsselkonzepten gehören die Strategie der aktiven Menge, spektrale Gradienten und erweiterte Lagrange-Methoden. Das Buch bietet eine umfassende quantitative Konvergenztheorie, die nicht näher spezifizierte Konstanten vermeidet. Anhand detaillierter numerischer Experimente demonstriert der Autor die überlegene Leistung der Algorithmen gegenüber herkömmlichen Methoden, insbesondere im Umgang mit großen Problemen mit spärlichem Hessisch. Die Leistungsfähigkeit der Algorithmen wird an großen (Milliarden von Variablen) Problemen der Mechanik, der optimalen Steuerung und der Unterstützung von Vektormaschinen gezeigt. Ideal für Forscher und Praktiker in der Optimierung und Computermathematik, ist dieser Band auch ein Einführungstext und eine Referenz für fortgeschrittene Studien in nichtlinearer Programmierung. Egal, ob Sie Wissenschaftler in angewandter Mathematik oder Ingenieur sind, der sich komplexen Optimierungsproblemen stellt: Dieses Buch bietet wertvolle Einsichten und praktische Werkzeuge für Ihre Arbeit.

Mit KI übersetzt

Inhaltsverzeichnis

Frontmatter

Background

Frontmatter

1. Linear Algebra

Abstract

The purpose of this chapter is to briefly review the notations, definitions, and results of linear algebra used in the rest of the book, such as matrix decompositions, norms, angles of subspaces, etc. We also introduce the generalized inverse and its stable evaluation.

Zdeněk Dostál

2. Optimization

We briefly review the results concerning the minimization of quadratic functions subject to linear and/or separable convex constraints. We review the formulation of optimization problems, the existence and uniqueness of the solution, the specific forms of the KKT conditions, and the duality theory, including semicoercive problems. The choice of topics is sufficient for understanding the algorithms described in the rest of the book. The results are presented with arguments that exploit the specific structure of these problems.

Zdeněk Dostál

Basic Algorithms

Frontmatter

3. Gradient Methods

Abstract

We review the basic algorithms using the gradient direction for unconstrained QP problems, discuss their convergence in Euclidean and energy norm, and examine the effect of the steplength on their performance. We pay special attention to the possibility of enhancing the information from the previous step via the steplength (the Barizilai–Borwein method) or momentum (Polyak’s heavy ball method).

Zdeněk Dostál

4. Conjugate Gradients as Direct Method

Abstract

First, we show how to use a conjugate basis to reduce the minimization of a quadratic function to solve the class of scalar QP problems. Then, we introduce the conjugate gradient method as a tool for constructing a conjugate basis using minimizers of the cost function in expanding Krylov spaces and related gradients to generate a conjugate basis and to find the solution in a finite number of steps. We postpone the analysis of intermediate iterations to Chap. 8.

Zdeněk Dostál

5. Gradient Projection

Abstract

An essential ingredient of our algorithms for solving QP and QCQP problems is the Euclidean projection on the convex set defined by separable convex constraints. Bound, spheric, and elliptic constraints are considered. Here, we provide nontrivial bounds on the decrease of f along the projected-gradient path in terms of bounds on the spectrum of its Hessian matrix \({\mathsf {A}}\). These results allow for the effective combination of gradient projection with the conjugate gradient method.

Zdeněk Dostál

6. From Penalty to Exact Augmented Lagrangians

Abstract

We first introduce the penalty method as a tool for reducing the equality-constrained quadratic programming problem to an unconstrained one and show that increasing the penalty enforces the reduced feasibility error. Then, we apply the penalty method to the augmented Lagrangian and show that we can achieve the same feasibility error without penalization using a suitable value of Lagrangian multipliers. We examine the convergence of the resulting augmented Lagrangian method with the exact solution of auxiliary problems.

Zdeněk Dostál

7. Active Sets with Finite Termination

Abstract

First, we present the working (active) set method, which reduces the bound-constrained problem to a series of unconstrained problems solved by a direct solver. Then, we introduce the Polyak method, which implements a solution of auxiliary unconstrained problems by conjugate gradients. We show how to speed up the Polyak algorithm by “looking ahead” so it can use inexact solutions to auxiliary problems.

Zdeněk Dostál

Optimal Algorithms

Frontmatter

8. Conjugate Gradients as Iterative Method

Abstract

Using the Chebyshev polynomials, we first give the bounds on the conjugate gradient iterates’ error in bounds on the spectrum of the SPD Hessian of the cost function. Then, we present two methods of improving the rate of convergence of conjugate gradients, in particular, preconditioning using specific information about the problem and preconditioning by the conjugate projector. The latter method does not transform variables so that it can be applied to problems with separable constraints. Finally, we present the algorithm cgSLS for solving the least square problems with symmetric positive semidefinite Hessian. We validate the theory by numerical experiments.

Zdeněk Dostál

9. SMALE for Equality Constraints

Abstract

Here, we present two variants of the augmented Lagrangian method that use the conjugate gradient method in the inner loop. We start with the asymptotically exact augmented Lagrangian method, controlling the precision of the auxiliary problem’s solutions by a user-defined forcing sequence. The regularization parameter controls the convergence rate of the outer loop. The second method is SMALE (semi-monotonic augmented Lagrangian for equality constraints). The inner loop precision is regulated by the increase of the Lagrangian. The unique theoretical results concerning SMALE include a bound on the number of iterations necessary to find an approximate solution with prescribed error and independent of the conditioning of constraints. The performance of SMALE can be improved by preconditioning that preserves the gap in the spectrum. The algorithms accept dependent equality constraints.

Zdeněk Dostál

10. MPRGP for Bound Constraints

Abstract

The core of this chapter is the description and analysis of the MPRGP (modified proportioning with reduced gradient projection) algorithm for solving bound-constrained quadratic programming problems. This active-set-based algorithm expands the active set by the free gradient projection and carries out minimization in the face by the conjugate gradient method. The algorithm balances the norms of the free and chopped gradients to ensure that the reduced free gradient is always sufficiently large in the CG iterations. The modified algorithm enjoys the R-linear rate of convergence of both the cost function and norm of projected gradient. Moreover, it has the finite termination property even for dual degenerate QP problems. We show that conjugate projector preconditioning (deflation) can improve the convergence rate. We also show how to adapt MPRGP to solve problems with SPS Hessian. The performance of the algorithms, including scalability, is illustrated by solving academic benchmarks and particle simulation.

Zdeněk Dostál

Chapter 11. MPGP and PBBF for Separable QCQP

Abstract

We describe the MPGP (modified proportioning with gradient projection) algorithm for solving quadratic programming problems with separable constraints. The algorithm combines the conjugate gradient steps to minimize the cost function in the face with gradient projection steps to change the face. The decision on which step to use depends on violating the KKT conditions. The MPGP algorithm enjoys the R-linear rate of convergence of both the cost function and norm of projected gradient. We also present an alternative PBBF algorithm using projected Barzilai–Borwein steps with fallback. The performance of the algorithms, including scalability, is illustrated by solving a contact problem with anisotropic Coulomb friction.

Zdeněk Dostál

Chapter 12. Solvers for Separable and Equality QP/QCQP Problems

The chapter describes the algorithm SMALSE (semi-monotonic augmented Lagrangians for separable and equality constraints) and its variant SMALBE for bound and equality constraints. The main idea of the algorithms is to treat both sets of constraints separately. This approach enables us to use the ingredients of the algorithms of the previous chapters. We also consider the algorithm SMALSE-Mw for separable and equality constraints with a strong curvature of the feasible set boundary. We prove the convergence results that support the solving of large problems. We introduce the adaptive preconditioning for improving the convergence rate. Numerical experiments illustrate optimality and the effect of adaptive reorthogonalization.

Zdeněk Dostál

Case Studies

Frontmatter

Chapter 13. Elliptic Variational Inequalities

Abstract

Here, we introduce a model problem, the semi-coercive scalar variational inequality, describe its discretization and decomposition into subdomains and clusters, reduce the problem by duality to the bound and equality-constrained QP problem, and report some theoretical and numerical results. The results show the unique efficiency of the SMALBE/MPRGP algorithms combined with the FETI methods. The numerical experiments include the bound and/or equality QP problems discretized by billions of nodal variables and a challenging roller-bearing problem with floating bodies and dual degenerate solution.

Zdeněk Dostál

Chapter 14. Contact Problem with Friction

Abstract

We briefly review the formulation and discretization of contact problem with friction. Then, we apply the domain decomposition method to generate a class of separable and equality-constrained QP problems with a uniformly bounded spectrum. The experiments show linear complexity and a stable number of outer iterations for the problem dimensions ranging from half a million to more than eleven million. We also provide results for yielding clamp connection.

Zdeněk Dostál

Chapter 15. Model Predictive Control

Abstract

Here, we consider bound-constrained QP problems that arise when applying the Model Predictive Control (MPC). We limit our attention to the oscillating masses regulator control problem from Wang and Boyd [261]. We formulate the problems, describe their specific features, and discuss the effect of parameters on the conditioning of constraints. Then, we compare the impact of using the Newton and conjugate gradient directions in MPRGP and PRGPN. Numerical experiments illustrate the discussion.

Zdeněk Dostál

Chapter 16. Support Vector Machines

Abstract

Here, we describe the primal and dual soft margin SVM problems and give the results of numerical experiments with solving simplified dual SVM problems with soft margin. We solved the resulting QP problems with SPS or SPD Hessian and bound constraints on four classification datasets from LIBSVM dataset web page [204], namely Heart, Diabetes, Australian, and Ionosphere. We used a standard MPRGP algorithm and a variant of the Barzilai and Borwain method.

Zdeněk Dostál

Chapter 17. PERMON and ESPRESO Software

Abstract

Many algorithms presented in this book were implemented in PERMON and ESPRESO software packages.

Zdeněk Dostál

Titel: Optimal Quadratic Programming and QCQP Algorithms with Applications
Verfasst von: Zdeněk Dostál
Verlag: Springer Nature Switzerland
Electronic ISBN: 978-3-031-95167-1
Print ISBN: 978-3-031-95166-4
DOI: https://doi.org/10.1007/978-3-031-95167-1

Die PDF-Dateien dieses Buches wurden gemäß dem PDF/UA-1-Standard erstellt, um die Barrierefreiheit zu verbessern. Dazu gehören Bildschirmlesegeräte, beschriebene nicht-textuelle Inhalte (Bilder, Grafiken), Lesezeichen für eine einfache Navigation, tastaturfreundliche Links und Formulare sowie durchsuchbarer und auswählbarer Text. Wir sind uns der Bedeutung von Barrierefreiheit bewusst und freuen uns über Anfragen zur Barrierefreiheit unserer Produkte. Bei Fragen oder Bedarf an Barrierefreiheit kontaktieren Sie uns bitte unter accessibilitysupport@springernature.com.

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Background

Frontmatter

1. Linear Algebra

2. Optimization

Basic Algorithms

Frontmatter

3. Gradient Methods

4. Conjugate Gradients as Direct Method

5. Gradient Projection

6. From Penalty to Exact Augmented Lagrangians

7. Active Sets with Finite Termination

Optimal Algorithms

Frontmatter

8. Conjugate Gradients as Iterative Method

9. SMALE for Equality Constraints

10. MPRGP for Bound Constraints

Chapter 11. MPGP and PBBF for Separable QCQP

Chapter 12. Solvers for Separable and Equality QP/QCQP Problems

Case Studies

Frontmatter

Chapter 13. Elliptic Variational Inequalities

Chapter 14. Contact Problem with Friction

Chapter 15. Model Predictive Control

Chapter 16. Support Vector Machines

Chapter 17. PERMON and ESPRESO Software

Backmatter