ConicBundle::FunctionOracle Class Reference
[Interface to ConicBundle for the Language C++]

oracle interface (abstract class). For each of your functions, provide a derived class. More...

#include <CBSolver.hxx>

Inheritance diagram for ConicBundle::FunctionOracle:

ConicBundle::FunctionObject

List of all members.

Public Member Functions

virtual int evaluate (const DVector &current_point, double relprec, double &objective_value, DVector &cut_values, std::vector< DVector > &eps_subgradients, std::vector< PrimalData * > &primal_data, 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.
virtual int subgradient_extension (const PrimalData *, const IVector &, DVector &)
 This routine is need not be implemented unless variables (constraints in Lagrangean relaxation) are added on the fly.


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 ConicBundle::CBSolver::evaluate() the generating primal objects for each subgradient. If no primal objects are returned, 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 the function ConicBundle::CBSolver::subgradient_extension() serves the purpose of filling in the missing coordinates in existing subgradients. If this feature is not needed, the function may be used as is and need not be reimplemented.


Member Function Documentation

virtual int ConicBundle::FunctionOracle::evaluate ( const DVector current_point,
double  relprec,
double &  objective_value,
DVector cut_values,
std::vector< DVector > &  eps_subgradients,
std::vector< PrimalData * > &  primal_data,
PrimalExtender *&  primal_extender 
) [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 and (epsilon) subgradient information. In any call several epsilon subgradients may be returned in cut_values and eps_subgradients, but at least one has to be returend. Each subgradient describes a linear minorant to the convex function and is used by the bundle method to form a cutting model of the convex function.

The i-th linear minorant consits of cut_values[i] (the value of the cutting plane in current_point) and epssubgradients[i] (a ConicBundle::DVector that describes the linear behavior)

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. The parameter primal_data serves this purpose. 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 in primal_data, 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 primal objects passed to the solver via primal_data must be objects allocated on the heap. The ownership of tese 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 DVector&) 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] cut_values (Dvector&) store for each linear minorant (epsilon subgradient) the value at the argument (must correspond to sequence in subgradients)
[out] eps_subgradients (std::vector<DVector>&) store for each linear minorant the epsilon subgradient vector (each of the same length as the argument, must correspond in sequence to cut_values.
[out] primal_data (std::vector<PrimalData*>&) If the function arises from Lagrangean relaxation and a primal approximation is desired then return the primal data objects corresponding to the eps_subgradients. The control over all PrimalData objects pointed to by primal_data is passed to the calling routine. The calling routine will delete these objectes eventually.
[out] primal_extender (PrimalExtender*&) if primal_data 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 by calling PrimalExtender::extend on each of these, 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.

virtual int ConicBundle::FunctionOracle::subgradient_extension ( const PrimalData ,
const IVector ,
DVector  
) [inline, virtual]

This routine is need not be implemented unless variables (constraints in Lagrangean relaxation) are added on the fly.

The solver calls this routine whenever new variables have been added on the fly in order to extend old subgradients to the new coordinates. If primal data was supplied for the subgradients then generating_primal holds a pointer to this (possibly aggregated) data, otherwise it is NULL.

In the presence of primal data, the new coordinates correspond to the violation of the new primal constraints. These have to be returned in new_subgradient_values; more precisely, for i=0 to varialb_indices.size()-1 the element new_subgradient_values[i] has to hold the subgradient information of constraint variable_indices[i];

If generating_primal is NULL, then the routine can only successfully extend the subgradients, if the new coordinates have no influence on the function; then the new subgradient coordinates are all zero and the components of new_subgradient_values have to be initialized to zero.

Parameters:
[in] generating_primal (const PrimalData*, may be NULL) If not Null it holds the (possibly aggregated) primal solution that generated the subgradient that needs to be extendend
[in] variable_indices (const IVector&) for the variables with indices in variable_indices[i], the subgradient coefficient has to be computed
[out] new_subgradient_values (DVector &) store the the subgradient coefficient of the variable with index variable_indices[i] at new_subgradient_values[i] for all i.
Returns:
  • 0 on success,
  • 1 if extension is impossible


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

Generated on Mon Nov 8 19:36:41 2010 for ConicBundle by  doxygen 1.5.6