CutPlane Class Reference

#include <CutPlane.h>

Inheritance diagram for CutPlane:

Public Member Functions
cLMRow	ReadSol (cIndex_Set &I, Index &D)
	! void ReSetAlg( unsigned char RstLvl = 0 ) {}
cLMRow	ReadBestSol (cIndex_Set &I, Index &D)
HpNum	ReadFiVal (cIndex wFi=Inf< Index >())
HpNum	ReadBestFiVal (cIndex wFi=Inf< Index >())
bool	IsOptimal (HpNum eps=0) const
cHpRow	ReadMult (cIndex_Set &I, Index &D, cIndex wFi=Inf< Index >())
HpNum	ReadLBMult (cIndex wFi=Inf< Index >())
Constructor
	CutPlane (std::istream *iStrm=0)
Other initializations
void	SetOsiSolver (OsiSolverInterface *osi=0)
	Sets the OsiSolver to be used by CutPlane to solve the RMP.
void	SetRadius (LMNum rad=Inf< LMNum >())
void	SetFiOracle (FiOracle *Fi=0)
void	SetLambda (cLMRow tLambda=0)
void	KeepBestLambda (const bool KBL=true)
void	SetNDOLog (ostream *outs=0, const char lvl=0)
Solving the problem
NDOStatus	Solve (void)
Adding / removing / changing data
void	AddVariables (Index NNwVrs, cLMRow IVs=0)
void	RemoveVariables (cIndex_Set whch=0, Index hwmny=0)
void	ChgFiV (cIndex wFi=Inf< Index >())
void	ChgSbG (cIndex strt=0, Index stp=Inf< Index >(), cIndex wFi=Inf< Index >())
Destructor
virtual	~CutPlane ()
	Destructor. It must be virtual.
Public Member Functions inherited from NDOSolver
	NDOSolver (std::istream *iStrm=0)
virtual void	SetPar (const int wp, const int value)
virtual void	SetPar (const int wp, cHpNum value)
virtual void	SetNDOTime (const bool TimeIt=true)
virtual void	ReSetAlg (unsigned char RstLvl=0)
Index	FiEval (void) const
Index	GiEval (void) const
Index	NrCalls (void) const
Index	NrIter (void) const
void	NDOTime (double &t_us, double &t_ss)
double	NDOTime (void)
Index	GetNumVar (void) const
virtual void	GetPar (const int wp, int &value)
virtual void	GetPar (const int wp, HpNum &value)
virtual	~NDOSolver ()

Private Member Functions
void	FiAndGi (void)
Index	DelRMPRows (HpNum lim)
void	OutRsts (void)
void	MemDealloc (void)

Private Attributes
Index	NumNames
HpNum	PurgeRows
Index	PurgeInvl
Index	HeurSubGU
Index	HeurSubGF
Index	HeurInvl
Index	KpPrimals
Index	PrintInvl
Index	MaxNumVar
LMRow	Lambda
LMRow	BestLambda
Index_Set	Base
Index	BaseSize
bool	KpBstL
HpRow	FiLambda
HpRow	BestFiLambda
HpNum	AFiLambda
HpNum	ABestFiLambda
SgRow	Gi
OsiSolverInterface *	OsiS
HpNum	AValueRMP
HpRow	ValueRMP
Index	RowsAdded
Index	MaxNRows
HpNum	Gap
HpNum	LowerBound
bool	TrueLB
bool	loptimal
Index_Set	EmptyNames
Index_Set	FullNames
Index_Set	SubPNames
SIndex	LastFull
Index	FirstEmpty
Index	AllocNumber

Additional Inherited Members
Public Types inherited from NDOSolver
enum	NDOParam {   kMaxItr = 0 , kMaxTme , ktStar , kEpsLin ,   kEInit , kEFnal , kEDcrs , kEStps ,   kLastNDOParam }
enum	NDOStatus {   kOK = 0 , kUnbndd , kUnfsbl , kStopped ,   kLwPrcsn , kStpIter , kStpTime , kError }
Protected Attributes inherited from NDOSolver
FiOracle *	Oracle
	(pointer to) the oracle for Fi
Index	MaxIter
	maximum number of iterations
HpNum	MaxTime
	maximum time (in seconds) for each call to Solve()
HpNum	tStar
	optimality related parameter: "scaling" of Fi
HpNum	EpsLin
	optimality related parameter: relative precision
HpNum	EInit
	precision-related parameter: initial precision
HpNum	EFnal
	precision-related parameter: final precision
HpNum	EDcrs
	precision-related parameter: rate of decrease
int	EStps
	precision-related parameter: number of steps
NDOStatus	Result
	result of the latest call to Solve()
Index	NumVar
	(current) number of variables
Index	NrFi
	number of components of Fi()
Index	SCalls
	nuber of calls to Solve() (the current included)
Index	ParIter
	nuber of iterations in this run
Index	FiEvaltns
	total number of Fi() calls
Index	GiEvaltns
	total number of Gi() calls
ostream *	NDOLog
	the output stream object for log purposes
char	NDOLLvl
	the "level of verbosity" of the log
OPTtimers *	NDOt
	OPTtimer for timing purposes.

Detailed Description

This class implements Kelley's Cutting Plane method for minimization of a convex function Fi() (possibly, the sum of k convex functions) over box constraints. At each step, a Restricted Master Problem (RMP) is constructed that provides a valid lower bound on the minimum value of the function using all (or part of) the first-prder information found so far, the RMP is solved and the function is evaluated in the minimum, until the gap betwen the RMP solution and the Fi solution is less than the required precision.

This implementation very partially follows the NDOSolver interface for "general" NonDifferentiable Optimization solvers, in the following sense:

1) Does not implement a "Phase 0", meaning that it requires the RMP to be bounded below, either by box constraints, or by the subgradients fetched at the first call, or at least by any crude but finite lower bound on the minimum of Fi(). 2) Does not support more complicated constraints set than boxes (although it would be very simple). 3) Does not correctly handle adding/removing variables etc. 4) Does not correctly handle functions Fi() that are only "approximately" computed.

Constructor & Destructor Documentation

CutPlane()

CutPlane

(

std::istream *

iStrm = 0

)

Constructor of the class.

The parameter ‘iStrm’, if provided, is taken as a pointer to a istream from which the algorithmic parameters for the Cutting plane algorithm are sequentially read in the following order. Each parameter must be placed at the beginning of a separate line, max 255 carachters long, with all the rest of the line up to the first newline carachter '
' (apart from a separating whitespace) being available for comments. Any line whose first carachter is '#' and any blank line is ignored. If 0 is passed, the file ends before reaching a given parameter, or some parameter is in the wrong format, each non-specified parameter is given a default value, shown in [] below.

Note that ‘iStrm’ is passed to the constructor of NDOSolver [see NDOSolver.h], which reads the general algorithmic parameters out of it; since the constructor of the CutPlane class is executed after the one of NDOSolver, the following parameters specific for the CutPlane have to be found in the stream after those of the base class.

• Index NumNames [100] number of items (re)allocated each time it is needed.
• HpNum PurgeRows [-1] Purge (delete) rows options: < 0 never purge rows; = 0 purge rows with slack greater than gap; > 0 purge rows with slack greater than gap * <this>.
• Index PurgeInvl [5] controls how often rows are purged.
• Index HeurSubGU [1] number of subgradients asked to the FiOracle, at every iteration and for every Fi-component, when the RMP is "artificially" bounded.
• Index HeurSubGF [1] number of subgradients asked to the FiOracle, every HeurInvl [see below] and for every Fi-component, when the RMP is "naturally" bounded.
• Index HeurInvl [30] how often "extra" subgradients are asked to the FiOracle, for every Fi-component, when the RMP is "naturally" bounded.
• Index KpPrimals [0] if == 0, do not care for subgradient "names".
• Index PrintInvl [50] how often log information is printed.

Member Function Documentation

AddVariables()

void AddVariables ( Index NNwVrs, cLMRow IVs = 0 )

virtual

Adds ‘NNwVrs’ new variables to the NDO problem. The new variables are added at the end of the current variable set, i.e., their "names" will be set to NumVar , ... , NumVar + NNwVrs - 1 (where ‘NumVar’ means "the number of variables *before* the call"). The total number of variables after the call will be < NumVar + NNwVrs when NumVar + NNwVrs > FiOracle::GetMaxNumVar() [see FiOracle.h].

IVs is a NNwVrs-vector containing the initial values for the newly created variables; IVs == 0 means that all the initial values are 0.

After a call to this method, a different function, on a different variable space, has to be minimized. Of course, the two functions must not be unrelated to one another; more specifically, it is required that the new function Fi( Lambda , LambdaNew ) is identical to the old function Fi( Lambda ) when restricted to the old space, i.e. that

Fi( Lambda , 0 ) = Fi( Lambda ) for all Lambda.

This implies, for instance, that all the previously collected subgradients are still subgradients for the restriction of the new Fi() to the subspace where all the new variables are zero. We also require that the every subgradient of the old Fi() can be extended to a subgradient of the new Fi() by just "filling in" the entries corresponding to the new variables with proper values (this is always possible e.g. for polyhedral functions). In other words, if the linear function

L( Lambda ) = G * Lambda + a

is known to minorize the old Fi(), then there must exist NewG such that

L( Lambda , LambdaNew ) = G * Lambda + NewG * LambdaNew + a

minorizes the new Fi(). Even better than that, the "linearization error" of L() at any point Lambda

Fi( Lambda ) - L( Lambda ) >= 0

is identical to the linearization error of the new L() at [ Lambda , 0 ]

Fi( Lambda , 0 ) - L( Lambda , 0 ) >= 0.

Then, the NDOSolver can use GetGi() [see FiOracle.h] to retrieve the new entries NewG for the newly created variables of the items "recorded" in the FiOracle, if it needs so, while all the already fetched information remains valid. Note that, if IVs == 0, the value of the function in the new point [ Lambda , 0 ] is also known.

Therefore, a call to this method assumes that the FiOracle already knows about the new set of variables to be created. In particular, the NDOSolver can use GetGi() as outlined above, and it can also use GetUB() and GetUC() [see FiOracle.h] to retrieve the lower and upper bounds on the variables; also, the NDOSolver can assume that, when the method is called, Oracle->GetNumVar() [see FiOracle.h] already returns the number of variables after the addiction of the new NNwVrs ones. Note that the likely caller for AddVariables() is the FiOracle itself; this is one of the reasons why the FiOracle may need a pointer to the NDOSolver that is using it [see SetNDOSolver() in FiOracle.h]. If AddVariables() is not directly called by the FiOracle, the caller must ensure that the FiOracle has been properly updated before calling the method. Note that this requirement is, for obvious reasons, opposite to what is assumed for RemoveVariables() [see below].

This operation is typically useful in the case of Lagrangian optimization where the set of relaxed constraints A( x ) [<]= b is very large, leading to a very-large-scale NDO problem. Such a problem could be tackled with a row generation scheme, i.e., working with only an "active subset" of the full set of constraints and revising it as necessary. In this setting, adding variables corresponds to inserting new relaxed constraints in the current active set.

Reimplemented from NDOSolver.

ChgFiV()

void ChgFiV ( cIndex wFi = Inf< Index >() )

inlinevirtual

This method signals to the NDO solver that there have been changes in the function Fi. These changes are such that the previously obtained information about the function is not completely useless, but it needs to be properly updated. If 0 <= wFi <= NrFi, the NDO solver is told that only the wFi-th component of Fi has changed; if Inf< Index >() > wFi > NrFi then all the components except the 0-th have changed, while if wFi == Inf< Index >() then all the components, comprised the 0-th, have changed.

The class of changes that are signalled by ChgFiV() are those where only the Fi-values are affected, but not the first-order information. In the Lagrangian case, they correspond to = changes in the objective function c( x ) of the Lagrangian problem, or = changes in the feasible set X of the Lagrangian problem.

In both cases, the first-order information (subgradient/constraint) corresponding to a particular dual solution/dual extreme ray x that has been previously generated can be re-used. If c( x ) changes, the old information given by x is still meaningful for the new Fi provided that it is properly translated [see GetVal() in FiOracle.h]. For the linear 0-th component, this corresponds to a change of the constant ‘b0’. If X changes, x can either be feasible/an extreme ray or not; if it is, then the old item associated to x is still valid for Fi with no changes, otherwise it should probably be discarded, which is signalled by GetVal() returning - INF.

In both cases, the changes that are needed to update the information are given by just one number for each dual solution x, which can be queried by means of the method GetVal() of class FiOracle. Of course, this means that the FiOracle already knows about the change. Indeed, the most likely caller for ChgFi() is the FiOracle itself; this is one of the reasons why the FiOracle may need a pointer to the NDOSolver that is using it [see SetNDOSolver() in FiOracle.h]. If ChgFiV() is not directly called by the FiOracle, the caller must ensure that the FiOracle has been properly informed before calling the method.

Reimplemented from NDOSolver.

ChgSbG()

void ChgSbG ( cIndex strt = 0, Index stp = Inf< Index >(), cIndex wFi = Inf< Index >() )

inlinevirtual

This method signals to the NDO solver that there have been changes in the function Fi. These changes are such that the previously obtained information about the function is not completely useless, but it needs to be properly updated. If 0 <= wFi <= NrFi, the NDO solver is told that only the wFi-th component of Fi has changed; if Inf< Index >() > wFi > NrFi then all the components except the 0-th have changed, while if wFi == Inf< Index >() then all the components, comprised the 0-th, have changed.

ChgSbG() signals that the first-order information relative to the variables with "names" comprised between strt and min( stp , NumVar ) - 1 for the specified components has changed. The changes are intended not to involve the Fi-values, i.e., if Fi-values change together with the first-order information then a separate call to ChgFiV() [see above] is required. In the Lagrangian case, changes to the first-order information correspond to changes in the constraints ‘A[ h ]()’/ right hand side ‘b’ (note that these changes are typically accompanied by changes of the Fi-values).

A call to this method assumes that the FiOracle already knows about the changes. In particular, the NDOSolver can use GetGi() [see FiOracle.h] to retrieve the new values for the changed entries of the items of the specified components of Fi, if it needs so. Indeed, the likely caller for ChgSbG() is the FiOracle itself; this is one of the reasons why the FiOracle may need a pointer to the NDOSolver that is using it [see SetNDOSolver() in FiOracle.h]. If ChgSbG() is not directly called by the FiOracle, the caller must ensure that the FiOracle has been properly updated before calling the method.

Reimplemented from NDOSolver.

IsOptimal()

bool IsOptimal ( HpNum eps = 0 ) const

virtual

This method should return true if the NDOSolver believes that the current solution [see ReadSol() above] is eps-optimal (relative). If eps == 0, then the optimality tolerances used by the solver to terminate are used.

This method may be called while Solve() is running, e.g. by the FiOracle: if IsOptimal(), then the NDOSolver is going to stop at this iteration, so the FiOracle can react accordingly.

Reimplemented from NDOSolver.

KeepBestLambda()

void KeepBestLambda ( const bool KBL = true )

virtual

Reimplemented from NDOSolver.

ReadBestFiVal()

HpNum ReadBestFiVal ( cIndex wFi = Inf< Index >() )

virtual

Returns the best Fi-value() found so far, i.e., those of the point returned by ReadBestSol(). Unlike ReadBestSol(), however, this method is supposed to work even if KeepBestLambda() is not called (too little storage is required here not to do that). If the NDO algorithm is of descent, the method returns the same values as ReadFiVal() [see above]; the implementation of ReadBestFiVal() provided by the base class works for this case.

For meaning of wFi, also refer to ReadFiVal().

Reimplemented from NDOSolver.

ReadBestSol()

cLMRow ReadBestSol ( cIndex_Set & I, Index & D )

virtual

Returns a read-only pointer to the point having the lowest Fi-value found so far. Note that it is necessary to call KeepBestLambda() in order to be sure that the ReadBestSol() works; if not, it can return 0. If the NDO algorithm is of descent, the method returns the same point as ReadSol() [see above]; the implementation of ReadBestSol() provided by the base class works for this case.

For "format" of the returned vector, also refer to ReadSol().

Reimplemented from NDOSolver.

ReadFiVal()

HpNum ReadFiVal ( cIndex wFi = Inf< Index >() )

virtual

Returns the Fi-value(s) of the point returned by ReadSol() [see above]. wFi tells the value of which "component" of Fi is required [see GetNrFi() in FiOracle.h]:

• wFi == 0 requires the value of the linear 0-th component of Fi.
• 1 <= wFi <= NrFi requires the value of the wFi-th component of Fi.
• Inf< Index >() > wFi > NrFi requires the value of the full function Fi except* the linear 0-th component.
• wFi == Inf< Index >() requires the value of the full function Fi.

Implements NDOSolver.

ReadLBMult()

HpNum ReadLBMult ( cIndex wFi = Inf< Index >() )

virtual

Some NDO algorithms may exploit the knowledge of Lower Bounds on the optimal value of the function [see GetLowerBound() in FiOracle.h] as a whole, or of its components. These bound can be thought as all-0 subgradients, and therefore they have a dual multiplier associated; think to the case when the LB is the optimal value of the function, so that the dual multiplier of the (all-0 subgradient associated to the) LB is 1. This method returns the value of the optimal dual multiplier associated to the LB; if 1 <= wFi <= NrFi the LB is that on the wFi-th component of Fi, otherwise the LB is that on the whole function.

Note

The multipliers returned by ReadMult( wFi ) [see above] should sum to 1 - ReadLBMult( wFi ) - ReadLBMult(), except when wFi == 1 so that two multipliers are the same and the sum must be 1 - ReadLBMult().

For "easy" components of Fi() [see FiOracle::GetBNC() ...], it makes no sense to define lower bounds on the component because they (if any) are already implicit in the available complete description of the function; in fact, FiOracle::GetLowerBound() never produces anything for "easy" components.

If the NDO algorithm does not exploit the LBs, no dual multipliers are associated with them, and this method must return 0.

Reimplemented from NDOSolver.

ReadMult()

cHpRow ReadMult ( cIndex_Set & I, Index & D, cIndex wFi = Inf< Index >() )

virtual

Convex minimization problems have a "dual" viewpoint (which is also briefly described in the general notes section of FiOracle.h). This method should return "dual" information about the problem, if the NDO algorithm is capable of computing it; as this is not always the case, a default implementation returning "no such information is available" is provided by the base class.

In general, the dual for the convex minimization problem

(P)   min{ Fi( Lambda ) }

is (D) inf{ Fi*( z ) : z = 0 }

where "*" indicates the Fenchel's conjugate operator; in fact, it is well-known that

inf{ Fi( Lambda ) } = - Fi*( 0 ),

so that the minimization of Fi is equivalent to problem of computing the conjugate of Fi in 0. The standard form in which Fi is available is that of a "black box" or "oracle" [see FiOracle.h]; from the dual viewpoint, an oracle is something that takes a point Lambda in the primal space and returns a point z in the dual space (essentially, the space of subgradients of Fi) such that Lambda is a subgradient of Fi* in z, together with the value Fi*( z ). This information is all that can be used from a "dual" NDO algorithm in order to solve the dual problem.

Since Fi* is a convex function, its epigraph is a convex set; each point (z, Fi*( z )) of the epigraph can be obtained as a convex combination of at most n + 1 other points of the epigraph. From the dual viewpoint, an NDO algorithm should produce a set of multipliers Theta[ z ] attached to all the subgradients/constraints (items) z generated by the oracle, such that

Sum{z} z * Theta[ z ] = 0 && Sum{z} Fi*( z ) * Theta[ z ] = Fi*( 0 ).

A (read-only) pointer to these Theta[] must be returned by ReadMult(), with 0 meaning that they are not available. The "format" of Theta[] depends on I: if I == 0, then Theta[] is a "dense" D-vector, i.e., the multiplier of item with "name" i is found in Theta[ i ] for i = 0, ..., D - 1, otherwise Theta[ i ] is the multiplier of the item with "name" I[ i ] for i = 0, ..., D - 1. I[] must be ordered in increasing sense and Inf< Index >()-terminated. The "names" of the items are those that are passed to the FiOracle [see SetMaxName() and SetGiName() in FiOracle.h].

In the Lagrangian case, a dual object x[ i ] is attached to the item z with name i; x[ i ] \in X if z is a subgradient, while x[ i ] is an extreme ray for X if z is a constraint. Then,

x = Sum{i \in D[]} Theta[ i ] * x[ i ]

is an optimal solution for the "convex relaxation" (D) of the original problem (OP) [see the general notes section in FiOracle.h], which can be constructed with this dual information and the help of the FiOracle.

When Fi is decomposable, the dual information is naturally "splitted" among the components of Fi, since the subgradients are. If 1 <= wFi <= NrFi (the number of different components, see SetFiOracle() above) then only the dual information relative to that component will be returned, i.e., I[] will only contain "names" of items corresponding to component wFi; otherwise all the dual information will be returned. In the Lagrangian case, a decomposable Fi corresponds to a separable X [see FiOracle.h], so that the dual information is divided among the disjoint components of X.

Note

For "easy" components of Fi() [see FiOracle::GetBNC() ...], a different type of information naturally "takes the place" of the multipliers: the optimal solution x[ wFi ]* of the Lagrangian problem in the current point in terms of the "original variables" of the wFi-th component. Thus, calls to ReadMult( wFi ) with an "easy" wFi have the following different meaning: the vector returned by the method (that may be "dense" or "sparse" as in the standard case) represents x[ wFi ]*, and it is therefore a FiOracle::GetBNC( wFi )-vector. This information, however, can only* be accessed when calling ReadMult( wFi ) for wFi <= NrFi: in "global" calls (wFi > NrFi) only the multipliers corresponding to non-easy components are returned.

The dual multipliers Theta[] corresponding to subgradients [of any given component] should be nonnegative and sum to 1—they are convex combinators—while the multipliers Theta[] corresponding to constraints [for any given component] need only be nonnegative. There is an exception to this rule, however, which happens if the NDO algorithms exploits the information provided by Lower Bounds on the optimal value of Fi and/or its components Fi[ i ]; these bounds have a dual meaning and therefore dual information attached to them, that is returned by the separate method ReadLBMult() [see below]. If this happens, the "ordinary" dual multipliers returned by ReadMult() and corresponding to subgradients may sum to a quantity strictly smaller than 1.

If Solve() returns kUnfeasible, the problem is unfeasible; this means that it is either dual unbounded or dual empty. In fact, the dual solution obtained as above is then a feasible ascent extreme ray for (D), that is c( x ) > 0 , A( x ) [<]= 0 and x' + beta * x \in X for each x' \in X and beta > 0. Thus, if X is nonempty then (D) is unbounded, otherwise it is empty.

Reimplemented from NDOSolver.

ReadSol()

cLMRow ReadSol ( cIndex_Set & I, Index & D )

virtual

! void ReSetAlg( unsigned char RstLvl = 0 ) {}

Implements NDOSolver.

RemoveVariables()

void RemoveVariables ( cIndex_Set whch = 0, Index hwmny = 0 )

virtual

Removes the variable whose "names" are contained in the vector ‘whch’, that should contain ‘hwnmy’ distinct values in the range 0 ... NumVar - 1, be ordered in increasing sense and be Inf< Index >()-terminated, i.e., whch[ hwnmy ] must be == Inf< Index >().

If whch == 0, all the variables are eliminated; in this case, hwmny is ignored.

The set of variable "names" is kept contiguous, i.e., it is always the set 0 ... NumVar - 1 for the value of NumVar after the call to the method; hence, some of the variables that are not eliminated need to be "renamed". This is done as follows: when variable ‘i’ is eliminated, all variables with names i + 1 ... NumVar - 1 take names i ... NumVar - 2, respectively (i.e., the names are shifted left by one to fill the gap). If multiple variables are eliminated, this is repeated for each variable, starting with the one with smaller name (the first one in whch) upwards. Note that if the last* variable is eliminated, no renaming has to be done.

After a call to this method, a different function, on a different variable space, has to be minimized. Of course, the two functions must not be unrelated to one another; more specifically, it is required that the new function Fi( Lambda ) is just the restriction of the old function Fi( Lambda , LambdaOld ) to the subspace where all the eliminated variables are zero, i.e. that

Fi( Lambda , 0 ) = Fi( Lambda ) for all Lambda.

This implies, for instance, that the projection of all the previously collected subgradients on the new space (the elimination of the entries corresponding to the removed variables) are still subgradients for the new function in the new space. In other words, if the linear function

L( Lambda , LambdaOld ) = G * Lambda + OldG * LambdaOld + a

is known to minorize the old Fi(), then

L( Lambda ) = G * Lambda + a

minorizes the new Fi(). Even better than that, the "linearization error" of L() at any point with LambdaOld = 0

Fi( Lambda , 0 ) - L( Lambda , 0 ) >= 0

is identical to the linearization error of L() at Lambda

Fi( Lambda ) - L( Lambda ) >= 0.

Also, note that the value of the new function in all the previously tested points with LambdaOld = 0 (if any) is known.

When this method is called, the removed variables must still be defined in the FiOracle, i.e., the NDOSolver is still allowed to query information about the variables being removed from the FiOracle. Of course, after the termination of the call to RemoveVariables() the FiOracle must be updated to reflect the change in the variables set. Note that the likely caller for RemoveVariables() is the FiOracle itself; this is one of the reasons why the FiOracle may need a pointer to the NDOSolver that is using it [see SetNDOSolver() in FiOracle.h]. If RemoveVariables() is not directly called by the FiOracle, the caller must ensure that the FiOracle is also properly updated after that the method returns. Note that this requirement is, for obvious reasons, opposite to what is assumed for AddVariables() [see above].

This operation is typically useful in the case of Lagrangian optimization, where it corresponds to the deletion of some of the relaxed constraints A( x ) [<]= b, hopefully because they have been detected to be redundant.

Reimplemented from NDOSolver.

SetFiOracle()

void SetFiOracle ( FiOracle * Fi = 0 )

virtual

Passes the FiOracle object to the NDOSolver class.

This MUST be done PRIOR to ANY CALL to ANY OTHER method of the class!

This is not done in the constructor in order to allow the user to change the function to be minimized during the lifetime of one NDOSolver object. Of course, this method must not be called within any other method of the class, as it (presumably) causes a complete reset of most internal data structures (e.g. the starting point, see below). Note that extensive support [see [Add/Remove]Variables() and Chg[FiV/SbG]() below] is given for cases where the function changes but the new function is "related" to the old one, so that "warm starts" can be attempted; of course, nothing of this kind can be expected when the FiOracle is changed with SetFiOracle().

Passing 0 as the pointer is intended signal the NDOSolver to release as much memory as possible and to sit down quietly in its corner, waiting for a new FiOracle to become available. After a SetFiOracle( 0 ) call, NO OTHER method of the class (apart from the destructor) should be called before SetFiOracle() is called again with a non-0 argument. However, specific NDO solvers may allow exceptions to this rule.

Reimplemented from NDOSolver.

SetLambda()

void SetLambda ( cLMRow tLambda = 0 )

virtual

Sets the starting point of the NDO algorithm; if 0 is given, or if the method is not called, some starting point is chosen by the solver (the all-0 vector being one of the prime candidates). Note that Solve() [see below] is expected to repotimize somehow using the results of the previous calls, if any, and using the latest "current point" as the starting point is one very typical way of doing it; SetLambda() can be used to reset the starting point.

No calls to SetLambda() are allowed while Solve() is running; the starting point can only be changed between two calls to Solve(), and this possibly has a nontrivial computational cost.

Note that tLambda must be feasible at least with respect to the non-negativity and upper bound constraints on the variables [see GetUC() and GetUB() in FiOracle.h]. Since one needs the FiOracle to check it, this method must not be called before SetFiOracle() [see above].

The vector pointed by tLambda is supposedly copied into internal data structures of the NDSolver, hence it can be modified and/or destroyed after the completion of the method.

Implements NDOSolver.

SetNDOLog()

void SetNDOLog ( ostream * outs = 0, const char lvl = 0 )

virtual

Set the log file and the level of log to be used. lvl controls the "level of verbosity" of the code.

• 0 => no log except error messages;
• 1 => just final results are written;
• 2 => succint results are written every PrintInvl iterations;
• 3 => results are written every iteration and are much more verbose.

Reimplemented from NDOSolver.

SetRadius()

void SetRadius

(

LMNum

rad = Inf< LMNum >()

)

Allows a very primitive form of stabilization by forcing all iterates from now on to lie in a ball (in the INF-Norm) of radius 2 * rad around the current point Lambda. This can be called before Solve(), possibly having already set a "smart" Lambda with SetLambda() [see below]. By calling SetRadius( Inf< LMNum >() ), the original box constraints (if any) on the variables are restored.

Solve()

NDOStatus Solve ( void )

virtual

Tries to minimize the function provided by the FiOracle. Note that, in principle, a call to Solve() is intended to restart the algorithm from the exact state that it reached at the end of the previous call to Solve(), if any, unless ReSetAlg() is called [see below]. This allows the user to interrupt the optimization process at any time and to resume it seamlessly at a later stage.

Returns if

kOK Optimization has been succesfull: a solution that is "optimal" (w.r.t. the current parameters settings) has been found.

kUnbndd Fi() is identically equal to - Infinity (or there has been an error in the FiOracle), i.e., Fi() has returned - INF, or it is unbounded below; the latter case can be detected only if a lower bound on the min. value of Fi is available [see FiOracle::GetMinusInfinity()].

kUnfsbl The domain of Fi is empty.

kStopped Solve() has been stopped for some reason, typically because FiOracle::GetFiStatus() returned FiOracle::kFiStop [see FiOracle.h]; this is possibly not an error, just maybe a request for a pause in the optimization process that might be restored in a later moment.

kLwPrcsn The NDO algorithm cannot proceed because the function cannot be computed with enough precision [see FiOracle::SetPrecision()]; this usually means that the function has been minimized up to the maximum extent that is possible due to the limited precision that the FiOracle can provide;

kStpIter The max. number of iterations has been exhausted.

kStpTime The max. allowed running time has been spent.

kError There was a (typically numerical) error of some sort in Solve() or in the FiOracle that forced the algorithm to quit.

Note that, whatever the exit condition be, some "current point" is usually available by calling ReadSol(), and its Fi-value by calling ReadFiVal() [see below].

Implements NDOSolver.

---

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

• CutPlane/CutPlane.h