Most classes are specializations/reinterpretations of the class Modification. More...
Classes | |
| class | ConicBundle::ModificationBase |
| basic routines for the base classes for reorganizing maps More... | |
| class | ConicBundle::Modification |
| base class for collecting and organizing a sequence of changes to linear data so that it can be carried out in one step later on; this class comprises all features, derived ones are specializations with partial reinterpretations. More... | |
| class | ConicBundle::GroundsetModification |
| Collects modifications for the unconstrained Groundset for appending, deleting or reassigning variables. More... | |
| class | ConicBundle::LPGroundsetModification |
| Collects modifications for the linearly constrained LPGroundset for appending, deleting or reassigning variables (with bounds and starting values) and constraints (with bounds) More... | |
| class | ConicBundle::AFTModification |
| collects modifications for an AffineFunctionTransformation for the scaling and offset constants as well as for appending, deleting or reassigning columns and rows of the transformation data More... | |
| class | ConicBundle::FunctionObjectModification |
| abstract interface for informing the bundle model routines about changes in the oracle function and, possibly, for modifying the affine transformation of the oracle function's arguments. More... | |
Detailed Description
Most classes are specializations/reinterpretations of the class Modification.
Dynamic additions and deletions of variables during the optimization process occur frequently in Lagrangian relaxation of primal linear cutting planes that are separated on basis of a current approximate solution. In the context of sums of convex functions they frequently represent coupling ressource constraints between function subgroups that compete for this ressource. The typical features are thus
- variables have to be added/deleted that are common to some of the functions but do not appear in all of them
- cutting models of unaffected functions can and should be preserved
- if the new variable is a multiplier of a new linear constraint, it typically starts with value zero, so even for the changed functions the function values are not affected. Furthermore, most subgradients arise as primal violation
of the relaxed constraints 
for some specific PrimalData 
. If this PrimalData is still available for an old subgradient, a new constraints 
in just gives rise to a new coordinate 
in this subgradient and the new entries can be filled in. If this can be done for all new coordinates of the subgradients in use, then also the cutting model of the modified functions can be preserved in spite of the changes. - in bundle methods it does not hurt too much to discard a model after a descent step, but if models cannot be preserved throughout sequences of null steps convergence is seriously endangered and the quality of the primal approximations is poor as well.
If the Lagrangian relaxation of a changing set of linear constraints is modelled via an AffineFunctionTransformation on the support function of the primal groundset, then all aspects can be handled and checked by ConicBundle directly. Indeed, in this case, the function representing the ground set will not be affected by the changes in the argument function. In several applications, however, the changes might also affect the function itself (e.g. if it uses a column generation approach on the primal side) and ConicBundle then needs the cooperation of the function in order to keep a model alive as long as possible. The attempt to support this in any thinkable form entails rather cumbersome details.
- All changes, those affecting any AffineFunctionTransformation or any Oracle, have to be communicated and excuted through the solver (and from this through its respective SumBlockModel) via so called modifications. The solver then adapts the groundset and possibly modifies some AffineFunctionTransformation automatically so that only those functions are affected that need to be. The models of affected functions communicate the local changes via modifications to their respective oracles by calling e.g. FunctionOracle::apply_modification(). Only if in this the oracle asserts that the modifcations may allow to preserve the cutting model by possibly providing extension routines for previous subgradients, will the model try to save the cutting model.
- All modifications are accumulated as long as possible before they are actually excuted (via a routine called e.g. Modification::incorporate()) This should help to keep the previously computed data valid as long as possible and may help to continue even if one modification turns out to fail the consistency checks in the accumulation process. Thus the function may not yet change even if a modification has been entered for it. Still, further modifications always have to be formulated as if the previous ones are already executed for the accumulation process to work independent of the actual point in time, when part or all of the modifcations are carried out.
- The modifications induced on the Groundset by MatrixCBSolver::append_variables(), MatrixCBSolver::delete_variables() and MatrixCBSolver::reassign_variables() are generated by MatrixCBSolver automatically (via GroundsetModification and LPGroundsetModification), but a function specific FunctionObjectModification to an AffineFunctionTransformation (via AFTModification) or to the oracles themselves (via an appropriate implementation of an OracleModification and e.g. MatrixFunctionOracle::apply_modification()) have to be given explicitly and consistently! Read the instructions there carefully.
- Changing an oracle during a call to e.g. MatrixFunctionOracle::evaluate() because of a primal column generation approach will typically also allow to preserve the model if a PrimalExtender is returned in the last argument to the calling SumBlockModel, so that it can adapt the PrimalData of past subgradients that are still in use there.
Examples modifications for the various oracle classes are NNCBoxSupportModification, SOCSupportModification, PSCAffineModification and AFTModification. The classes Modification and GroundsetModification come in handy in this.
