oracle interface (abstract class). For each of your functions, provide a derived class. More...
#include <CBSolver.hxx>
Public Member Functions | |
| virtual int | evaluate (const double *current_point, double relprec, double &objective_value, std::vector< Minorant *> &minorants, PrimalExtender *&primal_extender)=0 |
| Called by the solver. Has to Return function value and at least one (epsilon) subgradient and, possibly for Lagrangean relaxation, some primal data. More... | |
| virtual int | apply_modification (const OracleModification &oracle_modification, const double *new_center, const double *old_center, bool &discard_objective_in_center, bool &discard_model, bool &discard_aggregates, MinorantExtender *&minorant_extender) |
| This routine need not be implemented unless variables (constraints in Lagrangean relaxation) are added or deleted on the fly. More... | |
| virtual bool | check_correctness () const |
| switch on/off some correctness checks on the oracle | |
Detailed Description
oracle interface (abstract class). For each of your functions, provide a derived class.
The oracle interface is used to describe and pass convex objective functions to the ConicBundle::CBSolver. The dimension of the argument vector of the function must be set in ConicBundle::CBSolver::init_problem() and the functions are then added to the solver by ConicBundle::CBSolver::add_function().
If the sum of several such functions is to be minimized it is the task of the user to guarantee, that all dimensions match.
If the function corresponds to Lagrangean relaxation of a primal maximization problem one may want to generate a primal approximate solution. In this case, return in the function FunctionOracle::evaluate() within the minorant the generating primal objects for each subgradient/minorant. If no primal objects are included, there will be no primal aggregation.
If primal aggregation is used then it is possible to implement a primal cutting plane framework. This requires the introduction of new (dual) variables in the design space of the function. In this case a heap object MinorantExtender must be returend in the call of FunctionOracle::get_minorant_extender(); this must be able to fill in the missing coordinates in existing minorants/subgradients maybe on basis of the associated primal data stored in the minorants. If this feature is not needed, the function may be used as is and need not be reimplemented.
Member Function Documentation
◆ apply_modification()
|
virtual |
This routine need not be implemented unless variables (constraints in Lagrangean relaxation) are added or deleted on the fly.
The routine is only called by the solver if the variables indeed get modified. oracle_modification is then used to either transfer user supplied instructions to the oracle on how to modify itself or to inform the oracle about changes the solver was asked to perform on the variables. If available, the solver will also show the effect of these changes on the center point in new_center and old_center; if these are not available then they hold NULL. A user supplied oracle_modification will be checked for consistency with the actual changes in the variables and mismatches will cause failures.
The remaining variables are output variables by which the oracle tells the solver which information has a chance to be preserved in view of these changes. If e.g. the deletion of some nonzero variables invalidates the function value in the new center, the oracle has to set discard_objective_in_center=true. If the entire model cannot be preserved (this includes the aggregates and the function values), the oracle needs to set discard_model=true; If only aggregate minorants cannot be preserved, the oracle needs to set discard_aggregates=true. Whenever new variables were added, the model can only be preserved if the remaining minorants (maybe without aggregates) can be extended for these new variables. In this case the oracle has to supply the appropriate MinorantExtender via minorant_extender. A given minorant_extender will only be applied if new variables were added and indices passed to it then refer to the situation after* the changes (append and map-operation of OracleModification) were executed on them. If the operation fails for any of the minorants, the entire model will be discarded.
Return value 0 indicates that these actions allow to continue without errors, other return values result in an overall error on these changes.
◆ evaluate()
|
pure virtual |
Called by the solver. Has to Return function value and at least one (epsilon) subgradient and, possibly for Lagrangean relaxation, some primal data.
The evaluation method is the main interface to the bundle solver. The solver calls this method to obtain for the current_point (its dimension is set in ConicBundle::CBSolver::init_problem()) the objective_value and (epsilon) subgradient information. In any call several epsilon subgradients may be returned in minorants along with their offset, but at least one has to be returend. Each subgradient and offset describes a linear minorant to the convex function and is used by the bundle method to form a cutting model of the convex function.
In many applications, computing the function value is an iterative process that approaches the true function value from below. On input the code offers a bound in objective_value for the function value, above which it is certain that the code will reject the current point. If in the iterative process a lower bound on the function value exceeds this bound, then it is sufficient to return, instead of the true function value and a subgradient, the current lower bound and a vector so that together they describe a supporting hyperplane (i.e. a linear minorant) to the function at this point.
If the function corresponds to Lagrangean relaxation of a primal maximization problem one may want to generate a primal approximate solution. For this purpose the minorants may also hold information on the primal data. If at each call and for each epsilon subgradient the corresponding generating primal object (must be derived from ConicBundle::PrimalData, e.g., a ConicBundle::PrimalDVector) is stored, then the code automatically performs the aggregation corresponding to the aggregation of the subgradients on the primal data objects. The primal approximate solution is finally delivered by the methods ConicBundle::CBSolver::get_approximate_primal() or ConicBundle::CBSolver::get_center_primal().
All minorants passed to the solver must be objects allocated on the heap. The ownership of these objects is transferred to the solver and the solver will destroy them eventually, so DO NOT delete them yourself!
If no primal aggregation is desired, simply do not touch primal_data or clear it.
- Parameters
-
[in] current_point (const double*) argument of the function (e.g. the Lagrange multipliers) [in] relprec (double) relative precision requirement for objective values that may lead to descent steps (this precision is not required if it is already certain that the function value will be too poor) [in,out] objective_value (double&) - on input: value gives the threshold for a null step; you may stop, if a cutting plane yields at least this;
- on output: return an upper bound on the true function value within relprec *(abs(objval)+1.), if there is no linear minorant cutting above the threshold specified in objective_value on input. Otherwise the return value should be the max of cut_values.
[out] minorants (std::vector<Minorant*>) for returning linear minorants (subgradients and their offset values). At least one must be returned and the one at index 0 must maximize the value at the current point over all further ones given here. In particular its value at point should be above the threshold or be within relprec *(abs(objval)+1.) of the true objective. Within the minorants primal data may be supplied if this should be aggregated along. [out] primal_extender (PrimalExtender*&) if primal_data provided in minonrants of previous calls has now to be updated due to changes in the primal problem – e.g., this may happen in column generation – one may return a pointer to PrimalExtender object on the heap. This object will be used by ConicBundle to update all its internally stored primal_data objects in its minorants by calling PrimalExtender::extend on each of these (but not on those supplied by the new minorants). Afterwards ConicBundle deletes primal_extender. If this is not needed, the variable holds 0.
- Returns
- 0, all correct
- !=0, failure. This does not necessarily terminate the bundle method. Termination is forced only if no new subgradient is returned.
The documentation for this class was generated from the following file:
