Interface to ConicBundle for the Language C++

Solve $min_{y\in\mathbf{R}^m} f_0(y) + f_1(y) + ... + f_k(y)$ for convex functions f_i, the y-variables may be bounded or box constrained. The most important steps are explained here. More...

Classes

class  ConicBundle::PrimalData
 In Lagrangean relaxation an approximate primal solution can be generated by supplying primal information derived from this abstract class for each epsilon subgradient within ConicBundle::FunctionOracle::evaluate(). More...
class  ConicBundle::PrimalExtender
 Interface for extending PrimalData, e.g., in column generation approaches. More...
class  ConicBundle::PrimalDVector
 If in Lagrangean relaxation primal solutions are in the form of a ConicBundle::DVector, then an approximate primal solution can be generated by supplying primal information of this form for each epsilon subgradient within ConicBundle::FunctionOracle::evaluate(). More...
class  ConicBundle::FunctionObject
 basic function object (abstract class). It serves for using the same interface on distinct oracle types, but is not yet needed in the standard C++ interface. More...
class  ConicBundle::FunctionOracle
 oracle interface (abstract class). For each of your functions, provide a derived class. More...
class  ConicBundle::BundleParameters
 Serves for specifying parameters regarding the construction of the cutting model. More...
class  ConicBundle::CBSolver
 Bundle method solver. More...

Typedefs

typedef std::vector< double > ConicBundle::DVector
 A dense vector of double, arguments and subgradients are specified like this.
typedef std::vector< int > ConicBundle::IVector
 A dense vector of int, index vectors for deleting/reorganizing variables are specified like this.

Variables

const double ConicBundle::CB_plus_infinity
 serves as the value "minus infinity", i.e., all bounds <= this value are set to this value and are regarded as minus infinity
const double ConicBundle::CB_minus_infinity
 serves as the value "plus infinity", i.e., all bounds >= this value are set to this value and are regarded as plus infinity

Detailed Description

Solve $min_{y\in\mathbf{R}^m} f_0(y) + f_1(y) + ... + f_k(y)$ for convex functions f_i, the y-variables may be bounded or box constrained. The most important steps are explained here.

Setting up the Problem, the Functions, and the Main Loop

First create a new problem/solver ConicBundle::CBSolver, let us call it solver for brevity. In invoking the constructor a boolean flag may be set to enforce the use of a minimal bundle model that employs only one common aggregate and one common subgradient for all functions, so basically "no bundle", which may be favorable if fast iterations and/or little memory consumption are essential.

Next, set the dimension of the design variables/argument as well as possible box constraints on these by ConicBundle::CBSolver::init_problem().

Now set up each of your functions f_i as a ConicBundle::FunctionOracle. Via the routine ConicBundle::FunctionOracle::evaluate() you will supply, for a given argument, the function value and a subgradient (=the gradient if the function is differentiable) to the solver. The function evaluate() is the only function that you definitely have to provide, see the miniature example below.

The function oracles have to be added to the solver using the routine ConicBundle::CBSolver::add_function().

Once all functions are added, the optimization process can be started. If you know a good starting point then set it with ConicBundle::CBSolver::set_new_center_point() now, otherwise the method will pick the zero vector or, in the case of box constraints, the point closest to zero as starting point.

Finally, set up a loop that calls ConicBundle::CBSolver::do_descent_step() until ConicBundle::CBSolver::termination_code() is nonzero.

Setting up the Problem, the Functions, and the Main Loop

After the first call to ConicBundle::CBSolver::do_descent_step() you can retrieve, at any time, the current objective value by ConicBundle::CBSolver::get_objval() and the argument leading to this value by ConicBundle::CBSolver::get_center(). For some screen output, use ConicBundle::CBSolver::set_out().

Lagrangean Relaxation, Primal Approximations, and Cutting Planes

If you are optimizing the Lagrange multipliers of a Lagrangean relaxation, you might be interested in getting an approximation to your primal optimal solution. This can be done by specifying in each function for each (epsilon) subgradient the corresponding primal vectors that generate it, see the parameter primal_solutions in ConicBundle::FunctionOracle::evaluate() as a start. Then for each of your functions, you can retrieve the current primal approximation using ConicBundle::CBSolver::get_approximate_primal().

If, in addition, you plan to improve your primal relaxation via cutting planes, that are strongly violated by the current primal approximation, you should have a look at ConicBundle::CBSolver::append_variables(), ConicBundle::FunctionOracle::subgradient_extension() and ConicBundle::CBSolver::reinit_function_model(). If you want to get rid of primal constraints/dual variables, use ConicBundle::CBSolver::get_approximate_slacks() and ConicBundle::CBSolver::delete_variables().

//******************************************************************************
//*       Miniature Example in C++ for Convex Quadratic in Two Variables       * 
//******************************************************************************
#include "CBSolver.hxx"

using namespace std;
using namespace ConicBundle;

// f(x)=x^TAx+b^Tx+c with A=[5 1;1 4], b=[-12;-10], c=3 
class QFunction: public FunctionOracle
{
public:
  QFunction(){}

  int evaluate(const DVector& x, double relprec, 
               double& objective_value,
               DVector&  cut_vals,vector<DVector>&  subgradients,
               vector<PrimalData*>&  primal_solutions,
               PrimalExtender*&)
  {
    /* compute objective */
    objective_value= 5*x[0]*x[0]+2*x[0]*x[1]+4*x[1]*x[1]-12*x[0]-10*x[1]+3;
    /* compute and store one subgradient(=gradient) with two coordinates */
    cut_vals.push_back(objective_value);
    DVector subg(2,0.);
    subg[0]=2*(5*x[0]+x[1])-12;
    subg[1]=2*(x[0]+4*x[1])-10;
    subgradients.push_back(subg);
    return 0;
  }
};

int main(void)
{
  QFunction fun;

  CBSolver solver;         
  solver.init_problem(2);      // 2 variables, no bounds
  solver.add_function(fun);      
  solver.set_out(&cout,1);
 
  do {
    solver.do_descent_step();
  } while (!solver.termination_code());

  solver.print_termination_code(cout);

  DVector x;
  solver.get_center(x);
  cout<<" x[0]="<<x[0]<<" x[1]="<<x[1]<<" objval="<<solver.get_objval()<<endl;

  return 0;
}

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