KASKADE 7 development version
Public Types | Public Member Functions | Static Public Attributes | Protected Member Functions | Protected Attributes | List of all members
Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother > Class Template Referenceabstract

A multigrid solver for convex QPs. More...

#include <qpmg.hh>

Detailed Description

template<int d, class Prolongation, class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
class Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >

A multigrid solver for convex QPs.

This solves QPs of the form

\[ \min \frac{1}{2} x^T A x + c^T x \quad \text{s.t.} \quad Bx\le b. \]

On the finest level, this works with the augmented Lagrangian formulation

\[ \min \frac{1}{2} x^T A x + c^T x + \frac{\gamma}{2} \|(Bx-(b-\lambda/\gamma))_+\|^2 \]

for some multiplier \( \lambda \ge 0 \), and an appropriate multiplier update.

The multilevel minimization works with level-dependent penalty factors. On each level, the following computations ( \(\text{MGM}(A,B,x,c,b,\gamma)\) are performed:

Rationale: The level-dependence of the penalty factor is based on the following idea. Enforcing the constraint by the penalty should allow sufficient slack such as not to impede convergence of Gauß-Seidel. On coarser levels, GS is supposed to take larger steps (the whole reason for multigrid) approximately by a factor of two for each grid level, and so the penalty should increase the permitted steps by a factor of two as well. This means decreasing the penalty factor by four.

The restriction of multipliers is not necessary for asymptotically optimal complexity, as the number of constraints is \( \mathcal{O}(N^{1-1/d}) \) and therefore the computational work of a single V-cycle is \( \mathcal{O}(N + N^{1-1/d}\log N) = \mathcal{O}(N) \). Nevertheless, restricting the constraints in an appropriate way (open how to do this) might be beneficial for performance.

Template Parameters
dthe dimension of (vector valued) optimization variables
Prolongationdefines the data type of the prolongation matrices defining the hierarchy
Realfloating point format
Smootherthe smoother for the local QPs on all grids but the coarse one
CoarseSmootherthe smoother for the coarse grid

Definition at line 311 of file qpmg.hh.

Inheritance diagram for Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >:
Kaskade::QPMultiGridBase< d, Prolongation, QPPenaltySmoother< d, double >, QPPenaltySmoother< d, double >, double >

Public Types

using VectorX = Dune::BlockVector< Dune::FieldVector< Real, d > >
 
using VectorB = Dune::BlockVector< Dune::FieldVector< Real, 1 > >
 
using MatrixA = NumaBCRSMatrix< EntryA >
 
using MatrixB = NumaBCRSMatrix< Dune::FieldMatrix< Real, 1, d > >
 
using Self = QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >
 
using SmootherType = std::conditional_t< smoothersEqual, QPPenaltySmoother< d, double >, std::variant< QPPenaltySmoother< d, double >, QPPenaltySmoother< d, double > > >
 

Public Member Functions

 QPMultiGrid (MatrixA const &A, MatrixB const &B, std::vector< Prolongation > &&prolongations, Real smootherRegularization=0, bool blocks=true, bool directOnCoarse=true)
 Constructs the solver, providing the matrices \( A \) and \( B \). More...
 
 ~QPMultiGrid ()
 Destructor. More...
 
std::tuple< VectorX, VectorB, int > solve (VectorX x, VectorX const &c, VectorB const &b, VectorB const &lambda, double tol, int vcycles) const
 Approximately solves the QP for the given right hand side vectors up to a given tolerance. More...
 
VectorB firstOrderUpdate (VectorX const &x, VectorB const &b, VectorB const &lambda) const
 A first order update for the Lagrange multiplier. More...
 
SelfsetPenalty (Real gamma, bool levelDependent=false)
 Sets the penalty factor \( \gamma \). More...
 
SelfsetConstraintsMode (ParallelMode m)
 
SelfsetGlobalMode (ParallelMode m)
 
double getPenalty ()
 Returns the current penalty factor \( \gamma \). More...
 
VectorX step (VectorX const &x, VectorX c, VectorB b) const
 Computes a single V-cycle correction for approximately solving the QP for the given right hand side vectors. More...
 
std::tuple< VectorX, int > solve (VectorX x, VectorX const &c, VectorB const &b, double tol, int vcycles) const
 Approximately solves the QP for the given right hand side vectors up to a given tolerance. More...
 
SelfsetCoarseLevel (int coarselevel)
 Defines the grid level to be used as coarse grid. More...
 
SelfsetSmoothings (int pre, int post)
 
SelfsetCoarseCorrections (int n)
 Sets the number of coarse corrections to compute and apply. More...
 
SelfsetBulkMode (ParallelMode m)
 Defines the smoothing strategy to use for unconstrained degrees of freedom. More...
 
SelfsetLogger (MGSolverStatistics< d, double > *logger)
 Sets the logging facility for reporting solver statistics. More...
 

Static Public Attributes

static constexpr bool smoothersEqual
 

Protected Member Functions

virtual double computeEnergy (MatrixA const &A, MatrixB const &B, VectorX const &c, VectorB const &b, VectorX const &x) const
 Computes the energy, given by the penalized energy function. More...
 
virtual std::tuple< VectorX, VectorB, int > gradient (MatrixA const &A, MatrixB const &B, VectorX const &c, VectorB const &b, VectorX const &x) const
 Computes the gradient of the penalized energy function. More...
 
virtual std::tuple< VectorX, VectorX, VectorX, VectorB, int > gradient_extended (MatrixA const &A, MatrixB const &B, VectorX const &c, VectorB const &b, VectorX const &x) const
 Computes the gradient of the penalized energy function. More...
 
virtual double qpLinesearch (MatrixA const &A, MatrixB const &B, VectorX const &c, VectorB const &b, VectorX const &dx) const
 
virtual double computeEnergy (MatrixA const &A, MatrixB const &B, VectorX const &c, VectorB const &b, VectorX const &x) const=0
 Compute the problem energy of current iterate for logging purposes. More...
 
virtual std::tuple< VectorX, VectorB, int > gradient (MatrixA const &A, MatrixB const &B, VectorX const &c, VectorB const &b, VectorX const &x) const=0
 Compute the problem gradient of current iterate. More...
 
virtual std::tuple< VectorX, VectorX, VectorX, VectorB, int > gradient_extended (MatrixA const &A, MatrixB const &B, VectorX const &c, VectorB const &b, VectorX const &x) const=0
 Computes the gradient of current iterate, giving more information on the components of the gradient. (It might be split in several terms grad0 and grad1). More...
 
virtual double qpLinesearch (MatrixA const &A, MatrixB const &B, VectorX const &c, VectorB const &b, VectorX const &dx) const=0
 Compute the optimal step size in direction of dx. More...
 
MatrixB const & B () const
 Provides a reference to the fine grid constraints. More...
 

Protected Attributes

std::vector< SmootherTypesmoothers
 

Member Typedef Documentation

◆ MatrixA

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
using Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::MatrixA = NumaBCRSMatrix<EntryA>

Definition at line 320 of file qpmg.hh.

◆ MatrixB

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
using Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::MatrixB = NumaBCRSMatrix<Dune::FieldMatrix<Real,1,d> >

Definition at line 321 of file qpmg.hh.

◆ Self

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
using Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::Self = QPMultiGrid<d,Prolongation,Real,Smoother,CoarseSmoother>

Definition at line 322 of file qpmg.hh.

◆ SmootherType

using Kaskade::QPMultiGridBase< d, Prolongation, QPPenaltySmoother< d, double > , QPPenaltySmoother< d, double > , double >::SmootherType = std::conditional_t<smoothersEqual, QPPenaltySmoother< d, double > , std::variant<QPPenaltySmoother< d, double > ,QPPenaltySmoother< d, double > > >
inherited

Definition at line 105 of file qpmg.hh.

◆ VectorB

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
using Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::VectorB = Dune::BlockVector<Dune::FieldVector<Real,1> >

Definition at line 319 of file qpmg.hh.

◆ VectorX

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
using Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::VectorX = Dune::BlockVector<Dune::FieldVector<Real,d> >

Definition at line 318 of file qpmg.hh.

Constructor & Destructor Documentation

◆ QPMultiGrid()

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::QPMultiGrid ( MatrixA const &  A,
MatrixB const &  B,
std::vector< Prolongation > &&  prolongations,
Real  smootherRegularization = 0,
bool  blocks = true,
bool  directOnCoarse = true 
)

Constructs the solver, providing the matrices \( A \) and \( B \).

Parameters
Athe Hessian. The matrix is copied internally and need not exist after solver construction.
Bthe constraints. The matrix is referenced internally and has to exist during the lifetime of the solver.
blocks
  • block=true: treat blocks of dof coupled by constraints jointly (default)
  • block=false: treat all dofs individually (only for testing and comparison purposes)
Warning
This is intended for testing purposes only and may be removed in future.
Parameters
directOnCoarse
  • directOnCoarse=true use direct solver for problem on coarse grid
  • directOnCoarse=false use a few iterative (smoothing) steps on coarse grid (block Jacobi/Gauss Seidel)

◆ ~QPMultiGrid()

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::~QPMultiGrid ( )

Destructor.

Member Function Documentation

◆ B()

MatrixB const & Kaskade::QPMultiGridBase< d, Prolongation, QPPenaltySmoother< d, double > , QPPenaltySmoother< d, double > , double >::B ( ) const
protectedinherited

Provides a reference to the fine grid constraints.

◆ computeEnergy() [1/2]

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
virtual double Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::computeEnergy ( MatrixA const &  A,
MatrixB const &  B,
VectorX const &  c,
VectorB const &  b,
VectorX const &  x 
) const
protectedvirtual

Computes the energy, given by the penalized energy function.

\[ \frac{1}{2} x^T A x + c^T x + \frac{\gamma}{2} \|(Bx-b)_+\|^2 \]

◆ computeEnergy() [2/2]

virtual double Kaskade::QPMultiGridBase< d, Prolongation, QPPenaltySmoother< d, double > , QPPenaltySmoother< d, double > , double >::computeEnergy ( MatrixA const &  A,
MatrixB const &  B,
VectorX const &  c,
VectorB const &  b,
VectorX const &  x 
) const
protectedpure virtualinherited

Compute the problem energy of current iterate for logging purposes.

◆ firstOrderUpdate()

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
VectorB Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::firstOrderUpdate ( VectorX const &  x,
VectorB const &  b,
VectorB const &  lambda 
) const

A first order update for the Lagrange multiplier.

Compute first order multiplier update \lambda <- (\lambda + \gamma*(B*x-b))_+, or equivalently \lambda <- \lambda + max(-\lambda, \gamma*(B*x-b)). This makes only sense, however, if we have actually minimized - otherwise there is no new information in the constraint violation. Thus the accuracy of minimization should be sufficient.

Parameters
xprimal variable
bconstant constraint term
lambdaapproximate multiplier
Returns
multiplier update \( \delta\lambda \)

◆ getPenalty()

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
double Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::getPenalty ( )

Returns the current penalty factor \( \gamma \).

◆ gradient() [1/2]

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
virtual std::tuple< VectorX, VectorB, int > Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::gradient ( MatrixA const &  A,
MatrixB const &  B,
VectorX const &  c,
VectorB const &  b,
VectorX const &  x 
) const
protectedvirtual

Computes the gradient of the penalized energy function.

\[ \frac{1}{2} x^T A x + c^T x + \frac{\gamma}{2} \|(Bx-b)_+\|^2 \]

Returns
a tuple (grad, cons, nActive) consisting of:
  • grad: full gradient given by

    \[ Ax + c + \gamma*B^T(Bx-b)_+ \]

  • cons: vector of constraint violation give by

    \[ (Bx-b)_+ \]

  • nActive: number of active constraints, i.e.

    \[ | \{ i \colon (Bx-b)_i >= 0 \} | \]

◆ gradient() [2/2]

virtual std::tuple< VectorX, VectorB, int > Kaskade::QPMultiGridBase< d, Prolongation, QPPenaltySmoother< d, double > , QPPenaltySmoother< d, double > , double >::gradient ( MatrixA const &  A,
MatrixB const &  B,
VectorX const &  c,
VectorB const &  b,
VectorX const &  x 
) const
protectedpure virtualinherited

Compute the problem gradient of current iterate.

◆ gradient_extended() [1/2]

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
virtual std::tuple< VectorX, VectorX, VectorX, VectorB, int > Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::gradient_extended ( MatrixA const &  A,
MatrixB const &  B,
VectorX const &  c,
VectorB const &  b,
VectorX const &  x 
) const
protectedvirtual

Computes the gradient of the penalized energy function.

\[ \frac{1}{2} x^T A x + c^T x + \frac{\gamma}{2} \|(Bx-b)_+\|^2 \]

Returns
a tuple (grad, grad0, grad1, cons, nActive) consisting of:
  • grad: full gradient given by

    \[ Ax + c + \gamma*B^T(Bx-b)_+ \]

  • grad0: enegry component of gradient given by

    \[ Ax + c \]

  • grad1: penalty component of gradient given by

    \[ \gamma*B^T(Bx-b)_+ \]

  • cons: vector of constraint violation give by

    \[ (Bx-b)_+ \]

  • nActive: number of active constraints, i.e.

    \[ | \{ i \colon (Bx-b)_i >= 0 \} | \]

◆ gradient_extended() [2/2]

virtual std::tuple< VectorX, VectorX, VectorX, VectorB, int > Kaskade::QPMultiGridBase< d, Prolongation, QPPenaltySmoother< d, double > , QPPenaltySmoother< d, double > , double >::gradient_extended ( MatrixA const &  A,
MatrixB const &  B,
VectorX const &  c,
VectorB const &  b,
VectorX const &  x 
) const
protectedpure virtualinherited

Computes the gradient of current iterate, giving more information on the components of the gradient. (It might be split in several terms grad0 and grad1).

◆ qpLinesearch() [1/2]

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
virtual double Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::qpLinesearch ( MatrixA const &  A,
MatrixB const &  B,
VectorX const &  c,
VectorB const &  b,
VectorX const &  dx 
) const
protectedvirtual

◆ qpLinesearch() [2/2]

virtual double Kaskade::QPMultiGridBase< d, Prolongation, QPPenaltySmoother< d, double > , QPPenaltySmoother< d, double > , double >::qpLinesearch ( MatrixA const &  A,
MatrixB const &  B,
VectorX const &  c,
VectorB const &  b,
VectorX const &  dx 
) const
protectedpure virtualinherited

Compute the optimal step size in direction of dx.

◆ setBulkMode()

Self & Kaskade::QPMultiGridBase< d, Prolongation, QPPenaltySmoother< d, double > , QPPenaltySmoother< d, double > , double >::setBulkMode ( ParallelMode  m)
inherited

Defines the smoothing strategy to use for unconstrained degrees of freedom.

In contact problems, those are usually the interior nodes, and the ones without potential contact partner. The smoother can operate in parallel (Jacobi) or sequentially (Gauss-Seidel). In the parallel way, an exact linesearch is performed after the smoothing in order to guarantee descent.

◆ setCoarseCorrections()

Self & Kaskade::QPMultiGridBase< d, Prolongation, QPPenaltySmoother< d, double > , QPPenaltySmoother< d, double > , double >::setCoarseCorrections ( int  n)
inherited

Sets the number of coarse corrections to compute and apply.

Parameters
nnumber of coarse corrections
  • n=0: just the smoother on the fine grid is performed, no multigrid at all (for testing purposes only).
  • n=1: V-cycle (default)
  • n=2: W-cycle

◆ setCoarseLevel()

Self & Kaskade::QPMultiGridBase< d, Prolongation, QPPenaltySmoother< d, double > , QPPenaltySmoother< d, double > , double >::setCoarseLevel ( int  coarselevel)
inherited

Defines the grid level to be used as coarse grid.

Parameters
coarselevelthe coarse grid level, between 0 and the max grid level

If coarselevel is outside its allowed range, it is projected onto that range.

◆ setConstraintsMode()

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
Self & Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::setConstraintsMode ( ParallelMode  m)

◆ setGlobalMode()

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
Self & Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::setGlobalMode ( ParallelMode  m)

◆ setLogger()

Self & Kaskade::QPMultiGridBase< d, Prolongation, QPPenaltySmoother< d, double > , QPPenaltySmoother< d, double > , double >::setLogger ( MGSolverStatistics< d, double > *  logger)
inherited

Sets the logging facility for reporting solver statistics.

Parameters
loggera pointer to the logger object. This can be a nullpointer, in which case logging is stopped.

Ownership of the logger object remains with the caller. The logger object needs to exist for the lifetime of the QPMultiGrid class or until it is replaced by a different logger (or none).

◆ setPenalty()

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
Self & Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::setPenalty ( Real  gamma,
bool  levelDependent = false 
)

Sets the penalty factor \( \gamma \).

The default on construction is \( \gamma = 10^3 \).

Warning
set methods in the base class return a reference to the base class, which impairs chaining of setters. Call the derived class setters first, e.g.
mg.setPenalty(1e3).setCoarseCorrections(2);
Parameters
gammathe penalty parameter
levelDependentif set true, we use level dependent penaltys, i.e., gamma on finest level and gamma/4 recursively on coarser levels

◆ setSmoothings()

Self & Kaskade::QPMultiGridBase< d, Prolongation, QPPenaltySmoother< d, double > , QPPenaltySmoother< d, double > , double >::setSmoothings ( int  pre,
int  post 
)
inherited

◆ solve() [1/2]

std::tuple< VectorX, int > Kaskade::QPMultiGridBase< d, Prolongation, QPPenaltySmoother< d, double > , QPPenaltySmoother< d, double > , double >::solve ( VectorX  x,
VectorX const &  c,
VectorB const &  b,
double  tol,
int  vcycles 
) const
inherited

Approximately solves the QP for the given right hand side vectors up to a given tolerance.

Parameters
xinitial guess for the solution
clinear objective term
bconstant constraint term
toltolerance
Returns
a tuple \( (x,\mathrm{iter}) \) of solution vector, multiplier update, and iteration count

◆ solve() [2/2]

template<int d, class Prolongation , class Real = double, class Smoother = QPPenaltySmoother<d,Real>, class CoarseSmoother = QPPenaltySmoother<d,Real>>
std::tuple< VectorX, VectorB, int > Kaskade::QPMultiGrid< d, Prolongation, Real, Smoother, CoarseSmoother >::solve ( VectorX  x,
VectorX const &  c,
VectorB const &  b,
VectorB const &  lambda,
double  tol,
int  vcycles 
) const

Approximately solves the QP for the given right hand side vectors up to a given tolerance.

Parameters
xinitial guess for the solution
clinear objective term
bconstant constraint term
lambdaapproximate multiplier
toltolerance
Returns
a tuple \( (x,\delta\lambda,\mathrm{iter}) \) of solution vector, multiplier update, and iteration count

◆ step()

VectorX Kaskade::QPMultiGridBase< d, Prolongation, QPPenaltySmoother< d, double > , QPPenaltySmoother< d, double > , double >::step ( VectorX const &  x,
VectorX  c,
VectorB  b 
) const
inherited

Computes a single V-cycle correction for approximately solving the QP for the given right hand side vectors.

Parameters
xinitial guess for the solution
clinear objective term
bconstant constraint term
Returns
the correction dx

Member Data Documentation

◆ smoothers

std::vector<SmootherType> Kaskade::QPMultiGridBase< d, Prolongation, QPPenaltySmoother< d, double > , QPPenaltySmoother< d, double > , double >::smoothers
protectedinherited

Definition at line 228 of file qpmg.hh.

◆ smoothersEqual

constexpr bool Kaskade::QPMultiGridBase< d, Prolongation, QPPenaltySmoother< d, double > , QPPenaltySmoother< d, double > , double >::smoothersEqual
staticconstexprinherited

Definition at line 104 of file qpmg.hh.


The documentation for this class was generated from the following file: