Subspace projection preconditioner for the H-block of the KKT-System assuming that B and C have been Schur complemented into the H-block. For the A-Block, if it is there, the identity is used. If there is no A-block, PCG may be used. More...
#include <QPKKTSubspaceHPrecond.hxx>
Inheritance diagram for ConicBundle::QPKKTSubspaceHPrecond:
Public Member Functions | |
| QPKKTSubspaceHPrecond (CH_Matrix_Classes::Integer inmethod=0, CBout *cb=0, int cbinc=-1) | |
| default constructor | |
| virtual | ~QPKKTSubspaceHPrecond () |
| virtual destructor | |
| virtual int | init_data (QPSolverProxObject *Hp, QPModelBlockObject *model, const CH_Matrix_Classes::Sparsemat *A, const CH_Matrix_Classes::Indexmatrix *eq_indices, bool SchurComplAineq) |
| returns 1 if this class is not applicable in the current data situation, otherwise it stores the data pointers and these need to stay valid throught the use of the other routines but are not deleted here More... | |
| virtual int | init_system (const CH_Matrix_Classes::Matrix &KKTdiagx, const CH_Matrix_Classes::Matrix &KKTdiagy, CH_Matrix_Classes::Real Hfactor, CH_Matrix_Classes::Real prec, QPSolverParameters *params) |
| set up the primal dual KKT system for being solved for predictor and corrector rhs; the input objects KKTdiagx and KKTdiagy will not change during use of the preconditioner, so it suffices to store the address if they are need during application of the preconditioner | |
| virtual int | precondM1 (CH_Matrix_Classes::Matrix &vec) |
| returns M1^{-1}*vec; default: M1=I | |
| virtual int | set_subspace (const CH_Matrix_Classes::Matrix &insubspace) |
| if the method admits this, let the subspace be chosen externally | |
| virtual CH_Matrix_Classes::Real | get_lmin_invM1 () |
| return (an estimate of) the minimum eigenvalue of the preconditioner M1^{-1}; this is used, e.g., to correct the precission in MINRES | |
| virtual int | precond_invG1 (CH_Matrix_Classes::Matrix &vec) |
| for estimating the condition number with M1=G*G^T this returns G^{-1}*vec; default: G=I | |
| virtual int | precond_invG1tran (CH_Matrix_Classes::Matrix &vec) |
| for estimating the condition number with M1=G*G^T this returns G^{-T}*vec; default: G=I | |
| virtual CH_Matrix_Classes::Integer | precond_size () |
| for estimating the condition number directly for the preconditioned part only; negative numbers indicate that the routine is not implemented | |
| virtual int | cond_number_mult (CH_Matrix_Classes::Matrix &vec, const CH_Matrix_Classes::Matrix &KKTdiagx, const CH_Matrix_Classes::Matrix &KKTdiagy) |
| for estimating the condition number directly for the preconditioned part only | |
| virtual CH_Matrix_Classes::Integer | get_precond_rank () |
| for evaluation purposes with iterative solvers, return the rank of the precondiontioner used (or the number of n-vector multiplications per call) | |
| virtual CH_Tools::Microseconds | get_t_precond_mult () |
| for evaluation purposes with iterative solvers, return the time spent in the multiplication with | |
| virtual void | reset_t_precond_mult () |
| for evaluation purposes with iterative solvers, reset the time spent in the multiplication with the preconditioner to zero | |
 Public Member Functions inherited from ConicBundle::QPKKTPrecondObject | |
