Bundle method solver. More...

#include <CBSolver.hxx>

Public Member Functions
	CBSolver (std::ostream *out=0, int print_level=0)
	default constructor allows to set output level options from start (see also set_out())

Initialization
void	clear ()
	Clears all data structures and problem information but keeps ouptut settings and algorithmic parameter settings.

void	set_defaults ()
	Sets default values for algorithmic parameters that are not function specific (e.g., relative precision, weight and weight bounds for the augmentedproblem, etc.)

int	init_problem (int dim, const DVector lbounds=0, const DVector ubounds=0)
	Initializes the problem by setting up the design space (the dimension and possible box constraints of the variables) More...

int	add_function (FunctionObject &function)
	Adds a function, typically derived from ConicBundle::FunctionOracle; all functions added must have the same argument dimension. More...

int	set_lower_bound (int i, double lb)
	Sets lower bound for variable i, use ConicBundle::CB_minus_infinity for unbounded from below. More...

int	set_upper_bound (int i, double ub)
	Sets upper bound for variable i, use ConicBundle::CB_plus_infinity for unbounded from below. More...

int	append_variables (int n_append, const DVector lbounds=0, const DVector ubounds=0)
	Append new variables (always in last postions in this order). More...

int	delete_variables (const IVector &delete_indices, IVector &map_to_old)
	Deletes variables corresponding to the specified indices. More...

int	reassign_variables (const IVector &assign_new_from_old)
	Reassigns variables to new index positions by mapping to position i the variable that previously had index assign_new_from_old[i]. More...

Basic Algorithmic Routines and Parameters
int	solve (int maxsteps=0, bool stop_at_descent_steps=false)
	solves or does a prescribed number of iterations More...

int	termination_code () const
	Returns the termination code of the bundle algorithm for the latest descent step. More...

std::ostream &	print_termination_code (std::ostream &out)
	Outputs a text version of termination code, see termination_code(). More...

double	get_objval () const
	Returns the objective value resulting from last descent step (initially undefined). If no problem modification routines were called since then, it is the objective value at the point returned by get_center().

int	get_center (DVector &center) const
	Returns the next center point that was produced by the latest call to solve() (in some problem modification routines the center point may be updated immediately, in others the center point will be corrected automatically directly before starting the next descent step and its values may be infeasible till then). More...

double	get_sgnorm () const
	Returns Euclidean norm of the latest aggregate subgradient.

int	get_subgradient (DVector &subgradient) const
	Returns the latest aggregate subgradient. More...

virtual double	get_candidate_value () const
	Returns the objective value computed in the last step of solve(), independent of whether this was a descent step or a null step (initially undefined). More...

virtual int	get_candidate (DVector &candidate) const
	Returns the last point, the "candidate", at which the function was evaluated in solve(). More...

Advanced Algorithmic Routines and Parameters
int	set_term_relprec (const double term_relprec)
	Sets the relative precision requirements for successful termination (default 1e-5). More...

int	set_new_center_point (const DVector &center_point)
	Set the starting point/center that will be used in the next call to solve(). Each call to this routine causes an immediate evaluation of all oracles. More...

int	get_function_status (const FunctionObject &function) const
	Returns the return value of the latest evaluation call to this function.

int	get_approximate_slacks (DVector &center) const
	Returns the multipliers for the box constraints on the design variables; in Lagrangean relaxation they may be interpreted as primal slacks for inequality constraints. More...

const PrimalData *	get_approximate_primal (const FunctionObject &function) const
	returns the current approximate primal solution corresponding to the aggregate subgradient of the specified function. More...

const PrimalData *	get_center_primal (const FunctionObject &function) const
	Returns the primal solution corresponding to the best epsilon subgradient returned in the evaluation of the specified function at the current center point. If no primal data is availalbe, the function returns NULL. More...

const PrimalData *	get_candidate_primal (const FunctionObject &function) const
	Returns the primal solution corresponding to the best epsilon subgradient returned in the evaluation of the specified function at the point get_candidate. If no primal data is availalbe, the function returns NULL. More...

int	set_max_modelsize (const FunctionObject &function, int max_modelsize)
	Sets the maximum number of subgradients used in forming the cutting model of the specified function. More...

int	set_max_bundlesize (const FunctionObject &function, int max_bundlesize)
	Sets the maximum number of subgradients stored for use in forming the model or determining scaling information, it must be as least as large as max_modelsize (and is increased to this if not) More...

int	set_bundle_parameters (const FunctionObject &function, const BundleParameters &params)
	Sets the maximum bundlesize and the maximum number of new subgradients added in a bundle update of the cutting model for the specified function. The meaning of this routine may differ from standard for predefined special functions with special bundle types. More...

const BundleParameters *	get_bundle_parameters (const FunctionObject &function) const
	Retrieves current bundle parameters (not the actual size in use!) as set for the cutting model of the specified function. More...

int	reinit_function_model (const FunctionObject &function)
	Clears cutting model, subgradients and stored function values for the specified function. More...

int	call_primal_extender (const FunctionObject &function, PrimalExtender &primal_extender)
	Asks function to call primal_extender for each of its primal objects (see also FunctionOracle::evaluate() ) More...

double	get_last_weight () const
	Returns the current weight for the quadratic term in the augmented subproblem (may be interpreted as 1./step_size or 1./trustregion-radius).

int	set_next_weight (const double weight)
	Sets the weight (>0) to be used in the quadratic term of the next augmented subproblem (may be interpreted as 1./step_size or 1./trustregion-radius). More...

int	set_min_weight (const double min_weight)
	Sets a lower bound on the weight for the quadratic term of the augmented subproblem. More...

int	set_max_weight (const double max_weight)
	Sets an upper bound on the weight for the quadratic term of the augmented subproblem. More...

virtual int	set_variable_metric (int do_scaling)
	Use a scaling heuristic or switch off scaling alltogether. (the scaling heuristic resets the quadratic term to some diagonal matrix, switching it off resets the diagonal term to the identity) More...

virtual void	set_active_bounds_fixing (bool allow_fixing)
	If set to true (the default is false), some variables will be fixed automatically to the center value if their bounds are strongly active (i.e., the corresponding multipliers are big). More...

virtual void	clear_fail_counts (void)
	clears all fail counts on numerical function oder model failures, may be useful if this caused premature termination. More...

virtual void	set_eval_limit (int eval_limit)
	Sets an upper bound on the number of calls to the oracle (use negative numbers for no limit). More...

virtual void	set_inner_update_limit (int update_limit)
	Set an upper bound on the number of inner updates for the cutting model with primal slacks within one null step (use negative numbers for no limit). More...

Look Up Basic Paramaters (dimension, number of functions, ...)
int	get_dim ()
	Returns the current dimension of the design space/argument or -1 if no dimension is set.

int	get_n_functions ()
	Returns the current number of functions in the problem.

int	get_fixed_active_bounds (IVector &fixed_active_bounds) const
	Returns the indicator vector of variables temporarily fixed to the center value due to significantly positive multipliers for the box constraints. More...

Output
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...

Private Member Functions
	CBSolver (const CBSolver &)
	not available, blocked deliberately

CBSolver &	operator= (const CBSolver &)
	not available, blocked deliberately

Private Attributes
MatrixCBSolver *	solver
	pointer to internal solver

Detailed Description

Bundle method solver.

Minimizes the sum of convex functions that are given via ConicBundle::FunctionOracle interfaces, see the text explaining the C++ interface for a quick overview.

It provides special support for Lagrangean relaxation by generating primal approximate solutions if such information is provided in the function oracles.

Based on these primal approximations it is also possible to implement cutting plane schemes. Routines for adding and deleting corresponding dual variables as well as a framework for extending subgradients in order not to loose the cutting model are available.

Member Function Documentation

◆ add_function()

int ConicBundle::CBSolver::add_function ( FunctionObject & function )

Adds a function, typically derived from ConicBundle::FunctionOracle; all functions added must have the same argument dimension.

Besides the standard ConicBundle::FunctionOracle the interface only accepts a few other prespecified derivations of the class FunctionObject that come along with the CH_Matrix_Classes interface (e.g. for semidefinite and second order cones). Functions not derived from these will fail to be added and return a value !=0.

Returns

0 on success
!= 0 otherwise

◆ append_variables()

int ConicBundle::CBSolver::append_variables	(	int	n_append,
		const DVector *	lbounds = `0`,
		const DVector *	ubounds = `0`
	)

Append new variables (always in last postions in this order).

If 0 is feasible for the new coordinates then this is selected as starting value for the new coordinates; otherwise, the number closest to zero is used. If all new coordinates can be set to zero then it is assumed that for an existing center point the function values need not be recomputed (this is e.g. the case in Lagrangean relaxation; if this is not correct call reinit_function_model() below). Otherwise the old function values will be marked as outdated and will be recomputed at the next call to e.g. solve().

Attention: Be sure to update your objective functions so that they can handle the new variables before you call this and any further ConicBundle routines that require function evaluations. Also, these operations may lead to inavailability of certain other data such as subgradients and primal approximations.

Parameters

[in]	n_append	(int) number of variables to append (always in last position in the same order)
[in]	lbounds	(DVector*) If NULL, all appended variables are considered unbounded below, otherwise lowerb[i] gives the minimum feasible value for variable y[i], use ConicBundle::CB_minus_infinity for unbounded below.
[in]	ubounds	(DVector*) If NULL, all appended variables are considered unbounded above, otherwise upperb[i] gives the maximum feasible value for variable y[i], use ConicBundle::CB_plus_infinity for unbounded above.

Returns

0 on success
!= 0 otherwise

◆ call_primal_extender()

int ConicBundle::CBSolver::call_primal_extender	(	const FunctionObject &	function,
		PrimalExtender &	primal_extender
	)

Asks function to call primal_extender for each of its primal objects (see also FunctionOracle::evaluate() )

If the function is the Lagrangian dual of a primal problem and primal_data returned previous calls to the oracle has now to be updated due to changes in the primal problem – e.g., this may happen in column generation – the call causes updates of all internally stored primal_data objects by calling PrimalExtender::extend on each of these.

Parameters

[in]	function	(const FunctionObject&) the function added in add_function()
[in]	primal_extender	(PrimalExtender&) the object holding the extension function for primal_data

Returns

0 on success
1 if for this function it is not possible to use a primal_extender
2 if the primal_extender would be applicable but there is no primal_data

◆ clear_fail_counts()

virtual void ConicBundle::CBSolver::clear_fail_counts ( void )

virtual

clears all fail counts on numerical function oder model failures, may be useful if this caused premature termination.

◆ delete_variables()

int ConicBundle::CBSolver::delete_variables	(	const IVector &	delete_indices,
		IVector &	map_to_old
	)

Deletes variables corresponding to the specified indices.

The indices of the remaining variables are reassigned so that they are consecutive again, the routine returns in map_to_old a vector giving for each new index of these remaining variables the old coordinate.

If all of the deleted variables are zero, function values are assumed to remain correct (if this is not so, call reinit_function_model() below) Otherwise the old function values will be marked as outdated and will be recomputed at the next call to e.g. solve().

Attention: Be sure to update your objective functions so that they can handle the new variables before you call any further ConicBundle routines that require function evaluations. Also, these operations may lead to inavailability of certain other data such as subgradients and primal approximations.

Parameters

[in]	delete_indices	(const IVector&) the entries delete_indices[i] specify the indices of the variables to be deleted
[out]	map_to_old	(IVector&) after the call, element map_to_old[i] gives the old index (before the call) of the variable that now has index position i.

Returns

0 on success
!= 0 otherwise

◆ get_approximate_primal()

const PrimalData* ConicBundle::CBSolver::get_approximate_primal ( const FunctionObject & function ) const

returns the current approximate primal solution corresponding to the aggregate subgradient of the specified function.

PrimalData solutions must have been supplied in all previous calls to evaluate; In this case it returns the current approximate primal solution aggregated alongside with the aggregate subgradient. A primal solution may not be available after addition of constraints, if extension of the aggregate subgradient to the new coordinates failed. If no primal data is availalbe, the function returns NULL.

Returns

pointer to the primal data of the aggregate of this function object
0 if no primal is available

◆ get_approximate_slacks()

int ConicBundle::CBSolver::get_approximate_slacks ( DVector & center ) const

Returns the multipliers for the box constraints on the design variables; in Lagrangean relaxation they may be interpreted as primal slacks for inequality constraints.

Returns

0 on success
!= 0 otherwise

◆ get_bundle_parameters()

const BundleParameters* ConicBundle::CBSolver::get_bundle_parameters ( const FunctionObject & function ) const

Retrieves current bundle parameters (not the actual size in use!) as set for the cutting model of the specified function.

This may differ for predefined special functions with derived BundleParameter classes.

Parameters

[in] function (const FunctionObject&) the function added in add_function()

Returns

0 if no such function or such data is available
otherwise a pointer to the BundleParameters

◆ get_candidate()

virtual int ConicBundle::CBSolver::get_candidate ( DVector & candidate ) const

virtual

Returns the last point, the "candidate", at which the function was evaluated in solve().

If this evaluation lead to a descent step, it is the same point as in get_center().

Returns

0 on success
!= 0 otherwise

◆ get_candidate_primal()

const PrimalData* ConicBundle::CBSolver::get_candidate_primal ( const FunctionObject & function ) const

Returns the primal solution corresponding to the best epsilon subgradient returned in the evaluation of the specified function at the point get_candidate. If no primal data is availalbe, the function returns NULL.

Returns

pointer to the primal data of the minorant returned on evaluation of this function object at the current candidate
0 if no primal is available

◆ get_candidate_value()

virtual double ConicBundle::CBSolver::get_candidate_value ( ) const

virtual

Returns the objective value computed in the last step of solve(), independent of whether this was a descent step or a null step (initially undefined).

If no problem modification routines were called since then, it is the objective value at the point returned by get_candidate(). If this last evaluation led to a descent step, then it is the same value as in get_objval().

◆ get_center()

int ConicBundle::CBSolver::get_center ( DVector & center ) const

Returns the next center point that was produced by the latest call to solve() (in some problem modification routines the center point may be updated immediately, in others the center point will be corrected automatically directly before starting the next descent step and its values may be infeasible till then).

Returns

0 on success
!= 0 otherwise

◆ get_center_primal()

const PrimalData* ConicBundle::CBSolver::get_center_primal ( const FunctionObject & function ) const

Returns the primal solution corresponding to the best epsilon subgradient returned in the evaluation of the specified function at the current center point. If no primal data is availalbe, the function returns NULL.

Returns

pointer to the primal data of the minorant returned on evaluation of this function object at the current center
0 if no primal is available

◆ get_fixed_active_bounds()

int ConicBundle::CBSolver::get_fixed_active_bounds ( IVector & fixed_active_bounds ) const

Returns the indicator vector of variables temporarily fixed to the center value due to significantly positive multipliers for the box constraints.

Such a fixing indicates that the corresponding variables would like to stay at their bounds. There will be nonzero entries only if set_active_bounds_fixing() is switched on.

◆ get_subgradient()

int ConicBundle::CBSolver::get_subgradient ( DVector & subgradient ) const

Returns the latest aggregate subgradient.

Returns

0 on success
!= 0 otherwise

◆ init_problem()

int ConicBundle::CBSolver::init_problem	(	int	dim,
		const DVector *	lbounds = `0`,
		const DVector *	ubounds = `0`
	)

Initializes the problem by setting up the design space (the dimension and possible box constraints of the variables)

Clears all data structures and sets the dimension @ m for a new problem. for solving min_{y in R^m} f_0(y) + f_1(y) + ... Box constraints may be specified for y. (The functions f_i must be added by add_function()).

Lower and/or upper bounds must be speicified for all variables or for none of them. To specify no bounds at all, give Null pointers. Otherwise use ConicBundle::CB_minus_infinity for unbounded below and ConicBundle::CB_plus_infinity for unbounded above. For NULL pointers, unbounded will be used as default for all variables. Specifying bounds selectively is also possible by set_lower_bound() or set_upper_bound().

Parameters

[in]	dim	(int) the dimension of the argument/design space/the number of Lagrange multipliers
[in]	lbounds	(const DVector*) If NULL, all variables are considered unbounded below, otherwise lowerb[i] gives the minimum feasible value for variable y[i], use ConicBundle::CB_minus_infinity for unbounded below.
[in]	ubounds	(const DVector*) If NULL, all variables are considered unbounded above, otherwise upperb[i] gives the maximum feasible value for variable y[i], use ConicBundle::CB_plus_infinity for unbounded above.

Returns

0 on success
!= 0 otherwise

◆ print_termination_code()

std::ostream& ConicBundle::CBSolver::print_termination_code ( std::ostream & out )

Outputs a text version of termination code, see termination_code().

Returns

0 on success
!= 0 otherwise

◆ reassign_variables()

int ConicBundle::CBSolver::reassign_variables ( const IVector & assign_new_from_old )

Reassigns variables to new index positions by mapping to position i the variable that previously had index assign_new_from_old[i].

Old variables, that are not mapped to any position will be deleted. It is allowed to generate several copies of old variables.

If all of the deleted variables as well as new multiple copies are zero, function values are assumed to remain correct (if this is not so, call reinit_function_model() below). Otherwise the old function values will be marked as outdated and will be recomputed at the next call to e.g. solve().

Attention: Be sure to update your objective functions so that they can handle the new variables before you call any further ConicBundle routines that require function evaluations. Also, these operations may lead to inavailability of certain other data such as subgradients and primal approximations.

Parameters

[in] assign_new_from_old (const IVector&) entry assign_new_from_old[i] specifies the old index of the variable, that has to be copied to index position i.

Returns

0 on success
!= 0 otherwise

◆ reinit_function_model()

int ConicBundle::CBSolver::reinit_function_model ( const FunctionObject & function )

Clears cutting model, subgradients and stored function values for the specified function.

This has to be called whenever the specified function was modified so that the old subgradients and/or primal generators are no longer valid.

Parameters

[in] function (const FunctionObject&) the function added in add_function()

Returns

0 on success
!= 0 otherwise

◆ set_active_bounds_fixing()

virtual void ConicBundle::CBSolver::set_active_bounds_fixing ( bool allow_fixing )

virtual

If set to true (the default is false), some variables will be fixed automatically to the center value if their bounds are strongly active (i.e., the corresponding multipliers are big).

The coordinates to be fixed are redetermined in each call following a descent step or a change of the function. An indicator vector of the variables fixed in the last call can be obtained via the routine get_fixed_active_bounds().

Setting this value to true might improve the performance of the algorithm in some instances but there is no convergence theory. It might be particularly helpful within Lagrangian relaxation if a primal cutting plane approach is used and non-tight inequalities should be eliminated quickly (fixing then indicates large primal slack values).

Parameters

[in] allow_fixing (bool)

◆ set_bundle_parameters()

int ConicBundle::CBSolver::set_bundle_parameters	(	const FunctionObject &	function,
		const BundleParameters &	params
	)

Sets the maximum bundlesize and the maximum number of new subgradients added in a bundle update of the cutting model for the specified function. The meaning of this routine may differ from standard for predefined special functions with special bundle types.

Parameters

[in]	function	(const FunctionObject&) the function added in add_function()
[in]	params	(const BundleParameters&) some update parameters for the cutting model, see e.g. ConicBundle::BundleParameters

Returns

0 on success
!= 0 otherwise

◆ set_eval_limit()

virtual void ConicBundle::CBSolver::set_eval_limit ( int eval_limit )

virtual

Sets an upper bound on the number of calls to the oracle (use negative numbers for no limit).

If this number is reached, the algorithm will terminate independently of whether the last step was a descent or a null step. A negative number will be interepreted as no limit.

Parameters

[in] eval_limit (int)

◆ set_inner_update_limit()

virtual void ConicBundle::CBSolver::set_inner_update_limit ( int update_limit )

virtual

Set an upper bound on the number of inner updates for the cutting model with primal slacks within one null step (use negative numbers for no limit).

A negative number will be interepreted as no limit, i.e., the updates will be done till a certain precision of the cutting model is achieved.

Parameters

[in] update_limit (int)

◆ set_lower_bound()

int ConicBundle::CBSolver::set_lower_bound	(	int	i,
		double	lb
	)

Sets lower bound for variable i, use ConicBundle::CB_minus_infinity for unbounded from below.

The algorithm may have to adapt the center point aftwards. In this case the old function values will be marked as outdated and will be recomputed at the next call to e.g. solve().

Returns

0 on success
!= 0 otherwise

◆ set_max_bundlesize()

int ConicBundle::CBSolver::set_max_bundlesize	(	const FunctionObject &	function,
		int	max_bundlesize
	)

Sets the maximum number of subgradients stored for use in forming the model or determining scaling information, it must be as least as large as max_modelsize (and is increased to this if not)

The meaning of this routine may differ from standard for predefined special functions with special bundle types.

Parameters

[in]	function	(const FunctionObject&) the function added in add_function()
[in]	max_bundlesize	(int) maximum number of new epsilon subgradients to be used in bundle updates

Returns

0 on success
!= 0 otherwise

◆ set_max_modelsize()

int ConicBundle::CBSolver::set_max_modelsize	(	const FunctionObject &	function,
		int	max_modelsize
	)

Sets the maximum number of subgradients used in forming the cutting model of the specified function.

Quite often a very small model, e.g., 2, yields very fast iterations and good progress in time (sometimes at the cost of more evaluations). By limited numerical experience, a significant reduction in the number of evaluations can only be expected if the bundle is large enough to wrap the function rather tightly. Quite frequently, unfortunately, this entails that solving the quadratic subproblems is more expensive than function evaluation.

The meaning of this routine may differ from standard for predefined special functions with special bundle types.

Parameters

[in]	function	(const FunctionObject&) the function added in add_function()
[in]	max_modelsize	(int) maximum number of subgradients to be used in forming the cutting model

Returns

0 on success
!= 0 otherwise

◆ set_max_weight()

int ConicBundle::CBSolver::set_max_weight ( const double max_weight )

Sets an upper bound on the weight for the quadratic term of the augmented subproblem.

Nonpositive values indicate no bound. The new value shows its effect only at first dynamic change of the weight.

Parameters

[in] max_weight (double)

Returns

0 on success
!= 0 otherwise

◆ set_min_weight()

int ConicBundle::CBSolver::set_min_weight ( const double min_weight )

Sets a lower bound on the weight for the quadratic term of the augmented subproblem.

Nonpositive values indicate no bound. The new value shows its effect only at first dynamic change of the weight.

Parameters

[in] min_weight (double)

Returns

0 on success
!= 0 otherwise

◆ set_new_center_point()

int ConicBundle::CBSolver::set_new_center_point ( const DVector & center_point )

Set the starting point/center that will be used in the next call to solve(). Each call to this routine causes an immediate evaluation of all oracles.

Returns

0 on success
!= 0 otherwise

◆ set_next_weight()

int ConicBundle::CBSolver::set_next_weight ( const double weight )

Sets the weight (>0) to be used in the quadratic term of the next augmented subproblem (may be interpreted as 1./step_size or 1./trustregion-radius).

Independent of whether the weight violates current min- and max-bounds set in set_min_weight() and set_max_weight(), the next model will be computed for this value. Thereafter, however, it will be updated as usual; in particular, it may be truncated by min and max bounds immediately after the first subproblem.

In order to guarantee a constant weight (e.g. 1 is frequently a reasonable choice if the automatic default heuristic performs poorly), set the min and max bounds to the same value, too.

Parameters

[in] weight (double)

Returns

0 on success
!= 0 otherwise

◆ set_out()

void ConicBundle::CBSolver::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)

Parameters

[in]	out	(ostream) direct all output to (out). If out==NULL, there will be no output at all.
[in]	print_level	(int)

Output levels for print_level:

0 ... no output except for errors and warnings
1 ... line summary after each descent step
>1 ... undocumented and increasingly detailed log information. These higher levels should only be used if requested for debugging purposes.

Example for level 1:

00:00:00.00 endit  1   1   1   563.    563.  39041.188  39043.162
00:00:00.00 endit  2   2   2   563.    559.  38488.165  38490.200
00:00:00.00 endit  3   3   3   56.3    555.  33014.533  33211.856
00:00:00.00 endit  4   4   4   5.63    517. -14306.459  2738.0343
00:00:00.00 endit  5   5   5   4.04    148. -2692.1131  2.2150883
00:00:00.00 endit  6   6   6   4.01    1.29  1.7908952  2.0000581
00:00:00.00 endit  7   7   7   3.95  0.0213  1.9999387  2.0000000
00:00:00.00 _endit  8   8   8   3.95 2.94e-05  2.0000000  2.0000000

Column 1      2     3   4   5    6       7       8          9

Column 1: computation time in hh:mm:ss.dd,
Column 2: "endit" is convenient for grep and stands for "end of iteration". Iterations with termination_code()!=0 are marked with "_endit".
Column 3: number of descent steps
Column 4: number of descent and null steps. Up to initialization calls and reevaluations, this is the number of evaluation calls to the function oracles from within the bundle method. In the example all calls led to descent steps.
Column 5: number of innermost iterations. It differs from column 5 only in the case of variables with bounds in which case it gives the number of updates of the multipliers for the bounds (or primal slacks in Lagrangean relaxation). Exceedingly high numbers in this column indicate that some variables are constantly at their bounds and it might be possible to improve convergence by deleting them (i.e. set them as constants to this bound and remove the variable).
Column 6: the weight of the quadratic term in the augmented problem.
Column 7: the norm of the aggregate subgradient. If it is small, say below 0.1, then mostly this is good indication that the objective value is close to optimal.
Column 8: the value of the cutting model in the last candidate point. It is always a lower bound on the true function value in this point
Column 9: the objective value in the latest point that led to a descent step, i.e., the point returend by get_center(). Whenever termination_code() returns 0 this is also the objective value of the latest evaluation call to the function oracles and the value in the center point of the next iteration.

◆ set_term_relprec()

int ConicBundle::CBSolver::set_term_relprec ( const double term_relprec )

Sets the relative precision requirements for successful termination (default 1e-5).

Parameters

[in] term_relprec (double) The algorithm stops with termination code 1, if predicted progress for the next step is less than term_relprec times absolute function value plus one.

Returns

0 on success
!= 0 otherwise

◆ set_upper_bound()

int ConicBundle::CBSolver::set_upper_bound	(	int	i,
		double	ub
	)

Sets upper bound for variable i, use ConicBundle::CB_plus_infinity for unbounded from below.

The algorithm may have to adapt the center point aftwards. In this case the old function values will be marked as outdated and will be recomputed at the next call to e.g. solve().

Returns

0 on success
!= 0 otherwise

◆ set_variable_metric()

virtual int ConicBundle::CBSolver::set_variable_metric ( int do_scaling )

virtual

Use a scaling heuristic or switch off scaling alltogether. (the scaling heuristic resets the quadratic term to some diagonal matrix, switching it off resets the diagonal term to the identity)

Parameters

[in]

do_scaling

(int)

0 switch off the scaling heuristic
1 use a diagonal scaling heuristic
2 use a diagonal scaling heuristic combined with one for the bounds

Returns

0 on success
!= 0 otherwise

◆ solve()

int ConicBundle::CBSolver::solve	(	int	maxsteps = `0`,
		bool	stop_at_descent_steps = `false`
	)

solves or does a prescribed number of iterations

Bundle methods solve a problem by a sequence of so called descent steps that actually bring progress by moving from the current "center point" to a new center with better objective. A descent step may consist of several function evaluations (null steps), that lead to no immediate progress but mainly improve a cutting model of the objective function close to the current center point. A minimizer to the model is accepted as descent step if the function value at this point satisfies a sufficient decrease criterion in comparison to the decrease predicted by the model. Having found a descent step, the next center is automatically shifted to this successful candidate. Termination criteria may stop the process of seeking for a descent step, in which case the current center is kept and the routine termination_code() returns the termination code.

Restarting, after each descent step, the bundle method from scratch with the new center as starting point does not endanger convergence. Therefore, a descent step is the smallest unit, after which user interaction can take place safely. To allow this there is a flag stop_at_descent_steps that will cause the code to return after the next descent step.

If you know what your are doing, you may also use the input parameter maxsteps to force the algorithm to return after at most maxsteps null steps. Calling solve() again without any intermediate problem configurations will then simply continue the process where it stopped and convergence is save. During null steps one may not decrease the weight or delete nonzero variables of the center or the current candidate!

In a Lagrangean relaxation cutting plane approach one may want to separate and enlarge the dimension after a certain number of null steps. In this case the code will try to preserve the model, given appropriate subgradient extension routines have been provided. If the model cannot be extended, it has to be discarded (if subgradient extension is not successful this is done automatically), and the algorithm will be restarted from the current center point.

Parameters

[in]	maxsteps	(int) if maxsteps>0 the code returns after at most so many null steps
[in]	stop_at_descent_steps	(int) if true the code also returns whenever a descent step occured

Returns

0 on success
!= 0 otherwise

◆ termination_code()

int ConicBundle::CBSolver::termination_code ( ) const

Returns the termination code of the bundle algorithm for the latest descent step.

For resetting all counters relevant for termination see clear_fail_counts() .

Returns

0 : Not terminated. (Continue with the next solve())
1 : Relative precision criterion satisfied. (See set_term_relprec())
2 : Timelimit exceeded. (Currently the C interface does not offer a timelimit.)
4 : Maximum number of function reevaluations exceeded. (Indicates that there is a problem with one of the function oracles that seems to deliver no valid upper bounds on the true function value for descent steps)
8 : Maximum number of quadratic subproblem failures exceeded. (Indicates that the numerical limits of the inner quadratic programming solver are reached, no further progress expected)
16 : maximum number of model evaluation failures exceeded (Indicates that the numerical limits of the setup of the subproblem are reached, no further progress expected)
32 : maximum number of failures to increase the augmented model value exceeded (Indicates that the numerical limits of the interplay between subproblem and quadratic programming solver are reached, no further progress expected)
- 64 : maximum number of oracle calls (function evaluations) exceeded, see set_eval_limit()
- 128 : maximum number of oracle failures exceeded. This refers to function evaluations that terminate with insufficient precision but still provide a new approximate subgradient. A failure typically indicates numerical difficulties with the precision requirements. (Currently the interface does not allow to manipulate the limit, it is set to 10)

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

CBSolver.hxx

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Function Documentation

◆ add_function()

◆ append_variables()

◆ call_primal_extender()

◆ clear_fail_counts()

◆ delete_variables()

◆ get_approximate_primal()

◆ get_approximate_slacks()

◆ get_bundle_parameters()

◆ get_candidate()

◆ get_candidate_primal()

◆ get_candidate_value()

◆ get_center()

◆ get_center_primal()

◆ get_fixed_active_bounds()

◆ get_subgradient()

◆ init_problem()

◆ print_termination_code()

◆ reassign_variables()

◆ reinit_function_model()

◆ set_active_bounds_fixing()

◆ set_bundle_parameters()

◆ set_eval_limit()

◆ set_inner_update_limit()

◆ set_lower_bound()

◆ set_max_bundlesize()

◆ set_max_modelsize()

◆ set_max_weight()

◆ set_min_weight()

◆ set_new_center_point()

◆ set_next_weight()

◆ set_out()

◆ set_term_relprec()

◆ set_upper_bound()

◆ set_variable_metric()

◆ solve()

◆ termination_code()