| virtual void | clear () |
| reset data to empty | |
| QPKKTPrecondObject (CBout *cb=0, int cbinc=-1) | |
| default constructor | |
| virtual | ~QPKKTPrecondObject () |
| virtual destructor | |
| virtual int | precondM2 (CH_Matrix_Classes::Matrix &) |
| returns M2^{-1}vec; default: M2=I | |
| virtual CH_Matrix_Classes::Real | get_condition_number (const CH_Matrix_Classes::Matrix &KKTdiagx, const CH_Matrix_Classes::Matrix &KKTdiagy) |
| for estimating the condition number directly for the preconditioned part only | |
| Public Member Functions inherited from ConicBundle::CBout | |
| virtual void | set_out (std::ostream *out=0, int print_level=1) |
| Specifies the output level (out==NULL: no output at all, out!=NULL and level=0: errors and warnings, level>0 increasingly detailed information) More... | |
| virtual void | set_cbout (const CBout *cb, int incr=-1) |
| Specifies the output level relative to the given CBout class. More... | |
| void | clear_cbout () |
| reset to default settings (out=0,print_level=1) | |
| CBout (const CBout *cb=0, int incr=-1) | |
| calls set_cbout | |
| CBout (std::ostream *outp, int pl=1) | |
| initialize correspondingly | |
| CBout (const CBout &cb, int incr=0) | |
| copy constructor | |
| virtual bool | cb_out (int pl=-1) const |
| Returns true if out!=0 and (pl<print_level), pl<0 should be used for WARNINGS and ERRORS only, pl==0 for usual output. | |
| std::ostream & | get_out () const |
| If cb_out() returned true, this returns the output stream, but it will abort if called with out==0. | |
| std::ostream * | get_out_ptr () const |
| returns the pointer to the output stream | |
| int | get_print_level () const |
| returns the print_level | |
| virtual int | mfile_data (std::ostream &out) const |
| writes problem data to the given outstream | |
Protected Attributes | |
| CH_Matrix_Classes::Integer | method |
| selects generation method for preconditioner | |
| CH_Matrix_Classes::Matrix | diagH |
| diagonal of the prox term | |
| const CH_Matrix_Classes::Matrix * | Vp |
| lowrank part of the prox term | |
| CH_Matrix_Classes::Integer | last_nmult |
| last number of multplications in iterative solver | |
| CH_Matrix_Classes::Real | max_sigma |
| if >0 it gives the last maximum singular value found | |
| CH_Matrix_Classes::Matrix | Diag_inv |
| diagonal with KKT diagonal part, inverted, possibly the sqrt of it (if there is a low rank part) | |
| CH_Matrix_Classes::Real | diaginvval |
| if the value is > 0 then Diag_inv must be this values times the all ones vector | |
| CH_Matrix_Classes::Matrix | subspace |
| the subspace used for projection | |
| CH_Matrix_Classes::Matrix | lowrank |
| the selected lowrank representation | |
| CH_Matrix_Classes::Indexmatrix | pivlowrank |
| the pivot sequence used | |
| CH_Matrix_Classes::Matrix | eigvals |
| the eigenvalues of the low rank approximation on the subspace | |
| CH_Matrix_Classes::Matrix | eigvecs |
| the eigenvectors within the subspace | |
| CH_Matrix_Classes::Matrix | tmpmat |
| temporary matrix | |
| CH_Matrix_Classes::Matrix | tmpvec |
| temporary matrix | |
| CH_Matrix_Classes::Symmatrix | tmpsym |
| temporary symmetric matrix | |
| CH_Matrix_Classes::Matrix | keepeigs |
| eigenvalues used to update the subspace | |
| CH_Matrix_Classes::Matrix | keepvecs |
| eignevectors used to update the subspace | |
| CH_Matrix_Classes::Matrix | rotmat |
| rotation to update the subspace | |
| CH_Matrix_Classes::Matrix | Q |
| [only used in testing] QR factorization of D^(-.5)*lowrank*eigvecs | |
| CH_Tools::Clock | clock |
| for taking the time spent in various parts | |
| CH_Tools::Microseconds | t_gen_subspace |
| time spent in generating the subspace | |
| CH_Tools::Microseconds | t_comp_lowrank |
| time spent in generating the lowrank matrix by multiplying with subspace | |
| CH_Tools::Microseconds | t_comp_svd |
| time spent in computing the singular value decomposition | |
| CH_Tools::Microseconds | t_precond_mult |
| time spent in multiplying with the preconditioner | |
| Protected Attributes inherited from ConicBundle::QPKKTPrecondObject | |
| QPSolverProxObject * | Hp |
| points to the quadratic cost representation, may NOT be NULL afer init | |
| QPModelBlockObject * | model |
| points to the cutting model information, may be NULL | |
| const CH_Matrix_Classes::Sparsemat * | A |
| points to a possibly present constraint matrix, may be NULL | |
| const CH_Matrix_Classes::Indexmatrix * | eq_indices |
| if not NULL, these rows of A correspond to equations; needed for checking applicability of this Object | |
| bool | SchurComplAineq |
| if true, the inequalities of A are Schur complemented into the H block | |
| CH_Matrix_Classes::Real | Hfactor |
| the prox term of Hp is multiplied by this | |
Detailed Description
Subspace projection preconditioner for the H-block of the KKT-System assuming that B and C have been Schur complemented into the H-block. For the A-Block, if it is there, the identity is used. If there is no A-block, PCG may be used.
See the text to QPKKTSolverObject for the terminology of the primal dual KKT System and the general outline.
This implementation of a QPKKTPrecondObject is suitable e.g. for QPIterativeKKTHASolver and QPIterativeKKTHAeqSolver.
Depending on method the subspace is chosen deterministically or randomly generated. The code is still rather experimental and therefore currently a multitude of variants are implemented for testing.
The current variants of method are (recommendation: use 31)
- 0 ... no preconditioning
- 1 ... diagonal preconditioning
- 10 ... exact preconditioning (full low rank subspace, way to expensive in general)
- 11 ... Johnson-Lindenstrauss preconditioning, Achlioptas {-1,0,1} version
- 12 ... JL preconditioning, normal distribution N(0,1/cols)
- 20 ... randomized orthogonal subspace, updated from one system to the next
- 21 ... randomized orthogonal subspace, regenerated for every system
- 3[0-9] ... deterministic subspace selection, where the i in "3i" uses the minmum value 10^i for including a column. 31 is the recommended version.
The most important routines of the model described in the QPModelBlockObject that are required here are (besides sizes and multiplications with the bundle matrix B)
- QPModelBlockObject::prepare_BCSchur_JLprecond() for multiplying the Schur complemented model part with a subspace
- QPModelBlockObject::propose_BCSchur_pcsubspace() for deterministically appending subspace generated columns of the Schur complemented model part
Member Function Documentation
◆ init_data()
|
virtual |
returns 1 if this class is not applicable in the current data situation, otherwise it stores the data pointers and these need to stay valid throught the use of the other routines but are not deleted here
- Parameters
-
Hp may not be be NULL model may be NULL A may be NULL eq_indices if not NULL these rows of A correspond to equations SchurComplAineq if true, the inequalities of A are Schur complemented into the H block
Implements ConicBundle::QPKKTPrecondObject.
The documentation for this class was generated from the following file:
